<-- Back to the home page

Stirling Numbers of the Second Kind

{nk}\left\{ \begin{matrix} n\\ k \end{matrix} \right\} or S(n, k) is the number of ways of partitioning an nn element set into kk subsets.

A008277 on the OEIS

Basic Recurrence

{nn}=1 for n≥0\left\{{ n \atop n }\right\} = 1 \quad \text{ for } n \geq 0

{n0}={0k}=0 for n,k>0\left\{{ n \atop 0 }\right\} = \left\{{ 0 \atop k }\right\} = 0 \quad \text{ for } n, k>0

{n+1k}=k{nk}+{nk−1} for 0<k<n\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} \quad \text{ for } 0<k<n

Formulas

{nk}=1k!∑i=0k(−1)k−i(ki)in=∑i=0k(−1)k−iin(k−i)!i!\left\{ {n \atop k}\right\} = \frac{1}{k!}\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} i^n = \sum_{i=0}^k \frac{(-1)^{k-i} i^n}{(k-i)!i!}

Identities

∑k=0n{nk}(x)k=xn\sum_{k=0}^n \left\{ {n \atop k} \right\}(x)_k=x^n

{nn−1}=(n2)\left\{ {n \atop n-1}\right\} = \binom{n}{2}

{n2}=2n−1−1\left\{ {n \atop 2}\right\} = 2^{n-1}-1

{n+1k+1}=∑j=kn(nj){jk}\left\{{n+1\atop k+1}\right\} = \sum_{j=k}^n {n \choose j} \left\{{ j \atop k }\right\}\\

{n+1k+1}=∑j=kn(k+1)n−j{jk}\left\{{n+1\atop k+1}\right\} = \sum_{j=k}^n (k+1)^{n-j} \left\{{j \atop k}\right\}\\

{n+k+1k}=∑j=0kj{n+jj}\left\{{n+k+1 \atop k}\right\} = \sum_{j=0}^k j \left\{{ n+j \atop j }\right\} \\

{nℓ+m}(ℓ+mℓ)=∑k{kℓ}{n−km}(nk)\left\{{n \atop \ell+m } \right\} \binom{\ell+m}{\ell} = \sum_k \left\{{k \atop \ell} \right\} \left\{{n-k \atop m } \right\} \binom{n}{k}

Generating functions

See Wikipedia

Associated Stirling Numbers

Restricted Stirling Numbers

Bell Numbers