# Exponential Generating Functions For Derangements

I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this term, I derived a formula for the number of derangements of size $n$ using the inclusion/exclusion principle, namely that $D_n = n!\sum_{k=0}^{\infty}\frac{(-1)^k}{k!}$. How would I go about deriving this result using exponential generating functions, without using the inclusion/exclusion principle to derive $D_n$. The formula we are using for the these generating functions are $\Phi_D(x) = \sum_{n=0}^{\infty}|D_n|\frac{x^n}{n!}$.

If anyone could walk me through this example, I would greatly appreciate it :) Thanks!

-

Here’s one way. Start with the recurrence $d_{n+1}=nd_n+nd_{n-1}$, where $d_n$ is the number of derangements of $[n]=\{1,\dots,n\}$. Multiply by $\frac{x^n}{n!}$ and sum over $n\ge 0$:

$$\sum_{n\ge 0}d_{n+1}\frac{x^n}{n!}=\sum_{n\ge 0}nd_n\frac{x^n}{n!}+\sum_{n\ge 0}nd_{n-1}\frac{x^n}{n!}\;.\tag{1}$$

Let $$D(x)=\sum_{n\ge 0}d_n\frac{x^n}{n!}$$ be the exponential generating function in question. Then $$D\,'(x)=\sum_{n\ge 0}nd_n\frac{x^{n-1}}{n!}=\sum_{n\ge 1}d_n\frac{x^{n-1}}{(n-1)!}=\sum_{n\ge 0}d_{n+1}\frac{x^n}{n!}\;,\tag{2}$$

$$xD\,'(x)=x\sum_{n\ge 0}nd_n\frac{x^{n-1}}{n!}=\sum_{n\ge 0}nd_n\frac{x^n}{n!}\;,\tag{3}$$

and $$xD(x)=\sum_{n\ge 0}d_n\frac{x^{n+1}}{n!}=\sum_{n\ge 0}(n+1)d_n\frac{x^{n+1}}{(n+1)!}=\sum_{n\ge 1}nd_{n-1}\frac{x^n}{n!}=\sum_{n\ge 0}nd_{n-1}\frac{x^n}{n!}\;,\tag{4}$$ since by convention $d_{-1}=0$.

Compare $(2),(3)$, and $(4)$ with $(1)$, and you’ll see that

$$D\,'(x)=xD\,'(x)+xD(x)\;,$$ or $$(1-x)D\,'(x)=xD(x)\;.$$ This is a separable differential equation,

$$\frac{D\,'(x)}{D(x)}=\frac{x}{1-x}=-1+\frac1{1-x}\;,$$

which you can now solve for $D(x)$ by first-year calculus.

Here’s another way, quicker but sneakier. For any particular set $K$ of $k$ elements of $[n]$ there are $d_{n-k}$ permutations of $[n]$ that have $K$ as their set of fixed points. There are $\binom{n}k$ such subsets $K$, so there are $\binom{n}kd_{n-k}$ permutations of $[n]$ with exactly $k$ fixed points. Since there are $n!$ permutations of $[n]$ altogether, $$\sum_{k=0}^n\binom{n}kd_{n-k}=n!\;.\tag{5}$$ The lefthand side of $(5)$ is the $n$-th term of the binomial convolution of the sequences $\langle 1,1,1,\dots\rangle$ and $\langle d_n:n\in\Bbb N\rangle$, so the exponential generating function (egf) of the sequence

$$\left\langle\sum_{k=0}^n\binom{n}kd_{n-k}:n\in\Bbb N\right\rangle=\langle n!:n\in\Bbb N\rangle$$

is the product of the egfs of $\langle 1,1,1,\dots\rangle$ and $\langle d_n:n\in\Bbb N\rangle$. Clearly $$\sum_{n\ge 0}n!\frac{x^n}{n!}=\sum_{n\ge 0}x^n=\frac1{1-x}$$ and $$\sum_{n\ge 0}1\cdot\frac{x^n}{n!}=e^x\;,$$ so $$e^xD(x)=\frac1{1-x}\;,$$ and $$D(x)=\frac{e^{-x}}{1-x}\;.$$

-
Wow, quite interesting. To be honest, I feel more comfortable with the steps outlined in the first proof than I do in the second, even though I don't think I would of came to the realization of starting it off the way you did. As for the second one, I feel like it has more of a combinatorial nature, even though I don't quite understand all of the steps. I've never heard of the binomial convolution formula before and I am not quite familiar with equation (5) and the product of the EGFs described after. –  Nizbel99 Nov 19 '12 at 6:53
However, the second proof does seem to reflect what we're doing in class, given that we're talking about classes of structures, which is the motivation we're using in order to discuss EGFs :) –  Nizbel99 Nov 19 '12 at 6:54
@user43552: I thought that the first one was a bit more straightforward. You might want to download Herbert Wilf’s generatingfunctionology, freely available here; it’s not the easiest book, but I actually lifed that second derivation from it. –  Brian M. Scott Nov 19 '12 at 6:58
Thank you for the reference :) - Appreciated as always :) –  Nizbel99 Nov 19 '12 at 7:08
@user43552: My pleasure! –  Brian M. Scott Nov 19 '12 at 7:11
There's a shorter way even than the two in Brian's nice answer. Starting from the recurrence $D_n = n D_{n-1} + (-1)^n$, multiply by $x^n/n!$ and sum over $n \geq 0$ to get \begin{align} &\sum_{n \geq 0} D_n \frac{x^n}{n!} = \sum_{n \geq 0} n D_{n-1} \frac{x^n}{n!} + \sum_{n \geq 0} (-1)^n \frac{x^n}{n!} \\ \implies & G_D(x) = x \sum_{n \geq 1} D_{n-1} \frac{x^{n-1}}{(n-1)!} + e^{-x} \\ \implies & G_D(x) = x G_D(x) + e^{-x}, \end{align} which tells you that the exponential generating function is $$G_D(x) = \frac{e^{-x}}{1-x}.$$
Another way: There are $n!$ permutations in all. A permutation with $k$ fixed points shuffles the other $n - k$ elements around without fixed points, the $k$ fixed points can be selected in $\binom{n}{k}$ ways. So: $$n! = \sum_{0 \le k \le n} \binom{n}{k} d_{n -k}$$ This is a binomial convolution, using Mike Spivey's notation that gives: \begin{align*} \frac{1}{1 - x} &= G_D(x) e^x \\ G_D(x) &= \frac{e^{-x}}{1 - x} \end{align*}