next up previous contents
Next: Generating Functions Up: Special Sequences of Integers Previous: Transpositions and shuffles   Contents

Stirling numbers of the second kind

Definition 8.6.8   The Stirling number of the second kind, $ S(n,k)$, $ n,k \in \mathbb{N}_0$ is defined as the number of partitions of $ \{1,\dots,n\}$ into exactly $ k$ non-empty subsets. Also $ S(n,0)=0$ if $ n > 0$ and $ 1$ if $ n=0$.

Note that $ S(n,k) = 0$ if $ k > n$, $ S(n,n) = 1$ for all $ n$, $ S(n,n-1)
= \binom{n}{2}$ and $ S(n,2) = 2^{n-1} - 1$.

Lemma 8.6.9   A recurrence: $ S(n,k) = S(n-1,k-1) + k S(n-1,k)$.

Proof. In any partition of $ \{1,\dots,n\}$, the element $ n$ is either in a part on its own ( $ S(n-1,k-1)$ such) or with other things ( $ k S(n-1,k)$ such). $ \qedsymbol$

Proposition 8.6.10   For $ n \in \mathbb{N}_0$, $ x^n = \sum_k S(n,k) x^{\underline{k}}$.

Proof. Proof is by induction on $ n$. It is clearly true when $ n=0$, so take $ n > 0$ and assume the result is true for $ n-1$. Then

$\displaystyle x^n$ $\displaystyle = x x^{n-1}$    
  $\displaystyle = x \sum_k S(n-1,k) x^{\underline{k}}$    
  $\displaystyle = \sum_k S(n-1,k) x^{\underline{k}} (x - k + k)$    
  $\displaystyle = \sum_k S(n-1,k) x^{\underline{k+1}} + \sum_k k S(n-1,k) x^{\underline{k}}$    
  $\displaystyle = \sum_k S(n-1,k-1) x^{\underline{k}} + \sum_k k S(n-1,k) x^{\underline{k}}$    
  $\displaystyle = \sum_k S(n,k) x^{\underline{k}}$    as required.    

$ \qedsymbol$


next up previous contents
Next: Generating Functions Up: Special Sequences of Integers Previous: Transpositions and shuffles   Contents
root 2002-06-10