Questão 22 (PROFMAT-MA12-AV2/2013). Penélope quer distribuir 6 presentes entre seus sobrinhos Alfredo, Bruno, Carlos e Daniel, de modo que cada um receba pelo menos um presente. Todos os presentes devem ser distribuídos.
Resolva novamente o item a), supondo agora que todos os presentes sejam diferentes.

Passo 1

O que o enunciado pede e o que foi dado (dados extraídos do enunciado):
  • Existe um conjunto de 6 presentes.
  • Agora todos os presentes são diferentes (cada presente é distinto).
  • Há quatro sobrinhos distintos: Alfredo, Bruno, Carlos e Daniel.
  • Cada sobrinho deve receber pelo menos um presente (nenhum pode ficar sem presente).
  • Todos os presentes devem ser distribuídos.
    Pergunta: de quantas maneiras distintas isso pode ser feito?

Passo 2

Modelagem do problema (ideia básica que usamos para contar):
  • Como os presentes são diferentes e os sobrinhos são distintos, uma distribuição corresponde a atribuir a cada presente um destinatário (um dos quatro sobrinhos).
  • Assim, cada distribuição é uma função do conjunto dos 6 presentes para o conjunto dos 4 sobrinhos.
  • Se não houvesse a restrição “cada sobrinho recebe pelo menos um”, o número total de atribuições seria simplesmente 4^{6}, porque cada um dos 6 presentes tem 4 opções de destinatário independentemente.

Passo 3

Tratamento da restrição “cada sobrinho recebe pelo menos um” (princípio da inclusão-exclusão):
  • Queremos contar apenas as funções que são sobrejetivas (onto): todas as quatro imagens aparecem.
  • Pelo princípio da inclusão-exclusão, o número de funções de um conjunto de 6 elementos para um conjunto de 4 elementos que atingem todos os 4 elementos é
\sum_{k=0}^{4} (-1)^{k}\binom{4}{k}(4-k)^{6}.
Explicação das partes dessa fórmula:
  • \binom{4}{k} é o número de escolhas de k sobrinhos “proibidos” (aqueles que não recebem nenhum presente).
  • (4-k)^{6} é o número de funções que usam apenas os 4-k sobrinhos restantes (ou seja, funções que evitam exatamente aquele conjunto escolhido de k sobrinhos).
  • O sinal alternado (-1)^k vem da inclusão-exclusão para corrigir sobrecontagens.

Passo 4

Aplicando a fórmula termo a termo e calculando os valores:
  • Para k=0: \binom{4}{0}(4-0)^{6}=1\cdot4^{6}. Calculando, 4^{6}=4096.
  • Para k=1: \binom{4}{1}(4-1)^{6}=4\cdot3^{6}. Calculando, 3^{6}=729\quad\Rightarrow\quad 4\cdot3^{6}=4\cdot729=2916.
  • Para k=2: \binom{4}{2}(4-2)^{6}=6\cdot2^{6}. Calculando, 2^{6}=64\quad\Rightarrow\quad 6\cdot64=384.
  • Para k=3: \binom{4}{3}(4-3)^{6}=4\cdot1^{6}. Calculando, 1^{6}=1\quad\Rightarrow\quad 4\cdot1=4.
  • Para k=4: \binom{4}{4}(4-4)^{6}=1\cdot0^{6}=0 (não contribui).
Agora somando com os sinais alternados:
4^{6}-\binom{4}{1}3^{6}+\binom{4}{2}2^{6}-\binom{4}{3}1^{6} =4096-2916+384-4.
Fazendo as contas em ordem:
4096-2916=1180,
1180+384=1564,
1564-4=1560.

Passo 5

Método alternativo (verificação e entendimento extra): usar números de Stirling de segunda espécie.
  • O número de maneiras de particionar 6 objetos distintos em 4 caixas não rotuladas (cada caixa não vazia) é o número de Stirling \,S(6,4)\,.
  • Depois de particionar em 4 blocos não rotulados, rotula-se cada bloco com um sobrinho: há 4! maneiras de rotular. Logo o total é S(6,4)\cdot 4!.
  • Podemos calcular \,S(6,4)\, pela recorrência \,S(n,k)=kS(n-1,k)+S(n-1,k-1)\,. Construindo a tabela (resumida):
    • S(1,1)=1.
    • S(2,1)=1,\;S(2,2)=1.
    • S(3,2)=3,\;S(3,3)=1.
    • S(4,2)=7,\;S(4,3)=6,\;S(4,4)=1.
    • S(5,2)=15,\;S(5,3)=25,\;S(5,4)=10,\;S(5,5)=1.
    • Aplicando a recorrência para n=6: S(6,4)=4\cdot S(5,4)+S(5,3)=4\cdot10+25=65.
  • Então o número de distribuições é
S(6,4)\cdot 4! = 65\cdot 24.
Calculando, 65\cdot 24 = 1560, que confirma o resultado obtido por inclusão-exclusão.

Resposta

1560

Exercícios relacionados