Prove que (definindo
)
.
Passo 1
O enunciado pede para mostrar que, definindo
e denotando por
o número de dérangements (permutações sem ponto fixo) de
elementos, vale
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
elementos de duas maneiras. De um lado sabemos que são
. De outro, classificamos cada permutação pelo número
de pontos fixos que ela tem.
Passo 3
Se uma permutação tem exatamente
pontos fixos, primeiro escolhemos quais são esses
elementos: há
maneiras de fazer essa escolha.
Nos elementos restantes exigimos que não fiquem fixos, ou seja, formem um dérangement. O número de dérangements de
elementos é, por definição,
.
maneiras de fazer essa escolha.
Nos
Passo 4
Somando sobre todos os valores possíveis de
(de
a
) obtemos todas as permutações de
elementos: