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$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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