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
D_{n} \;=\; n!\,\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}.
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) é
D_n \;=\; n! \;-\;\bigl|A_1\cup A_2\cup\cdots\cup A_n\bigr|.

Passo 3

Pelo Princípio da Inclusão-Exclusão,
\bigl|A_1\cup \cdots\cup A_n\bigr| =\sum_{k=1}^{n}(-1)^{k-1} \sum_{1\le i_1<\cdots<i_k\le n} \bigl|A_{i_1}\cap\cdots\cap A_{i_k}\bigr|.
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
\bigl|A_1\cup \cdots\cup A_n\bigr| =\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}(n-k)!.

Passo 4

Substituindo em D_n = n! -\bigl|A_1\cup\cdots\cup A_n\bigr|, obtemos
D_n = n! \;-\;\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}(n-k)! =\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)!,
onde no último passo incluímos k=0 (com \binom{n}{0}(n-0)! = n! e sinal (-1)^0=1). Agora note que
\binom{n}{k}(n-k)! \;=\;\frac{n!}{k!\,(n-k)!}\,(n-k)! =\frac{n!}{k!}.
Logo
D_n =\sum_{k=0}^{n}(-1)^k\;\frac{n!}{k!} =n!\,\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

Resposta

D_{n}=n!\,\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}.

Exercícios relacionados