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 Plantilla:Mvar bolas indistinguibles en Plantilla:Mvar 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 Plantilla:Mvar y Plantilla:Mvar, el número de Plantilla:Mvar-tuplas de enteros positivos cuya suma es Plantilla:Mvar es igual al número de subconjuntos de Plantilla:Math elementos de un conjunto con Plantilla:Math elementos.

Por ejemplo, si Plantilla:Math y Plantilla:Math, 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

$(\genfrac{}{}{0ex}{}{n-1}{k-1})=(\genfrac{}{}{0ex}{}{10-1}{4-1})=(\genfrac{}{}{0ex}{}{9}{3})=84.$

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

Segundo teorema

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

Por ejemplo, si Plantilla:Math y Plantilla:Math, 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\ge 0$) como:

$\left((\genfrac{}{}{0ex}{}{k}{n})\right)=(\genfrac{}{}{0ex}{}{k+n-1}{n})=(\genfrac{}{}{0ex}{}{13}{10})=286$

$\left((\genfrac{}{}{0ex}{}{n+1}{k-1})\right)=(\genfrac{}{}{0ex}{}{n+1+k-1-1}{k-1})=(\genfrac{}{}{0ex}{}{13}{3})=286$

$(\genfrac{}{}{0ex}{}{n+k-1}{k-1})=(\genfrac{}{}{0ex}{}{10+4-1}{4-1})=(\genfrac{}{}{0ex}{}{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 Plantilla:Math y Plantilla:Math, 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 Plantilla:Math 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 Plantilla:Math espacios entre estrellas. Se obtiene una configuración eligiendo Plantilla:Math 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 $(\genfrac{}{}{0ex}{}{n-1}{k-1})$ posibles combinaciones. $◻$

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 Plantilla:Math y Plantilla:Math, 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 $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$ posibilidades, observemos que cualquier disposición de estrellas y barras consta de un total de Plantilla:Math objetos, n de los cuales son estrellas y Plantilla:Math de los cuales son barras. Por lo tanto, solo necesitamos elegir Plantilla:Math de las Plantilla:Math 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). $◻$

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\ge 0$

Demostración por funciones generadoras

Ambos casos son muy similares, veremos el caso cuando $x_i\ge 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 Plantilla:Mvar 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 Plantilla:Mvar 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

$(\genfrac{}{}{0ex}{}{m+k-1}{k-1})$

Para el caso cuando $x_i>0$, necesitamos agregar Plantilla:Mvar 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

$(\genfrac{}{}{0ex}{}{m-1}{k-1})$.

Bibliografía

• Plantilla:Cita libro
• Plantilla:Cita web