# Derivation of derangement with inclusion-exclusion

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.

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

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