Combinatorics – Exponential Generating Function for Derangements

combinatoricsderangementsgenerating-functionspermutations

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!

Best Answer

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

Related Question