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)
style\left\{{n\atopk}\right\}
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.
The Stirling numbers of the second kind, written
S(n,k)
\lbracestyle{n\atopk}\rbrace
n
k
k
n
\left\{{n\atopn}\right\}=1
\left\{{n\atop1}\right\}=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:[2]
\left\{{n\atopk}\right\}=
1 | |
k! |
k | |
\sum | |
i=0 |
(-1)k-i\binom{k}{i}in=
k | |
\sum | |
i=0 |
(-1)k-iin | |
(k-i)!i! |
.
The Stirling numbers of the second kind may also be characterized as the numbers that arise when one expresses powers of an indeterminate x in terms of the falling factorials[3]
(x)n=x(x-1)(x-2) … (x-n+1).
(In particular, (x)0 = 1 because it is an empty product.)
In other words
n | |
\sum | |
k=0 |
\left\{{n\atopk}
n. | |
\right\}(x) | |
k=x |
Various notations have been used for Stirling numbers of the second kind. The brace notation 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] According to the third edition of The Art of Computer Programming, this notation was also used earlier by Jovan Karamata in 1935.[7] [8] 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.
See main article: Bell number.
Since the Stirling number
\left\{{n\atopk}\right\}
Bn=\sum
n | |
k=0 |
\left\{{n\atopk}\right\}
over all values of k is the total number of partitions of a set with n members. This number is known as the nth Bell number.
Analogously, the ordered Bell numbers can be computed from the Stirling numbers of the second kind via
an=
n | |
\sum | |
k=0 |
k!\left\{{n\atopk}\right\}.
Below is a triangular array of values for the Stirling numbers of the second kind :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||||||||||||
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 | ||||||||||||
10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 |
As with the binomial coefficients, this table could be extended to , but the entries would all be 0.
Stirling numbers of the second kind obey the recurrence relation
\left\{{n+1\atopk}\right\}=k\left\{{n\atopk}\right\}+\left\{{n\atopk-1}\right\} for 0<k<n
\left\{{n\atopn}\right\}=1 for n\geq0 and \left\{{n\atop0}\right\}=\left\{{0\atopn}\right\}=0 forn>0.
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 objects into k nonempty subsets either contains the -th object as a singleton or it does not. The number of ways that the singleton is one of the subsets is given by
\left\{{n\atopk-1}\right\}
since we must partition the remaining objects into the available subsets. In the other case the -th object belongs to a subset containing other objects. The number of ways is given by
k\left\{{n\atopk}\right\}
since we partition all objects other than the -th into k subsets, and then we are left with k choices for inserting object . Summing these two values gives the desired result.
Another recurrence relation is given by
\left\lbrace\begin{matrix}n\ k\end{matrix}\right\rbrace=
kn | |
k! |
k-1 | |
-\sum | |
r=1 |
\left\lbrace\begin{matrix | |
n |
\ r\end{matrix}\right\rbrace}{(k-r)!}.
which follows from evaluating
n | |
\sum | |
r=0 |
\left\{{n\atopr}
n | |
\right\}(x) | |
r=x |
x=k
Some simple identities include
\left\{{n\atopn-1}\right\}=\binom{n}{2}.
This is because dividing n elements into sets necessarily means dividing it into one set of size 2 and sets of size 1. Therefore we need only pick those two elements;
and
\left\{{n\atop2}\right\}=2n-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 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.
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.
\begin{align} \left\{{n+1\atopk+1}\right\}&=
n | |
\sum | |
j=k |
{n\choosej}\left\{{j\atopk}\right\}\\ \left\{{n+1\atopk+1}\right\}&=
n | |
\sum | |
j=k |
(k+1)n-j\left\{{j\atopk}\right\}\\ \left\{{n+k+1\atopk}\right\}&=
k | |
\sum | |
j=0 |
j\left\{{n+j\atopj}\right\}\\ \left\{{n\atop\ell+m}\right\}\binom{\ell+m}{\ell}&=\sumk\left\{{k\atop\ell}\right\}\left\{{n-k\atopm}\right\}\binom{n}{k} \end{align}
The Stirling numbers of the second kind are given by the explicit formula:
\left\{{n\atopk}\right\} =
1 | |
k! |
k | |
\sum | |
j=0 |
(-1)k-j{k\choosej}
k | |
j | |
j=0 |
(-1)k-jjn | |
(k-j)!j! |
.
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 .
xn
\Deltakxn=
k | |
\sum | |
j=0 |
(-1)k-j{k\choosej}(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:
Bm(0)=\sum
m | |
k=0 |
(-1)kk! | |
k+1 |
\left\{{m\atopk}\right\}.
The evaluation of incomplete exponential Bell polynomial Bn,k(x1,x2,...) on the sequence of ones equals a Stirling number of the second kind:
\left\{{n\atopk}\right\}=Bn,k(1,1,...,1).
Another explicit formula given in the NIST Handbook of Mathematical Functions is
\left\{{n\atopk}\right\}=\sum \begin{array{c} c1+\ldots+ck=n-k\\ c1,\ldots, ck \geq 0 \end{array} }
c1 | |
1 |
c2 | |
2 |
…
ck | |
k |
The parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient:
\left\{{n\atopk}\right\}\equiv\binom{z}{w} \pmod{2},
z=n-\left\lceil\displaystyle
k+1 | |
2 |
\right\rceil, w=\left\lfloor\displaystyle
k-1 | |
2 |
\right\rfloor.
More directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
\begin{align} A: \sumi\inA2i&=n-k,\\ B: \sumj\inB2j&=\left\lfloor\dfrac{k-1}{2}\right\rfloor.\\ \end{align}
One can mimic a bitwise AND operation by intersecting these two sets:
\begin{Bmatrix}n\\k\end{Bmatrix}\bmod2= \begin{cases} 0,&A\capB\ne\empty;\\ 1,&A\capB=\empty; \end{cases}
to obtain the parity of a Stirling number of the second kind in O(1) time. In pseudocode:
\begin{Bmatrix}n\\k\end{Bmatrix}\bmod2:=\left[\left(\left(n-k\right) \And \left(\left(k-1\right)div2\right)\right)=0\right];
\left[b\right]
The parity of a central Stirling number of the second kind
style\left\{{2n\atopn}\right\}
n
For a fixed integer n, the ordinary generating function for Stirling numbers of the second kind
\left\{{n\atop0}\right\},\left\{{n\atop1}\right\},\ldots
n | |
\sum | |
k=0 |
\left\{{n\atopk}\right\}xk=Tn(x),
Tn(x)
n | |
\sum | |
k=0 |
\left\{{n\atopk}\right\}(x)k=xn
n+1 | |
\sum | |
k=1 |
\left\{{n+1\atopk}\right\}(x-1)k-1=xn
Which has special case
n | |
\sum | |
k=0 |
\left\{{n\atopk}\right\}(n)k=nn
infty | |
\sum | |
n=k |
\left\{{n\atopk}\right\}xn=
k | |
\prod | |
r=1 |
1 | |
1-rx |
=
1 | |
xk(1/x)k+1 |
infty | |
\sum | |
n=k |
\left\{{n\atopk}\right\}
xn | |
n! |
=
(ex-1)k | |
k! |
.
A mixed bivariate generating function for the Stirling numbers of the second kind is
infty | |
\sum | |
k=0 |
infty | |
\sum | |
n=k |
\left\{{n\atopk}\right\}
xn | |
n! |
yk=
y(ex-1) | |
e |
.
If
n\geq2
1\leqk\leqn-1
1 | |
2 |
(k2+k+2)kn-k-1-1\leq\left\{{n\atopk}\right\}\leq
1 | |
2 |
{n\choosek}kn-k
For fixed value of
k,
n → infty
\left\{{n\atopk}\right\}\underset{n\toinfty}{\sim}
kn | |
k! |
.
If
k=o(\sqrt{n})
\left\{{n+k\atopn}\right\}\underset{n\toinfty}{\sim}
n2k | |
2kk! |
.
A uniformly valid approximation also exists: for all such that, one has
\left\{{n\atopk}\right\}\sim\sqrt{
v-1 | |
v(1-G) |
where , and
G\in(0,1)
G=veG-v
0.066/n
For fixed
n
\left\{{n\atopk}\right\}
kn
\left\{{n\atop1}\right\}<\left\{{n\atop2}\right\}< … <\left\{{n\atopkn}\right\}\geq\left\{{n\atopkn+1}\right\}> … >\left\{{n\atopn}\right\}.
Looking at the table of values above, the first few values for
kn
0,1,1,2,2,3,3,4,4,4,5,\ldots
When
n
kn\underset{n\toinfty}{\sim}
n | |
logn |
,
and the maximum value of the Stirling number can be approximated with
log\left\{{n\atopkn}\right\}=nlogn-nloglogn-n+O(nloglogn/logn).
If X is a random variable with a Poisson distribution with expected value λ, then its n-th moment is
n | |
E(X | |
k=0 |
\left\{{n\atopk}\right\}λ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 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
E(Xn)=
m | |
\sum | |
k=0 |
\left\{{n\atopk}\right\}.
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.
The Stirling numbers of the second kind can represent the total number of rhyme schemes for a poem of n lines.
S(n,k)
The r-Stirling number of the second kind
\left\{{n\atopk}\right\}r
\left\{{n\atopk}\right\}r=k\left\{{n-1\atopk}\right\}r+\left\{{n-1\atopk-1}\right\}r
Some combinatorial identities and a connection between these numbers and context-free grammars can be found in [13]
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.[14] It is denoted by
Sr(n,k)
Sr(n+1,k)=k Sr(n,k)+\binom{n}{r-1}Sr(n-r+1,k-1)
The 2-associated numbers appear elsewhere as "Ward numbers" and as the magnitudes of the coefficients of Mahler polynomials.
Denote the n objects to partition by the integers 1, 2, ..., n. Define the reduced Stirling numbers of the second kind, denoted
Sd(n,k)
|i-j|\geqd
Sd(n,k)=S(n-d+1,k-d+1),n\geqk\geqd
(hence the name "reduced").[15] Observe (both by definition and by the reduction formula), that
S1(n,k)=S(n,k)