2
$\begingroup$

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.

$\endgroup$

marked as duplicate by Marc van Leeuwen, Carl Mummert, user147263, Johanna, Jack D'Aurizio Feb 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.

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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