Vtyjkyuk

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^inftyfrac(-1)^kk!$. 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|fracx^nn!$.

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 $fracx^nn!$ and sum over $nge 0$:

$$sum_nge 0d_n+1fracx^nn!=sum_nge 0nd_nfracx^nn!+sum_nge 0nd_n-1fracx^nn!;.tag1$$

(Here I make the assumption that $d_-1=0$: this is consistent with the recurrence, so it causes no problems.) Let $$D(x)=sum_nge 0d_nfracx^nn!$$ be the exponential generating function in question. Then $$D,'(x)=sum_nge 0nd_nfracx^n-1n!=sum_nge 1d_nfracx^n-1(n-1)!=sum_nge 0d_n+1fracx^nn!;,tag2$$

$$xD,'(x)=xsum_nge 0nd_nfracx^n-1n!=sum_nge 0nd_nfracx^nn!;,tag3$$

and $$xD(x)=sum_nge 0d_nfracx^n+1n!=sum_nge 0(n+1)d_nfracx^n+1(n+1)!=sum_nge 1nd_n-1fracx^nn!=sum_nge 0nd_n-1fracx^nn!;,tag4$$ 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,

$$fracD,'(x)D(x)=fracx1-x=-1+frac11-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 $binomnk$ such subsets $K$, so there are $binomnkd_n-k$ permutations of $[n]$ with exactly $k$ fixed points. Since there are $n!$ permutations of $[n]$ altogether, $$sum_k=0^nbinomnkd_n-k=n!;.tag5$$ The lefthand side of $(5)$ is the $n$-th term of the binomial convolution of the sequences $langle 1,1,1,dotsrangle$ and $langle d_n:ninBbb Nrangle$, so the exponential generating function (egf) of the sequence

$$leftlanglesum_k=0^nbinomnkd_n-k:ninBbb Nrightrangle=langle n!:ninBbb Nrangle$$

is the product of the egfs of $langle 1,1,1,dotsrangle$ and $langle d_n:ninBbb Nrangle$. Clearly $$sum_nge 0n!fracx^nn!=sum_nge 0x^n=frac11-x$$ and $$sum_nge 01cdotfracx^nn!=e^x;,$$ so $$e^xD(x)=frac11-x;,$$ and $$D(x)=frace^-x1-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 $binomnk$ ways. So:
$$
n! = sum_0 le k le n binomnk d_n -k
$$
This is a binomial convolution, using Mike Spivey's notation that gives:
$$
beginalign*
frac11 - x &= G_D(x) e^x \
G_D(x) &= frace^-x1 - x
endalign*
$$

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
beginalign
&sum_n geq 1 D_n fracx^nn! = sum_n geq 1 n D_n-1 fracx^nn! + sum_n geq 1 (-1)^n fracx^nn! \
implies & G_D(x) - 1 = x sum_n geq 1 D_n-1 fracx^n-1(n-1)! + e^-x - 1, text as $D_0 = 1$ \
implies & G_D(x) = x G_D(x) + e^-x,
endalign
which tells you that the exponential generating function is $$G_D(x) = frace^-x1-x.$$

Yet another couple of ways.

Method 1.
$$mathcalD = operatornameSscriptsize ET(operatornameCscriptsize YC_> 1) implies D(z) = expleft(ln frac11-z - zright) = frace^-z1-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) = lnfrac11-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)! fracz^nn! = sum_nge 2fracz^nn = ln frac11-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) = expleft(sum_n > r fracz^rrright) = frace^-z-z^2/2 - dots - z^r/r1-z.$$
Of course, the $r=0$ case simply gives the EGF of all permutations, $explnfrac11-z = frac11-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 $mathcalP$ be the class of all permutations, and let $mathcalQ$ 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 $mathcalQ$ is got by taking an arbitrary permutation and inserting a set of fixed points in it: $mathcalQ = mathcalP star operatornameSscriptsize ET(mathcalZ)$. 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) = frac11-ze^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) = dfrace^z(u-1)1-z$. The EGF of derangements is got by setting $u = 0$ in the above:
$$D(z) = P(z, 0) = frace^-z1-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 $dfracz^kk!dfrace^-z1-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
$$mathcalP = mathcalD star operatornameSscriptsize ET(mathcalZ)
implies P(z) = D(z) e^z implies D(z) = frace^-z1-z
$$
which is the same as Brian M. Scott's second approach and vonbrand's answer.