View source for Stirling numbers

{{TEX|done}}

{{MSC|05A|11B73}}

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]

If $B_n$ denotes the $n$-th [[Bell numbers|Bell number]], the total number of partitions of an $n$-set (cf. [[Combinatorial analysis]]) , then
$$B_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: cycles 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 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}

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