21 De quantas maneiras podemos distribuir 15 livros diferentes para 15 crianças (um para cada uma) depois recolher os livros e novamente fazer a distribuição de forma que nenhuma criança receba o mesmo livro anteriormente recebido?
Passo 1
O enunciado pede o número de maneiras de primeiro distribuir 15 livros distintos para 15 crianças (uma bijeção) e, em seguida, redistribuir os mesmos livros de modo que nenhuma criança receba o livro que já tivera. O conteúdo principal é contagem de permutações e o conceito de derangement (permutação sem pontos fixos).
Passo 2
Para a primeira distribuição qualquer bijeção de 15 livros em 15 crianças pode ser feita de
maneiras.
Passo 3
Após recolher os livros, queremos contar quantas distribuições evitam que cada criança receba de novo exatamente o mesmo livro. Se identificarmos a primeira distribuição por uma permutação
e a segunda por
, a condição
para todo
equivale a exigir que a composição
seja uma permutação de
sem pontos fixos. Tais permutações são chamadas de derangements.
Passo 4
O número de derangements de
elementos, denotado por
, pode ser obtido por inclusão-exclusão:
Passo 5
Assim, para
a segunda distribuição pode ser feita de
maneiras. Logo, o total de pares de distribuições válidas é