Barras y estrellas (combinatoria)

En combinatoria, el diagrama de barras y estrellas es una ayuda gráfica para derivar ciertos teoremas combinatorios. Fue popularizado por William Feller en su clásico libro sobre probabilidad. Se puede utilizar para resolver muchos problemas de conteo simples, como cuántas formas hay de colocar n bolas indistinguibles en k contenedores distinguibles.​

Enunciados de teoremas

El método de las barras y las estrellas a menudo se introduce específicamente para demostrar los siguientes dos teoremas de combinatoria elemental relacionados con el número de soluciones de una ecuación.

Primer teorema

Para cualquier par de enteros positivos n y k, el número de k-tuplas de enteros positivos cuya suma es n es igual al número de subconjuntos de k − 1 elementos de un conjunto con n − 1 elementos.

Por ejemplo, si n = 10 y k = 4, el teorema da el número de soluciones de $x_{1}+x_{2}+x_{3}+x_{4}=10$ (con enteros $x_{1},x_{2},x_{3},x_{4}>0$) como el coeficiente binomial

${\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84.$

Esto corresponde al número de composiciones de un número entero.

Segundo teorema

Para cualquier par de enteros positivos n y k, el número de k-tuplas de enteros no negativos cuya suma es n es igual al número de multiconjuntos de cardinalidad n tomados de un conjunto de tamaño k, o equivalentemente, el número de multiconjuntos de cardinalidad k − 1 tomado de un conjunto de tamaño n + 1 .

Por ejemplo, si n = 10 y k = 4, el teorema da el número de soluciones de $x_{1}+x_{2}+x_{3}+x_{4}=10$ (con enteros $x_{1},x_{2},x_{3},x_{4}\geq 0$) como:

$\left(\!\!{k \choose n}\!\!\right)={k+n-1 \choose n}={\binom {13}{10}}=286$

$\left(\!\!{n+1 \choose k-1}\!\!\right)={n+1+k-1-1 \choose k-1}={\binom {13}{3}}=286$

${\binom {n+k-1}{k-1}}={\binom {10+4-1}{4-1}}={\binom {13}{3}}=286$

Esto corresponde al número de composiciones débiles de un número entero.

Demostraciones mediante el método de estrellas y barras

Demostración del primer teorema

Supongamos que hay n objetos (representados aquí por estrellas) que se colocarán en k contenedores, de modo que todos los contenedores contengan al menos un objeto. Los contenedores son distinguibles (digamos que están numerados de 1 a k), pero las n estrellas no lo son (por lo que las configuraciones solo se distinguen por el número de estrellas presentes en cada contenedor). Por tanto, una configuración se representa mediante una k-tupla de enteros positivos, como en el enunciado del teorema (el número de elementos de cada contenedor

Por ejemplo, con n = 7 y k = 3, comienza colocando las estrellas en una línea:

★  ★  ★  ★  ★  ★  ★

Fig. 1: Siete objetos, representados por estrellas

La configuración quedará determinada una vez que se sepa cuál es la primera estrella que va al segundo contenedor, cuál es la primera estrella que va al tercer contenedor, etc. Esto se indica colocando k − 1 barras entre las estrellas (separadores entre contenedores). Debido a que no se permite que ningún contenedor esté vacío (todas las variables son positivas), hay como máximo una barra entre cualquier par de estrellas.

Por ejemplo:

★  ★  ★  ★ | ★ | ★  ★

Fig. 2: Las dos barras dan lugar a tres contenedores con, respectivamente, 4, 1 y 2 objetos.

Hay n − 1 espacios entre estrellas. Se obtiene una configuración eligiendo k − 1 de estos espacios para contener una barra. El número de formas de elegir $k-1$ espacios de entre un total de $n-1$ es el número de subconjuntos de $k-1$ elementos de uno de $n-1$. Por lo tanto, por definición, hay ${\tbinom {n-1}{k-1}}$ posibles combinaciones. $\quad \square$

Demostración del segundo teorema

En este caso, se debilitan las restricciones: se pide la no negatividad en lugar de la positividad. Esto significa, utilizando las barras y estrellas anteriores, que podemos colocar múltiples barras entre estrellas, antes de la primera estrella y después de la última estrella (permitimos contenedores vacíos).

Por ejemplo, cuando n = 7 y k = 5, la 5-tupla (4, 0, 1, 2, 0) se puede representar mediante el siguiente diagrama:

★  ★  ★  ★ | | ★ | ★  ★ |

Fig. 3: Cuatro barras dan lugar a cinco contenedores con 4, 0, 1, 2 y 0 objetos, respectivamente.

Para ver que hay ${\tbinom {n+k-1}{k-1}}$ posibilidades, observemos que cualquier disposición de estrellas y barras consta de un total de n + k − 1 objetos, n de los cuales son estrellas y k − 1 de los cuales son barras. Por lo tanto, solo necesitamos elegir k − 1 de las n + k − 1 posiciones para que sean barras (o, de manera equivalente, elegir n de las posiciones para que sean estrellas), pues el resto quedarán determinadas a ser estrellas (o, equivalentemente, barras). $\quad \square$

El primer teorema se puede ahora reformular en términos del segundo, porque el requisito de que todas las variables sean positivas equivale a asignar previamente a cada variable un 1 y preguntar el número de soluciones cuando cada variable no es negativa.

Por ejemplo:

$x_{1}+x_{2}+x_{3}+x_{4}=10$

con $x_{1},x_{2},x_{3},x_{4}>0$

es equivalente a:

$x_{1}+x_{2}+x_{3}+x_{4}=6$

con $x_{1},x_{2},x_{3},x_{4}\geq 0$

Demostración por funciones generadoras

Ambos casos son muy similares, veremos el caso cuando $x_{i}\geq 0$ primero. El 'contenedor' se convierte

${\frac {1}{1-x}}$

Esto también se puede escribir como

$1+x+x^{2}+\dots$

y el exponente de x nos dice cuántas bolas se colocan en el cubo.

Cada cubo adicional está representado por otro ${\frac {1}{1-x}}$, por lo que la función generadora final es

${\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}={\frac {1}{(1-x)^{k}}}$

Como sólo tenemos m bolas, queremos el coeficiente de $x^{m}$ (escrito $[x^{m}]:$ )

$[x^{m}]:{\frac {1}{(1-x)^{k}}}$

Esta es una función generadora muy conocida: genera las diagonales en el Triángulo de Pascal y el coeficiente de $x^{m}$ es

${\binom {m+k-1}{k-1}}$

Para el caso cuando $x_{i}>0$, necesitamos agregar x al numerador para indicar que hay al menos una bola en el cubo.

${\frac {x}{1-x}}{\frac {x}{1-x}}\dots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}$

y el coeficiente de $x^{m}$ es

${\binom {m-1}{k-1}}$.

Bibliografía

• Pitman, Jim (1993). Probability. Berlin: Springer-Verlag. ISBN 0-387-97974-3. 
• Weisstein, Eric W. «Multichoose». Mathworld -- A Wolfram Web Resource. Consultado el 18 de noviembre de 2012.