Stirling number: Difference between revisions
imported>Richard Pinch (new article, just a start) |
imported>Bruce M. Tindall mNo edit summary |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | |||
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. | 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. | ||
| Line 17: | Line 18: | ||
* [AD],[BC] | * [AD],[BC] | ||
The | 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: | For example, 4 objects can be arranged into 2 subsets in seven ways, so ''s''(4,2) = 7: | ||
| Line 30: | Line 31: | ||
==References== | ==References== | ||
* {{cite book | author=Ronald L. Graham | coauthors=Donald E. Knuth, Oren Patashnik | title=Concrete Mathematics | publisher=[[ | * {{cite book | author=Ronald L. Graham | coauthors=Donald E. Knuth, Oren Patashnik | title=Concrete Mathematics | publisher=[[Addison Wesley]] | year=1989 | isbn=0-201-14236-8 | pages=243-253 }} | ||
Latest revision as of 13:34, 7 February 2009
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.