De quantas maneiras podemos distribuir 30 brinquedos distintos para 29 crianças, de modo que toda criança receba, pelo menos, um brinquedo?

Passo 1

Resumo do enunciado: temos 30 brinquedos todos diferentes e 29 crianças diferentes, e queremos dar brinquedos de modo que cada criança receba pelo menos um.
Conteúdo: é um problema de contagem de distribuições (funções) sobrejetoras. Para resolver precisamos do princípio da inclusão–exclusão ou da conexão com números de Stirling de segunda espécie.

Passo 2

Vamos pensar em cada brinquedo “escolhendo” uma criança para quem vai.
Sem restrição, cada um dos 30 brinquedos pode ir para qualquer uma das 29 crianças, dando no total
29^30
maneiras. Mas aí algumas crianças podem acabar sem brinquedo.

Passo 3

Para garantir que cada criança tenha pelo menos um, usamos o princípio da inclusão–exclusão.
Número de distribuições em que cada criança recebe ≥1 brinquedo é
sumi=0^29(-1)^ibinom29i(29-i)^30,
onde em cada termo tiramos crianças que ficarão de fora e contamos distribuições para as restantes, ajustando sinal.

Passo 4

Felizmente, existe uma fórmula mais simples nesse caso: o número de maneiras de distribuir S(n,n-1),(n-1)! objetos distintos em S(n,n-1)=binomn2 caixas distintas, cada caixa não vazia, vale
S(30,29)=binom302=30cdot 292=435
onde são os números de Stirling de 2. E sabe-se que
Aqui , então

e multiplicamos por .

Resposta

boxed435cdot 29!

Exercícios relacionados