# The number of bijections $f$ of $\{1, 2,…, n\}$ such that $f(i) \ne i$ for any $i$ [duplicate]

This question already has an answer here:

Show that the number of bijections $f$ of $\{1, 2,..., n\}$ such that $f(i) \ne i$ for any $i$ is equal to $$\sum_{j=0}^{n}(-1)^j\frac{n!}{j!}.$$

Can I get some help for the above problem? I am not getting it at all.

## marked as duplicate by Marc van Leeuwen, Carl Mummert, user147263, Johanna, Jack D'AurizioFeb 22 '15 at 15:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 3 Answers

Hint: Use the principle of inclusion-exclusion with conditions $c_i: f(i) = i$ to find the number of bijections with at least one fixed point. Then subtract this number from the number of all bijections to get the result.

Such bijections are called derangements. The Week $2$ homework Counting Derangements here gives one approach, using an inclusion-exclusion argument, while still leaving most of the details to you. (It also has four sets of answers by different people.) You can find full derivations, using a variety of techniques, in any number of books, including Graham, Knuth, & Patashnik, Concrete Mathematics, Miklós Bóna, Introduction to Enumerative Combinatorics, and Wilf, generatingfunctionology; the last is freely available here.

A nice derivation starts with considering a permutation with exactly $k$ fixed points in $n$, there are $\dbinom{n}{k} D_{n - k}$ of those. In all there are $n!$ permutations. This gives the recurrence: $$n! = \sum_{0 \le k \le n} \binom{n}{k} D_{n - k}$$ Define the exponential generating function: $$\widehat{D}(z) = \sum_{n \ge 0} D_n \frac{z^n}{n!}$$ The recurrence is the binomial convolution of 1 and $D_n$, so: $$\frac{1}{1 - z} = e^z \widehat{D}(z)$$ Thus: $$\widehat{D}(z) = \frac{e^{-z}}{1 - z}$$ From this, as multipling by $(1 - z)^{-1}$ gives partial sums of coefficients: $$\frac{D_n}{n!} = \sum_{0 \le k \le n} \frac{(-1)^k}{k!}$$