The use of exponential generating functions (EGFs)Stirling numbers combinatorial mathematics and possibly the canonical example of how symbolic combinatorics is used. It also illustrates the parallels in the construction of these two types of numbers, lending support to the binomial-style notation that is used for them.
This article uses the coefficient extraction operator
[
z
n
]
{\displaystyle [z^{n}]}
formal power series , as well as the (labelled) operators
C
{\displaystyle {\mathfrak {C}}}
P
{\displaystyle {\mathfrak {P}}}
symbolic combinatorics . Given a combinatorial class, the cycle operator creates the class obtained by placing objects from the source class along a cycle of some length, where cyclical symmetries are taken into account, and the set operator creates the class obtained by placing objects from the source class in a set (symmetries from the symmetric group, i.e. an "unstructured bag".) The two combinatorial classes (shown without additional markers) are
permutations (for unsigned Stirling numbers of the first kind):
P
=
SET
(
CYC
(
Z
)
)
,
{\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})),}
and
set partitions into non-empty subsets (for Stirling numbers of the second kind):
B
=
SET
(
SET
≥
1
(
Z
)
)
,
{\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})),}
where
Z
{\displaystyle {\mathcal {Z}}}
Warning : The notation used here for the Stirling numbers is not that of the Wikipedia articles on Stirling numbers; square brackets denote the signed Stirling numbers here.
Stirling numbers of the first kind
edit
The unsigned Stirling numbers of the first kind count the number of permutations of [n ] with k cycles. A permutation is a set of cycles, and hence the set
P
{\displaystyle {\mathcal {P}}\,}
P
=
SET
(
U
×
CYC
(
Z
)
)
,
{\displaystyle {\mathcal {P}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {CYC} ({\mathcal {Z}})),\,}
where the singleton
U
{\displaystyle {\mathcal {U}}}
statistics of random permutations .
Translating to generating functions we obtain the mixed generating function of the unsigned Stirling numbers of the first kind:
G
(
z
,
u
)
=
exp
(
u
log
1
1
−
z
)
=
(
1
1
−
z
)
u
=
∑
n
=
0
∞
∑
k
=
0
n
[
n
k
]
u
k
z
n
n
!
.
{\displaystyle G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}
Now the signed Stirling numbers of the first kind are obtained from the unsigned ones through the relation
(
−
1
)
n
−
k
[
n
k
]
.
{\displaystyle (-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].}
Hence the generating function
H
(
z
,
u
)
{\displaystyle H(z,u)}
H
(
z
,
u
)
=
G
(
−
z
,
−
u
)
=
(
1
1
+
z
)
−
u
=
(
1
+
z
)
u
=
∑
n
=
0
∞
∑
k
=
0
n
(
−
1
)
n
−
k
[
n
k
]
u
k
z
n
n
!
.
{\displaystyle H(z,u)=G(-z,-u)=\left({\frac {1}{1+z}}\right)^{-u}=(1+z)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}
A variety of identities may be derived by manipulating this generating function :
(
1
+
z
)
u
=
∑
n
=
0
∞
(
u
n
)
z
n
=
∑
n
=
0
∞
z
n
n
!
∑
k
=
0
n
(
−
1
)
n
−
k
[
n
k
]
u
k
=
∑
k
=
0
∞
u
k
∑
n
=
k
∞
z
n
n
!
(
−
1
)
n
−
k
[
n
k
]
=
e
u
log
(
1
+
z
)
.
{\displaystyle (1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{u\log(1+z)}.}
In particular, the order of summation may be exchanged, and derivatives taken, and then z or u may be fixed.
A simple sum is for
n
≥
2
{\displaystyle n\geq 2}
∑
k
=
0
n
(
−
1
)
k
[
n
k
]
=
0.
{\displaystyle \sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=0.}
This formula holds because the exponential generating function of the sum is
H
(
z
,
−
1
)
=
1
1
+
z
and hence
n
!
[
z
n
]
H
(
z
,
−
1
)
=
(
−
1
)
n
n
!
.
{\displaystyle H(z,-1)={\frac {1}{1+z}}\quad {\mbox{and hence}}\quad n![z^{n}]H(z,-1)=(-1)^{n}n!.}
Some infinite sums include
∑
n
=
k
∞
[
n
k
]
z
n
n
!
=
(
−
log
(
1
−
z
)
)
k
k
!
{\displaystyle \sum _{n=k}^{\infty }\left[{\begin{matrix}n\\k\end{matrix}}\right]{\frac {z^{n}}{n!}}={\frac {\left(-\log(1-z)\right)^{k}}{k!}}}
where
|
z
|
<
1
{\displaystyle |z|<1}
z
=
0
{\displaystyle z=0}
log
(
1
+
z
)
{\displaystyle \log(1+z)}
z
=
−
1.
{\displaystyle z=-1.}
This relation holds because
[
u
k
]
H
(
z
,
u
)
=
[
u
k
]
exp
(
u
log
(
1
+
z
)
)
=
(
log
(
1
+
z
)
)
k
k
!
.
{\displaystyle [u^{k}]H(z,u)=[u^{k}]\exp \left(u\log(1+z)\right)={\frac {\left(\log(1+z)\right)^{k}}{k!}}.}
Stirling numbers of the second kind
edit
These numbers count the number of partitions of [n ] into k nonempty subsets. First consider the total number of partitions, i.e. B n
B
n
=
∑
k
=
1
n
{
n
k
}
and
B
0
=
1
,
{\displaystyle B_{n}=\sum _{k=1}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}{\mbox{ and }}B_{0}=1,}
i.e. the Bell numbers . The Flajolet–Sedgewick fundamental theorem applies (labelled case).
The set
B
{\displaystyle {\mathcal {B}}\,}
B
=
SET
(
SET
≥
1
(
Z
)
)
.
{\displaystyle {\mathcal {B}}=\operatorname {SET} (\operatorname {SET} _{\geq 1}({\mathcal {Z}})).}
This decomposition is entirely analogous to the construction of the set
P
{\displaystyle {\mathcal {P}}\,}
P
=
SET
(
CYC
(
Z
)
)
.
{\displaystyle {\mathcal {P}}=\operatorname {SET} (\operatorname {CYC} ({\mathcal {Z}})).}
and yields the Stirling numbers of the first kind. Hence the name "Stirling numbers of the second kind."
The decomposition is equivalent to the EGF
B
(
z
)
=
exp
(
exp
z
−
1
)
.
{\displaystyle B(z)=\exp \left(\exp z-1\right).}
Differentiate to obtain
d
d
z
B
(
z
)
=
exp
(
exp
z
−
1
)
exp
z
=
B
(
z
)
exp
z
,
{\displaystyle {\frac {d}{dz}}B(z)=\exp \left(\exp z-1\right)\exp z=B(z)\exp z,}
which implies that
B
n
+
1
=
∑
k
=
0
n
(
n
k
)
B
k
,
{\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k},}
by convolution of exponential generating functions and because differentiating an EGF drops the first coefficient and shifts B n +1z n /n !.
The EGF of the Stirling numbers of the second kind is obtained by marking every subset that goes into the partition with the term
U
{\displaystyle {\mathcal {U}}\,}
B
=
SET
(
U
×
SET
≥
1
(
Z
)
)
.
{\displaystyle {\mathcal {B}}=\operatorname {SET} ({\mathcal {U}}\times \operatorname {SET} _{\geq 1}({\mathcal {Z}})).}
Translating to generating functions, we obtain
B
(
z
,
u
)
=
exp
(
u
(
exp
z
−
1
)
)
.
{\displaystyle B(z,u)=\exp \left(u\left(\exp z-1\right)\right).}
This EGF yields the formula for the Stirling numbers of the second kind:
{
n
k
}
=
n
!
[
u
k
]
[
z
n
]
B
(
z
,
u
)
=
n
!
[
z
n
]
(
exp
z
−
1
)
k
k
!
{\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=n![u^{k}][z^{n}]B(z,u)=n![z^{n}]{\frac {(\exp z-1)^{k}}{k!}}}
or
n
!
[
z
n
]
1
k
!
∑
j
=
0
k
(
k
j
)
exp
(
j
z
)
(
−
1
)
k
−
j
{\displaystyle n![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}}
which simplifies to
n
!
k
!
∑
j
=
0
k
(
k
j
)
(
−
1
)
k
−
j
j
n
n
!
=
1
k
!
∑
j
=
0
k
(
k
j
)
(
−
1
)
k
−
j
j
n
.
{\displaystyle {\frac {n!}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}{\frac {j^{n}}{n!}}={\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}(-1)^{k-j}j^{n}.}
Ronald Graham , Donald Knuth , Oren Patashnik (1989): Concrete Mathematics , Addison–Wesley, ISBN 0-201-14236-8 D. S. Mitrinovic , Sur une classe de nombre relies aux nombres de Stirling , C. R. Acad. Sci. Paris 252 (1961), 2354–2356.A. C. R. Belton, The monotone Poisson process , in: Quantum Probability (M. Bozejko, W. Mlotkowski and J. Wysoczanski, eds.), Banach Center Publications 73, Polish Academy of Sciences, Warsaw, 2006
Milton Abramowitz and Irene A. Stegun , Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables , USGPO, 1964, Washington DC, ISBN 0-486-61272-4 
![{\displaystyle [z^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16378bf9f6c602c971e93212ae4fc4a18658fa9f)
![{\displaystyle G(z,u)=\exp \left(u\log {\frac {1}{1-z}}\right)=\left({\frac {1}{1-z}}\right)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b03c145e3a6dca53c5b8b983a0d099886606ed)
![{\displaystyle (-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ee2adc72f418a3b3db07de990da9d16ef8f9317)
![{\displaystyle H(z,u)=G(-z,-u)=\left({\frac {1}{1+z}}\right)^{-u}=(1+z)^{u}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}\,{\frac {z^{n}}{n!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b593bd2afc37e0074a4e4f72d0883afa36c54504)
![{\displaystyle (1+z)^{u}=\sum _{n=0}^{\infty }{u \choose n}z^{n}=\sum _{n=0}^{\infty }{\frac {z^{n}}{n!}}\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]u^{k}=\sum _{k=0}^{\infty }u^{k}\sum _{n=k}^{\infty }{\frac {z^{n}}{n!}}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=e^{u\log(1+z)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a3a9c96d6694c2cb22364df476a972e8aa08d41)
![{\displaystyle \sum _{k=0}^{n}(-1)^{k}\left[{\begin{matrix}n\\k\end{matrix}}\right]=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ebf010a112fe20c94a0c54632a3a4eac7aa3db2)
![{\displaystyle H(z,-1)={\frac {1}{1+z}}\quad {\mbox{and hence}}\quad n![z^{n}]H(z,-1)=(-1)^{n}n!.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b163f781f1c4e4fcb912cd5458123426b318c88)
![{\displaystyle \sum _{n=k}^{\infty }\left[{\begin{matrix}n\\k\end{matrix}}\right]{\frac {z^{n}}{n!}}={\frac {\left(-\log(1-z)\right)^{k}}{k!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71d1c6c01d85f77ef64e21d11e233d394c76bba6)
![{\displaystyle [u^{k}]H(z,u)=[u^{k}]\exp \left(u\log(1+z)\right)={\frac {\left(\log(1+z)\right)^{k}}{k!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6c88aea4798576902f921bb1268b67347580bbe)
![{\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=n![u^{k}][z^{n}]B(z,u)=n![z^{n}]{\frac {(\exp z-1)^{k}}{k!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a67aa854ea914d34f8be2d5f6ea7f175ce9d75c)
![{\displaystyle n![z^{n}]{\frac {1}{k!}}\sum _{j=0}^{k}{k \choose j}\exp(jz)(-1)^{k-j}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e127b7f0efa5602037974f23a1a513f1e51fc65a)
