Prove que o número de soluções inteiras não negativas da equação x1+x2++xk=n é igual a binomn+k-1k-1.

Passo 1

Beleza, o enunciado quer que a gente prove que o número de soluções inteiras não negativas da equação
x1 + x2 + cdots + xk = n
é
binomn + k - 1k - 1
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 “ star ,star ,lvert ,star ,lvert ,star ,star ” 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 binomn + k - 1k - 1 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 .

Resposta

boxedbinomn + k - 1k - 1

Exercícios relacionados