Proving $\sum_{k=m}^n \binom{k}{m} {n\brack k} = \sum_{k=m}^n \frac{n!}{k!} {k\brack m} $ the following two identities involve (unsigned) Stirling numbers of the first kind:
$$
\sum_{k=m}^n \binom{k}{m} {n\brack k} =_{(1)}
{n+1\brack m+1} =_{(2)}
\sum_{k=m}^n \frac{n!}{k!} {k\brack m}
$$
the first, (1), has a simple algebraic proof but no obvious combinatorial interpretation, whereas the second, (2), makes sense combinatorially but i have so far found no obvious route to prove it algebraically.
question can anyone provide either or both of these missing links - i.e. an algebraic demonstration of (2) and/or a combinatorial interpretation of (1)? i would also appreciate any perceptive remarks on (i) how it is that combinatorial intuition can sometimes cut through the knot of apparently complex calculations, and (ii) whether there is any formalization which allows proofs to be systematically generated from valid combinatorial arguments.
note
(a) algebraic proof of (1):
let $P_n(x)$ be the polynomial $x(x+1)\dots(x+n-1)$. the coefficient of $x^k$ in $P_n(x)$ is ${n\brack k}$.
taking coefficients of $x^{m+1}$ in the identity
$
P_{n+1}(x)=xP_n(x+1)
$
:
$$
\begin{align}
{n+1\brack m+1}&=[x^{m+1}]P_{n+1}(x) \\
&=[x^{m+1}]xP_{n}(x+1) \\
&=[x^{m}]P_{n}(x+1) \\
&=[x^{m}]\sum_{k=m}^n {n\brack k} (x+1)^k \\
\\
&= \sum_{k=m}^n \binom{k}{m} {n\brack k}
\end{align} \\
$$
(b) to interpret (2) combinatorially we use the fact that ${n\brack k}$ is the number of ways of placing $n$ objects in $k$ cycles.
if we rewrite
$$
\sum_{k=m}^n \frac{n!}{k!} {k\brack m} = 
\sum_{k=m}^n (n-k)!\binom{n}{k} {k\brack m}
$$
then we may equate the RHS to ${n+1\brack m+1}$ by the following argument. to arrange $n+1$ objects as $m+1$ cycles, first set aside any one object. From the remaining $n$ objects, select $j \ge m$. arrange these $j$ objects into $m$ cycles. the $n-j$ unselected objects, together with the object initially set aside,  can be arranged as a cycle in $(n-j)!$ ways.
 A: 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).
A: 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].$$
