# §26.8 Set Partitions: Stirling Numbers

## §26.8(i) Definitions

$s\left(n,k\right)$ denotes the Stirling number of the first kind: $(-1)^{n-k}$ times the number of permutations of $\{1,2,\ldots,n\}$ with exactly $k$ cycles. See Table 26.8.1.

 26.8.1 $\displaystyle s\left(n,n\right)$ $\displaystyle=1,$ $n\geq 0$, ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E1 Encodings: TeX, pMML, png See also: Annotations for §26.8(i), §26.8 and Ch.26 26.8.2 $\displaystyle s\left(1,k\right)$ $\displaystyle=\delta_{1,k},$ ⓘ Symbols: $\delta_{\NVar{j},\NVar{k}}$: Kronecker delta, $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind and $k$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E2 Encodings: TeX, pMML, png See also: Annotations for §26.8(i), §26.8 and Ch.26
 26.8.3 $(-1)^{n-k}s\left(n,k\right)=\sum_{1\leq b_{1}<\cdots $n>k\geq 1$. ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E3 Encodings: TeX, pMML, png See also: Annotations for §26.8(i), §26.8 and Ch.26

$S\left(n,k\right)$ denotes the Stirling number of the second kind: the number of partitions of $\{1,2,\ldots,n\}$ into exactly $k$ nonempty subsets. See Table 26.8.2.

 26.8.4 $S\left(n,n\right)=1,$ $n\geq 0$, ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E4 Encodings: TeX, pMML, png See also: Annotations for §26.8(i), §26.8 and Ch.26
 26.8.5 $S\left(n,k\right)=\sum 1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}},$ ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E5 Encodings: TeX, pMML, png See also: Annotations for §26.8(i), §26.8 and Ch.26

where the summation is over all nonnegative integers $c_{1},c_{2},\ldots,c_{k}$ such that $c_{1}+c_{2}+\cdots+c_{k}=n-k.$

 26.8.6 $S\left(n,k\right)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\genfrac{(}{)}{0.0pt}{}{% k}{j}j^{n}.$

## §26.8(ii) Generating Functions

 26.8.7 $\sum_{k=0}^{n}s\left(n,k\right)x^{k}={\left(x-n+1\right)_{n}},$ ⓘ Symbols: ${\left(\NVar{a}\right)_{\NVar{n}}}$: Pochhammer’s symbol (or shifted factorial), $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $x$: real variable, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.3 (in slightly different form) Permalink: http://dlmf.nist.gov/26.8.E7 Encodings: TeX, pMML, png Addition (effective with 1.1.2): The Pochhammer symbol now links to its definition. See also: Annotations for §26.8(ii), §26.8 and Ch.26

where ${\left(x\right)_{n}}$ is the Pochhammer symbol: $x(x+1)\cdots(x+n-1)$.

 26.8.8 $\sum_{n=0}^{\infty}s\left(n,k\right)\frac{x^{n}}{n!}=\frac{(\ln\left(1+x\right% ))^{k}}{k!},$ $|x|<1$,
 26.8.9 $\sum_{n,k=0}^{\infty}s\left(n,k\right)\frac{x^{n}}{n!}y^{k}=(1+x)^{y},$ $|x|<1$.
 26.8.10 $\sum_{k=1}^{n}S\left(n,k\right){\left(x-k+1\right)_{k}}=x^{n},$ ⓘ Symbols: ${\left(\NVar{a}\right)_{\NVar{n}}}$: Pochhammer’s symbol (or shifted factorial), $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $x$: real variable, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.4 Referenced by: §26.15 Permalink: http://dlmf.nist.gov/26.8.E10 Encodings: TeX, pMML, png Addition (effective with 1.1.2): The Pochhammer symbol now links to its definition. See also: Annotations for §26.8(ii), §26.8 and Ch.26
 26.8.11 $\sum_{n=0}^{\infty}S\left(n,k\right)\,x^{n}=\frac{x^{k}}{(1-x)(1-2x)\cdots(1-% kx)},$ $|x|<1/k$, ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $x$: real variable, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.4 Permalink: http://dlmf.nist.gov/26.8.E11 Encodings: TeX, pMML, png See also: Annotations for §26.8(ii), §26.8 and Ch.26
 26.8.12 $\sum_{n=0}^{\infty}S\left(n,k\right)\frac{x^{n}}{n!}=\frac{({\mathrm{e}}^{x}-1% )^{k}}{k!},$
 26.8.13 $\sum_{n,k=0}^{\infty}S\left(n,k\right)\frac{x^{n}}{n!}y^{k}=\exp\left(y({% \mathrm{e}}^{x}-1)\right).$

## §26.8(iii) Special Values

For $n\geq 1$,

 26.8.14 $\displaystyle s\left(n,0\right)$ $\displaystyle=0,$ $\displaystyle s\left(n,1\right)$ $\displaystyle=(-1)^{n-1}(n-1)!,$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $!$: factorial (as in $n!$) and $n$: nonnegative integer A&S Ref: 24.1.3 Permalink: http://dlmf.nist.gov/26.8.E14 Encodings: TeX, TeX, pMML, pMML, png, png See also: Annotations for §26.8(iii), §26.8 and Ch.26
 26.8.15 $s\left(n,2\right)=(-1)^{n}(n-1)!\left(1+\frac{1}{2}+\cdots+\frac{1}{n-1}\right),$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $!$: factorial (as in $n!$) and $n$: nonnegative integer A&S Ref: 24.1.3 Permalink: http://dlmf.nist.gov/26.8.E15 Encodings: TeX, pMML, png See also: Annotations for §26.8(iii), §26.8 and Ch.26
 26.8.16 $-s\left(n,n-1\right)=S\left(n,n-1\right)=\genfrac{(}{)}{0.0pt}{}{n}{2},$
 26.8.17 $\displaystyle S\left(n,0\right)$ $\displaystyle=0,$ $\displaystyle S\left(n,1\right)$ $\displaystyle=1,$ $\displaystyle S\left(n,2\right)$ $\displaystyle=2^{n-1}-1.$ ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind and $n$: nonnegative integer A&S Ref: 24.1.4 Permalink: http://dlmf.nist.gov/26.8.E17 Encodings: TeX, TeX, TeX, pMML, pMML, pMML, png, png, png See also: Annotations for §26.8(iii), §26.8 and Ch.26

## §26.8(iv) Recurrence Relations

 26.8.18 $s\left(n,k\right)=s\left(n-1,k-1\right)-(n-1)s\left(n-1,k\right),$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.3 Permalink: http://dlmf.nist.gov/26.8.E18 Encodings: TeX, pMML, png See also: Annotations for §26.8(iv), §26.8 and Ch.26
 26.8.19 $\genfrac{(}{)}{0.0pt}{}{k}{h}s\left(n,k\right)=\sum_{j=k-h}^{n-h}\genfrac{(}{)% }{0.0pt}{}{n}{j}s\left(n-j,h\right)s\left(j,k-h\right),$ $n\geq k\geq h$,
 26.8.20 $s\left(n+1,k+1\right)=n!\sum_{j=k}^{n}\frac{(-1)^{n-j}}{j!}\,s\left(j,k\right),$
 26.8.21 $s\left(n+k+1,k\right)=-\sum_{j=0}^{k}(n+j)s\left(n+j,j\right).$
 26.8.22 $S\left(n,k\right)=kS\left(n-1,k\right)+S\left(n-1,k-1\right),$ ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.4 Permalink: http://dlmf.nist.gov/26.8.E22 Encodings: TeX, pMML, png See also: Annotations for §26.8(iv), §26.8 and Ch.26
 26.8.23 $\genfrac{(}{)}{0.0pt}{}{k}{h}S\left(n,k\right)=\sum_{j=k-h}^{n-h}\genfrac{(}{)% }{0.0pt}{}{n}{j}S\left(n-j,h\right)S\left(j,k-h\right),$ $n\geq k\geq h$,
 26.8.24 $S\left(n,k\right)=\sum_{j=k}^{n}S\left(j-1,k-1\right)k^{n-j},$
 26.8.25 $S\left(n+1,k+1\right)=\sum_{j=k}^{n}\genfrac{(}{)}{0.0pt}{}{n}{j}S\left(j,k% \right),$
 26.8.26 $S\left(n+k+1,k\right)=\sum_{j=0}^{k}jS\left(n+j,j\right).$

## §26.8(v) Identities

 26.8.27 $s\left(n,n-k\right)=\sum_{j=0}^{k}(-1)^{j}\genfrac{(}{)}{0.0pt}{}{n-1+j}{k+j}% \,\genfrac{(}{)}{0.0pt}{}{n+k}{k-j}\*S\left(k+j,j\right),$
 26.8.28 $\sum_{k=1}^{n}s\left(n,k\right)=0,$ $n>1$, ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.3 Permalink: http://dlmf.nist.gov/26.8.E28 Encodings: TeX, pMML, png See also: Annotations for §26.8(v), §26.8 and Ch.26
 26.8.29 $\sum_{k=1}^{n}(-1)^{n-k}s\left(n,k\right)=n!,$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $!$: factorial (as in $n!$), $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.3 Permalink: http://dlmf.nist.gov/26.8.E29 Encodings: TeX, pMML, png See also: Annotations for §26.8(v), §26.8 and Ch.26
 26.8.30 $\sum_{j=k}^{n}s\left(n+1,j+1\right)\,n^{j-k}=s\left(n,k\right).$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $j$: nonnegative integer, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.3 Permalink: http://dlmf.nist.gov/26.8.E30 Encodings: TeX, pMML, png See also: Annotations for §26.8(v), §26.8 and Ch.26
 26.8.31 $\frac{1}{k!}\,\frac{{\mathrm{d}}^{k}}{{\mathrm{d}x}^{k}}f(x)=\sum_{n=k}^{% \infty}\frac{s\left(n,k\right)}{n!}\,\Delta^{n}f(x),$

when $f(x)$ is analytic for all $x$, and the series converges, where

 26.8.32 $\Delta f(x)=f(x+1)-f(x);$ ⓘ Symbols: $\Delta$: forward difference operator and $x$: real variable Permalink: http://dlmf.nist.gov/26.8.E32 Encodings: TeX, pMML, png See also: Annotations for §26.8(v), §26.8 and Ch.26

 26.8.33 $S\left(n,n-k\right)=\sum_{j=0}^{k}(-1)^{j}\genfrac{(}{)}{0.0pt}{}{n-1+j}{k+j}% \genfrac{(}{)}{0.0pt}{}{n+k}{k-j}\*s\left(k+j,j\right),$
 26.8.34 $\sum_{j=0}^{n}j^{k}x^{j}=\sum_{j=0}^{k}S\left(k,j\right)x^{j}\frac{{\mathrm{d}% }^{j}}{{\mathrm{d}x}^{j}}\left(\frac{1-x^{n+1}}{1-x}\right),$
 26.8.35 $\sum_{j=0}^{n}j^{k}=\sum_{j=0}^{k}j!S\left(k,j\right)\genfrac{(}{)}{0.0pt}{}{n% +1}{j+1},$
 26.8.36 $\sum_{k=0}^{n}(-1)^{n-k}k!S\left(n,k\right)=1.$ ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $!$: factorial (as in $n!$), $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.1.4 Permalink: http://dlmf.nist.gov/26.8.E36 Encodings: TeX, pMML, png See also: Annotations for §26.8(v), §26.8 and Ch.26
 26.8.37 $\frac{1}{k!}\Delta^{k}f(x)=\sum_{n=k}^{\infty}\frac{S\left(n,k\right)}{n!}% \frac{{\mathrm{d}}^{n}}{{\mathrm{d}x}^{n}}f(x),$

when $f(x)$ is analytic for all $x$, and the series converges.

Let $A$ and $B$ be the $n\times n$ matrices with $(j,k)$th elements $s\left(j,k\right)$, and $S\left(j,k\right)$, respectively. Then

 26.8.38 $A^{-1}=B.$ ⓘ A&S Ref: 24.1.4 Permalink: http://dlmf.nist.gov/26.8.E38 Encodings: TeX, pMML, png See also: Annotations for §26.8(v), §26.8 and Ch.26
 26.8.39 $\sum_{j=k}^{n}s\left(j,k\right)S\left(n,j\right)=\sum_{j=k}^{n}s\left(n,j% \right)S\left(j,k\right)=\delta_{n,k}.$

See §24.15(iii).

## §26.8(vii) Asymptotic Approximations

 26.8.40 $s\left(n+1,k+1\right)\sim(-1)^{n-k}\frac{n!}{k!}(\gamma+\ln n)^{k},$ $n\to\infty$,

uniformly for $k=o\left(\ln n\right)$, where $\gamma$ is Euler’s constant (§5.2(ii)).

 26.8.41 $s\left(n+k,k\right)\sim\frac{(-1)^{n}}{2^{n}n!}k^{2n},$ $k\to\infty$,

$n$ fixed.

 26.8.42 $S\left(n,k\right)\sim\frac{k^{n}}{k!},$ $n\to\infty$,

$k$ fixed.

 26.8.43 $S\left(n+k,k\right)\sim\frac{k^{2n}}{2^{n}n!},$ $k\to\infty$,

uniformly for $n=o\left(k^{1/2}\right)$.

For asymptotic approximations for $s\left(n+1,k+1\right)$ and $S\left(n,k\right)$ that apply uniformly for $1\leq k\leq n$ as $n\to\infty$ see Temme (1993) and Temme (2015, Chapter 34).

For other asymptotic approximations and also expansions see Moser and Wyman (1958a) for Stirling numbers of the first kind, and Moser and Wyman (1958b), Bleick and Wang (1974) for Stirling numbers of the second kind.

For asymptotic estimates for generalized Stirling numbers see Chelluri et al. (2000).