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!
$\endgroup$ 01 Answer
$\begingroup$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}}\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}}\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 and 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.
$\endgroup$ 3
