the following two identities involve (unsigned) Stirling numbers of the first kind: $$ \sum_{k=m}^n \binom{k}{m} \begin{bmatrix} n \\ k \end{bmatrix}=_{(1)} \begin{bmatrix} n+1 \\ m+1 \end{bmatrix} =_{(2)} \sum_{k=m}^n \frac{n!}{k!} \begin{bmatrix} k \\ m \end{bmatrix} $$ 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 $\begin{bmatrix} n \\ k \end{bmatrix}$.

taking coefficients of $x^{m+1}$ in the identity $ P_{n+1}(x)=xP_n(x+1) $ : $$ \begin{align} \begin{bmatrix} n+1 \\ m+1 \end{bmatrix}&=[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 \begin{bmatrix} n \\ k \end{bmatrix} (x+1)^k \\ \\ &= \sum_{k=m}^n \binom{k}{m} \begin{bmatrix} n \\ k \end{bmatrix} \end{align} \\ $$ (b) to interpret (2) combinatorially we use the fact that $\begin{bmatrix} n \\ k \end{bmatrix} $ is the number of ways of placing $n$ objects in $k$ cycles.

if we rewrite $$ \sum_{k=m}^n \frac{n!}{k!} \begin{bmatrix} k \\ m \end{bmatrix} = \sum_{k=m}^n (n-k)!\binom{n}{k} \begin{bmatrix} k \\ m \end{bmatrix} $$

then we may equate the RHS to $\begin{bmatrix} n+1 \\ m+1 \end{bmatrix}$ 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.

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.