Namespaces
Variants
Actions

Stirling numbers

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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=54253