Prove que (definindo
)
Passo 1
O enunciado pede para provar a identidade de contagem
onde definimos
. O conteúdo é contagem de permutações e deranjos.
Passo 2
Qualquer permutação de
elementos pode ser classificada pelo número
de pontos fixos (elementos que permanecem em sua posição original). Se uma permutação tiver exatamente
pontos fixos, então os outros
elementos não podem ficar fixos, ou seja, formam um deranjo desses
elementos.
Passo 3
Para escolher quais são os
pontos fixos usamos
maneiras. Em seguida, os
elementos restantes devem ser dispostos sem ponto fixo, o que pode ser feito de
formas. Portanto, o número de permutações com exatamente
pontos fixos é
Passo 4
Somando sobre todas as possibilidades de
de
a
, cobrimos todas as permutações de
elementos. Logo,