Stars and bars

"Stars and bars" é uma técnica matemática para resolver certos problemas combinatórios. Isso ocorre sempre que você deseja contar o número de maneiras de agrupar objetos idênticos.

Teorema

O número de maneiras de colocar $n$ objetos idênticos em $k$ caixas rotuladas é $$\binom{n + k - 1}{n}.$$

A prova envolve transformar os objetos em estrelas e separar as caixas usando barras (portanto, o nome, pode ser em bolinhas, estrelas, qualquer maneira, como resolver um problema de combinatória). Por exemplo, podemos representar com $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$ a seguinte situação: na primeira caixa há um objeto, na segunda caixa há dois objetos, a terceira está vazio e na última caixa há dois objetos. Essa é uma maneira de dividir 5 objetos em 4 caixas.

Todas as partições podem ser representadas usando $n$ estrelas e $k - 1$ barras e cada permutação (usando $n$ estrelas e $k - 1$ barras) representa uma partição. Portanto, o número de maneiras de dividir $n$ objetos idênticos em $k$ caixas é o mesmo número para o qual existem permutações de $n$ estrelas e $k - 1$ barras. O coeficiente binomial nos fornece a fórmula desejada.

Número de somas inteiras não negativas

Este problema é uma aplicação direta do teorema.

Você precisa contar o número de soluções da equação $$x_1 + x_2 + \dots + x_k = n$$ com $x_i \ge 0$.

Novamente, podemos representar uma solução usando estrelas e barras. Por exemplo, a solução $1 + 3 + 0 = 4$ for $n = 4$, $k = 3$ pode ser representada usando $\bigstar | \bigstar \bigstar \bigstar |$.

Esse é exatamente o teorema das estrelas e das barras. Portanto, a solução será $\binom{n + k - 1}{n}$.

Número de somas inteiras de limite inferior

Isso pode ser facilmente estendido para somas inteiras com diferentes limites inferiores. Ou seja, queremos contar o número de soluções para a equação $$x_1 + x_2 + \dots + x_k = n$$ com $x_i \ge a_i$.

Após substituir $x_i' := x_i - a_i$ recebemos a equação modificada $$(x_1' + a_i) + (x_2' + a_i) + \dots + (x_k' + a_k) = n$$ $$\Leftrightarrow ~ ~ x_1' + x_2' + \dots + x_k' = n - a_1 - a_2 - \dots - a_k$$ com $x_i' \ge 0$. Portanto, reduzimos o problema para o caso mais simples com $x_i' \ge 0$ e, novamente, podemos aplicar o teorema/método das estrelas e barras.