Stirling number

Revision as of 10:20, 25 October 2010 by Pvnp (talk | contribs) (Stirling Numbers of the Second Kind)

There are two kinds of Stirling numbers: Stirling numbers of the first kind and Stirling numbers of the second kind. They appear in many situations in combinatorics.


Stirling Numbers of the First Kind

The Stirling number of the first kind, $S_1(n, k)$, is the number of permutations of an $n$-element set with exactly $k$ cycles.

For example, $S_1(4, 2) = 11$ because (writing all our permutations in cycle notation) we have the permutations $\{(1)(234), (1)(243), (134)(2),(143)(2),(124)(3),(142)(3),(123)(4),(132)(4), (12)(34), (13)(24), (14)(23)\}$.

Stirling Numbers of the Second Kind

The Stirling number of the second kind, $S_2(n, k)$, is the number of partitions of an $n$-element set into exactly $k$ subsets.

For example, $S_2(4, 2) = 7$ because we have the partitions $\{1 | 234, 2|134, 3|124, 4|123, 12|34, 13|24, 14|23\}$.


The number of such subsets can be calculated using the following formula: \[S(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j{k \choose j} (k-j)^n\]