Stirling Numbers of the First Kind and Permutations

Question

How to prove that the number of $[n]$ permutations with $k$ cycles is equal with $|s(n,k)|$?

Answer 1

You have

$$x^{\underline n}=\sum_{k=0}^ns(n,k)x^k\;,$$

where $x^{\underline n}=x(x-1)\ldots(x-n+1)$. Notice that if you replace $x^{\underline n}$ by

$$x^{\overline n}=x(x+1)\ldots(x+n-1)\;,$$

you get the absolute values of the same coefficients:

$$x^{\overline n}=\sum_{k=0}^n|s(n,k)|x^k\;.$$

Now

$$\begin{align*} \sum_{k=0}^n|s(n,k)|x^k&=x^{\underline n}\\ &=(x+n-1)x^{\overline{n-1}}\\ &=(x+n-1)\sum_{k=0}^{n-1}|s(n-1,k)|x^k\\ &=\sum_{k=0}^{n-1}|s(n-1,k)|x^{k+1}+\sum_{k=0}^{n-1}(n-1)|s(n-1,k)|x^k\\ &=\sum_{k=1}^n|s(n-1,k-1)|x^k+\sum_{k=0}^{n-1}(n-1)|s(n-1,k)|x^k\\ &=|s(n-1,n-1)|x^n+\sum_{k=1}^{n-1}\big(|s(n-1,k-1)|+(n-1)|s(n-1,k)|\big)x^k+(n-1)|s(n-1,0)|\\ &=x^n+\sum_{k=1}^{n-1}\big(|s(n-1,k-1)|+(n-1)|s(n-1,k)|\big)x^k\\ &=\sum_{k=0}^{n-1}\big(|s(n-1,k-1)|+(n-1)|s(n-1,k)|\big)x^k\;, \end{align*}$$

so

$$|s(n,k)|=|s(n-1,k-1)|+(n-1)|s(n-1,k)|\;.$$

Now show that the number of permutations of $[n]$ with $k$ cycles satisfies the same recurrence and has the same initial values. If you get stuck, there’s a proof here.