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.
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
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
presentes para o conjunto dos sobrinhos. - Se não houvesse a restrição “cada sobrinho recebe pelo menos um”, o número total de atribuições seria simplesmente
, porque cada um dos presentes tem 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
elementos para um conjunto de elementos que atingem todos os elementos é
Explicação das partes dessa fórmula:
-
é o número de escolhas de sobrinhos “proibidos” (aqueles que não recebem nenhum presente). -
é o número de funções que usam apenas os sobrinhos restantes (ou seja, funções que evitam exatamente aquele conjunto escolhido de sobrinhos). - O sinal alternado
vem da inclusão-exclusão para corrigir sobrecontagens.
Passo 4
Aplicando a fórmula termo a termo e calculando os valores:
- Para
: . Calculando, - Para
: . Calculando, - Para
: . Calculando, - Para
: . Calculando, - Para
: (não contribui).
Agora somando com os sinais alternados:
Fazendo as contas em ordem:
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
objetos distintos em caixas não rotuladas (cada caixa não vazia) é o número de Stirling . - Depois de particionar em
blocos não rotulados, rotula-se cada bloco com um sobrinho: há maneiras de rotular. Logo o total é . - Podemos calcular
pela recorrência . Construindo a tabela (resumida): -
. -
. -
. -
. -
. - Aplicando a recorrência para
:
-
- Então o número de distribuições é
Calculando,
, que confirma o resultado obtido por inclusão-exclusão.
Resposta
1560