Estrellas y barras (combinatoria)

En combinatoria , el diagrama de estrellas y barras (también llamado de palos y piedras , ^{[ 1 ]} bolas y barras , ^{[ 2 ]} y puntos y divisores ^{[ 3 ]} ) es una ayuda gráfica para derivar ciertos teoremas combinatorios . Se puede utilizar para resolver diversos problemas de conteo , como cuántas maneras hay de colocar $n$ bolas indistinguibles en $k$ contenedores distinguibles. ^{[ 4 ]} La solución a este problema en particular viene dada por el coeficiente binomial. ${\tbinom {n+k-1}{k-1}}$ , que es el número de subconjuntos de tamaño $k - 1$ que se pueden formar a partir de un conjunto de tamaño $n + k - 1$ .

Si, por ejemplo, hay dos bolas y tres recipientes, entonces el número de maneras de colocar las bolas es ${\tbinom {2+3-1}{3-1}}={\tbinom {4}{2}}=6$ La tabla muestra las seis formas posibles de distribuir las dos bolas, las cadenas de estrellas y barras que las representan (donde las estrellas indican las bolas y las barras separan los contenedores entre sí), y los subconjuntos que corresponden a las cadenas. Como se necesitan dos barras para separar tres contenedores y hay dos bolas, cada cadena contiene dos barras y dos estrellas. Cada subconjunto indica cuál de los cuatro símbolos de la cadena correspondiente es una barra.

Enunciados de teoremas

El método de las estrellas y las barras se introduce a menudo específicamente para demostrar los dos teoremas siguientes de combinatoria elemental relativos al 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 subconjuntos de $(k - 1) elementos de un conjunto con$ $n - 1$ elementos.

Por ejemplo, si $n = 10$ y $k = 4$ , el teorema proporciona el número de soluciones de $x 1 + x 2 + x 3 + x 4 = 10$ (con $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,

dónde ${\tbinom {n-1}{k-1}}$ es el número de combinaciones de $n - 1$ elementos tomados de $k - 1$ en k − 1.

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 tamaño $k - 1$ tomados de un conjunto de tamaño $n + 1$ , o equivalentemente, el número de multiconjuntos de tamaño $n$ tomados de un conjunto de tamaño $k$ , y viene dado por

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

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

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

donde el coeficiente del multiconjunto $\left(\!\!{\binom {k}{n}}\!\!\right)$ es el número de multiconjuntos de tamaño $n$ , con elementos tomados de un conjunto de tamaño $k$ .

Esto corresponde a composiciones débiles de un entero. Con $k$ fijo, los números para $n = 0, 1, 2, 3, ...$ son aquellos en la $(k - 1)$ -ésima diagonal del triángulo de Pascal . Por ejemplo, cuando $k = 3,$ el $n$ -ésimo número es el $(n + 1)$ -ésimo número triangular , que cae en la segunda diagonal, 1, 3, 6, 10, ....

Pruebas mediante el método de estrellas y barras

Demostración del primer teorema

El problema de enumerar k -tuplas cuya suma es n es equivalente al problema de contar configuraciones del siguiente tipo: supongamos que hay n objetos que se colocan en k contenedores, de modo que todos los contenedores contengan al menos un objeto. Los contenedores están distinguidos (digamos que están numerados del 1 al k ), pero los n objetos no lo están (por lo que las configuraciones solo se distinguen por la cantidad de objetos presentes en cada contenedor). Una configuración se representa, por lo tanto, mediante una k -tupla de enteros positivos.

Los n objetos ahora se representan como una fila de n estrellas; los contenedores adyacentes están separados por barras. La configuración se especificará indicando el límite entre el primer y el segundo contenedor, el límite entre el segundo y el tercer contenedor, y así sucesivamente. Por lo tanto, se deben colocar $k - 1$ barras entre las estrellas. Como ningún contenedor puede estar vacío, hay como máximo una barra entre cualquier par de estrellas. Hay $n - 1$ espacios entre las estrellas y, por lo tanto, $n - 1$ posiciones en las que se puede colocar una barra. Se obtiene una configuración eligiendo $k - 1$ de estos espacios para contener una barra; por lo tanto, hay ${\tbinom {n-1}{k-1}}$ configuraciones.

Ejemplo

Con $n = 7$ y $k = 3$ , comienza colocando siete estrellas en línea:

★ ★ ★ ★ ★ ★ ★

Figura 1: Siete objetos, representados por estrellas

Ahora indique los límites entre los contenedores:

★ ★ ★ ★ | ★ | ★ ★

Figura 2: Estas dos barras dan lugar a tres contenedores que contienen 4, 1 y 2 objetos.

En general, se deben elegir dos de las seis posiciones posibles de la barra. Por lo tanto, hay ${\tbinom {6}{2}}=15$ tales configuraciones.

Demostración del segundo teorema

En este caso, la restricción debilitada de no negatividad en lugar de positividad implica que podemos colocar varias barras entre las estrellas y que también se pueden colocar una o más barras antes de la primera estrella y después de la última. En cuanto a las configuraciones que involucran objetos y contenedores, ahora se permite que los contenedores estén vacíos.

En lugar de un $(k - 1)$ -conjunto de posiciones de barra tomadas de un conjunto de tamaño $n - 1$ como en la demostración del Teorema uno, ahora tenemos un $(k - 1)$ -multiconjunto de posiciones de barra tomadas de un conjunto de tamaño $n + 1$ (ya que las posiciones de barra pueden repetirse y ya que los extremos ahora son posiciones de barra permitidas). Una interpretación alternativa en términos de multiconjuntos es la siguiente: hay un conjunto de $k$ etiquetas de contenedor del cual se debe elegir un multiconjunto de tamaño $n$ , la multiplicidad de una etiqueta de contenedor en este multiconjunto indica el número de objetos colocados en ese contenedor. La igualdad $\left(\!\!{n+1 \choose k-1}\!\!\right)=\left(\!\!{k \choose n}\!\!\right)$ También puede entenderse como una equivalencia de diferentes problemas de conteo: el número de $k-$ tuplas de enteros no negativos cuya suma es $n$ es igual al número de $(n + 1)$ -tuplas de enteros no negativos cuya suma es $k - 1$ , lo cual se obtiene intercambiando los roles de las barras y las estrellas en los diagramas que representan configuraciones.

Para ver la expresión ${\tbinom {n+k-1}{k-1}}$ Observamos directamente que cualquier disposición de estrellas y barras consta de un total de $n + k - 1$ símbolos, de los cuales $n son estrellas y$ $k - 1$ son barras. Por lo tanto, podemos colocar $n + k - 1$ espacios y elegir $k - 1$ de ellos para que contengan barras (o, equivalentemente, elegir n de los espacios para que contengan estrellas).

Ejemplo

Cuando $n = 7$ y $k = 5$ , la tupla (4, 0, 1, 2, 0) puede representarse mediante el siguiente diagrama:

★ ★ ★ ★ | | ★ | ★ ★ |

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

Si las posibles posiciones de las barras se etiquetan como 1, 2, 3, 4, 5, 6, 7, 8, donde la etiqueta $i \leq 7$ corresponde a una barra que precede a la $i$ -ésima estrella y sigue a cualquier estrella anterior, y 8 a una barra que sigue a la última estrella, entonces esta configuración corresponde al $(k - 1)$ -multiconjunto ${5,5,6,8}$ , como se describe en la demostración del segundo teorema. Si los contenedores se etiquetan como 1, 2, 3, 4, 5, entonces también corresponde al $n-$ multiconjunto ${1,1,1,1,3,4,4}$ , también como se describe en la demostración del segundo teorema.

Relación entre los teoremas uno y dos

El teorema uno se puede reformular en términos del teorema dos, porque el requisito de que cada variable sea positiva se puede imponer desplazando cada variable en −1 y luego exigiendo solo que cada variable sea no 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,$

dónde $x'_{i}=x_{i}-1$ para cada $i\in \{1,2,3,4\}$ .

Otros ejemplos

{\displaystyle {\tbinom {3}{2}}.} — Se distribuyen cuatro galletas entre Tom, Dick y Harry ( **TDH** ) de tal manera que cada uno recibe al menos una. 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 galletas se indican con circunflejos rojos ( **^ ^ ^** ). Con tres personas, necesitamos dos símbolos de barra ( **| |** ) para ocupar dos cualesquiera de los tres espacios. Por lo tanto, el problema se reduce a encontrar el coeficiente binomial. ${\tbinom {3}{2}}.$ También se muestran las tres composiciones 3 correspondientes de 4 .

Ejemplo 1

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

Ejemplo 2

Si $n = 5$ , $k = 4$ y las $k$ etiquetas de los bins son $a, b, c, d$ , entonces ★|★★★||★ podría representar la cuádrupla ( $1, 3, 0, 1)$ , o el multiconjunto de posiciones de barra ${2, 5, 5}$ , o el multiconjunto de etiquetas de bin ${a, b, b, b, d}$ . La solución de este problema debería usar el Teorema 2 con $n = 5$ estrellas y $k - 1 = 3$ barras para dar ${\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56$ configuraciones.

Ejemplo 3

En la demostración del segundo teorema puede haber más barras que estrellas, lo cual no puede ocurrir en la demostración del primer teorema.

Por lo tanto, por ejemplo, 10 bolas en 7 contenedores dan como resultado ${\tbinom {16}{6}}$ configuraciones, mientras que 7 bolas en 10 contenedores da ${\tbinom {16}{9}}$ configuraciones, y 6 bolas en 11 contenedores da ${\tbinom {16}{10}}={\tbinom {16}{6}}$ configuraciones.

Ejemplo 4

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

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

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 cuádrupla (4, 2, 0, 1) como ejemplo ilustrativo para esta representación simbólica: εεεε0εε00ε .

Relación con las funciones generadoras

Las enumeraciones de los teoremas uno y dos también se pueden encontrar utilizando funciones generadoras que involucran expresiones racionales simples. Los dos casos son muy similares; veremos el caso cuando $x_{i}\geq 0$ , es decir, primero el segundo teorema. Solo hay una configuración para un solo contenedor y cualquier número dado de objetos (porque los objetos no se distinguen). Esto está representado por la función generadora.

1+1x+1x^{2}+1x^{3}+\ldots =1+x+x^{2}+x^{3}+\ldots ={\frac {1}{1-x}}.

La serie es geométrica, y la última igualdad se cumple analíticamente para $| x | < 1$ , pero se entiende mejor en este contexto como una manipulación de series de potencias formales . El exponente de $x$ indica cuántos objetos se colocan en el contenedor.

Cada contenedor adicional está representado por otro factor de ${\frac {1}{1-x}}$ ; la función generadora para $k$ intervalos es

\underbrace {{\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}} _{k{\text{ factors}}}={\frac {1}{(1-x)^{k}}}

,

donde la multiplicación es el producto de Cauchy de series de potencias formales.

Para hallar el número de configuraciones con $n$ objetos, queremos el coeficiente de $x^{n}$ (denotado anteponiendo a la expresión de la función generadora $[x^{n}]$ ), eso es,

[x^{n}]{\frac {1}{(1-x)^{k}}}=[x^{n}](1-x)^{-k}

.

Este coeficiente se puede encontrar utilizando series binomiales y coincide con el resultado del segundo teorema, a saber: ${\tbinom {n+k-1}{k-1}}$ .

Esta expresión del producto de Cauchy se justifica mediante estrellas y barras: el coeficiente de $x^{n}$ en la expansión del producto

\underbrace {(1+x+x^{2}+\ldots )(1+x+x^{2}+\ldots )\ldots (1+x+x^{2}+\ldots )} _{k{\text{ factors}}}

es el número de maneras de obtener la $enésima$ potencia de $x$ multiplicando una potencia de $x$ de cada uno de los $k$ factores. Así, las estrellas representan $las x$ y una barra separa las $x$ que provienen de un factor de las que provienen del siguiente.

Para el caso en que $x_{i}>0$ , es decir, Teorema uno, ninguna configuración tiene un contenedor vacío, y por lo tanto la función generadora para un solo contenedor es

x+x^{2}+x^{3}+\ldots ={\frac {x}{1-x}}

.

Por lo tanto, el producto de Cauchy es ${\frac {x^{k}}{(1-x)^{k}}}$ y el coeficiente de $x^{n}$ se encuentra utilizando series binomiales que es ${\tbinom {n-1}{k-1}}$ .

Véase también

Referencias

↑ Batterson, J. Matemáticas competitivas para la escuela secundaria . El arte de resolver problemas.
↑ Flajolet, Philippe; Sedgewick, Robert (26 de junio de 2009). Combinatoria analítica . Cambridge University Press. ISBN 978-0-521-89806-5.
↑ "El arte de resolver problemas" . artofproblemsolving.com . Consultado el 26 de octubre de 2021 .
↑ Feller, William (1968). Introducción a la teoría de la probabilidad y sus aplicaciones . Vol. 1 (3.ª ed.). Wiley. pág. 38.
↑ 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 de la KNAW . 17 : 870–873 . Consultado el 16 de mayo de 2024 .
↑ 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» . The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science . Serie 6. 29 (170): 297–301 . doi : 10.1080/14786440208635308 . Consultado el 5 de diciembre de 2020 .
^ Planck, Max (1901). "Ueber das Gesetz der Energieverteilung im Normalspectrum" . Annalen der Physik . 309 (3): 553– 563. Bibcode : 1901AnP...309..553P . doi : 10.1002/andp.19013090310 .
↑ Gearhart, C. (2002). "Planck, el cuanto y los historiadores" (PDF) . Phys. Perspect . 4 (2): 170– 215. Bibcode : 2002PhP.....4..170G . doi : 10.1007/s00016-002-8363-7 . Consultado el 16 de mayo de 2024 .

Lecturas adicionales

Pitman, Jim (1993). Probabilidad . Berlín: Springer-Verlag. ISBN 0-387-97974-3.
Weisstein, Eric W. "Multichoose" . Mathworld -- Un recurso web de Wolfram . Consultado el 18 de noviembre de 2012 .

[1] Batterson, J. Matemáticas competitivas para la escuela secundaria . El arte de resolver problemas.

[2] Flajolet, Philippe; Sedgewick, Robert (26 de junio de 2009). Combinatoria analítica . Cambridge University Press. ISBN 978-0-521-89806-5.

[:0-3] "El arte de resolver problemas" . artofproblemsolving.com . Consultado el 26 de octubre de 2021 .

[4] Feller, William (1968). Introducción a la teoría de la probabilidad y sus aplicaciones . Vol. 1 (3.ª ed.). Wiley. pág. 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 de la 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» . The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science . 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. Bibcode : 1901AnP...309..553P . doi : 10.1002/andp.19013090310 .

[8] Gearhart, C. (2002). "Planck, el cuanto y los historiadores" (PDF) . Phys. Perspect . 4 (2): 170– 215. Bibcode : 2002PhP.....4..170G . doi : 10.1007/s00016-002-8363-7 . Consultado el 16 de mayo de 2024 .

[ 1 ]

[ 2 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]