Citizendium - a community developing a quality, comprehensive compendium of knowledge, online and free.Click here to join and contribute |

CZ thanks our previous donors. Donate here. Treasurer's Financial Report |

# Stirling number

In combinatorics, the **Stirling numbers** count 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 number of the first kind *S*(*n*,*k*) counts 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 Stirling number of the second kind *s*(*n*,*k*) counts 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 (1989).
*Concrete Mathematics*. Addison Wesley, 243-253. ISBN 0-201-14236-8.