Prove que o número de soluções inteiras não negativas da equação
é igual a
.
Passo 1
Beleza, o enunciado quer que a gente prove que o número de soluções inteiras não negativas da equação
é
Isso cai na matéria de contagem/combinatória, mais especificamente no famoso “método das estrelas e barras”. Vamos usar esse método para transformar o problema em escolher posições em uma sequência.
Passo 2
Primeiro, pensa que você tem
bolinhas idênticas (essas bolinhas são as “unidades” que somam até
) e
caixinhas onde colocar essas bolinhas (cada caixinha representa uma variável
). Como as bolinhas são idênticas e as caixinhas são diferentes, cada jeitinho de distribuir as
bolinhas nas
caixinhas corresponde a uma solução
. Por exemplo, se
e
, a distribuição
significa que na caixinha 1 tem 2 bolinhas, na 2 tem 1, na 3 tem 2 (2+1+2=5).
Passo 3
Agora vem o truque das “estrelas e barras”. A gente vai desenhar uma sequência de símbolos onde cada bolinha é uma estrela “
” e a transição de uma caixinha para outra é uma barra “
”.
- Como temos
bolinhas, teremos estrelas. - Como temos
caixinhas, precisamos de barras para separar as partes.
Por exemplo, para
,
, a seqüência
significa “2 estrelas antes da primeira barra” (ou seja
), “1 estrela entre as barras” (
), e “2 estrelas depois da segunda barra” (
).
Passo 4
Qual é o número de sequências formadas por
estrelas e
barras? No total são
posições, e a gente só precisa escolher quais
delas serão barras (o resto automaticamente vira estrelas). O número de maneiras de escolher
posições entre
é justamente o coeficiente binomial
Essa é a contagem de todas as possíveis distribuições, ou seja, de todas as soluções não negativas de
.