Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

4 Answers 4

up vote 8 down vote accepted

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

share|improve this answer
    
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
1  
@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}.$$

share|improve this answer
    
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

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

share|improve this answer
    
+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 at 5:50

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.