Sum with Stirling numbers of first kind

Question

I have problems with proving this equation: $$ \sum_{k=0}^n s_1(n,k)\cdot 2^{k} = (n+1)!$$ where $s_1(n,k)$ is the Stirling number of first kind.

Answer 1

Here’s a combinatorial proof: Given a permutation $\pi$ of $[n]$ with $k$ cycles in cycle notation, write the least element of each cycle first, then construct a permutation of $[n+1]$ by forming a cycle beginning with $n+1$ and choosing for each cycle in $\pi$, in the order of descending first (i.e. least) elements, whether to append it to the cycle. That’s $k$ independent binary choices, so $2^k$ possibilities. You get each permutation of $[n+1]$ exactly once in this way: You can go in the other direction by taking a permutation of $[n+1]$, writing it in cycle notation with $n+1$ as the first element in its cycle, and splitting that cycle at every element that’s less than all preceding elements.