Stirling number of the second kind

A Stirling numbers of the second kind, denoted S(n,k), is the number of ways to partition a set of n objects into k groups. There are two types of Stirling numbers: Stirling numbers of the first kind and Stirling numbers of the second kind. They are inverses of one-another, when taken as triangular matrices. Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions.

1 Definition
2 Bell numbers
3 Table of values
4 Properties
5 Applications
6 Reduced Stirling Numbers of the Second Kind
7 See also
8 References

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. They can be calculated using the following explicit formula.

$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n$ ^[1]

Bell numbers

The sum over the vales for k of the Stirling numbers of the second kind, gives us

$B_n=\sum_{k=0}^n S(n,k)$

the nth Bell number, that is the total the number of partitions of a set with n members.

If we let

$(x)_n=x(x-1)(x-2)\cdots(x-n+1)$

(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

$\sum_{k=0}^n S(n,k)(x)_k=x^n.$

(Confusingly, the notation that combinatorialists use for falling factorials coincides with the notation used in special functions for rising factorials; see Pochhammer symbol.)

Table of values

Below is a table of values for the Stirling numbers of the second kind (sequence A008277 in OEIS):

n \ k	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1

As with the binomial coefficients, this table could be extended to $k > n$ , but those entries would all be $0$ .

Properties

Recurrence relation

Stirling numbers of the second kind obey the recurrence relation

$\left\{{n\atop k}\right\} = \left\{{n-1\atop k-1}\right\} +k \left\{{ n-1 \atop k }\right\}$

with

$\left\{{ n \atop 1 }\right\}=1 \quad \mbox { and } \quad \left\{{ n \atop n }\right\} = 1.$

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 understand this recurrence, observe that a partition of the $n$ objects into $k$ nonempty subsets either contains the subset ${n}$ or it does not. The number of ways that ${n}$ is one of the subsets is given by

$\left\{{ n-1 \atop k-1 }\right\}$

since we must partition the remaining $n - 1$ objects into the available $k - 1$ subsets. The number of ways that ${n}$ is not one of the subsets (that is, $n$ belongs to a subset containing other elements) is given by

$k \left\{{ n-1 \atop k }\right\}$

since we partition all elements other than $n$ into $k$ subsets, and then are left with $k$ choices for inserting the element $n$ . Summing these two values gives the desired result.

Parity

Parity of Stirling numbers of the second kind.

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:

$\begin{Bmatrix}n\\k\end{Bmatrix}\equiv\binom{z}{w}\pmod{2},\quad z = n - \left\lceil\dfrac{k + 1}{2}\right\rceil,\ w = \left\lfloor\dfrac{k - 1}{2}\right\rfloor.$

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

$\begin{align} \mathbb{A}:\ \sum_{i\in\mathbb{A}} 2^i &= n-k,\\ \mathbb{B}:\ \sum_{j\in\mathbb{B}} 2^j &= \left\lfloor\dfrac{k - 1}{2}\right\rfloor,\\ \end{align}$

then mimic a bitwise AND operation by intersecting these two sets:

$\begin{Bmatrix}n\\k\end{Bmatrix}\bmod 2 = \begin{cases} 0, & \mathbb{A}\cap\mathbb{B}\ne\empty\\ 1, & \mathbb{A}\cap\mathbb{B}=\empty \end{cases}$

to obtain the parity of a Stirling number of the second kind in O(1) time.

Simple identities

Some simple identities include

$\left\{\begin{matrix} n \\ n-1 \end{matrix}\right\} = {n \choose 2}.$

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

$\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = 2^{n-1}-1.$

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.

$\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = \frac{ \frac11 (2^{n-1}-1^{n-1}) }{0!}$

$\left\{\begin{matrix} n \\ 3 \end{matrix}\right\} = \frac{ \frac11 (3^{n-1}-2^{n-1})- \frac12 (3^{n-1}-1^{n-1}) }{1!}$

$\left\{\begin{matrix} n \\ 4 \end{matrix}\right\} = \frac{ \frac11 (4^{n-1}-3^{n-1})- \frac22 (4^{n-1}-2^{n-1}) + \frac13 (4^{n-1}-1^{n-1})}{2!}$

$\left\{\begin{matrix} n \\ 5 \end{matrix}\right\} = \frac{ \frac11 (5^{n-1}-4^{n-1})- \frac32 (5^{n-1}-3^{n-1}) + \frac33 (5^{n-1}-2^{n-1}) - \frac14 (5^{n-1}-1^{n-1}) }{3!}$

$\vdots$

Explicit formula

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

$\left\{\begin{matrix} n \\ k \end{matrix}\right\} =\sum_{j=1}^k (-1)^{k-j} \frac{j^{n-1}}{(j-1)!(k-j)!} =\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n .$

This formula is a special case of the k 'th forward difference of the monomial $x n$ evaluated at x = 0:

$\Delta^k x^n = \sum_{j=0}^{k}(-1)^{k-j}{k \choose j} (x+j)^n.$

Because the Bernoulli polynomials may be written in terms of these forward differences, one immediately obtains a relation in the Bernoulli numbers:

$B_m(0)=\sum_{k=0}^m \frac {(-1)^k k!}{k+1} \left\{\begin{matrix} m \\ k \end{matrix}\right\}.$

Generating function

A generating function for the Stirling numbers of the second kind is given by

$\sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} (x)_k = x^n.$

Applications

Moments of the Poisson distribution

If X is a random variable with a Poisson distribution with expected value λ, then its nth moment is

$E(X^n)=\sum_{k=1}^n S(n,k)\lambda^k.$

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).

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

$E(X^n) = \sum_{k=1}^m S(n,k).$

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.

Rhyming Schemes

The Stirling numbers of the second kind can represent the total number of rhyme schemes for a poem of n lines. $S (n, k)$ 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).

Cereal Box Problem

The Stirling numbers of the second kind can represent the total number of ways a person can collect all prizes after opening a given number of cereal boxes. For example, if there are 3 prizes, and one opens three boxes, there is $S (3,3)$ , or 1 way to win, {1,2,3}. If 4 boxes are opened, there are 6 ways to win $S (4,3)$ ; {1,1,2,3}, {1,2,1,3}, {1,2,3,1}, {1,2,2,3}, {1,2,3,2}, {1,2,3,3}.

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 $S d (n, k)$ , 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 $|i-j| \geq d$ . It has been shown that these numbers satisfy

$S^d(n, k) = S(n-d+1, k-d+1), n \geq k \geq d$

(hence the name "reduced").[1] Observe (both by definition and by the reduction formula), that $S 1 (n, k) = S (n, k)$ , the familiar Stirling numbers of the second kind.

References

^ H. Sharp, Jr., Cardinality of finite topologies, J. Combinatorial Theory 5 (1968), 82-86.

Stirling numbers of the second kind, S(n,k) on PlanetMath.
Weisstein, Eric W., "Stirling Number of the Second Kind" from MathWorld.
Calculator for Stirling Numbers of the Second Kind
Jack van der Elsen, Black and white transformations, Maastricht 2005, ISBN 90-423-0263-1 [Amazon-US | Amazon-UK]

Open source encyclopedia content modification information:

This page was last modified on 9 March 2010 at 07:55.

Authorship and Review

Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.

Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Stirling number of the second kind", which is available in its original form here:

http://en.wikipedia.org/w/index.php?title=Stirling_number_of_the_second_kind

All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.

Stirling number of the second kind -- Please Click to Return to Front Page