Numbers parameterizing ways to partition a set
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 formula_1 or formula_2. Stirling numbers of the second kind occur in the field of mathematics called 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 formula_1 or formula_4 or with other notations, count the number of ways to partition a set of formula_5 labelled objects into formula_6 nonempty unlabelled subsets. Equivalently, they count the number of different equivalence relations with precisely formula_6 equivalence classes that can be defined on an formula_5 element set. In fact, there is a bijection between the set of partitions and the set of equivalence relations on a given set. Obviously,
formula_9 for "n" ≥ 0, and formula_10 for "n" ≥ 1,
as 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:
formula_11
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
formula_12
Stirling numbers of the second kind satisfy the relation
formula_13
Notation.
Various notations have been used for Stirling numbers of the second kind. The brace notation formula_14 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 formula_15 counts set partitions of an "n"-element set into "k" parts, the sum 
formula_16
over all values of "k" is the total number of partitions of a set with "n" members. This number is known as the "n"th Bell number. 
Analogously, the ordered Bell numbers can be computed from the Stirling numbers of the second kind via
formula_17
Table of values.
Below is a triangular array of values for the Stirling numbers of the second kind {{OEIS|A008277}}:
As with the binomial coefficients, this table could be extended to {{math|"k" ; "n"}}, but the entries would all be 0.
Properties.
Recurrence relation.
Stirling numbers of the second kind obey the recurrence relation
formula_18
with initial conditions
formula_19
For instance, the number 25 in column "k" = 3 and row "n" = 5 is given by 25 = 7 + (3×6), where 7 is the number above and to the left of 25, 6 is the number above 25 and 3 is the column containing the 6.
To prove this recurrence, observe that a partition of the {{tmath|n+1}} objects into "k" nonempty subsets either contains the {{tmath|(n+1)}}-th object as a singleton or it does not. The number of ways that the singleton is one of the subsets is given by
formula_20
since we must partition the remaining {{mvar|n}} objects into the available {{tmath|k-1}} subsets. In the other case the {{tmath|(n+1)}}-th object belongs to a subset containing other objects. The number of ways is given by
formula_21
since we partition all objects other than the {{tmath|(n+1)}}-th into "k" subsets, and then we are left with "k" choices for inserting object {{tmath|n+1}}. Summing these two values gives the desired result.
Another recurrence relation is given by
formula_22
which follows from evaluating formula_23 at formula_24.
Simple identities.
Some simple identities include
formula_25
This is because dividing "n" elements into {{math|"n" − 1}} sets necessarily means dividing it into one set of size 2 and {{math|"n" − 2}} sets of size 1. Therefore we need only pick those two elements;
and
formula_26
To see this, first note that there are 2{{sup|"n"}} "ordered" pairs of complementary subsets "A" and "B". In one case, "A" is empty, and in another "B" is empty, so {{math|2{{sup|"n"}} − 2}} ordered pairs of subsets remain. Finally, since we want "unordered" pairs rather than "ordered" pairs we divide this last number by 2, giving the result above.
Another explicit expansion of the recurrence-relation gives identities in the spirit of the above example.
Identities.
The table in section 6.1 of "Concrete Mathematics" provides a plethora of generalized forms of finite sums involving the Stirling numbers. Several particular finite sums relevant to this article include
formula_27
Explicit formula.
The Stirling numbers of the second kind are given by the explicit formula:
formula_28
This can be derived by using inclusion-exclusion to count the surjections from "n" to "k" and using the fact that the number of such surjections is formula_29.
Additionally, this formula is a special case of the "k"th forward difference of the monomial formula_30 evaluated at "x" = 0:
formula_31
Because the Bernoulli polynomials may be written in terms of these forward differences, one immediately obtains a relation in the Bernoulli numbers:
formula_32
The evaluation of incomplete exponential Bell polynomial "B""n","k"("x"1,"x"2...) on the sequence of ones equals a Stirling number of the second kind:
formula_33
Another explicit formula given in the "NIST Handbook of Mathematical Functions" is
formula_34
Parity.
The parity of a Stirling number of the second kind is same as the parity of a related binomial coefficient:
formula_35 where formula_36
This relation is specified by mapping "n" and "k" coordinates onto the Sierpiński triangle.
More directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
formula_37
One can mimic a bitwise AND operation by intersecting these two sets:
formula_38
to obtain the parity of a Stirling number of the second kind in "O"(1) time. In pseudocode:
formula_39
where formula_40 is the Iverson bracket.
The parity of a central Stirling number of the second kind formula_41 is odd if and only if formula_5 is a fibbinary number, a number whose binary representation has no two consecutive 1s.
Generating functions.
For a fixed integer "n", the ordinary generating function for Stirling numbers of the second kind formula_43 is given by
formula_44
where formula_45 are Touchard polynomials. If one sums the Stirling numbers against the falling factorial instead, one can show the following identities, among others:
formula_46
and
formula_47
which has special case
formula_48
For a fixed integer "k", the Stirling numbers of the second kind have rational ordinary generating function
formula_49
and have an exponential generating function given by
formula_50
A mixed bivariate generating function for the Stirling numbers of the second kind is
formula_51
Lower and upper bounds.
If formula_52 and formula_53, then
formula_54 
Asymptotic approximation.
For fixed value of formula_55 the asymptotic value of the Stirling numbers of the second kind as formula_56 is given by
formula_57
If formula_58 (where "o" denotes the little o notation) then
formula_59
A uniformly valid approximation also exists: for all {{mvar|k}} such that {{math|1 ; "k" ; "n"}}, one has
formula_60
where formula_61, and formula_62 is the unique solution to formula_63. Relative error is bounded by about formula_64.
Unimodality.
For fixed formula_5, formula_66 is unimodal, that is, the sequence increases and then decreases. The maximum is attained for at most two consecutive values of "k". That is, there is an integer formula_67 such that
formula_68
Looking at the table of values above, the first few values for formula_67 are formula_70
When formula_5 is large
formula_72
and the maximum value of the Stirling number can be approximated with
formula_73 
Applications.
Moments of the Poisson distribution.
If "X" is a random variable with a Poisson distribution with expected value λ, then its "n-"th moment is
formula_74
In particular, the "n"th moment of the Poisson distribution with expected value 1 is precisely the number of partitions of a set of size "n", i.e., it is the "n"th Bell number (this fact is Dobiński's formula).
Moments of fixed points of random permutations.
Let the random variable "X" be the number of fixed points of a uniformly distributed random permutation of a finite set of size "m". Then the "n"th moment of "X" is
formula_75
Note: The upper bound of summation is "m", not "n".
In other words, the "n"th moment of this probability distribution is the number of partitions of a set of size "n" into no more than "m" parts.
This is proved in the article on random permutation statistics, although the notation is a bit different.
Rhyming schemes.
The Stirling numbers of the second kind can represent the total number of rhyme schemes for a poem of "n" lines. formula_1 gives the number of possible rhyming schemes for "n" lines using "k" unique rhyming syllables. As an example, for a poem of 3 lines, there is 1 rhyme scheme using just one rhyme (aaa), 3 rhyme schemes using two rhymes (aab, aba, abb), and 1 rhyme scheme using three rhymes (abc).
Variants.
"r"-Stirling numbers of the second kind.
The "r"-Stirling number of the second kind formula_77 counts the number of partitions of a set of "n" objects into "k" non-empty disjoint subsets, such that the first "r" elements are in distinct subsets. These numbers satisfy the recurrence relation
formula_78
Some combinatorial identities and a connection between these numbers and context-free grammars can be found in 
Associated Stirling numbers of the second kind.
An "r"-associated Stirling number of the second kind is the number of ways to partition a set of "n" objects into "k" subsets, with each subset containing at least "r" elements. It is denoted by formula_79 and obeys the recurrence relation
formula_80
The 2-associated numbers {{OEIS|A008299}} appear elsewhere as "Ward numbers" and as the magnitudes of the coefficients of Mahler polynomials.
Reduced Stirling numbers of the second kind.
Denote the "n" objects to partition by the integers 1, 2, ..., "n". Define the reduced Stirling numbers of the second kind, denoted formula_81, to be the number of ways to partition the integers 1, 2, ..., "n" into "k" nonempty subsets such that all elements in each subset have pairwise distance at least "d". That is, for any integers "i" and "j" in a given subset, it is required that formula_82. It has been shown that these numbers satisfy
formula_83
(hence the name "reduced"). Observe (both by definition and by the reduction formula), that formula_84, the familiar Stirling numbers of the second kind.