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.
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
Sem restrição, cada um dos 30 brinquedos pode ir para qualquer uma das 29 crianças, dando no total
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 é
Número de distribuições em que cada criança recebe ≥1 brinquedo é
onde em cada termo tiramos
Passo 4
Felizmente, existe uma fórmula mais simples nesse caso: o número de maneiras de distribuir
objetos distintos em
caixas distintas, cada caixa não vazia, vale
onde
Aqui
, então
e multiplicamos por