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.