Computing the coefficients of the egf of derangements

74 Views Asked by At

Recall that a derangement is a permutation with no fixed points and let $\mathcal{D}$ be the combinatorial class of derangements. Find the exponential generating function $D(z)$ of $\mathcal{D}$ and a formula for its coefficients $[z^n]D(z)$.

Recalling the cycle notation of permutations we see that

$$\mathcal{D} = SET(CYC_{\ge 1}(Z)),$$

so $D(z) = \exp \big( \log \big(\frac{1}{1-z}\big)-1 \big) = \frac{e^{-z}}{1-z}$. So evaluating the coefficient requires us to multiply the corresponding power series:

\begin{align} e^{-z} \cdot \frac{1}{1-z} = \sum_{n = 0}^\infty \frac{(-z)^n}{n!} \cdot \sum_{n = 0}^\infty z^n = \sum_{n = 0}^\infty \frac{(-z)^n}{n!} \cdot \sum_{n = 0}^\infty n! \frac{z^n}{n!} \end{align}

Now I tried to use the multiplication rule for egfs:

$$ A(z)\cdot B(z) = \sum_{n = 0}^\infty \bigg( \sum_{k=0}^n \binom{n}{k} a_kb_{n-k} \bigg) \frac{z^n}{n!}$$

but this does not yield a good result. Am I missing something?

EDIT:

Here is the final (and correct) computation:

\begin{align} \sum_{n = 0}^\infty \frac{(-z)^n}{n!} \cdot \sum_{n = 0}^\infty n! \frac{z^n}{n!} &= \sum_{n = 0}^\infty \bigg( \sum_{k=0}^n \binom{n}{k} (-1)^k(n-k)! \bigg) \frac{z^n}{n!} \\ &= \sum_{n = 0}^\infty \bigg( \sum_{k=0}^n \frac{n!}{k!} (-1)^k \bigg) \frac{z^n}{n!} \\ &= \sum_{n = 0}^\infty \bigg( n! \sum_{k=0}^n \frac{(-1)^k }{k!} \bigg) \frac{z^n}{n!} \end{align}