# Stirling number

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 $c(n, k)$ is the number of permutations of an $n$-element set with exactly $k$ cycles.

For example, $c(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(n, k)$ is the number of partitions of an $n$-element set into exactly $k$ non-empty subsets.

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

Stirling numbers of the second kind satisfy the recursion $$S(n + 1, k) = k S(n, k) + S(n, k - 1).$$

(This can easily be shown by considering the cases that $n + 1$ is in a part of size $1$ or size larger than $1$.) They can also be calculated using the formula $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j{k \choose j} (k-j)^n.$$

The total number of partitions of an $n$-element set is $B_n = \sum_{k = 1}^n S(n, k)$ and is called the $n$th Bell number.