En el contexto de las matemáticas combinatorias , las estrellas y barras (también llamadas "palos y piedras" [1] y "bolas y barras" [2] ) son una ayuda gráfica para derivar ciertos teoremas combinatorios . Fue popularizado por William Feller en su libro clásico sobre probabilidad . Se puede usar para resolver muchos problemas simples de conteo , como cuántas formas hay de poner n bolas indistinguibles en k contenedores distinguibles. [3]
Declaraciones de teoremas
El método de estrellas y barras a menudo se introduce específicamente para probar los dos teoremas siguientes de combinatoria elemental sobre 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 subconjuntos de ( k - 1) elementos de un conjunto con n - 1 elementos.
Por ejemplo, si y , el teorema da el número de soluciones a:
con
La respuesta viene dada por el coeficiente binomial . Para el ejemplo anterior, hay de ellos.
Estos consisten en las permutaciones de las tuplas .
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 multijuegos de cardinalidad k - 1 tomados de un conjunto de tamaño n + 1.
Por ejemplo, si y , el teorema da el número de soluciones a:
con
La respuesta viene dada por el coeficiente binomial . Para el ejemplo anterior, hay de ellos.
Pruebas mediante el método de estrellas y barras.
Teorema uno
Suponga que hay n objetos (representados aquí por estrellas) para colocar en k contenedores, de modo que todos los contenedores contienen 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 está representada por una k -tupla de enteros positivos, como en el enunciado del teorema.
Por ejemplo, con n = 7 y k = 3, comience colocando las estrellas en una línea:
La configuración se determinará una vez que se sepa cuál es la primera estrella que va al segundo bin, y la primera estrella al tercer bin, 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:
★ ★ ★ ★ | | | ★ | | | ★ ★ |
Hay n - 1 espacios entre las estrellas. Se obtiene una configuración eligiendo k - 1 de estos espacios para contener una barra; por lo tanto hayposibles combinaciones .
Teorema dos
En este caso, la restricción debilitada de la no negatividad en lugar de la positividad significa que podemos colocar múltiples barras entre las 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:
★ ★ ★ ★ | | | | | ★ | | | ★ ★ | | |
Ver que estos objetos se cuentan por el coeficiente binomial , observe que los arreglos deseados consisten en n + k - 1 objetos ( n estrellas y k - 1 barras).
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 es no negativa.
Por ejemplo:
con
es equivalente a:
con
Ejemplos de
Ejemplo 1
Muchos problemas de palabras elementales en combinatoria se resuelven mediante los teoremas anteriores. Por ejemplo, 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 una de ellas reciba al menos un dólar, se puede observar que las distribuciones son esencialmente equivalentes a tuplas de tres monedas positivas. enteros cuya suma es 7. (Aquí la primera entrada en la tupla es el número de monedas dadas a Ámbar, y así sucesivamente.) Por lo tanto, se aplica el teorema 1 de barras y estrellas, con n = 7 y k = 3, y hay formas de distribuir las monedas.
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 de 4 (1, 3, 0, 1). La representación de cualquier multiset para este ejemplo debe usar SAB2 con n = 5 estrellas y k - 1 = 3 barras para dar.
Ejemplo 3
SAB2 permite más barras que estrellas, lo que no está permitido en SAB1.
Así por ejemplo, bolas en contenedores es , tiempo bolas en contenedores es , con bolas en contenedores como
Ejemplo 4
Si tenemos la serie infinita de Taylor , entonces podemos usar este método para expandir la suma. Para el enésimo término de la expansión, estamos eligiendo n potencias de x de m ubicaciones separadas. Por lo tanto hay formas de formar nuestro enésimo poder:
Ejemplo 5
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, como una derivación simple de la expresión de Max Planck de "complexiones". [4]
Planck llamó "complexiones" al número R de posibles distribuciones de elementos de energía P ε sobre N resonadores: [5]
La representación gráfica contendría P multiplicado por el símbolo " ε " y ( N - 1) multiplicado por el signo "|" para cada posible distribución. En su demostración, Ehrenfest y Kamerlingh Onnes tomaron N = 4 y P = 7 ( es decir , R = 120 combinaciones). Eligieron la tupla de 4 (4, 2, 0, 1) como ejemplo ilustrativo de esta representación simbólica: εεεε | εε || ε
Ver también
Referencias
- ^ Batterson, J. Competencia de matemáticas para la escuela secundaria . Arte de resolver problemas.
- ^ Flajolet, Philippe; Sedgewick, Robert (26 de junio de 2009). Combinatoria analítica . Prensa de la Universidad de Cambridge. ISBN 978-0-521-89806-5.
- ^ Feller, William (1950). Introducción a la teoría de la probabilidad y sus aplicaciones . 1 (2ª ed.). Wiley.
- ^ Ehrenfest, Paul; Kamerlingh Onnes, Heike (1915). "Deducción simplificada de la fórmula de la teoría de combinaciones que Planck utiliza como base de su teoría de la radiación" . The London, Edinburgh y Dublin Philosophical Magazine y 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. doi : 10.1002 / y p.19013090310 . Consultado el 5 de diciembre de 2020 .
Otras lecturas
- 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 .