Stirling numbers of the second kind

[1] Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions.

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.

or with other notations, count the number of ways to partition a set of

Unlike Stirling numbers of the first kind, they can be calculated using a one-sum formula:[2] 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[3] (In particular, (x)0 = 1 because it is an empty product.)

was used by Imanuel Marx and Antonio Salmeri in 1962 for variants of these numbers.

[4][5] This led Knuth to use it, as shown here, in the first volume of The Art of Computer Programming (1968).

[6][7] According to the third edition of The Art of Computer Programming, this notation was also used earlier by Jovan Karamata in 1935.

[8][9] The notation S(n, k) was used by Richard Stanley in his book Enumerative Combinatorics and also, much earlier, by many other writers.

Analogously, the ordered Bell numbers can be computed from the Stirling numbers of the second kind via Below is a triangular array of values for the Stirling numbers of the second kind (sequence A008277 in the OEIS): As with the binomial coefficients, this table could be extended to k > n, but the entries would all be 0.

The number of ways that the singleton is one of the subsets is given by since we must partition the remaining n objects into the available ⁠

Summing these two values gives the desired result.

Therefore we need only pick those two elements; and To see this, first note that there are 2n ordered pairs of complementary subsets A and B.

Another explicit expansion of the recurrence-relation gives identities in the spirit of the above example.

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 The Stirling numbers of the second kind are given by the explicit formula: 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

Additionally, this formula is a special case of the kth forward difference of the monomial

evaluated at x = 0: Because the Bernoulli polynomials may be written in terms of these forward differences, one immediately obtains a relation in the Bernoulli numbers: The evaluation of incomplete exponential Bell polynomial Bn,k(x1,x2,...) on the sequence of ones equals a Stirling number of the second kind: Another explicit formula given in the NIST Handbook of Mathematical Functions is The parity of a Stirling number of the second kind is same as the parity of a related binomial coefficient: 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: One can mimic a bitwise AND operation by intersecting these two sets: to obtain the parity of a Stirling number of the second kind in O(1) time.

The parity of a central Stirling number of the second kind

[11] For a fixed integer n, the ordinary generating function for Stirling numbers of the second kind

If one sums the Stirling numbers against the falling factorial instead, one can show the following identities, among others: and which has special case For a fixed integer k, the Stirling numbers of the second kind have rational ordinary generating function and have an exponential generating function given by A mixed bivariate generating function for the Stirling numbers of the second kind is If

the asymptotic value of the Stirling numbers of the second kind as

(where o denotes the little o notation) then A uniformly valid approximation also exists: for all k such that 1 < k < n, one has where

The maximum is attained for at most two consecutive values of k. That is, there is an integer

is large and the maximum value of the Stirling number can be approximated with If X is a random variable with a Poisson distribution with expected value λ, then its n-th moment is In particular, the nth 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 nth Bell number (this fact is Dobiński's formula).

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 nth moment of X is Note: The upper bound of summation is m, not n. In other words, the nth 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.

It has been shown that these numbers satisfy (hence the name "reduced").