# §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 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 26
 26.8.3 $(-1)^{n-k}s\left(n,k\right)=\sum_{1\leq b_{1}<\dots $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 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 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 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}=(x-n+1)_{n},$ ⓘ Symbols: $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 See also: Annotations for 26.8(ii), 26.8 and 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(1+x))^{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)(x-k+1)_{k}=x^{n},$ ⓘ 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 Referenced by: §26.15 Permalink: http://dlmf.nist.gov/26.8.E10 Encodings: TeX, pMML, png See also: Annotations for 26.8(ii), 26.8 and 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 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 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 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 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 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).$ ⓘ Symbols: $s\left(\NVar{n},\NVar{k}\right)$: Stirling number of the first kind, $j$: nonnegative integer, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E21 Encodings: TeX, pMML, png See also: Annotations for 26.8(iv), 26.8 and 26
 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 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},$ ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $j$: nonnegative integer, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E24 Encodings: TeX, pMML, png See also: Annotations for 26.8(iv), 26.8 and 26
 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).$ ⓘ Symbols: $S\left(\NVar{n},\NVar{k}\right)$: Stirling number of the second kind, $j$: nonnegative integer, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.8.E26 Encodings: TeX, pMML, png See also: Annotations for 26.8(iv), 26.8 and 26

## §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 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 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 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 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 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 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).