Proving $\sum_{k=m}^n \binom{k}{m} {n\brack k} = \sum_{k=m}^n \frac{n!}{k!} {k\brack m} $

So here's an idea on how you can prove (1) combinatorially. Let $N$ be the set $\{1 \ldots n\}$, and define $Z = \{(R,B)\}$ where $R$ is a permutation of some subset of $N$ with exactly $m$ cycles (the "red" permutation), and $B$ is any permutation of the remaining elements of $N$ (the "blue" permutation).

On the one hand, for any $k \ge m$, you can start with any permutation of $N$ with $k$ cycles (of which there are ${n\brack k}$), pick any $m$ of the $k$ cycles (which can be done in $\binom{k}{m}$ ways) to color red, and then the remaining cycles define the blue permutation using cycle notation. This gives the left side of (1).

On the other hand, let $X$ be any permutation of $N \cup \{*\}$, where $*$ is not in $N$, with exactly $m+1$ cycles, of which there are ${n+1\brack m+1}$. Color the $m$ cycles which do not contain $*$ red.

For the blue permutation, let the remaining cycle $Y$ containing $*$ be written as $(*,y_1, \ldots, y_{\ell})$; since a cycle is identical up to rotation, we may assume without loss of generality that $*$ comes first. Let $\{n_1 \ldots n_\ell\}$ be the elements of $N$ that appear in $Y$, where $n_i < n_{i+1}$; note that as sets $\{y_1 \ldots y_\ell\} = \{n_1 \ldots n_\ell\}$. Define the blue permutation via the function $\pi:n_i \rightarrow y_i$. So every $X$ corresponds to a unique $(R,B)$, showing the right side of (1).

For the second equality recall the conbinatorial species for factorizations into cycles which is

$$\mathfrak{P}(\mathfrak{C}(\mathcal{Z}))$$

which yields

$$\left[k\atop m\right] = k! [z^k] \frac{1}{m!} \left(\log\frac{1}{1-z}\right)^m.$$

This yields for the RHS of identity two

$$\frac{n!}{m!} \sum_{k=m}^n [z^k] \left(\log\frac{1}{1-z}\right)^m = \frac{n!}{m!} [z^n] \frac{1}{1-z} \left(\log\frac{1}{1-z}\right)^m = Q_{n,m}.$$

We also have

$$\sum_{n\ge m+1} \left[n\atop m+1\right] \frac{z^n}{n!} = \frac{1}{(m+1)!} \left(\log\frac{1}{1-z}\right)^{m+1}$$

which implies that (differentiate)

$$\sum_{n\ge m+1} \left[n\atop m+1\right] \frac{z^{n-1}}{(n-1)!} = \frac{1}{m!} \left(\log\frac{1}{1-z}\right)^m \times (1-z) \times \frac{1}{(1-z)^2}$$

or alternatively

$$\sum_{n\ge m} \left[n+1\atop m+1\right] \frac{z^{n}}{n!} = \frac{1}{m!} \frac{1}{1-z} \left(\log\frac{1}{1-z}\right)^m$$

which means that

$$Q_{n,m} = \left[n+1\atop m+1\right].$$