Prove que (definindo )

Passo 1

O enunciado pede para provar a identidade de contagem
n! ;=;binomn0Dn+binomn1Dn-1+cdots+binomnnD0,
onde definimos D0=1. O conteúdo é contagem de permutações e deranjos.

Passo 2

Qualquer permutação de n elementos pode ser classificada pelo número k de pontos fixos (elementos que permanecem em sua posição original). Se uma permutação tiver exatamente k pontos fixos, então os outros n-k elementos não podem ficar fixos, ou seja, formam um deranjo desses n-k elementos.

Passo 3

Para escolher quais são os k pontos fixos usamos binomnk maneiras. Em seguida, os n-k elementos restantes devem ser dispostos sem ponto fixo, o que pode ser feito de Dn-k formas. Portanto, o número de permutações com exatamente k pontos fixos é
binomnk,Dn-k

Passo 4

Somando sobre todas as possibilidades de k de 0 a n, cobrimos todas as permutações de n elementos. Logo,
n! ;=;sumk=0^nbinomnkDn-k

Resposta

n! ;=;sumk=0^nbinomnkDn-k

Exercícios de Livros Relacionados