Stirling numbers of the first kind identity

Question

Prove the following identity for the signless Stirling numbers of the first kind: $$\sum_{m=k}^n c(n,m){m \choose k}=c(n+1,k+1)$$ I'm trying to rewrite the sum as follows $$c(n,k){k \choose k}+c(n,k+1){k+1 \choose k}+...+c(n,n){n \choose k}$$ using the recurrence of the signless Stirling numbers of the first kind, I want to condense this sum to get $$c(n,k)+nc(n,k+1)=c(n+1,k+1)$$ but I am unsure how. Any thoughts?

Note: we cannot use EGFs, so an alternative combinatoric proof would also be helpful!

Answer 1

I’ll get you started on a combinatorial proof.

Consider a permutation $\sigma$ of $[n]$ that has $m$ cycles, where $k\le m\le n$; we can write $\sigma$ in the standard form

$$\sigma=(a_1\ldots a_{\ell_1})(a_{\ell_1+1}\ldots a_{\ell_2})\ldots(a_{\ell_{m-1}+1}\ldots a_m)\,,\tag{1}$$

where the leading elements $a_1,a_{\ell_1+1},\ldots,a_{\ell_{m-1}+1}$ are the largest elements of their respective cycles, and $a_1<a_{\ell_1+1}<\ldots<a_{\ell_{m-1}+1}$. There are $\binom{m}k$ ways to choose $k$ of those cycles and amalgamate the remaining $m-k$ cycles into a single cycle headed by $n+1$ to get a permutation of $[n+1]$ with $k+1$ cycles.

For instance, if $m=k+2$, and the $k$ cycles that we choose are all of the cycles except the first and last shown in $(1)$, the new permutation of $[n+1]$ will be $$(a_{\ell_1+1}\ldots a_{\ell_2})\ldots(a_{\ell_{m-2}+1}\ldots a_{\ell_{m-1}})((n+1)a_1\ldots a_{\ell_1}a_{\ell_{m-1}+1}\ldots a_m)\,.$$ For a concrete numerical example let $\sigma=(21)(534)(7)(986)$, where clearly $n=9$. If $k=2$, I can choose the first and third cycles and combine the second and fourth in a third cycle that contains $n+1=10$ to get $(21)(7)(10\,534986)$; or I can choose the third and fourth and get $(7)(986)(10\,21534)$. Since $\binom42=6$, I can get $6$ permutations of $[10]$ in this way, each with $k+1=3$ cycles; the other four are $(21)(534)(10\,7986)$, $(21)(986)(10\,5347)$, $(534)(7)(10\,21986)$, and $(534)(986)(10\,217)$.

There are $c(n,m)$ such permutations $\sigma$, and each gives rise in this fashion to $\binom{m}k$ permutations of $[n+1]$ with $k+1$ cycles, so to complete the combinatorial proof you need only show that these permutations of $[n+1]$ are distinct, and that every permutation of $[n+1]$ with $k+1$ cycles can be produced in this fashion.