Difference between revisions of "Stirling numbers"
From Encyclopedia of Mathematics
m (→References: isbn link) |
(details) |
||
| Line 3: | Line 3: | ||
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. | 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. | + | * 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$. | For example, 4 objects can be arranged into 2 cycles in eleven ways, so $S(4,2) = 11$. | ||
| Line 24: | Line 24: | ||
$$ | $$ | ||
| − | 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. | + | * 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$: | For example, 4 objects can be arranged into 2 subsets in seven ways, so $s(4,2) = 7$: | ||
| Line 36: | Line 36: | ||
* {AD},{BC} | * {AD},{BC} | ||
| − | If $B_n$ denotes the [[Bell numbers]], the total number of | + | 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) \ . | B_n = \sum_{k=1}^n s(n,k) \ . | ||
Latest revision as of 07:23, 7 November 2023
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
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison Wesley (1989) pp.243-253. ISBN 0-201-14236-8
How to Cite This Entry:
Stirling numbers. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stirling_numbers&oldid=54252
Stirling numbers. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stirling_numbers&oldid=54252