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

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

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!}$$