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.
[1] 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.
Por ejemplo, si n = 10 y k = 4, el teorema da el número de soluciones de
) como el coeficiente binomial Esto corresponde al número de composiciones de un número entero.
Por ejemplo, si n = 10 y k = 4, el teorema da el número de soluciones de
) como: Esto corresponde al número de composiciones débiles de un número entero.
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:
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.
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.
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:
3: Cuatro barras dan lugar a cinco contenedores con 4, 0, 1, 2 y 0 objetos, respectivamente.
Para ver que hay
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).
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.
El 'contenedor' se convierte Esto también se puede escribir como y el exponente de x nos dice cuántas bolas se colocan en el cubo.
Cada cubo adicional está representado por otro
, por lo que la función generadora final es Como sólo tenemos m bolas, queremos el coeficiente de
) Esta es una función generadora muy conocida: genera las diagonales en el Triángulo de Pascal y el coeficiente de
, necesitamos agregar x al numerador para indicar que hay al menos una bola en el cubo.