7
$\begingroup$

I read many articles on the derivation of the derangement formula but I can't understand them clearly. At first I read the Wikipedia article. I understand the recursive derivation of derangement. But I am interested in understanding the inclusion-exclusion based formula for derangements.

$\endgroup$

1 Answer 1

17
$\begingroup$

Suppose we want to count $D_n$, the number of derangements of $\{1,\cdots,n\}$.

Let S be the set of all permutations of $\{1,\cdots,n\}$, and

let $T_i$ be the set of permutations which leave $i$ in its natural position.

Then $D_n=\lvert T_1^c\cap\cdots\cap T_n^c\rvert$

$=\lvert S\rvert-\sum_{i}\vert T_i\rvert+\sum_{i<j}\lvert T_i\cap T_j\rvert-\sum_{i<j<k}\lvert T_i\cap T_j\cap T_k\rvert+\cdots+(-1)^n\lvert T_1\cap\cdots\cap T_n\rvert$

$=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\binom{n}{3}(n-3)!+\cdots+(-1)^n\binom{n}{n}(n-n)!$

$=\displaystyle n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\cdots+(-1)^n\frac{n!}{n!}=n!\left[1-\frac{1}{1!}+\frac{1}{2!~}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\right].$

$\endgroup$
3
  • $\begingroup$ I couldn't understand it completely. I am familiarized with these notations but what is the meaning of the notations . $\endgroup$ Commented Sep 13, 2014 at 5:08
  • $\begingroup$ Let me know which notation you would like me to explain further, and I'll try to do that. $\endgroup$
    – user84413
    Commented Sep 13, 2014 at 19:38
  • $\begingroup$ Straightforward method! +1 $\endgroup$
    – DatBoi
    Commented Feb 14, 2021 at 7:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .