Stirling numbers of the first kind

Definition 5.6.4   $s(n,k)$ is the number of permutations of $\{1,\dots,n\}$ with precisely $k$ cycles (including fixed points).

For instance $s(n,n) = 1$, $s(n,n-1) = \binom{n}{2}$, $s(n,1) = (n-1)!$, $s(n,0) = s(0,k) = 0$ for all $k,n \in \mathbb{N}$ but $s(0,0) = 1$.

Lemma 5.6.5  

$$s(n,k) = s(n-1,k-1) + (n-1) s(n-1,k)$$

Proof. Either the point $n$ is in a cycle on its own ( $s(n-1,k-1)$ such) or it is not. In this case, $n$ can be inserted into any of $n-1$ places in any of the $s(n-1,k)$ permutations of $\{1,\dots,n-1 \}$. $\qedsymbol$

We can use this recurrence to prove this proposition. (Proof left as exercise.)

Proposition 5.6.6  

$$x^{\overline{n}} = \sum_k s(n,k) x^k$$