Exponential Generating Function 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!

Solution 1:

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}\;.$$

Solution 2:

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

Solution 3:

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

Solution 4:

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.