- Stirling numbers of the second kind
In
mathematics , Stirling numbers of the second kind, together withStirling numbers of the first kind , are one of the two types ofStirling number s. They commonly occur in the study ofcombinatorics , 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 onStirling number s.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
:B_n=sum_{k=1}^n S(n,k)
is the "n"th Bell number.If we let
:x)_n=x(x-1)(x-2)cdots(x-n+1)
(in particular, ("x")0 = 1 because it is an
empty product ) be thefalling 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 function s for "rising" factorials; seePochhammer symbol .)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
:left{egin{matrix} n \ k end{matrix} ight} = left{egin{matrix} n-1 \ k-1 end{matrix} ight} +k left{egin{matrix} n-1 \ k end{matrix} ight}
with
:left{egin{matrix} n \ 1 end{matrix} ight}=1quad mbox { and } quad left{egin{matrix} n \ n end{matrix} ight} = 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.
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:
:egin{Bmatrix}n\kend{Bmatrix}equivinom{z}{w}pmod{2},quad z = n - leftlceildfrac{k + 1}{2} ight ceil, w = leftlfloordfrac{k - 1}{2} ight floor.
Or directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
:egin{align}mathbb{A}: sum_{iinmathbb{A 2^i &= n-k,\mathbb{B}: sum_{jinmathbb{B 2^j &= leftlfloordfrac{k - 1}{2} ight floor,\end{align}
then mimic a bitwise AND operation by intersecting these two sets:
:egin{Bmatrix}n\kend{Bmatrix}mod 2 =egin{cases} 0, & mathbb{A}capmathbb{B} eempty\ 1, & mathbb{A}capmathbb{B}=emptyend{cases}
to obtain the parity of a Stirling number of the second kind in "O"(1) time.
imple identities
Some simple identities include
:left{egin{matrix} n \ n-1 end{matrix} ight} = {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{egin{matrix} n \ 2 end{matrix} ight} = 2^{n-1}-1.
To see this, first note that there are 2 "n" "ordered" pairs of complementary subsets "A" and "B". In one case, "A" is empty, and in another "B" is empty, so 2 "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 expanding of the recurrence-relation gives identities in the spirit of the above example.
:left{egin{matrix} n \ 2 end{matrix} ight} = frac{ frac11 (2^{n-1}-1^{n-1}) }{0!}
:left{egin{matrix} n \ 3 end{matrix} ight} = frac{ frac11 (3^{n-1}-2^{n-1})- frac12 (3^{n-1}-1^{n-1}) }{1!}
:left{egin{matrix} n \ 4 end{matrix} ight} = frac{ frac11 (4^{n-1}-3^{n-1})- frac22 (4^{n-1}-2^{n-1}) + frac13 (4^{n-1}-1^{n-1})}{2!}
:left{egin{matrix} n \ 5 end{matrix} ight} = 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{egin{matrix} n \ k end{matrix} ight}=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 themonomial 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 polynomial s may be written in terms of these forward differences, one immediately obtains a relation in theBernoulli number s::B_m(0)=sum_{k=0}^m frac {(-1)^k k!}{k+1} left{egin{matrix} m \ k end{matrix} ight}.
Generating function
A
generating function for the Stirling numbers of the second kind is given by:sum_{k=0}^n left{egin{matrix} n \ k end{matrix} ight} (x)_k = x^n.Moments of the Poisson distribution
If "X" is a
random variable with aPoisson distribution withexpected value λ, then its "n"th moment is:E(X^n)=sum_{k=1}^n S(n,k)lambda^k.
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
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 "n"th 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 "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 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 scheme s 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 1 rhyme (aaa), 3 rhyme schemes using two rhymes (aab, aba, abb), and one rhyme scheme using 3 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}.
ee also
*
Bell number - the number of partitions of a set with "n" membersReferences
*.
*A008277 Triangle of Stirling numbers of 2nd kind, S2(n,k), n >= 1, 1<=k<=n. [http://www.research.att.com/~njas/sequences/A008277]
Wikimedia Foundation. 2010.