$\newcommand{\ds}{\displaystyle}$ $\newcommand{\ogf}{\stackrel{ogf}{\longleftrightarrow}}$ $\newcommand{\egf}{\stackrel{egf}{\longleftrightarrow}}$ $\newcommand{\sns}[2]{\genfrac{\{}{\}}{0pt}{0}{#1}{#2}}$
There is another way to associate a sequence with a power series
We will see that this association is as useful as ogf in solving many combinatorial problems.
We can recover $(a_n)$ from its egf $A(z)$ by asking its coefficient of $z^n/n!$ term. That is
$$ a_n = \left[\frac{z^n}{n!} \right]A(z)$$The name exponential generating functions stem from the fact that egf of the constant sequence $(1)$ is simply the exponential function.
$$ \sum_{n=0}^{\infty} \frac{z^n}{n!} = 1+ z+ \frac{z^2}{2!} + \cdots = e^z $$Suppose $(a_n) \egf A(z)$ and $(b_n) \egf B(z)$. Then as expected we have
$$ (a_n+b_n) \egf A(z) + B(z) $$The product of two egfs is a bit more interesting:
Suppose
$$ A(z)= \sum_k a_k\frac{z^k}{k!}\quad \text{and}\quad B(z)=\sum_j b_j\dfrac{z^j}{j!}$$Then
$$A(z)B(z) = \sum_{k,j} \dfrac{a_kb_j}{k!j!}z^{k+j} = \sum_n \sum_{k=0}^n \binom{n}{k}a_kb_{n-k}\frac{z^n}{n!}$$That is
$$ C(z):= A(z)B(z) \egf c_n = \sum_{k=0}^n \binom{n}{k}a_kb_{n-k} = \sum_{k=0}^n \binom{n}{k}a_{n-k}b_k $$Since $(1) \egf e^z$, when $B(z) = e^z$ we have
$$ c_n \egf C(z) = e^zA(z) \egf \sum_{k=0}^n \binom{n}{k}a_k$$Certainly $C(z) = e^z A(z)$ simply means $A(z) = e^{-z}C(z)$ and as $e^{-z} \egf (-1)^n$, we have
And, $$(x+y)^n \egf e^{(x+y)z} = e^{xz}e^{yz} \egf \sum_{k=0}^n \binom{n}{k}x^ky^{n-k}$$
So we have just proved the binomial theorem.
Allocation problems with constriants. We have seen that in Notes 08
Count the number of surjective maps from $[m]$ to $[n]$ ($m \ge n$)
We have solved this problem using PIE. We now solve it using egf.
Let $a(m,k)$ be the number of surjective maps from a set of size $m$ to a set of size $k$.
So $a(0,0) = 1$, $a(m,0)=0$ if $m > 0$ and $a(m,k) = 0$ if $k > m$.
Note that
$$ f \longleftrightarrow f|_{\mathrm{rng} f}$$is a 1-to-1 correspondence between the functions from $[m]$ to $[n]$ and the surjections from $[m]$ to some subsets of $[n]$.
There are $\ds \binom{n}{k}$ $k$-subsets of $n$. Thus, we conclude that
$$n^m = \sum_{k=1}^{n} \binom{n}{k}a(m,k) = \sum_{k=0}^n \binom{n}{k}a(m,k)$$It follows form the inversion formula that
$$ a(m,n) = \sum_{k=0}^n \binom{n}{k}(-1)^{n-k}k^m = \sum_{k=0}^n \binom{n}{k}(-1)^{k}(n-k)^m. $$Let $\ds \sns{n}{k}$ denote the number of $k$-partitions of a set of size $n$ (i.e. the partitions of a set of size $n$ with $k$ parts)
These are called the Stirling numbers of the second kind
Since a surjection $f$ from $[n]$ to $[k]$ is determined by its set of fibres (preimages of elements of $[k]$ under $f$) which is a $k$-partition of $[n]$ and where each of this fibres mapsto (there are $k!$ ways), therefore
$$a(n,k) = k!\sns{n}{k}$$So as a bonus, we get the closet form of $\sns{n}{k}$:
\begin{align*} \sns{n}{k} &= \frac{a(n,k)}{k!} = \sum_{r=0}^k \binom{k}{r}(-1)^{k-r}\frac{1}{k!}r^n = \sum_{r=0}^k (-1)^{k-r}\frac{r^n}{r!(k-r)!} \end{align*}Exercise. Find $\sns{4}{2}$.
We have seen how to compute $d_n$ the number of derangements of $n$-things using PIE. Now we compute it using egf.
This time the observation is that a permutation $\sigma$ of $[n]$ is determined by the $k$-subset ($0 \le k \le n$) that it fixes pointwise and a derangement on the complement of that $k$-subset.
So there are
$$ \binom{n}{k}d_{n-k} $$permutations of $[n]$ that has $k$ fix points.
Since every permutation of $n$ fixes $k$ points for some $0 \le k \le n$, therefore
$$ n! = \sum_{k=0}^n \binom{n}{k}d_{n-k} $$So again, we conclude from the inversion formula that
$$ d_n = \sum_{k=0}^n(-1)^{k}\binom{n}{k}(n-k)!$$