next up previous contents
Next: Transpositions and shuffles Up: Permutations Previous: Permutations   Contents

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  

$\displaystyle 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  

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



root 2002-06-10