Stirling numbers of the second kind

Stirling numbers of the second kind obey the recurrence relation

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

for k > 0 with initial conditions

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

for n > 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 understand this recurrence, observe that a partition of the ${\displaystyle n+1}$ objects into k nonempty subsets either contains the ${\displaystyle (n+1)}$-th object as a singleton or it does not. The number of ways that the singleton is one of the subsets is given by

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

since we must partition the remaining n objects into the available ${\displaystyle k-1}$ subsets. In the other case the ${\displaystyle (n+1)}$-th object belongs to a subset containing other objects. The number of ways is given by

${\displaystyle k\left\{{n \atop k}\right\}}$

since we partition all objects other than the ${\displaystyle (n+1)}$-th into k subsets, and then we are left with k choices for inserting object ${\displaystyle n+1}$. Summing these two values gives the desired result.

Some more recurrences are as follows:

${\displaystyle \left\{{n+1 \atop k+1}\right\}=\sum _{j=k}^{n}{n \choose j}\left\{{j \atop k}\right\},}$

${\displaystyle \left\{{n+1 \atop k+1}\right\}=\sum _{j=k}^{n}(k+1)^{n-j}\left\{{j \atop k}\right\},}$

${\displaystyle \left\{{n+k+1 \atop k}\right\}=\sum _{j=0}^{k}j\left\{{n+j \atop j}\right\}.}$

If ${\displaystyle n\geq 2}$ and ${\displaystyle 1\leq k\leq n-1}$, then

${\displaystyle L(n,k)\leq \left\{{n \atop k}\right\}\leq U(n,k)}$

where

${\displaystyle L(n,k)={\frac {1}{2}}(k^{2}+k+2)k^{n-k-1}-1}$

and

${\displaystyle U(n,k)={\frac {1}{2}}{n \choose k}k^{n-k}.}$ [11]

For fixed ${\displaystyle n}$, ${\displaystyle \left\{{n \atop k}\right\}}$ has a single maximum, which is attained for at most two consecutive values of k. That is, there is an integer ${\displaystyle K_{n}}$ such that

${\displaystyle \left\{{n \atop 1}\right\}<\left\{{n \atop 2}\right\}<\cdots <\left\{{n \atop K_{n}}\right\},}$

${\displaystyle \left\{{n \atop K_{n}}\right\}\geq \left\{{n \atop K_{n}+1}\right\}>\cdots >\left\{{n \atop n}\right\}.}$

When ${\displaystyle n}$ is large

${\displaystyle K_{n}\sim {\frac {n}{\log n}},}$

and the maximum value of the Stirling number of second kind is

${\displaystyle \log \left\{{n \atop K_{n}}\right\}=n\log n-n\log \log n-n+O(n\log \log n/\log n).}$ [11]

Parity of Stirling numbers of the second kind.

The parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient:

${\displaystyle \left\{{n \atop k}\right\}\equiv {\binom {z}{w}}\ {\pmod {2}},}$ where ${\displaystyle z=n-\left\lceil \displaystyle {\frac {k+1}{2}}\right\rceil ,\ w=\left\lfloor \displaystyle {\frac {k-1}{2}}\right\rfloor .}$

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:

${\displaystyle {\begin{aligned}\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{aligned}}}

One can mimic a bitwise AND operation by intersecting these two sets:

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2={\begin{cases}0,&\mathbb {A} \cap \mathbb {B} \neq \emptyset$ ;\\1,&\mathbb {A} \cap \mathbb {B} =\emptyset ;\end{cases}}}

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

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}\,{\bmod {\,}}2:=\left[\left(\left(n-k\right)\ \And \ \left(\left(k-1\right)\,\mathrm {div} \,2\right)\right)=0\right];}$

where ${\displaystyle \left[b\right]}$ is the Iverson bracket.

Some simple identities include

${\displaystyle \left\{{n \atop n-1}\right\}={\binom {n}{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

${\displaystyle \left\{{n \atop 2}\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 expansion of the recurrence-relation gives identities in the spirit of the above example.

${\displaystyle {\begin{aligned}\left\{{n \atop 2}\right\}&={\frac {{\frac {1}{1}}(2^{n-1}-1^{n-1})}{0!}}\\[8pt]\left\{{n \atop 3}\right\}&={\frac {{\frac {1}{1}}(3^{n-1}-2^{n-1})-{\frac {1}{2}}(3^{n-1}-1^{n-1})}{1!}}\\[8pt]\left\{{n \atop 4}\right\}&={\frac {{\frac {1}{1}}(4^{n-1}-3^{n-1})-{\frac {2}{2}}(4^{n-1}-2^{n-1})+{\frac {1}{3}}(4^{n-1}-1^{n-1})}{2!}}\\[8pt]\left\{{n \atop 5}\right\}&={\frac {{\frac {1}{1}}(5^{n-1}-4^{n-1})-{\frac {3}{2}}(5^{n-1}-3^{n-1})+{\frac {3}{3}}(5^{n-1}-2^{n-1})-{\frac {1}{4}}(5^{n-1}-1^{n-1})}{3!}}\\[8pt]&{}\ \ \vdots \end{aligned}}}$

These examples can be summarized by the recurrence

${\displaystyle \left\lbrace {\begin{matrix}n\\k\end{matrix}}\right\rbrace ={\frac {k^{n}}{k!}}-\sum _{r=1}^{k-1}{\frac {\left\lbrace {\begin{matrix}n\\r\end{matrix}}\right\rbrace }{(k-r)!}}.}$

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

${\displaystyle \left\{{n \atop k}\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 can be derived by using inclusion-exclusion to count the number of surjections from n to k and using the fact that the number of such surjections is ${\textstyle k!\left\{{n \atop k}\right\}}$.

Additionally, this formula is a special case of the kth forward difference of the monomial ${\displaystyle x^{n}}$ evaluated at x = 0:

${\displaystyle \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:

${\displaystyle B_{m}(0)=\sum _{k=0}^{m}{\frac {(-1)^{k}k!}{k+1}}\left\{{m \atop k}\right\}.}$

For a fixed integer n, the ordinary generating function for the Stirling numbers of the second kind ${\displaystyle \left\{{n \atop 0}\right\},\left\{{n \atop 1}\right\},\ldots }$ is given by

${\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}x^{k}=T_{n}(x),}$

where ${\displaystyle T_{n}(x)}$ are Touchard polynomials. If one sums the Stirling numbers against the falling factorial instead, one can show the following identities, among others:

${\displaystyle \sum _{k=0}^{n}\left\{{n \atop k}\right\}(x)_{k}=x^{n}}$

and

${\displaystyle \sum _{k=1}^{n+1}\left\{{n+1 \atop k}\right\}(x-1)_{k-1}=x^{n}.}$

For a fixed integer k, the Stirling numbers of the second kind ${\displaystyle \left\{{0 \atop k}\right\},\left\{{1 \atop k}\right\},\ldots }$ have rational ordinary generating function

${\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}x^{n-k}=\prod _{r=1}^{k}{\frac {1}{1-rx}}={\frac {1}{(k+1)!x^{k+1}{\binom {\frac {1}{x}}{k+1}}}}}$

and have exponential generating function given by

${\displaystyle \sum _{n=k}^{\infty }\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}={\frac {(e^{x}-1)^{k}}{k!}}.}$

A mixed bivariate generating function for the Stirling numbers of the second kind is

${\displaystyle \sum _{0\leq k\leq n}\left\{{n \atop k}\right\}{\frac {x^{n}}{n!}}y^{k}=e^{y(e^{x}-1)}.}$

For fixed value of ${\displaystyle k,}$ the asymptotic value of the Stirling numbers of the second kind as ${\displaystyle n\rightarrow \infty }$ is given by

${\displaystyle \left\{{n \atop k}\right\}\sim {\frac {k^{n}}{k!}}.}$

On the other side, if ${\displaystyle k=o({\sqrt {n}})}$ (where o denotes the little o notation) then

${\displaystyle \left\{{n \atop n-k}\right\}\sim {\frac {(n-k)^{2k}}{2^{k}k!}}\left(1+{\frac {1}{3}}{\frac {2k^{2}+k}{n-k}}+{\frac {1}{18}}{\frac {4k^{4}-k^{2}-3k}{(n-k)^{2}}}+\cdots \right).}$[12]

A uniformly valid approximation also exists: for all k such that 1 < k < n, one has

${\displaystyle \left\{{n \atop k}\right\}\sim {\sqrt {\frac {v-1}{v(1-G)}}}\left({\frac {v-1}{v-G}}\right)^{n-k}{\frac {k^{n}}{n^{k}}}e^{k(1-G)}\left({n \atop k}\right),}$

where ${\displaystyle G=-W_{0}(-ve^{-v}),v=n/k}$, and ${\displaystyle W_{0}(z)}$ is the main branch of the Lambert W function.[13] Relative error is bounded by about ${\displaystyle 0.066/n}$.

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

${\displaystyle E(X^{n})=\sum _{k=1}^{n}\left\{{n \atop k}\right\}\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 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

${\displaystyle E(X^{n})=\sum _{k=1}^{m}\left\{{n \atop k}\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. ${\displaystyle 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).

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 ${\displaystyle S_{r}(n,k)}$ and obeys the recurrence relation

${\displaystyle S_{r}(n+1,k)=k\ S_{r}(n,k)+{\binom {n}{r-1}}S_{r}(n-r+1,k-1)}$

The 2-associated numbers (sequence A008299 in the OEIS) 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 ${\displaystyle 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 ${\displaystyle |i-j|\geq d}$. It has been shown that these numbers satisfy

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

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