In mathematics, Stirling numbers of the second kind, together with Stirling numbers of the first kind, are one of the two types of Stirling numbers. They commonly occur in the study of combinatorics, where they count the number of permutations. The Stirling numbers of the first and second kind can be understood to be inverses of one-another, when taken as triangular matrices. This article is devoted to specifics of Stirling numbers of the second kind; further identities linking the two kinds, and general information, is given in the article on Stirling numbers. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, Stirling numbers arise in a variety of combinatorics problems. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... In mathematics, Stirling numbers arise in a variety of combinatorics problems. ...

Definition

The Stirling numbers of the second kind S(n,k) (with a capital "S") count the number of ways to partition a set of n elements into k nonempty subsets. The sum

is the nth Bell number. If we let The Bell numbers, named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus (sequence A000110 in OEIS): In general, Bn is the number of partitions of a set of size n. ...

(in particular, (x)₀ = 1 because it is an empty product) be the falling factorial, we can characterize the Stirling numbers of the second kind by In mathematics, an empty product, or nullary product, is the result of multiplying no numbers. ... In mathematics, the Pochhammer symbol is used in the theory of special functions to represent the rising factorial or upper factorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial The empty product (x)0 is defined to be 1 in both cases. ...

(Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.) In mathematics, several functions are important enough to deserve their own name. ... In mathematics, the Pochhammer symbol, introduced by Leo August Pochhammer, is used in the theory of special functions to represent the rising factorial or upper factorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial To distinguish the two, the notations and are commonly used...

Table of values

Below is a table of values for the Stirling numbers of the second kind:

Recurrence relation

Stirling numbers of the second kind obey the recurrence relation

with

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.

Parity

Using a Sierpiński triangle, it's easy to show that the parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient: Sierpinski triangle The Sierpinski triangle, also called the Sierpinski gasket, is a fractal, named after WacÅ‚aw SierpiÅ„ski who described it in 1916. ... In mathematics, any integer (whole number) is either even or odd. ... In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is the number of combinations that exist. ...

Or directly, let two sets contain positions of 1's in binary representations of results of respective expressions:

then mimick 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. In mathematics, any integer (whole number) is either even or odd. ... Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...

Simple identities

Some simple identities include

This is because dividing n elements into n − 1 sets necessarily means dividing it into one set of size 2 and n − 2 sets of size 1. Therefore we need only pick those two elements;

and

To see this, first note that there are 2 ⁿ ordered pairs of complementary subsets A and B. In one case, A is empty, and in another B is empty, so 2 ⁿ − 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 expanding of the recurrence-relation gives identities in the spirit of the above example.

Explicit formula

The Stirling numbers of the second kind are given by the explicit formula:

This formula is a special case of the k 'th forward difference of the monomial xⁿ evaluated at x = 0: In mathematics, a difference operator maps a function, f(x), to another function, f(x + a) − f(x + b). ... In mathematics, a monomial (or mononomial) is a particular kind of polynomial, having just one term. ...

Because the Bernoulli polynomials may be written in terms of these forward differences, one immediately obtains a relation in the Bernoulli numbers: In mathematics, the Bernoulli numbers Bn were first discovered in connection with the closed forms of the sums for various fixed values of n. ... In mathematics, the Bernoulli numbers are a sequence of rational numbers with deep connections in number theory. ...

Generating function

A generating function for the Stirling numbers of the second kind is given by In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...

Moments of the Poisson distribution

If X is a random variable with a Poisson distribution with expected value λ, then its nth moment is A random variable is a mathematical function that maps outcomes of random experiments to numbers. ... In probability theory and statistics, the Poisson distribution is a discrete probability distribution. ... In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are... -1...

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 Dobinski's formula). A partition of U into 6 blocks: an Euler diagram representation. ... In combinatorial mathematics, Dobinskys formula states that the number of partitions of a set of n members is This has come to be called the nth Bell number Bn, after Eric Temple Bell. ...

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 nth moment of X is In probability theory and statistics, the discrete uniform distribution is a discrete probability distribution that can be characterized by saying that all values of a finite set of possible values are equally probable. ... A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. ...

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 on the page on random permutation statistics, although the notation is a bit different. In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ... The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. ...

References

• Stirling numbers of the second kind, S(n,k) on PlanetMath.