Estrellas y barras

Estrellas y barras (stars and bars) es una técnica matemática para resolver ciertos problemas combinatorios. Aparece siempre que se quiere contar el número de formas de agrupar objetos idénticos.

Teorema

El número de formas de poner $n$ objetos idénticos en $k$ cajas etiquetadas es

$$\binom{n + k - 1}{n}.$$

La demostración consiste en convertir los objetos en estrellas y separar las cajas usando barras (de ahí el nombre). P. ej. podemos representar con $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$ la siguiente situación: en la primera caja hay un objeto, en la segunda hay dos objetos, la tercera está vacía y en la última hay dos objetos. Esta es una forma de dividir 5 objetos en 4 cajas.

Debería ser bastante obvio que toda partición se puede representar usando $n$ estrellas y $k - 1$ barras y que toda permutación de estrellas y barras con $n$ estrellas y $k - 1$ barras representa una partición. Por lo tanto, el número de formas de dividir $n$ objetos idénticos en $k$ cajas etiquetadas es el mismo que el número de permutaciones de $n$ estrellas y $k - 1$ barras. El coeficiente binomial nos da la fórmula deseada.

Número de sumas de enteros no negativos

Este problema es una aplicación directa del teorema.

Se quiere contar el número de soluciones de la ecuación

$$x_1 + x_2 + \dots + x_k = n$$

con $x_i \ge 0$.

De nuevo podemos representar una solución usando estrellas y barras. P. ej. la solución $1 + 3 + 0 = 4$ para $n = 4$, $k = 3$ se puede representar usando $\bigstar | \bigstar \bigstar \bigstar |$.

Es fácil ver que esto es exactamente el teorema de estrellas y barras. Por lo tanto la solución es $\binom{n + k - 1}{n}$.

Número de sumas de enteros positivos

Un segundo teorema da una interpretación conveniente para enteros positivos. Consideremos las soluciones de

$$x_1 + x_2 + \dots + x_k = n$$

con $x_i \ge 1$.

Podemos considerar $n$ estrellas, pero esta vez podemos poner a lo sumo una barra entre estrellas, porque dos barras entre estrellas representarían $x_i=0$, es decir, una caja vacía. Hay $n-1$ huecos entre estrellas para colocar $k-1$ barras, así que la solución es $\binom{n-1}{k-1}$.

Número de sumas de enteros con cota inferior

Esto se puede extender fácilmente a sumas de enteros con distintas cotas inferiores. Es decir, queremos contar el número de soluciones de la ecuación

$$x_1 + x_2 + \dots + x_k = n$$

con $x_i \ge a_i$.

Tras sustituir $x_i’ := x_i - a_i$ obtenemos la ecuación 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$$

con $x_i’ \ge 0$. Así reducimos el problema al caso más simple con $x_i’ \ge 0$ y de nuevo podemos aplicar el teorema de estrellas y barras.

Número de sumas de enteros con cota superior

Con ayuda del principio de inclusión-exclusión también se pueden restringir los enteros con cotas superiores. Véase la sección Número de sumas de enteros con cota superior en el artículo correspondiente.

Problemas de práctica

• Codeforces - Array 
• Codeforces - Kyoya and Coloured Balls 
• Codeforces - Colorful Bricks 
• Codeforces - Two Arrays 
• Codeforces - One-Dimensional Puzzle