Generating function of derangements

Question

I am pretty new to the topic of generating functions and I would appreciate if someone could help me out with this problem I have.

In the lecture we have proven the following generating function for the number of derangements $d(n)$ in $S_{n}$: $$D(z):=\sum_{n \geq 0}\frac{d(n)}{n!}z^{n} = \frac{e^{-z}}{1-z}$$ We did that by "manipulating" the term with $(1-z)$ and using the identity $d(n) = (n-1) [d(n-1) + d(n-2)]$. This has led us to a differential equation which we then solved to complete the proof.

First of all, what does that mean, "manipulate"?

I am now supposed to give an alternative proof by manipulating $D(z)e^{z}$ and using the following identity: $$n! = \sum_{k=0}^{n}\binom{n}{k} d(k)$$

I tried doing it the same way we did it in the lecture, but as I have no clue about generating functions, I failed. I'd really appreciate some advice or ideas that could lead to solving this.

Answer 1

You know that

$$e^z=\sum_{n\ge 0}\frac1{n!}z^n$$

and that

$$D(z)=\sum_{n\ge 0}\frac{d(n)}{n!}z^n\;.$$

Now take the Cauchy product:

$$D(z)e^z=\left(\sum_{n\ge 0}\frac{d(n)}{n!}z^n\right)\left(\sum_{n\ge 0}\frac1{n!}z^n\right)=\sum_{n\ge 0}c_nz^n\;,$$

where

$$c_n=\sum_{k=0}^n\left(\frac{d(k)}{k!}\cdot\frac1{(n-k)!}\right)=\sum_{k=0}^n\frac{d(k)}{k!(n-k)!}=\frac1{n!}\sum_{k=0}^n\frac{n!}{k!(n-k)!}d(k)\;.$$

• What is another notation for $\dfrac{n!}{k!(n-k)!}$?
• Now use the identity that you were given and one of the first power series that you learned to express $D(z)e^z$ as a rather simple function of $z$, and solve for $D(z)$.