Derivación de la desviación con inclusión-exclusión

Question

He leído muchos artículos sobre la derivación de la fórmula de enajenación pero no consigo entenderlos con claridad. Al principio leí el artículo de Wikipedia . Entiendo la derivación recursiva del desvarío. Pero me interesa entender la fórmula basada en la inclusión-exclusión de los desvaríos.

Answer 1

Supongamos que queremos contar $D_n$ el número de desviaciones de $\{1,\cdots,n\}$ .

Sea S el conjunto de todas las permutaciones de $\{1,\cdots,n\}$ y

dejar $T_i$ sea el conjunto de permutaciones que dejan $i$ en su posición natural.

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