En matemáticas y especialmente en combinatoria, una partición plana o partición bidimensional de un entero es un conjunto de enteros no negativos doblemente indexados (con i,j enteros y positivos) que es no creciente para ambos índices. Esto significa que:
y para todo i y j.
Además solo un número finito de los son distintos de cero. Una partición plana de un entero puede representarse gráficamente mediante una pila de cubos unitarios sobre el punto (i, j) en el plano gausiano, resultando un sólido tridimensional como el mostrado en la imagen.
La suma de una partición plana es:
La suma describe el número de cubos que forman la partición plana. El número de particiones planas de suma n se denota como PL(n).
Por ejemplo, hay 6 particiones planas con suma 3:
Por lo que PL(3) = 6. (En este caso, las particiones planas se obtienen usando indexado de matrices para las coordenadas y las entradas iguales a cero son eliminadas en pos de la legibilidad). Sea el número total de particiones planas en las que r es el número de filas distintas de cero, s es el número de columnas distintas de cero y t es el mayor entero de la matriz. Las particiones planas son a menudo descritas por las posiciones de los cubos unidad. Por ello una partición plana se define como un subconjunto finito de puntos de latitud enteros positivos (i, j, k) en , tal que (r, s, t) están contenidos en y si (i, j, k) satisface , y , entonces (i, j, k) también están contenidos en .
Funciones generadoras de particiones planas
De acuerdo con Percy A. MacMahon, la función generadora de PL(n) viene dada por:[1]
Esto a veces se denomina función de MacMahon.
Esta fórmula puede ser vista como la análoga bidimensional del producto de Euler para el número de particiones de enteros de n. No hay fórmula análoga conocida para dimensiones superiores (i.e., para particiones sólidas).[2] El problema del carácter asintótico de las particiones planas fue resuelto por E. M. Wright.[3] Para mayores , se obtiene:
Aquí, el error tipográfico en los artículos de Wright ha sido corregido, tras ser señalado por Mutafchiev y Kamenov.[4] La evaluación numérica da el resultado:
Alrededor de 1896 Percy Alexander MacMahon conformó la función generadora de particiones planas que son subconjuntos de en su primer tratado sobre particiones planas.[5] La fórmula se obtiene de
Una demostración de esta fórmula puede encontrarse en el libro Análisis Combinatorio, por Percy A. MacMahon.[6] Percy A. MacMahon también menciona en su libro Análisis Combinatorio las funciones generadoreas de planos en el artículo 429.[7] La fórmula para funciones generadoras puede ser escrita de modo alternativo, dado por
Considerando q = 1 en las fórmulas de arriba, resulta
Percy A. MacMahon obtuvo que el número total de particiones planas en viene dado por .[8] En el caso planario (cuando t = 1), resultan los Coeficiente binomial:
Diagramas de Ferrers para particiones planass
Otra representación de las particiones planass viene dada por el diagrama de Normal Macleods 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 DF: Si el nodo , entonces también lo son los nodos con para todo .
Sustituyendo cada nodo de una partición plana por un cubo con bordes alineados con los ejes se obtiene una representación pila de cubos de la partición plana.
Equivalencia de las dos representaciones
Dado un diagrama de Ferrers, la partición plana (tal y como se entiende en la definición principial) se construye de esta forma
- Sea el número de nodos en el diagrama de Ferrers con coordenadas de la forma donde denota un valor arbitrario. Se verifica que la satisfacción de las condiciones para la partición plana es condición necesaria para el diagrama de Ferrers.
Dado un conjunto de que forman una partición plana, se obtiene el diagrama de Ferrers de esta forma.
- Comenzamos con un diagrama sin nodos. Para cada distinto de cero, se añade nodos de la forma para al diagrama. Por construcción, es sencillo ver que se satisface la condición del diagrama de Ferrers.
Por ejemplo, debajo se muestran las representaciones de una partición plana de 5.
Encima, todos los nodos del diagrama están escritos como una columna, y solo hemos escrito el no nulo, como es convencional.
Acción de S2, S3 y C3 en particiones planas
es el grupo de permutaciones actuando sobre las dos primeras coordenadas de (i,j,k). Este grupo contiene la identidad (i,j,k) y la trasposición (i,j,k,)→(j,i,k). El número de elementos en una órbita se denota como ||. denota el conjunto de órbitas de elementos de bajo la acción de . La altura de un elemento (i,j,k) se define por:
La altura se incrementa en uno a cada paso que se aleja de la esquina trasera inferior. Por ejemplo, la posición de esquina (1,1,1) tiene altura 1 y ht(2,1,1)=2. ht() es la altura de una órbita, que es la altura de cualquier elemento de la órbita. Esta notación de altura difiere de la 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 de puede generar nuevas particiones planas a partir de una partición plana dada. Abajo se muestranseis particiones planas de 4 que son generadas por acción de . Solo el intercambio de las primeras dos coordenadas se manifiesta en la representación mostrada a continuación.
se denomina grupo de permutaciones cíclicas y consiste en
Particiones planas simétricas
Una partición plana se denomina simétrica 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 respecto al plano x = y. Se muestra a continuación un ejemplo de partición plana simétrica. Se adjunta la matriz visualizada.
En 1898, Percy Alexander MacMahon formuló su conjetura sobre la función generatriz de particiones planas simétricas que son subconjuntos de .[11] Esta conjetura se denomina La conjetura de MacMahon. La función generatriz viene dada por
Ian G. MacDonald[10] señaló que la conjetura de MacMahon se reduce a
En 1972, Edward A. Bender y Donald Knuth[12] conjeturaron una forma cerrada simple para la función generatriz para particiones con como mucho r filas y orden estrictamente decreciente en filas. George Andrews[13] demostró que la conjuntura de Bender y Knuth y la conjetura de MacMahon eran equivalentes. La conjetura de MacMahon fue probada casi simultáneamente por George Andrews en 1977[14] y después Ian G. MacDonald presentó una prueba alternativa.[10] Poner q=1 da como resultado la función continua que viene dada por
Para una prueba del caso q = 1, pueden consultar escrito de George Andrews MacMahon's conjecture on symmetric plane partitions.[15]
Particiones planas cíclicamente simétricas
se denomina cíclicamente simétrica si la fila i de es conjugada de la columna i para todo i- La columna i es una partición ordinaria. El conjugado de una partición es la partición cuyo diagrama es el traspuesto 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) están también en . A continuación, un ejemplo de partición plana cíclicamente simétrica y su visualización.
la conjetura de Ian G. Macdonald aporta una fórmula para calcular el número de particiones planas cíclicamente simétricas para un entero r dado. Esta conjetura se denomina Conjetura MacDonald. La función generatriz para planos cíclicamente simétricos subconjuntos de viene dada por
Esta ecuación puede también ser escrita como
En 1979 George Andrews ha demostrado la conjetura de MacDonald para q = 1 como conjetura "débil" de MacMahon.[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 tratado Prueba de la conjetura de MacDonald.[17] La fórmula para viene dada por la conjetura "débil" de MacMahon.
Particiones planas totalmente simétricas
Una partición plana totalmente simétrica es una partición simétrica y cíclicamente simétrica. Esto significa que el diagrama es simétrico en los tres planos de la diagonal. Por lo que si (i,j,k) todas las permutaciones de (i,j,k) están también en . A continuación, un ejemplo de 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 posteriormente, en 2005, George Andrews, Peter Paule y Carsten Schneider[19] también dieron una prueba. Alrededor de 1983, George Andrews y David Robbins establecieron de forma independiente una fórmula explícita del producto para la función de generación de conteo de órbitas para particiones planas totalmente simétricas.[20][21] Esta fórmula ya había sido mencionada en el documento de George E. Andrews Particiones planas totalmente simétricas, que se publicó en 1980.[22]
La conjetura se llama q-TSPP y viene dada por:
Sea el grupo simétrico. La función de conteo orbital para particiones planas totalmente simétricas que se ajustan dentro de viene dada por la fórmula
Esta conjetura se convirtió en un teorema en 2011. Para obtener una prueba de la q-TSPP, consúltese el documento "Una prueba de George Andrews" y la q-TSPP de David Robbins por Christoph Koutschan, Manuel Kauers y Doron Zeilberger.[23]
Particiones planas autocomplementarias
Si para todo , , la partición plana se denomina autocomplementaria. Es necesario que el producto sea par. A continuación, un ejemplo de partición plana simétrica autocomplementaria y su visualización.
Richard P. Stanley[24] conjeturó fórmulas para el total de particiones autocomplementarias. . Según Richard Stanley, David Robbins también formuló para este propósito en una forma distinta pero equivalente. El número total de particiones planas autocomplementarias subconjuntos de viene dado por
Es necesario que el producto de r,s y t sea par. Una prueba puede encontrarse en el tratado Simetrías de particiones planas, por Stanley.[25][24] Las pruebas funcionan con funciones de Schur . La prueba de Stanley de la enumeración ordinaria de particiones planas autocomplementarias da el análogo q sustituyendo por .[26]
Esto es un caso especial de la fórmula de Stanley.[27] La función generatriz para particiones autocomplementarias es dada por
Sustituyendo esta fórmula en
nos sirve para obtener el caso análogo q deseado.
Particiones planas autocomplementarias cíclicamente simétricas
Una partición plana se denomina autocomplementaria cíclicamente simétrica si es cíclicamente simétrica y autocomplementaria. Esta figura representa el modelo expuesto, y la matriz asociada al mismo.
En una comunicación privada con Stanley, David P. Robins conjeturó que el número total de particiones planas autocomplementarias cíclicamente simétricas dada por [21][24] El número total de particiones autocomplementarias cíclicamente simétricas viene dada por
es el número de of matrices de signo alterno. Una fórmula para viene dada por
Greg Kuperberg demostró que la fórmula para en 1994. [28]
Particiones planas autocomplementarias totalmente simétricas
Una partición plana totalmente simétrica es una partición plana que es a la vez totalmente simétrica y autocomplementaria. Por ejemplo, la matriz aquí mostrada es de este tipo, acompañada por su correspondiente representación.
La fórmula fue conjeturada por William H. Mills, David Robbins y Howard Rumsey en su tratado Particiones planas autocomplementarias completamente simétricas.[29] El número total de particiones planas autocomplementarias totalmente simétricas viene dado por
George Andrews demostró esta fórmula en 1994, en su tratado Particiones planas V: La conjetura TSSCPP.[30]
Referencias
- ↑ Richard P. Stanley, Enumerative Combinatorics, Volume 2. Corollary 7.20.3.
- ↑ R.P. Stanley, Enumerative Combinatorics, Volume 2. pp. 365, 401–2.
- ↑ E. M. Wright, Asymptotic partition formulae I. Plane partitions, The Quarterly Journal of Mathematics 1 (1931) 177–189.
- ↑ L. Mutafchiev and E. Kamenov, "Asymptotic formula for the number of plane partitions of positive integers", Comptus Rendus-Academie Bulgare Des Sciences 59 (2006), no. 4, 361.
- ↑ MacMahon, Percy A. (1896). «XVI. Memoir on the theory of the partition of numbers.-Part I». Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 187: Article 52.
- ↑ MacMahon, Major Percy A. (1916). Combinatory Analysis Vol 2. Chambridge: at the University Press. pp. §495.
- ↑ MacMahon, Major Percy A. (1916). «Combinatory Analysis». Chambridge: At the University Press 2: §429.
- ↑ MacMahon, Major Percy A. (1916). Combinatory Analysis. Chambridge: at the University Press. pp. §429,§494.
- ↑ Atkin, A. O. L.; Bratley, P.; Macdonald, I. G.; McKay, J. K. S. (1967). «Some computations for m-dimensional partitions». Proc. Camb. Phil. Soc. 63 (4): 1097-1100. Bibcode:1967PCPS...63.1097A. doi:10.1017/s0305004100042171.
- ↑ a b c d Macdonald, Ian G. (1998). Symmetric Functions and Hall Polynomials. Clarendon Press. pp. 20f, 85f. ISBN 9780198504504.
- ↑ MacMahon, Percy Alexander (1899). «Partitions of numbers whose graphs possess symmetry». Transactions of the Cambridge Philosophical Society 17.
- ↑ Bender and Knuth (1972). «Enumeration of plane partitions». Journal of Combinatorial Theory, Series A 13: 40-54. doi:10.1016/0097-3165(72)90007-6.
- ↑ Andrews, George E. (1977). «Plane partitions II: The equivalence of the Bender-Knuth and MacMahon conjectures». Pacific Journal of Mathematics 72 (2): 283-291. doi:10.2140/pjm.1977.72.283.
- ↑ Andrews, George (1975). «Plane Partitions (I): The Mac Mahon Conjecture». Adv. Math. Suppl. Stud. 1.
- ↑ Andrews, George E. (1977). «MacMahon's conjecture on symmetric plane partitions». Proceedings of the National Academy of Sciences 74 (2): 426-429. Bibcode:1977PNAS...74..426A. PMC 392301. PMID 16592386. doi:10.1073/pnas.74.2.426.
- ↑ Andrews, George E. (1979). «Plane Partitions(III): The Weak Macdonald Conjecture». Inventiones Mathematicae 53 (3): 193-225. Bibcode:1979InMat..53..193A. doi:10.1007/bf01389763.
- ↑ Mills, Robbins, Rumsey (1982). «Proof of the Macdonald conjecture». Inventiones Mathematicae 66: 73-88. Bibcode:1982InMat..66...73M. doi:10.1007/bf01404757.
- ↑ Stembridge, John R. (1995). «The Enumeration of Totally Symmetric Plane Partitions». Advances in Mathematics 111 (2): 227-243. doi:10.1006/aima.1995.1023.
- ↑ Andrews, Paule, Schneider (2005). «Plane Partitions VI: Stembridge's TSPP theorem». Advances in Applied Mathematics 34 (4): 709-739. doi:10.1016/j.aam.2004.07.008.
- ↑ Bressoud, David M. (1999). Proofs and Confirmations. Cambridge University Press. pp. conj. 13. ISBN 9781316582756.
- ↑ a b Stanley, Richard P. (1970). «A Baker's dozen of conjectures concerning plane partitions». Combinatoire énumérative: 285-293.
- ↑ Andrews, George (1980). «Totally symmetric plane partitions». Abstracts Amer. Math. Soc 1: 415.
- ↑ Koutschan, Kauers, Zeilberger (2011). «A proof of George Andrews' and David Robbins' q-TSPP conjecture». PNAS 108 (6): 2196-2199. Bibcode:2011PNAS..108.2196K. arXiv:1002.4384. doi:10.1073/pnas.1019186108.
- ↑ a b c Stanley, Richard P. (1986). «Symmetries of Plane Partitions». Journal of Combinatorial Theory, Series A 43: 103-113. doi:10.1016/0097-3165(86)90028-2.
- ↑ «Erratum». Journal of Combinatorial Theory 43: 310. 1986.
- ↑ Eisenkölbl, Theresia (2008). «A Schur function identity related to the (-1)-enumeration of self complementary plane partitions». Journal of Combinatorial Theory, Series A 115: 199-212. doi:10.1016/j.jcta.2007.05.004.
- ↑ Stanley, Richard P. (1971). «Theory and Application of Plane Partitions. Part 2». Advances in Applied Mathematics 50 (3): 259-279. doi:10.1002/sapm1971503259.
- ↑ Kuperberg, Greg (1994). «Symmetries of plane partitions and the permanent-determinant method». Journal of Combinatorial Theory, Series A 68: 115-151. Bibcode:1994math.....10224K. arXiv:math/9410224. doi:10.1016/0097-3165(94)90094-9.
- ↑ Mills, Robbins, Rumsey (1986). «Self-Complementary Totally Symmetric Plane Partitions». Journal of Combinatorial Theory, Series A 42 (2): 277-292. doi:10.1016/0097-3165(86)90098-1.
- ↑ Andrews, George E. (1994). «Plane Partitions V: The TSSCPP Conjecture». Journal of Combinatorial Theory, Series A 66: 28-39. doi:10.1016/0097-3165(94)90048-5.
Bibliografía
- G. Andrews, The Theory of Partitions, Cambridge University Press, Cambridge, 1998, ISBN 0-521-63766-X
- Bender, Edward A.; Knuth, Donald E. (1972), «Enumeration of plane partitions», Journal of Combinatorial Theory, Series A 13: 40-54, ISSN 1096-0899, MR 0299574, doi:10.1016/0097-3165(72)90007-6.
- I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1999, ISBN 0-19-850450-0
- P.A. MacMahon, Combinatory analysis, 2 vols, Cambridge University Press, 1915-16.
Enlaces externos
- Weisstein, Eric W. «Plane partition». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- OEIS sequence A000219 (Number of planar partitions of n)
- The DLMF page on Plane Partitions