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
15!
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 \sigma e a segunda por \tau, a condição \tau(i)\neq\sigma(i) para todo i equivale a exigir que a composição
h = \sigma^{-1}\circ\tau
seja uma permutação de \{1,\dots,15\} sem pontos fixos. Tais permutações são chamadas de derangements.

Passo 4

O número de derangements de n elementos, denotado por D_n, pode ser obtido por inclusão-exclusão:
D_n = n!\,\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

Passo 5

Assim, para n=15 a segunda distribuição pode ser feita de D_{15} maneiras. Logo, o total de pares de distribuições válidas é
15!\times D_{15} =15!\times\Bigl(15!\,\sum_{k=0}^{15}\frac{(-1)^k}{k!}\Bigr) =(15!)^2\sum_{k=0}^{15}\frac{(-1)^k}{k!}.

Resposta

15!\,D_{15} =15!\,\Bigl(15!\sum_{k=0}^{15}\frac{(-1)^k}{k!}\Bigr) =(15!)^2\sum_{k=0}^{15}\frac{(-1)^k}{k!}.

Exercícios relacionados