En matemáticas y especialmente en combinatoria , una partición plana es una matriz bidimensional de enteros no negativos.(con índices enteros positivos i y j ) que no aumenta en ambos índices. Esto significa que
- y para todo i y j.
Además, sólo un número finito de los son distintos de cero. Las particiones planas se pueden representar visualmente mediante la colocación de una pila de cubos unitarios por encima del punto ( i , j ) en el plano, dando un sólido tridimensional como se muestra en la imagen.
La suma de una partición plana es
La suma describe el número de cubos que componen la partición plana. El número de particiones planas con suma n se denota PL ( n ).
Por ejemplo, hay seis particiones planas con suma 3:
entonces PL (3) = 6. (Aquí las particiones planas se dibujan usando la indexación matricial para las coordenadas y las entradas iguales a 0 se suprimen para facilitar la lectura).ser el número total de particiones planas en las que r es el número de filas que no son iguales a cero, s es el número de columnas que no son cero y t es el número entero más grande de la matriz. Las particiones planas se describen a menudo por las posiciones de los cubos unitarios . Por lo tanto, una partición plana se define como un subconjunto finitode puntos reticulares enteros positivos ( i , j , k ) en, tal que si ( r , s , t ) se encuentra eny si ( i , j , k ) satisface, y , entonces ( i , j , k ) también se encuentra en.
Función generadora de particiones planas
Como resultado de Percy A. MacMahon , la función generadora de PL ( n ) está dada por
Esto a veces se denomina función MacMahon .
Esta fórmula puede verse como el análogo bidimensional de la fórmula del producto de Euler para el número de particiones enteras de n . No se conoce una fórmula análoga para particiones en dimensiones más altas (es decir, para particiones sólidas ). [2] La asintótica de las particiones planas fue desarrollada por EM Wright . [3] Se obtiene, para grandes, que [un]
Evaluar numéricamente los rendimientos
Alrededor de 1896, Percy A. MacMahon estableció la función de generación de particiones planas que son subconjuntos deen su primer artículo sobre tabiques planos. [5] La fórmula viene dada por
Una prueba de esta fórmula se puede encontrar en el libro Análisis combinatorio escrito por Percy A. MacMahon. [6] Percy A. MacMahon también menciona en su libro Análisis combinatorio las funciones generadoras de particiones planas en el artículo 429. [7] La fórmula para la función generadora se puede escribir de una manera alternativa, que viene dada por
Establecer q = 1 en las fórmulas anteriores produce
Percy A. MacMahon obtuvo que el número total de particiones planas en es dado por . [8] El caso plano (cuando t = 1) produce los coeficientes binomiales :
Diagramas de Ferrers para tabiques planos
Otra representación de las particiones planas tiene la forma de diagramas de Ferrers . El diagrama de Ferrers de una partición plana de es una colección de puntos o nodos ,, con satisfaciendo la condición: [9]
- Condición FD: Si el nodo , entonces también lo hacen todos los nodos con para todos .
Reemplazar cada nodo de una partición plana por un cubo unitario con bordes alineados con los ejes conduce a la representación de la pila de cubos para la partición plana.
Equivalencia de las dos representaciones
Dado un diagrama de Ferrers, se construye la partición plana (como en la definición principal) de la siguiente manera.
- Dejar ser el número de nodos en el diagrama de Ferrers con coordenadas de la forma dónde denota un valor arbitrario. La colección formar una partición plana. Se puede verificar que la condición FD implica que se satisfacen las condiciones para una partición plana.
Dado un conjunto de que forman una partición plana, se obtiene el diagrama de Ferrers correspondiente de la siguiente manera.
- Comience con el diagrama de Ferrers sin nodos. Por cada distinto de cero , agregar nodos de la forma por al diagrama de Ferrers. Por construcción, es fácil ver que se cumple la condición FD.
Por ejemplo, a continuación se muestran las dos representaciones de un plano con particiones de 5.
Arriba, todos los nodos del diagrama de Ferrers están escritos como una columna y solo hemos escrito los que no desaparecen como es convencional.
Acción de S 2 , S 3 y C 3 en tabiques planos
es el grupo de permutaciones que actúa sobre las dos primeras coordenadas de ( i, j, k ). Este grupo contiene la identidad ( i, j, k ) y la transposición ( i, j, k ) → ( j, i, k ). El número de elementos en una órbita. se denota por ||. denota el conjunto de órbitas de elementos de bajo la acción de . La altura de un elemento ( i, j, k ) está definida por
La altura aumenta en uno por cada paso que se aleja de la esquina trasera derecha. Por ejemplo, la posición de la esquina ( 1,1,1 ) tiene una altura 1 y ht (2,1,1) = 2 . HT () es la altura de una órbita, que es la altura de cualquier elemento en la órbita. Esta notación de la altura difiere de la notación de Ian G. Macdonald . [10]
Hay una acción natural del grupo de permutación. en un diagrama de Ferrers, esto corresponde a permutar simultáneamente las tres coordenadas de todos los nodos. Esto generaliza la operación de conjugación para particiones. La acción depuede generar nuevas particiones de plano a partir de una partición de plano determinada. A continuación se muestran seis particiones planas de 4 que son generadas por elacción. Solo el intercambio de las dos primeras coordenadas se manifiesta en la representación que se da a continuación.
se llama el grupo de permutaciones cíclicas y consta de
Particiones planas simétricas
Una partición plana se llama simétrico si π i , j = π j, i para todo i, j . En otras palabras, una partición plana es simétrica si ( i, j, k )si y solo si ( j, i, k ). Las particiones planas de este tipo son simétricas con respecto al plano x = y . A continuación se da un ejemplo de una partición plana simétrica. Adjunta se visualiza la matriz.
En 1898, Percy A. MacMahon formuló su conjetura sobre la función generadora de particiones planas simétricas que son subconjuntos de. [11] Esta conjetura se llama La conjetura de MacMahon. La función generadora está dada por
Ian G. Macdonald [10] señaló que la conjetura de Percy A. MacMahon se reduce a
En 1972 Edward A. Bender y Donald E. Knuth [12] conjeturaron una forma cerrada simple para la función generadora de la partición plana que tiene como máximo r filas y una disminución estricta a lo largo de las filas. George Andrews [13] mostró que la conjetura de Edward A. Bender y Donald E. Knuth y la conjetura de MacMahon son equivalentes. La conjetura de MacMahon fue probada casi simultáneamente por George Andrews en 1977 [14] y más tarde Ian G. Macdonald presentó una prueba alternativa [10] [ejemplo 16-19, págs. 83-86]. Cuando se establece q = 1 se obtiene la función de conteo que es dado por
Para una prueba del caso q = 1, consulte la conjetura de MacMahon en el artículo de George Andrews sobre las particiones planas simétricas . [15]
Particiones planas cíclicamente simétricas
π se llama cíclicamente simétrico, si la i -ésima fila dese conjuga a la i -ésima columna para todo i . La i -ésima fila se considera una partición ordinaria. El conjugado de una partición es la partición cuyo diagrama es la transposición de la partición . [10] En otras palabras, la partición plana es cíclicamente simétrica si siempre que ( i, j, k )entonces ( k, i, j ) y ( j, k, i ) también están en. A continuación se muestra un ejemplo de una partición plana cíclicamente simétrica y su visualización.
La conjetura de Ian G. Macdonald proporciona una fórmula para calcular el número de particiones planas cíclicamente simétricas para un entero r dado . Esta conjetura se llama La conjetura de Macdonald . La función generadora para particiones planas cíclicamente simétricas que son subconjuntos de es dado por
Esta ecuación también se puede escribir de otra manera
En 1979, George Andrews ha probado la conjetura de Macdonald para el caso q = 1 como la conjetura "débil" de Macdonald . [16] Tres años después, William. H. Mills, David Robbins y Howard Rumsey demostraron el caso general de la conjetura de Macdonald en su artículo Prueba de la conjetura de Macdonald . [17] La fórmula paraviene dada por la conjetura "débil" de Macdonald
Particiones planas totalmente simétricas
Una partición plana totalmente simétrica es una partición plana que es simétrica y cíclicamente simétrica. Esto significa que el diagrama es simétrico en los tres planos diagonales. Entonces, por lo tanto, si ( i, j, k )entonces las seis permutaciones de ( i, j, k ) también están en. A continuación se da un ejemplo de una matriz para una partición plana totalmente simétrica. La imagen muestra la visualización de la matriz.
Ian G. Macdonald encontró el número total de particiones planas totalmente simétricas que son subconjuntos de. La fórmula viene dada por
En 1995, John R. Stembridge probó por primera vez la fórmula para[18] y más tarde en 2005 fue probado por George Andrews , Peter Paule y Carsten Schneider. [19] Alrededor de 1983, George Andrews y David Robbins establecieron independientemente una fórmula de producto explícita para la función de generación de conteo de órbitas para particiones planas totalmente simétricas. [20] [21] Esta fórmula ya se mencionó en el artículo de George E. Andrews Particiones planas totalmente simétricas que se publicó en 1980. [22] La conjetura se llama La conjetura q -TSPP y está dada por:
Dejar ser el grupo simétrico. La función de conteo de órbitas para particiones planas totalmente simétricas que caben dentro está dado por la fórmula
Esta conjetura se convirtió en un teorema en 2011. Para obtener una prueba de la conjetura q -TSPP, consulte el artículo Una prueba de la conjetura q-TSPP de George Andrews y David Robbins de Christoph Koutschan , Manuel Kauers y Doron Zeilberger . [23]
Tabiques planos autocomplementarios
Si para todos , , entonces la partición plana se llama autocomplementaria. Es necesario que el productoincluso. A continuación se muestra un ejemplo de una partición plana simétrica autocomplementaria y su visualización.
Richard P. Stanley [24] conjeturó fórmulas para el número total de particiones planas autocomplementarias. Según Richard Stanley, David Robbins también formuló fórmulas para el número total de particiones planas autocomplementarias en una forma diferente pero equivalente. El número total de particiones planas autocomplementarias que son subconjuntos de es dado por
Es necesario que el producto de r, s y t es par. Se puede encontrar una prueba en el artículo Simetrías de particiones planas que fue escrito por Richard P. Stanley. [25] [24] La demostración funciona con funciones de Schur.. La prueba de Stanley de la enumeración ordinaria de particiones planas autocomplementarias produce el q -análogo sustituyendo por . [26] Este es un caso especial de la fórmula de contenido de gancho de Stanley. [27] La función generadora para particiones planas autocomplementarias está dada por
Sustituyendo esta fórmula en
proporciona el estuche q -análogo deseado .
Particiones planas autocomplementarias cíclicamente simétricas
Una partición plana se llama autocomplementario cíclicamente simétrico si es cíclicamente simétrico y autocomplementario . La figura presenta una partición plana autocomplementaria cíclicamente simétrica y la matriz correspondiente se muestra a continuación.
En una comunicación privada con Richard P. Stanley , David Robbins conjeturó que el número total de particiones planas autocomplementarias cíclicamente simétricas está dado por. [21] [24] El número total de particiones planas autocomplementarias cíclicamente simétricas está dado por
es el numero de matrices de signos alternos . Una fórmula para es dado por
Greg Kuperberg demostró la fórmula paraen 1994. [28]
Tabiques planos autocomplementarios totalmente simétricos
Una partición plana autocomplementaria totalmente simétrica es una partición plana que es a la vez totalmente simétrica y autocomplementaria . Por ejemplo, la matriz a continuación es una partición plana de este tipo; se visualiza en la imagen adjunta.
La formula fue conjeturada por William H. Mills, David Robbins y Howard Rumsey en su obra Particiones planas totalmente simétricas autocomplementarias . [29] El número total de particiones planas autocomplementarias totalmente simétricas viene dado por
George Andrews ha probado esta fórmula en 1994 en su artículo Particiones planas V: La conjetura TSSCPP . [30]
Referencias
- ^ Richard P. Stanley , Combinatoria enumerativa , volumen 2. Corolario 7.20.3.
- ^ RP Stanley , Combinatoria enumerativa , volumen 2. págs. 365, 401-2.
- ^ EM Wright , Fórmulas de partición asintótica I. Particiones planas, The Quarterly Journal of Mathematics 1 (1931) 177-189.
- ^ L. Mutafchiev y E. Kamenov, "Fórmula asintótica para el número de particiones planas de enteros positivos", Comptus Rendus-Academie Bulgare Des Sciences 59 (2006), no. 4, 361.
- ^ MacMahon, Percy A. (1896). "XVI. Memoria sobre la teoría de la partición de números.-Parte I". Transacciones filosóficas de la Royal Society of London A: Ciencias matemáticas, físicas y de ingeniería . 187 : Artículo 52.
- ^ MacMahon, Mayor Percy A. (1916). Análisis combinatorio Vol 2 . Prensa de la Universidad de Cambridge. págs. §495.
- ^ MacMahon, Mayor Percy A. (1916). Análisis combinatorio . 2 . Prensa de la Universidad de Cambridge. págs. §429.
- ^ MacMahon, Mayor Percy A. (1916). Análisis combinatorio . Prensa de la Universidad de Cambridge. págs. §429, §494.
- ^ Atkin, AOL; Bratley, P .; Macdonald, IG; McKay, JKS (1967). "Algunos cálculos para particiones m -dimensionales". Proc. Camb. Phil. Soc . 63 (4): 1097-1100. Código Bibliográfico : 1967PCPS ... 63.1097A . doi : 10.1017 / s0305004100042171 .
- ^ a b c d Macdonald, Ian G. (1998). Funciones simétricas y polinomios de pasillo . Prensa de Clarendon. págs. 20 y siguientes. ISBN 9780198504504.
- ^ MacMahon, Percy Alexander (1899). "Particiones de números cuyas gráficas poseen simetría". Transacciones de la Sociedad Filosófica de Cambridge . 17 .
- ^ Bender y Knuth (1972). "Enumeración de particiones planas". Revista de Teoría Combinatoria, serie A . 13 : 40–54. doi : 10.1016 / 0097-3165 (72) 90007-6 .
- ^ Andrews, George E. (1977). "Plano particiones II: la equivalencia de las conjeturas de Bender-Knuth y MacMahon" . Pacific Journal of Mathematics . 72 (2): 283-291. doi : 10.2140 / pjm.1977.72.283 .
- ^ Andrews, George (1975). "Planos de particiones (I): la conjetura de Mac Mahon". Adv. Matemáticas. Supl. Stud . 1 .
- ^ Andrews, George E. (1977). "Conjetura de MacMahon sobre particiones planas simétricas" . Actas de la Academia Nacional de Ciencias . 74 (2): 426–429. Código Bibliográfico : 1977PNAS ... 74..426A . doi : 10.1073 / pnas.74.2.426 . PMC 392301 . PMID 16592386 .
- ^ Andrews, George E. (1979). "Particiones de plano (III): la conjetura débil de Macdonald". Inventiones Mathematicae . 53 (3): 193–225. Código bibliográfico : 1979InMat..53..193A . doi : 10.1007 / bf01389763 . S2CID 122528418 .
- ^ Molinos; Robbins; Rumsey (1982). "Prueba de la conjetura de Macdonald". Inventiones Mathematicae . 66 : 73–88. Código Bibliográfico : 1982InMat..66 ... 73M . doi : 10.1007 / bf01404757 . S2CID 120926391 .
- ^ Stembridge, John R. (1995). "La enumeración de particiones planas totalmente simétricas". Avances en Matemáticas . 111 (2): 227–243. doi : 10.1006 / aima.1995.1023 .
- ^ Andrews; Paule; Schneider (2005). "Plano de particiones VI: teorema TSPP de Stembridge". Avances en Matemática Aplicada . 34 (4): 709–739. doi : 10.1016 / j.aam.2004.07.008 .
- ^ Bressoud, David M. (1999). Pruebas y confirmaciones . Prensa de la Universidad de Cambridge. págs. conj. 13. ISBN 9781316582756.
- ^ a b Stanley, Richard P. (1970). "Una docena de conjeturas de Baker sobre particiones planas". Enumérative Combinatoire : 285-293.
- ^ Andrews, George (1980). "Tabiques planos totalmente simétricos". Resúmenes Amer. Matemáticas. Soc . 1 : 415.
- ^ Koutschan; Kauers; Zeilberger (2011). "Una prueba de la conjetura q-TSPP de George Andrews y David Robbins". PNAS . 108 (6): 2196–2199. arXiv : 1002.4384 . Código bibliográfico : 2011PNAS..108.2196K . doi : 10.1073 / pnas.1019186108 . S2CID 12077490 .
- ^ a b c Stanley, Richard P. (1986). "Simetrías de particiones planas". Revista de Teoría Combinatoria, serie A . 43 : 103-113. doi : 10.1016 / 0097-3165 (86) 90028-2 .
- ^ "Errata". Revista de teoría combinatoria . 43 : 310. 1986.
- ^ Eisenkölbl, Theresia (2008). "Una identidad de la función Schur relacionada con la (-1) -enumeración de particiones planas autocomplementarias" . Revista de Teoría Combinatoria, serie A . 115 : 199–212. doi : 10.1016 / j.jcta.2007.05.004 .
- ^ Stanley, Richard P. (1971). "Teoría y aplicación de particiones planas. Parte 2". Estudios de Matemática Aplicada . 50 (3): 259-279. doi : 10.1002 / sapm1971503259 .
- ^ Kuperberg, Greg (1994). "Simetrías de tabiques planos y el método de determinante permanente". Revista de Teoría Combinatoria, serie A . 68 : 115-151. arXiv : matemáticas / 9410224 . Bibcode : 1994math ..... 10224K . doi : 10.1016 / 0097-3165 (94) 90094-9 . S2CID 14538036 .
- ^ Molinos; Robbins; Rumsey (1986). "Particiones planas totalmente simétricas autocomplementarias" . Revista de Teoría Combinatoria, serie A . 42 (2): 277-292. doi : 10.1016 / 0097-3165 (86) 90098-1 .
- ^ Andrews, George E. (1994). "Plano de particiones V: la conjetura TSSCPP" . Revista de Teoría Combinatoria, serie A . 66 : 28–39. doi : 10.1016 / 0097-3165 (94) 90048-5 .
- ↑ Aquí se corrigió el error tipográfico (en el artículo de Wright), señalado por Mutafchiev y Kamenov. [4]
- G. Andrews , La teoría de las particiones , Cambridge University Press, Cambridge, 1998, ISBN 0-521-63766-X
- Bender, Edward A .; Knuth, Donald E. (1972), "Enumeración de particiones planas", Journal of Combinatorial Theory, Serie A , 13 : 40–54, doi : 10.1016 / 0097-3165 (72) 90007-6 , ISSN 1096-0899 , MR 0299574
- IG Macdonald , Funciones simétricas y polinomios de pasillo , Oxford University Press, Oxford, 1999, ISBN 0-19-850450-0
- PA MacMahon , Análisis combinatorio , 2 vols, Cambridge University Press, 1915–16.
enlaces externos
- Weisstein, Eric W. "Partición plana" . MathWorld .
- Secuencia OEIS A000219 (Número de particiones planas de n)
- La página DLMF sobre particiones de plano