Stirling numbers

2020 Mathematics Subject Classification: Primary: 05A Secondary: 11B73 [MSN][ZBL]

In combinatorics, counts of certain arrangements of objects into a given number of structures. There are two kinds of Stirling number, depending on the nature of the structure being counted.

* The Stirling numbers of the first kind $S(n,k)$ count the number of ways $n$ labelled objects can be arranged into $k$ cycles: cycles are regarded as equivalent, and counted only once, if they differ by a cyclic permutation, thus $[ABC] = [BCA] = [CAB]$ but is counted as different from $[CBA] = [BAC] = [ACB]$. The order of the cycles in the list is irrelevant.

For example, 4 objects can be arranged into 2 cycles in eleven ways, so $S(4,2) = 11$.

* [ABC],[D]
* [ACB],[D]
* [ABD],[C]
* [ADB],[C]
* [ACD],[B]
* [ADC],[B]
* [BCD],[A]
* [BDC],[A]
* [AB],[CD]
* [AC],[BD]
* [AD],[BC]

The number of permutations on $n$ letters with exactly $k$ cycles is given by $S(n,k)$. Hence $$ n!=\sum_{k=1}^nS(n,k) \ . $$

* The Stirling numbers of the second kind $s(n,k)$ count the number of ways $n$ labelled objects can be arranged into $k$ subsets: the subsets are regarded as equivalent, and counted only once, if they have the same elements, thus $\\{ABC\\} = \\{BCA\\} = \\{CAB\\} = \\{CBA\\} = \\{BAC\\} = \\{ACB\\}$; the order of the subsets in the list is also irrelevant.

For example, 4 objects can be arranged into 2 subsets in seven ways, so $s(4,2) = 7$:

* {ABC},{D}
* {ABD},{C}
* {ACD},{B}
* {BCD},{A}
* {AB},{CD}
* {AC},{BD}
* {AD},{BC}

If $B_n$ denotes the Bell numbers, the total number of partitions of a set of size $n$, thren $$ B_n = \sum_{k=1}^n s(n,k) \ . $$

See also: Combinatorial analysis.

## References[edit]

* Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison Wesley (1989) pp.243-253. ISBN 0-201-14236-8