Estrellas y barras (combinatoria)

Ayuda gráfica para derivar algunos conceptos en combinatoria.

En el contexto de las matemáticas combinatorias , estrellas y barras (también llamadas "palos y piedras", ^[1] "bolas y barras", ^[2] y "puntos y divisores" ^[3] ) son una ayuda gráfica para derivar ciertos teoremas combinatorios . . Se puede utilizar para resolver muchos problemas de conteo simples , como cuántas formas hay de colocar n bolas indistinguibles en k contenedores distinguibles. ^[4]

Los teoremas uno y dos son los coeficientes utilizados para 2 rangos de soporte diferentes en la distribución de probabilidad binomial negativa.

Declaraciones de teoremas

El método de las estrellas y las barras 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.

Teorema uno

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 ( k − 1) subconjuntos de 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 ₁ + x ₂ + x ₃ + x ₄ = 10 (con x ₁ , x ₂ , x ₃ , x ₄ > 0 ) como el coeficiente binomial

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

Esto corresponde a composiciones de un número entero.

Teorema dos

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 ₁ + x ₂ + x ₃ + x ₄ = 10 (con x ₁ , x ₂ , x ₃ , x ₄ ${\displaystyle \geq 0}$ ) como:

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

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

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

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

Pruebas mediante el método de estrellas y barras.

Prueba del teorema uno

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 del 1 al 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.

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 se determinará una vez que se sepa cuál es la primera estrella que va al segundo contenedor, y la primera estrella que va al tercer contenedor, etc. Esto se indica colocando k − 1 barras entre las estrellas. 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: Estas dos barras dan lugar a tres contenedores que contienen 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; por lo tanto hay posibles combinaciones . ${\displaystyle {\tbinom {n-1}{k-1}}}$

Teorema dos prueba

En este caso, la restricción debilitada de la no negatividad en lugar de la positividad significa que podemos colocar múltiples barras entre estrellas, antes de la primera estrella y después de la última estrella.

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

★ ★ ★ ★ | | ★ | ★ ★ |

Fig. 3: Estas cuatro barras dan lugar a cinco contenedores que contienen 4, 0, 1, 2 y 0 objetos.

Para ver que hay posibles arreglos, observe que cualquier arreglo de estrellas y barras consta de un total de n + k − 1 objetos, n de los cuales son estrellas y k − 1 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). ${\displaystyle {\tbinom {n+k-1}{k-1}}}$

El teorema 1 ahora se puede reformular en términos del teorema 2, 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:

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

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

es equivalente a:

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

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

Pruebas generando funciones.

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

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

Esto también se puede escribir como

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

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

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

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

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

${\displaystyle [x^{n}]:{\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 es ${\displaystyle x^{n}}$

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

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

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

y el coeficiente de es ${\displaystyle x^{n}}$

${\displaystyle {\binom {n-1}{k-1}}}$

Ejemplos

Muchos problemas planteados elementales en combinatoria se resuelven mediante los teoremas anteriores.

Se distribuyen cuatro galletas entre Tom, Dick y Harry ( TDH ) de tal manera que cada uno recibe al menos una galleta. Las 4 galletas se representan tradicionalmente como estrellas ( **** ). Pero aquí se muestran como círculos del color de las galletas ( ●●●● ). Los 3 espacios entre las cookies se indican con signos de intercalación rojos ( ^ ^ ^ ). Con tres personas, necesitamos 2 símbolos de barra ( | | ) para ocupar dos de los tres espacios. Por lo tanto, el problema se reduce a encontrar el coeficiente binomial. También se muestran las tres composiciones 3 correspondientes de 4 . ${\displaystyle {\tbinom {3}{2}}.}$

La combinación de tres opciones y dos produce dos resultados, dependiendo de si se permite que un contenedor tenga cero artículos. En ambos casos, el número de contenedores es 3. Si no se permite cero, el número de cookies es n = 6 , como se describe en la figura anterior. Si se permite cero, el número de cookies es solo n = 3 .

Ejemplo 1

Si se desea contar el número de formas de distribuir siete monedas de un dólar indistinguibles entre Amber, Ben y Curtis de modo que cada uno de ellos reciba al menos un dólar, se puede observar que las distribuciones son esencialmente equivalentes a tuplas de tres números enteros positivos cuya suma es 7. (Aquí la primera entrada en la tupla es el número de monedas dadas a Amber, y así sucesivamente). Por lo tanto, se aplica el teorema 1 de estrellas y barras, con n = 7 y k = 3 , y hay formas de distribuir las monedas. . ${\displaystyle {\tbinom {7-1}{3-1}}=15}$

Ejemplo 2

Si n = 5 , k = 4 y un conjunto de tamaño k es {a, b, c, d}, entonces ★|★★★||★ podría representar el conjunto múltiple {a, b, b, b, d } o la tupla 4 (1, 3, 0, 1). La representación de cualquier conjunto múltiple para este ejemplo debe usar SAB2 con n = 5 , k – 1 = 3 barras para dar . ${\displaystyle {\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56}$

Ejemplo 3

SAB2 permite más barras que estrellas, lo que no está permitido en SAB1.

Entonces, por ejemplo, 10 bolas en 7 contenedores es , mientras que 7 bolas en 10 contenedores es , con 6 bolas en 11 contenedores como ${\displaystyle {\tbinom {16}{6}}}$ ${\displaystyle {\tbinom {16}{9}}}$ ${\displaystyle {\tbinom {16}{10}}={\tbinom {16}{6}}.}$

Ejemplo 4

Si tenemos la serie de potencias infinitas

${\displaystyle \left[\sum _{k=1}^{\infty }x^{k}\right],}$

Podemos usar este método para calcular el producto de Cauchy de m copias de la serie. Para el n.ésimo término de la expansión, estamos seleccionando n potencias de x de m ubicaciones separadas. Por tanto, hay formas de formar nuestra enésima potencia: ${\displaystyle {\tbinom {n-1}{m-1}}}$

${\displaystyle \left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}}$

Ejemplo 5

El método gráfico fue utilizado por Paul Ehrenfest y Heike Kamerlingh Onnes —con el símbolo ε (elemento energético cuántico) en lugar de una estrella y el símbolo 0 en lugar de una barra— como una simple derivación de la expresión de Max Planck para el número de "tez" para un sistema de "resonadores" de una sola frecuencia. ^{[5] [6]}

Por complexiones ( microestados ), Planck se refería a distribuciones de P elementos energéticos ε sobre N resonadores. ^{[7] [8]} El número R de complexiones es

${\displaystyle R={\frac {(N+P-1)!}{P!(N-1)!}}.\ }$

La representación gráfica de cada distribución posible contendría P copias del símbolo ε y N – 1 copias del símbolo 0 . En su demostración, Ehrenfest y Kamerlingh Onnes tomaron N = 4 y P = 7 ( es decir , R = 120 combinaciones). Eligieron la 4-tupla (4, 2, 0, 1) como ejemplo ilustrativo de esta representación simbólica: εεεε0εε00ε .

Ver también

• Coeficiente binomial gaussiano
• Partición (teoría de números)
• Doce caminos
• Distribución multinomial de Dirichlet

Referencias

1. Batterson, J. Competencia de matemáticas para la escuela secundaria . Arte de resolver problemas.
2. Flajolet, Philippe; Sedgewick, Robert (26 de junio de 2009). Combinatoria Analítica . Prensa de la Universidad de Cambridge. ISBN 978-0-521-89806-5.
3. "El arte de resolver problemas". artofproblemsolving.com . Consultado el 26 de octubre de 2021 .
4. Feller, William (1968). Una introducción a la teoría de la probabilidad y sus aplicaciones . vol. 1 (3ª ed.). Wiley. pag. 38.
5. Ehrenfest, Paul; Kamerlingh Onnes, Heike (1914). "Deducción simplificada de la fórmula a partir de la teoría de combinaciones que Planck utiliza como base de su teoría de la radiación". Actas del KNAW . 17 : 870–873 . Consultado el 16 de mayo de 2024 .
6. Ehrenfest, Paul; Kamerlingh Onnes, Heike (1915). "Deducción simplificada de la fórmula a partir de la teoría de combinaciones que Planck utiliza como base de su teoría de la radiación". Revista filosófica y revista científica de Londres, Edimburgo y Dublín . Serie 6. 29 (170): 297–301. doi : 10.1080/14786440208635308 . Consultado el 5 de diciembre de 2020 .
7. Planck, Max (1901). "Ueber das Gesetz der Energieverteilung im Normalspectrum". Annalen der Physik . 309 (3): 553–563. Código bibliográfico : 1901AnP...309..553P. doi : 10.1002/andp.19013090310 .
8. Gearhart, C. (2002). "Planck, lo cuántico y los historiadores" (PDF) . Física. Perspectiva . 4 (2): 170–215. Código Bib : 2002PhP.....4..170G. doi :10.1007/s00016-002-8363-7 . Consultado el 16 de mayo de 2024 .

Otras lecturas

• Pitman, Jim (1993). Probabilidad . Berlín: Springer-Verlag. ISBN 0-387-97974-3.
• Weisstein, Eric W. "Elección múltiple". Mathworld: un recurso web de Wolfram . Consultado el 18 de noviembre de 2012 .