Prove que o número de permutações caóticas de n elementos é
D_{n}=n!\sum_{k=0}^{n} \frac{(-1)^{k}}{k!} .
Passo 1
O enunciado pede para mostrar que o número D_{n} de permutações de \{1,2,\dots,n\} sem ponto fixo (também chamadas de derangements ou permutações caóticas) satisfaz
O conteúdo principal aqui é o Princípio da Inclusão-Exclusão aplicado ao conjunto de todas as permutações de n elementos. Vamos usá-lo para contar quantas permutações não deixam nenhum elemento fixo.
Passo 2
Definimos, para cada i\in\{1,\dots,n\}, o conjunto
A_i = \{\text{permutações que fixam o elemento }i\}.
Então o total de permutações com pelo menos um ponto fixo é
\bigl|A_1\cup A_2\cup\cdots\cup A_n\bigr|.
Como o número total de permutações é n!, o número que não fixa nenhum elemento (ou seja, D_n) é
Mas se fixarmos exatamente k pontos (isto é, pertencermos a A_{i_1}\cap\cdots\cap A_{i_k}), sobra permutar os n-k restantes de qualquer forma, totalizando (n-k)! permutações. E há \binom{n}{k} escolhas dos k pontos fixos. Logo