# Sum of derangements and binomial coefficients

I’m trying to find the closed form for the following formula

$$\sum_{i=0}^n {n \choose i} D(i)$$

where $D(i)$ is the number of derangement for $i$ elements. A derangement is a permutation in which none of the objects appear in their “natural” (i.e., ordered) place. For example, the only derangements of $\{1,2,3\}$ are $\{2,3,1\}$ and $\{3,1,2\}$, so $!3=2$.

#### Solutions Collecting From Web of "Sum of derangements and binomial coefficients"

Hint: Any permutation on $[n]$ splits $[n]$ in to two sets of points: the set of points which are fixed, and the set of points which are not. To count the number of permutations with $i$ points not fixed and $n-i$ fixed, you would choose which $i$ points are going to be permuted; fix the other points; and put any permutation on the permuted points which has no fixed points. (That last bit sounds like a derangement of $i$ elements!)

For the sake of completeness we present an algebraic proof. Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating function of
$$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now derangements are represented by the combinatorial species $\mathcal{D}$ with specification
$$\mathcal{D} = \mathfrak{P}(\mathfrak{C}_2(\mathcal{Z})+\mathfrak{C}_3(\mathcal{Z})+ \mathfrak{C}_4(\mathcal{Z})+\cdots).$$
This means that they have exponential generating function
$$D(z) = \exp\left(\frac{z^2}{2}+\frac{z^3}{3}+\frac{z^4}{4}+\cdots\right) = \exp\left(-z + \log\frac{1}{1-z}\right) = \frac{1}{1-z} \exp(-z).$$

This is our $A(z)$ as described in the introduction. Our $B(z)$ is determined by the sum that we want to calculate to be the exponential generating function of the constant sequence with value one.
$$B(z) = \sum_{n\ge 0}\frac{z^n}{n!} = \exp(z).$$

It follows that
$$A(z) B(z) = \frac{1}{1-z}$$
and therefore the sum is
$$n! [z^n] A(z) B(z) = n![z^n] \frac{1}{1-z} = n!$$
which is the closed form that we were trying to compute.