Namespaces
Variants
Actions

Difference between revisions of "Stirling numbers"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Stirling numbers)
 
(details)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
{{TEX|done}}
+
{{TEX|done}}{{MSC|05A|11B73}}
−
 
 
−
{{MSC|05A}}
 
  
 
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 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.
+
* 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 21: Line 19:
 
* [AD],[BC]
 
* [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.
+
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$:
 
For example, 4 objects can be arranged into 2 subsets in seven ways, so $s(4,2) = 7$:
Line 32: Line 35:
 
* {AC},{BD}
 
* {AC},{BD}
 
* {AD},{BC}
 
* {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==
 
==References==
−
* Ronald L. Graham, Donald E. Knuth, Oren Patashnik, ''Concrete Mathematics'', Addison Wesley (1989) pp.243-253.  ISBN 0-201-14236-8
+
* Ronald L. Graham, Donald E. Knuth, Oren Patashnik, ''Concrete Mathematics'', Addison Wesley (1989) pp.243-253.  {{ISBN|0-201-14236-8}}

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=34711
Retrieved from "https://encyclopediaofmath.org/index.php?title=Stirling_numbers&oldid=54253"