En la teoría de números y la combinatoria enumerativa , los números de Bell ordenados o los números de Fubini cuentan el número de ordenamientos débiles en un conjunto de n elementos (ordenamientos de los elementos en una secuencia que permite lazos , como los que podrían surgir como resultado de una carrera de caballos ). [1] A partir de n = 0, estos números son
Los números de Bell ordenados se pueden calcular mediante una fórmula de suma que incluya coeficientes binomiales o mediante una relación de recurrencia . Junto con los ordenamientos débiles, cuentan varios otros tipos de objetos combinatorios que tienen una correspondencia biyectiva con los ordenamientos débiles, como las particiones multiplicativas ordenadas de un número sin cuadrados [2] o las caras de todas las dimensiones de un permutoedro [3] ( por ejemplo, la suma de caras de todas las dimensiones en el octaedro truncado es 1 + 14 + 36 + 24 = 75 [4] ).
Historia
Los números ordenados de Bell aparecen en la obra de Cayley (1859) , quien los utilizó para contar ciertos plátanos con n + 1 hojas totalmente ordenadas. En los árboles considerados por Cayley, cada camino de raíz a hoja tiene la misma longitud, y el número de nodos a la distancia i de la raíz debe ser estrictamente menor que el número de nodos a la distancia i + 1, hasta llegar a las hojas. [5] En tal árbol, hay n pares de hojas adyacentes, que pueden estar débilmente ordenadas por la altura de su antepasado común más bajo ; este orden débil determina el árbol. Mor y Fraenkel (1984) llaman a los árboles de este tipo "árboles de Cayley", y llaman a las secuencias que pueden usarse para etiquetar sus huecos (secuencias de n enteros positivos que incluyen al menos una copia de cada entero positivo entre uno y el valor máximo en la secuencia) "Permutaciones de Cayley". [6]
Pippenger (2010) rastrea el problema de contar ordenamientos débiles, que tiene la misma secuencia que su solución, al trabajo de Whitworth (1886) . [7] [8]
Estos números fueron llamados números de Fubini por Louis Comtet, porque cuentan el número de formas diferentes de reorganizar el orden de las sumas o integrales en el teorema de Fubini , que a su vez lleva el nombre de Guido Fubini . [9] Por ejemplo, para una integral bivariada, el teorema de Fubini establece que
donde estas tres formulaciones corresponden a los tres ordenamientos débiles en dos elementos. En general, en una integral multivariante, el orden en el que las variables pueden agruparse en una secuencia de integrales anidadas forma un orden débil.
Los números de Bell , que llevan el nombre de Eric Temple Bell , cuentan el número de particiones de un conjunto , y los ordenamientos débiles contados por los números de Bell ordenados pueden interpretarse como una partición junto con un orden total en los conjuntos de la partición. [10]
Fórmula
El n- ésimo número ordenado de Bell puede estar dado por una fórmula de suma que incluya los números de Stirling del segundo tipo , que cuentan el número de particiones de un conjunto de n elementos en k subconjuntos no vacíos, [11] [12] expandidos en un doble suma que involucra coeficientes binomiales (usando una fórmula que expresa números de Stirling como una suma de coeficientes binomiales), o dada por una serie infinita : [7] [10]
Una fórmula de suma alternativa expresa los números de Bell ordenados en términos de los números eulerianos , que cuentan el número de permutaciones de n elementos con k + 1 corridas de elementos crecientes: [13]
donde A n es el n- ésimo polinomio euleriano.
La función de generación exponencial de los números Bell ordenados es [7] [10] [12] [14]
Esto se puede expresar de manera equivalente como el hecho de que los números de Bell ordenados son los números en la primera columna de la matriz infinita (2 I - P ) −1 , donde I es la matriz identidad y P es una forma de matriz infinita del triángulo de Pascal . [15] Basado en una integración de contorno de esta función generadora, los números de Bell ordenados se pueden expresar mediante la suma infinita [2] [16]
y aproximado como [2] [12] [17] [18] [16]
Debido a que log 2 es menor que uno, la forma de esta aproximación muestra que los números de Bell ordenados exceden los factoriales correspondientes en un factor exponencial. La convergencia asintótica de esta aproximación puede expresarse como
Recurrencia y periodicidad modular
Además de las fórmulas anteriores, los números de Bell ordenados se pueden calcular mediante la relación de recurrencia [7] [17]
El significado intuitivo de esta fórmula es que un orden débil en n elementos puede dividirse en una selección de algún conjunto no vacío de i elementos que entran en la primera clase de equivalencia del orden, junto con un orden débil más pequeño en los n restantes - i artículos. Como caso base para la recurrencia, a (0) = 1 (hay un orden débil en cero elementos). Con base en esta recurrencia, se puede demostrar que estos números obedecen a ciertos patrones periódicos en aritmética modular : para n suficientemente grande ,
- [17]
- y
- [19]
Good (1975) y Poonen (1988) dan varias identidades modulares adicionales . [11] [20]
Aplicaciones adicionales
Como ya se ha mencionado, los números de Bell ordenados cuentan ordenaciones débiles, caras de permutoedros , árboles de Cayley, permutaciones de Cayley, particiones multiplicativas ordenadas de números libres de cuadrados y fórmulas equivalentes en el teorema de Fubini. Los pedidos débiles, a su vez, tienen muchas otras aplicaciones. Por ejemplo, en las carreras de caballos , los acabados fotográficos han eliminado la mayoría, pero no todos los empates, llamados en este contexto eliminatorias , y se puede describir el resultado de una carrera que puede contener empates (incluidos todos los caballos, no solo los primeros tres finalistas). usando un orden débil. Por esta razón, los números Bell ordenados cuentan el número posible de resultados de una carrera de caballos, [1] o los posibles resultados de una elección de candidatos múltiples . [21] Por el contrario, cuando los elementos se ordenan o clasifican de una manera que no permite empates (como ocurre con el orden de las cartas en una baraja de cartas u órdenes de bateo entre los jugadores de béisbol ), el número de pedidos de n elementos es un número factorial n !, [22] que es significativamente menor que el correspondiente número ordenado de Bell. [23]
Kemeny (1956) usa los números de Bell ordenados para describir la "complejidad" de una relación n -aria , por lo que se refiere al número de otras relaciones que se pueden formar a partir de ella permutando y repitiendo sus argumentos (disminuyendo la aridad con cada repetición). . [24] En esta aplicación, para cada relación derivada, los argumentos de la relación original están débilmente ordenados por las posiciones de los argumentos correspondientes de la relación derivada.
Velleman & Call (1995) consideran las cerraduras de combinación con un teclado numérico, en las que se pueden presionar varias teclas simultáneamente y una combinación consiste en una secuencia de pulsaciones de teclas que incluye cada tecla exactamente una vez. Como muestran, el número de combinaciones diferentes en tal sistema viene dado por los números de Bell ordenados. [13]
Ellison y Klein (2001) señalan una aplicación de estos números a la teoría de la optimalidad en lingüística . En esta teoría, las gramáticas para los lenguajes naturales se construyen clasificando ciertas restricciones y (en un fenómeno llamado tipología factorial) el número de gramáticas diferentes que se pueden formar de esta manera se limita al número de permutaciones de las restricciones. Un artículo revisado por Ellison y Klein sugirió una extensión de este modelo lingüístico en el que se permiten los lazos entre las restricciones, de modo que la clasificación de las restricciones se convierte en un orden débil en lugar de un orden total. Como señalan, la magnitud mucho mayor de los números de Bell ordenados, en relación con los factoriales correspondientes , permite que esta teoría genere un conjunto de gramáticas mucho más rico. [23]
Referencias
- ↑ a b de Koninck, JM (2009), Esos fascinantes números , American Mathematical Society, p. 4, ISBN 9780821886311. Debido a esta aplicación, de Koninck llama a estos números "números de caballo", pero este nombre no parece ser de uso generalizado.
- ^ a b c Sklar, Abe (1952), "On the factorization of squarefree integers", Proceedings of the American Mathematical Society , 3 : 701–705, doi : 10.1090 / S0002-9939-1952-0050620-1 , JSTOR 2032169 , MR 0050620.
- ^ Ziegler, Günter M. (1995), Conferencias sobre politopos , Textos de posgrado en matemáticas, 152 , Springer, p. 18.
- ^ 1, 14, 36, 24 es la cuarta fila de este triángulo (secuencia A019538 en la OEIS )
- ^ Cayley, A. (1859), "Sobre las formas analíticas llamadas árboles, segunda parte", Revista filosófica , Serie IV, 18 (121): 374–378, doi : 10.1017 / CBO9780511703706.026. En Obras completas de Arthur Cayley , pág. 113 .
- ^ Mor, M .; Fraenkel, AS (1984), "Permutaciones de Cayley", Matemáticas discretas , 48 (1): 101-112, doi : 10.1016 / 0012-365X (84) 90136-5 , MR 0732206.
- ^ a b c d Pippenger, Nicholas (2010), "El hipercubo de resistencias, expansiones asintóticas y arreglos preferenciales", Revista de matemáticas , 83 (5): 331–346, arXiv : 0904.1757 , doi : 10.4169 / 002557010X529752 , MR 2762645.
- ^ Whitworth, WA (1886), Elección y oportunidad , Deighton: Bell and Co., Proposición XXII, p. 93. Como lo cita Pippenger (2010) .
- ^ Comtet, Louis (1974), Combinatoria avanzada: El arte de las expansiones finitas e infinitas (PDF) (edición revisada y ampliada), D. Reidel Publishing Co., p. 228, Archivado desde el original (PDF) en 07/04/2014 , recuperado 12/03/2013.
- ^ a b c Knopfmacher, A .; Mays, ME (2005), "A survey of factorization count functions", International Journal of Number Theory , 1 (4): 563–581, doi : 10.1142 / S1793042105000315 , MR 2196796.
- ^ a b Bueno, IJ (1975), "El número de ordenaciones de n candidatos cuando se permiten empates" (PDF) , Fibonacci Quarterly , 13 : 11-18, MR 0376367.
- ^ a b c Sprugnoli, Renzo (1994), "Arreglos de Riordan y sumas combinatorias", Matemáticas discretas , 132 (1-3): 267-290, doi : 10.1016 / 0012-365X (92) 00570-H , hdl : 10338.dmlcz / 143149 , MR 1297386.
- ^ a b Velleman, Daniel J .; Call, Gregory S. (1995), "Permutaciones y candados de combinación", Mathematics Magazine , 68 (4): 243–253, doi : 10.2307 / 2690567 , MR 1363707.
- ^ Getu, Seyoum; Shapiro, Louis W .; Woan, Wen Jin; Woodson, Leon C. (1992), "Cómo adivinar una función generadora", SIAM Journal on Discrete Mathematics , 5 (4): 497–499, doi : 10.1137 / 0405040 , MR 1186818.
- ^ Lewis, Barry (2010), "Revisiting the Pascal matrix", American Mathematical Monthly , 117 (1): 50–66, doi : 10.4169 / 000298910X474989 , MR 2599467.
- ^ a b Bailey, Ralph W. (1998), "El número de ordenamientos débiles de un conjunto finito", Social Choice and Welfare , 15 (4): 559–562, doi : 10.1007 / s003550050123 , MR 1647055.
- ^ a b c Gross, OA (1962), "Arreglos preferenciales", The American Mathematical Monthly , 69 : 4–8, doi : 10.2307 / 2312725 , MR 0130837.
- ^ Barthélémy, J.-P. (1980), "Un equivalente asintótico del número total de pedidos por adelantado en un conjunto finito", Discrete Mathematics , 29 (3): 311–313, doi : 10.1016 / 0012-365X (80) 90159-4 , MR 0560774.
- ^ Kauffman, Dolores H. (1963), "Nota sobre acuerdos preferenciales", The American Mathematical Monthly , 70 : 62, doi : 10.2307 / 2312790 , MR 0144827.
- ^ Poonen, Bjorn (1988), "Periodicidad de una secuencia combinatoria", Fibonacci Quarterly , 26 (1): 70–76, MR 0931425.
- ^ Petković, Miodrag (2009), Famosos rompecabezas de grandes matemáticos , American Mathematical Society, p. 194, ISBN 9780821886304.
- ^ Harris, John; Hirst, Jeffry L .; Mossinghoff, Michael J. (2008), Combinatoria y teoría de grafos , Textos de pregrado en matemáticas (2ª ed.), Springer, p. 132, ISBN 9780387797106.
- ^ a b Ellison, T. Mark; Klein, Ewan (2001), "Review: The Best of All Possible Words (revisión de la teoría de la optimización: una descripción general , Archangeli, Diana & Langendoen, D. Terence, eds., Blackwell, 1997)", Journal of Linguistics , 37 ( 1): 127–143, JSTOR 4176645.
- ^ Kemeny, John G. (1956), "Dos medidas de complejidad", The Journal of Philosophy , 52 (24): 722–733, JSTOR 2022697.