Prove que (definindo D_{0}=1 ) n!=\binom{n}{0} D_{n}+\binom{n}{1} D_{n-1}+\binom{n}{2} D_{n-2}+\ldots+\binom{n}{n} D_{0}.

Passo 1

O enunciado pede para mostrar que, definindo \,D_{0}=1 e denotando por \,D_{n} o número de dérangements (permutações sem ponto fixo) de n elementos, vale
n! \;=\;\binom{n}{0}D_{n} \;+\;\binom{n}{1}D_{n-1}\;+\;\cdots+\;\binom{n}{n}D_{0}.
O conteúdo principal é contagem de permutações e uso de classificação segundo o número de pontos fixos.

Passo 2

Vamos contar o total de permutações de n elementos de duas maneiras. De um lado sabemos que são n!. De outro, classificamos cada permutação pelo número k de pontos fixos que ela tem.

Passo 3

Se uma permutação tem exatamente k pontos fixos, primeiro escolhemos quais são esses k elementos: há \displaystyle \binom{n}{k}
maneiras de fazer essa escolha.
Nos n-k elementos restantes exigimos que não fiquem fixos, ou seja, formem um dérangement. O número de dérangements de n-k elementos é, por definição, D_{n-k}.

Passo 4

Somando sobre todos os valores possíveis de k (de 0 a n) obtemos todas as permutações de n elementos:
\sum_{k=0}^{n}\binom{n}{k}D_{n-k} \;=\;n!.

Resposta

n! \;=\;\sum_{k=0}^{n}\binom{n}{k}D_{n-k}

Exercícios relacionados