De quantas maneiras podemos distribuir 8 objetos idênticos em 3 caixas distintas, de modo que nenhuma fique vazia?
Passo 1
O enunciado dá as seguintes informações:
- Há
objetos idênticos. - Há
caixas distintas. - Nenhuma caixa pode ficar vazia.
O que é pedido:
- Contar de quantas maneiras distintas podemos distribuir os
objetos nas caixas, obedecendo a condição de que nenhuma caixa fique vazia.
Passo 2
Modelagem do problema com variáveis (isso deixa tudo claro matematicamente).
- Seja
o número de objetos na caixa 1, o número de objetos na caixa 2 e o número de objetos na caixa 3. - Cada
deve ser um inteiro positivo (porque nenhuma caixa pode ficar vazia), ou seja, para . - A soma deve ser a quantidade total de objetos:
Agora o problema é contar o número de soluções inteiras positivas dessa equação.
Passo 3
Transformação para facilitar a contagem (tirar 1 de cada caixa para garantir positividade):
- Defina
para . Assim cada é um inteiro não negativo, . - Substituindo na soma, obtemos
ou seja
Portanto, contar soluções positivas
é equivalente a contar soluções não negativas
da equação acima.
Passo 4
Explicação didática da fórmula padrão (a famosa ideia “stars and bars”):
- Queremos contar o número de soluções inteiras não negativas da soma
com
.
- Pense em
estrelas alinhadas: . Para dividir essas estrelas em caixas distintas precisamos colocar separadores (barras) entre as estrelas (ou nas extremidades) para formar três blocos (alguns blocos podem ter zero estrelas). - Visualmente, qualquer arranjo de
estrelas e barras em sequência corresponde a uma solução distinta. O total de símbolos é , e basta escolher as posições das barras entre essas posições. - O número de maneiras de escolher as posições das barras é o número de combinações de
posições tomadas a , isto é
- Em geral, para somar
estrelas em caixas não-negativas, o número é . Aqui e .
Passo 5
Aplicação numérica e cálculo final:
- Usando a fórmula com
e ,
- Calcule
:
Portanto há
distribuições possíveis.