- Quantas são as soluções inteiras e não-negativas de
?
Passo 1
O enunciado pergunta: “Quantas são as soluções inteiras e não-negativas de
?”.
Informações dadas e objetivo claros: procuramos todas as tuplas com
tais que a soma seja menor ou igual a
. Não há restrição extra (como ordem, limites individuais etc.).
Informações dadas e objetivo claros: procuramos todas as tuplas
Passo 2
Vamos transformar a desigualdade em uma igualdade introduzindo uma variável “folga” (às vezes chamada de variável slack). Defina uma nova variável
por
Como
e
, temos
inteiro. Portanto as soluções de interesse correspondem exatamente às soluções inteiras e não-negativas da equação
com
.
Passo 3
Agora o problema é clássico: contar o número de soluções inteiras e não-negativas de uma soma de
variáveis igual a
. Vou explicar a ferramenta que usamos para isso (a famosa técnica “estrelas e barras”).
Passo 4
Ensinando “estrelas e barras” (intuição e prova curta): pense que você tem
unidades idênticas (representadas por
estrelas) que serão distribuídas em
caixas (cada caixa corresponde a uma variável
). Uma maneira de codificar uma distribuição é escrever as
estrelas em linha e colocar
barras entre elas para separar as quatro caixas. Por exemplo,
significa
,
,
,
. Toda distribuição corresponde a uma escolha de posições das
barras entre as
estrelas e nos extremos possíveis, e toda escolha distinta de posições de barras dá uma distribuição distinta. Então o problema se reduz a contar o número de maneiras de intercalar
estrelas e
barras em uma sequência — ou seja, escolher as posições das
barras entre as
espaços totais.
Formalizando: número de soluções não-negativas de
é
Aqui
é o número de variáveis (caixas) e
é o total de estrelas. A fórmula vem exatamente do argumento “escolher as posições das
barras entre
posições”.
Passo 5
Aplicando a fórmula ao nosso caso: temos
variáveis (
) e
. Portanto o número de soluções é
Passo 6
Calculemos
. Pela definição de coeficiente binomial,
Para calcular sem expandir todos os fatoriais, podemos simplificar:
Logo há
soluções.
Passo 7
(Aqui uma verificação alternativa rápida, só para fixar a ideia.) Outra maneira seria somar, para cada
, o número de soluções de
. Para cada
há
soluções, e a soma
pela identidade do “Hockey-stick” dá
. Portanto confirma o resultado.
Resposta
84