In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by S ( n , k ) {\displaystyle S(n,k)} or { n k } {\displaystyle \textstyle \left\{{n \atop k}\right\}} . Stirling numbers of the second kind occur in combinatorics and the study of partitions. They are named after James Stirling. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the second kind. Identities linking the two kinds appear in the article on Stirling numbers.
Definition The Stirling numbers of the second kind, written S ( n , k ) {\displaystyle S(n,k)} or { n k } {\displaystyle \lbrace \textstyle {n \atop k}\rbrace } or with other notations, count the number of ways to partition a set of n {\displaystyle n} labelled objects into k {\displaystyle k} nonempty unlabelled subsets. Equivalently, they count the number of different equivalence relations with precisely k {\displaystyle k} equivalence classes that can be defined on an n {\displaystyle n} element set. In fact, there is a bijection between the set of partitions and the set of equivalence relations on a given set. Obviously,
{ n 0 } = 0 {\displaystyle \left\{{n \atop 0}\right\}=0} for n ≥ 1, { n n } = 1 {\displaystyle \left\{{n \atop n}\right\}=1} for n ≥ 0, and { n 1 } = 1 {\displaystyle \left\{{n \atop 1}\right\}=1} for n ≥ 1, as there is no empty partition of a nonempty set, the only way to partition an n-element set into n parts is to put each element of the set into its own part, and the only way to partition a nonempty set into one part is to put all of the elements in the same part. Unlike Stirling numbers of the first kind, they can be calculated using a one-sum formula:
{ n k } = 1 k ! ∑ i = 0 k ( − 1 ) k − i ( k i ) i n = ∑ i = 0 k ( − 1 ) k − i i n ( k − i ) ! i ! . {\displaystyle \left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n}=\sum _{i=0}^{k}{\frac {(-1)^{k-i}i^{n}}{(k-i)!i!}}.}
The Stirling numbers of the first kind may be characterized as the numbers that arise when one expresses powers of an indeterminate x in terms of the falling factorials
( x ) n = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) . {\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1).}
Notation Various notations have been used for Stirling numbers of the second kind. The brace notation { n k } {\textstyle \textstyle \lbrace {n \atop k}\rbrace } was used by Imanuel Marx and Antonio Salmeri in 1962 for variants of these numbers. This led Knuth to use it, as shown here, in the first volume of The Art of Computer Programming (1968). According to the third edition of The Art of Computer Programming, this notation was also used earlier by Jovan Karamata in 1935. The notation S(n, k) was used by Richard Stanley in his book Enumerative Combinatorics and also, much earlier, by many other writers. The notations used on this page for Stirling numbers are not universal, and may conflict with notations in other sources.
Relation to Bell numbers
Since the Stirling number { n k } {\displaystyle \left\{{n \atop k}\right\}} counts set partitions of an n-element set into k parts, the sum
… excerpt ends here. Continue reading the full article.
