# 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}$$

(Here I make the assumption that $d_{-1}=0$: this is consistent with the recurrence, so it causes no problems.) 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
@AlJebr: It needn’t: the original constant term has derivative $0$, so it makes no difference whether one includes it or not. I thought that it might be clearer to leave that term in the sum at first, simply replacing the general term by its derivative, and then point out at the next step that in fact we can start the indexing at $1$ without losing anything. – Brian M. Scott Mar 15 at 7:31
@AlJebr: If there is more than one way to express something, you use whatever expression is most useful for your purposes. This is every bit as true for power series as for anything else. I get the feeling that you’re trying to bypass thinking about what’s actually happening in the computation in favor of applying a mechanical rule; that’s not a good idea, at least not until you’ve become so familiar with such calculations that they are mechanical for you. – Brian M. Scott Mar 15 at 7:40

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*}

-
+1. Quite nice! – Mike Spivey May 23 '13 at 3:12
+1, but actually this is the same as Brian's second way. – ShreevatsaR Jan 20 '14 at 5:50

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 1$ to get \begin{align} &\sum_{n \geq 1} D_n \frac{x^n}{n!} = \sum_{n \geq 1} n D_{n-1} \frac{x^n}{n!} + \sum_{n \geq 1} (-1)^n \frac{x^n}{n!} \\ \implies & G_D(x) - 1 = x \sum_{n \geq 1} D_{n-1} \frac{x^{n-1}}{(n-1)!} + e^{-x} - 1, \text{ as $D_0 = 1$} \\ \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}.$$

-
You first have to show that the two recurrences are equivalent. – marty cohen May 21 '13 at 19:56
@martycohen: Well, that depends on what you already know about the derangement numbers. But it is easy to get from the recurrence Brian uses to the one I use. See, for example, this blog post. – Mike Spivey May 23 '13 at 3:10
I just came across this question and noted that using $(9)$ from this answer, we simply need to multiply by $x^n$ and sum for $n\ge1$ to get $f(x)-1-xf(x)=e^{-x}-1$ which immediately gives $f(x)=\frac{e^{-x}}{1-x}$. This is essentially what you have here (+1) – robjohn Sep 18 '15 at 22:46
I just noticed that you are summing for $n\ge0$. What do you use for $D_{-1}$? Of course, it is being multiplied by $\frac{0}{0!}$, so perhaps we don't need to worry too much, but somehow, it still bothers me. – robjohn Sep 18 '15 at 22:48
@robjohn: Better? :) – Mike Spivey Sep 18 '15 at 23:15

Yet another couple of ways.

Method 1. $$\mathcal{D} = \operatorname{S\scriptsize ET}(\operatorname{{C\scriptsize YC}_{> 1}}) \implies D(z) = \exp\left(\ln \frac1{1-z} - z\right) = \frac{e^{-z}}{1-z}.$$

Explanation: A derangement, a permutation with no fixed points, is a set of cycles each containing more than one element. The EGF for such cycles can be got by either taking the known EGF for all cycles, namely $C(z) = \ln\frac1{1-z}$, and subtracting the term "$z$" that corresponds to the unique cycle of length $1$, or, if you don't know $C(z)$, with explicit counting as $$C_{>1}(z) = \sum_{n \ge 2} (n-1)! \frac{z^n}{n!} = \sum_{n\ge 2}\frac{z^n}{n} = \ln \frac1{1-z} - z$$

And as derangements are sets of such cycles, their EGF is the exponential of the EGF of such cycles. (This set→exp-of-EGFs fact is also known as the exponential formula.)

Note that the above aproach also easily gives the generating function for the number of permutations with all cycles of length greater than $r$ for any $r$ (derangements is the $r=1$ case): it's $$D_r(z) = \exp\left(\sum_{n > r} \frac{z^r}r\right) = \frac{e^{-z-z^2/2 - \dots - z^r/r}}{1-z}.$$ Of course, the $r=0$ case simply gives the EGF of all permutations, $\exp\ln\frac1{1-z} = \frac1{1-z}$, as expected.

Method 2.
This is a generating-functions analogue of the inclusion-exclusion principle. Though it is overkill for this problem, here it is as an illustration.

Let $\mathcal{P}$ be the class of all permutations, and let $\mathcal{Q}$ be the class of all permutations with some subset of their fixed-points (possibly none, possibly all) specially distinguished. Viewing it differently, any member of $\mathcal{Q}$ is got by taking an arbitrary permutation and inserting a set of fixed points in it: $\mathcal{Q} = \mathcal{P} \star \operatorname{S\scriptsize ET}(\mathcal{Z})$. Using the variable $z$ to mark size and the variable $v$ to mark the distinguished fixed points, we get the (bivariate) EGF $Q(z,v) = \frac1{1-z}e^{zv}$.

Now if $P(z, u)$ is the EGF for permutations where $z$ marks size and $u$ marks the fixed points, the act of "distinguishing" some of the fixed points corresponds to the substitution $1 + v$ for $u$ in the EGF for permutations: every fixed point (marked by $u$) is either distinguished (marked by $v$) or not (unmarked). So we have $Q(z, v) = P(z, 1 + v)$ or equivalently $P(z, u) = Q(z, u - 1) = \dfrac{e^{z(u-1)}}{1-z}$. The EGF of derangements is got by setting $u = 0$ in the above: $$D(z) = P(z, 0) = \frac{e^{-z}}{1-z}$$

This approach also gives the EGF number of permutations with exactly $k$ fixed points, as the coefficient of $u^k$ in the above: it's $\dfrac{z^k}{k!}\dfrac{e^{-z}}{1-z}$.

References: Both the above are from the book Analytic Combinatorics by Flajolet and Sedgewick, pp. 122–123 and 207–208 respectively.

Of course, a simpler observation is that any permutation is a derangement along with a set of fixed points added, so $$\mathcal{P} = \mathcal{D} \star \operatorname{S\scriptsize ET}(\mathcal{Z}) \implies P(z) = D(z) e^z \implies D(z) = \frac{e^{-z}}{1-z}$$ which is the same as Brian M. Scott's second approach and vonbrand's answer.

-