Partición plana de los enteros

Una partición plana representada como pilas de cubos unitarios

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 $\pi _{i,j}$ (con i,j enteros y positivos) que es no creciente para ambos índices. Esto significa que:

$\pi _{i,j}\geq \pi _{i,j+1}\quad$ y $\quad \pi _{i,j}\geq \pi _{i+1,j}\,$ para todo i y j.

Además solo un número finito de los $\pi _{i,j}$ son distintos de cero. Una partición plana de un entero puede representarse gráficamente mediante una pila de $\pi _{i,j}$ 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:

$n=\sum _{i,j}\pi _{i,j}$

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:

${\begin{matrix}1&1&1\end{matrix}}\qquad {\begin{matrix}1&1\\1&\end{matrix}}\qquad {\begin{matrix}1\\1\\1&\end{matrix}}\qquad {\begin{matrix}2&1&\end{matrix}}\qquad {\begin{matrix}2\\1&\end{matrix}}\qquad {\begin{matrix}3\end{matrix}}$

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 $N_{i}(r,s,t)$ 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 ${\mathcal {P}}$ de puntos de latitud enteros positivos (i, j, k) en $\mathbb {N} ^{3}$, tal que (r, s, t) están contenidos en ${\mathcal {P}}$ y si (i, j, k) satisface $1\leq i\leq r$, $1\leq j\leq s$ y $1\leq k\leq t$, entonces (i, j, k) también están contenidos en ${\mathcal {P}}$.

${\mathcal {B}}(r,s,t)=\{(i,j,k)|1\leq i\leq r,1\leq j\leq s,1\leq k\leq t\}$

Funciones generadoras de particiones planas

De acuerdo con Percy A. MacMahon, la función generadora de PL(n) viene dada por:​

$\sum _{n=0}^{\infty }{\mbox{PL}}(n)\,x^{n}=\prod _{k=1}^{\infty }{\frac {1}{(1-x^{k})^{k}}}=1+x+3x^{2}+6x^{3}+13x^{4}+24x^{5}+\cdots .$

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).​ El problema del carácter asintótico de las particiones planas fue resuelto por E. M. Wright.​ Para mayores $n$, se obtiene:

$\mathrm {PL} (n)\sim {\frac {\zeta (3)^{7/36}}{\sqrt {12\pi }}}\ \left({\frac {n}{2}}\right)^{-25/36}\ \exp \left(3\ \zeta (3)^{1/3}\left({\frac {n}{2}}\right)^{2/3}+\zeta '(-1)\right)\ ,$

Aquí, el error tipográfico en los artículos de Wright ha sido corregido, tras ser señalado por Mutafchiev y Kamenov.​ La evaluación numérica da el resultado:

$\ln \mathrm {PL} (n)\sim 2.00945n^{2/3}-0.69444\ln n-1.4631.$

Alrededor de 1896 Percy Alexander MacMahon conformó la función generadora de particiones planas que son subconjuntos de ${\mathcal {B}}(r,s,t)$ en su primer tratado sobre particiones planas.​ La fórmula se obtiene de

$\sum _{\pi \in {\mathcal {B}}(r,s,t)}q^{|\pi |}=\prod _{i=1}^{r}\prod _{j=1}^{s}{\frac {1-q^{i+j+t-1}}{1-q^{i+j-1}}}$

Una demostración de esta fórmula puede encontrarse en el libro Análisis Combinatorio, por Percy A. MacMahon.​ Percy A. MacMahon también menciona en su libro Análisis Combinatorio las funciones generadoreas de planos en el artículo 429.​ La fórmula para funciones generadoras puede ser escrita de modo alternativo, dado por

$\sum _{\pi \in {\mathcal {B}}(r,s,t)}q^{|\pi |}=\prod _{i=1}^{r}\prod _{j=1}^{s}\prod _{k=1}^{t}{\frac {1-q^{i+j+k-1}}{1-q^{i+j+k-2}}}$

Considerando q = 1 en las fórmulas de arriba, resulta

$N_{1}(r,s,t)=\prod _{(i,j,k)\in {\mathcal {B}}(r,s,t)}{\frac {i+j+k-1}{i+j+k-2}}=\prod _{i=1}^{r}\prod _{j=1}^{s}{\frac {i+j+t-1}{i+j-1}}$

Percy A. MacMahon obtuvo que el número total de particiones planas en ${\mathcal {B}}(r,s,t)$ viene dado por $N_{1}(r,s,t)$.​ En el caso planario (cuando t = 1), resultan los Coeficiente binomial:

${\mathcal {B}}(r,s,1)={\binom {r+s}{r}}$

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 $n$ es una colección de $n$ puntos o nodos, $\lambda =(\mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{n})$, con $\mathbf {y} _{i}\in \mathbb {Z} _{\geq 0}^{3}$ satisfaciendo la condición:​

Condición DF: Si el nodo $\mathbf {a} =(a_{1},a_{2},a_{3})\in \lambda$, entonces también lo son los nodos $\mathbf {y} =(y_{1},y_{2},y_{3})$ con $0\leq y_{i}\leq a_{i}$ para todo $i=1,2,3$.

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 $\pi _{i,j}$ el número de nodos en el diagrama de Ferrers con coordenadas de la forma $(i-1,j-1,*)$ 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 $\pi _{i,j}$ que forman una partición plana, se obtiene el diagrama de Ferrers de esta forma.

Comenzamos con un diagrama sin nodos. Para cada $\pi _{i,j}$ distinto de cero, se añade $\pi _{i,j}$ nodos de la forma $(i-1,j-1,y_{3})$ para $0\leq y_{3}<\pi _{i,j}-1$ 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.

$\left({\begin{smallmatrix}0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}0\\0\\1\end{smallmatrix}}{\begin{smallmatrix}0\\1\\0\end{smallmatrix}}{\begin{smallmatrix}1\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\1\\0\end{smallmatrix}}\right)\qquad \Longleftrightarrow \qquad {\begin{matrix}2&1\\1&1\end{matrix}}$

Encima, todos los nodos del diagrama están escritos como una columna, y solo hemos escrito el $\pi _{i,j}$ no nulo, como es convencional.

Acción de S₂, S₃ y C₃ en particiones planas

${\mathcal {S}}_{2}$ 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 $\eta$ se denota como |$\eta$|. ${\mathcal {B}}/{\mathcal {S}}_{2}$ denota el conjunto de órbitas de elementos de ${\mathcal {B}}$ bajo la acción de ${\mathcal {S}}_{2}$. La altura de un elemento (i,j,k) se define por:

$ht(i,j,k)=i+j+k-2$

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($\eta$) 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.​

Hay una acción natural del grupo de permutación ${\mathcal {S}}_{3}$ 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 ${\mathcal {S}}_{3}$ 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 ${\mathcal {S}}_{3}$. Solo el intercambio de las primeras dos coordenadas se manifiesta en la representación mostrada a continuación.

${\begin{smallmatrix}3&1\end{smallmatrix}}\quad {\begin{smallmatrix}3\\1\end{smallmatrix}}\quad {\begin{smallmatrix}2&1&1\end{smallmatrix}}\quad {\begin{smallmatrix}2\\1\\1\end{smallmatrix}}\quad {\begin{smallmatrix}1&1&1\\1\end{smallmatrix}}\quad {\begin{smallmatrix}1&1\\1\\1\end{smallmatrix}}$

${\mathcal {C}}_{3}$ se denomina grupo de permutaciones cíclicas y consiste en

$(i,j,k)\rightarrow (i,j,k),\quad (i,j,k)\rightarrow (j,k,i),\quad {\textrm {and}}\quad (i,j,k)\rightarrow (k,i,j).$

Particiones planas simétricas

Una partición plana $\pi$ se denomina simétrica si $\pi$_i,j = $\pi$_j,i para todo i,j . En otras palabras, una partición plana es simétrica si (i,j,k)$\in {\mathcal {B}}(r,s,t)$ si y solo si (j,i,k)$\in {\mathcal {B}}(r,s,t)$. 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.

Una partición plana simétrica de suma 35

${\begin{matrix}4&3&3&2&1\\3&3&2&1&\\3&2&2&1&\\2&1&1&&\\1&&&&\end{matrix}}$

En 1898, Percy Alexander MacMahon formuló su conjetura sobre la función generatriz de particiones planas simétricas que son subconjuntos de ${\mathcal {B}}(r,r,t)$.​ Esta conjetura se denomina La conjetura de MacMahon. La función generatriz viene dada por

$\sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}q^{|\pi |}=\prod _{i=1}^{r}\left[{\frac {1-q^{t+2i-1}}{1-q^{2i-1}}}\prod _{j=i+1}^{r}{\frac {1-q^{2(i+j+t-1)}}{1-q^{2(i+j-1)}}}\right]$

Ian G. MacDonald​ señaló que la conjetura de MacMahon se reduce a

$\sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}$

En 1972, Edward A. Bender y Donald Knuth​ 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​ 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​ y después Ian G. MacDonald presentó una prueba alternativa.​ Poner q=1 da como resultado la función continua $N_{2}(r,r,t)$ que viene dada por

$N_{2}(r,r,t)=\prod _{i=1}^{r}{\frac {2i+t-1}{2i-1}}\prod _{1\leq i<j\leq r}{\frac {i+j+t-1}{i+j-1}}$

Para una prueba del caso q = 1, pueden consultar escrito de George Andrews MacMahon's conjecture on symmetric plane partitions.​

Particiones planas cíclicamente simétricas

$\pi$ se denomina cíclicamente simétrica si la fila i de $\pi$ es conjugada de la columna i para todo i- La columna i es una partición ordinaria. El conjugado de una partición $\pi$ es la partición cuyo diagrama es el traspuesto de la partición $\pi$.​ En otras palabras, la partición plana es cíclicamente simétrica si siempre que (i,j,k)$\in {\mathcal {B}}(r,s,t)$ entonces (k,i,j) y (j,k,i) están también en ${\mathcal {B}}(r,s,t)$. A continuación, un ejemplo de partición plana cíclicamente simétrica y su visualización.

Partición plana cíclicamente simétrica

${\begin{matrix}6&5&5&4&3&3\\6&4&3&3&1&\\6&4&3&1&1&\\4&2&2&1&&\\3&1&1&&&\\1&1&1&&&\end{matrix}}$

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 ${\mathcal {B}}(r,r,r)$ viene dada por

$\sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {C}}_{3}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,t)/{\mathcal {C}}_{3}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}$

Esta ecuación puede también ser escrita como

$\prod _{\eta \in {\mathcal {B}}(r,r,t)/{\mathcal {C}}_{3}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}=\prod _{i=1}^{r}\left[{\frac {1-q^{3i-1}}{1-q^{3i-2}}}\prod _{j=i}^{r}{\frac {1-q^{3(r+i+j-1)}}{1-q^{3(2i+j-1)}}}\right]$

En 1979 George Andrews ha demostrado la conjetura de MacDonald para q = 1 como conjetura "débil" de MacMahon.​ 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.​ La fórmula para $N_{3}(r,r,r)$ viene dada por la conjetura "débil" de MacMahon.

$N_{3}(r,r,r)=\prod _{i=1}^{r}\left[{\frac {3i-1}{3i-2}}\prod _{j=i}^{r}{\frac {i+j+r-1}{2i+j-1}}\right]$

Particiones planas totalmente simétricas

Una partición plana totalmente simétrica $\pi$ 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)$\in {\mathcal {B}}(r,s,t)$ todas las permutaciones de (i,j,k) están también en ${\mathcal {B}}(r,s,t)$. A continuación, un ejemplo de una partición plana totalmente simétrica. La imagen muestra la visualización de la matriz.

Partición plana totalmente simétrica

${\begin{matrix}5&4&4&3&1\\4&3&3&1&\\4&3&2&1&\\3&1&1&&\\1&&&&\end{matrix}}$

Ian G. Macdonald encontró el número total de particiones planas totalmente simétricas que son subconjuntos de ${\mathcal {B}}(r,r,r)$. La fórmula viene dada por

$N_{4}(r,r,r)=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}{\frac {1+ht(\eta )}{ht(\eta )}}$

En 1995, John R. Stembridge probó por primera vez la fórmula para $N_{4}(r,r,r)$,​ y posteriormente, en 2005, George Andrews, Peter Paule y Carsten Schneider​ 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.​​ 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.​

La conjetura se llama q-TSPP y viene dada por:

Sea ${\mathcal {S}}_{3}$ el grupo simétrico. La función de conteo orbital para particiones planas totalmente simétricas que se ajustan dentro de ${\mathcal {B}}(r,r,r)$ viene dada por la fórmula

$\sum _{\pi \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}{\frac {1-q^{1+ht(\eta )}}{1-q^{ht(\eta )}}}=\prod _{1\leq i\leq j\leq k\leq r}{\frac {1-q^{i+j+k-1}}{1-q^{i+j+k-2}}}$

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.​

Particiones planas autocomplementarias

Si $\pi _{i,j}+\pi _{r-i+1,s-j+1}=t$ para todo $1\leq i\leq r$, $1\leq j\leq s$, la partición plana se denomina autocomplementaria. Es necesario que el producto $r\cdot s\cdot t$ sea par. A continuación, un ejemplo de partición plana simétrica autocomplementaria y su visualización.

${\begin{matrix}4&4&3&2&1\\4&2&2&2&\\3&2&1&&\end{matrix}}$

Richard P. Stanley​ conjeturó fórmulas para el total de particiones autocomplementarias. $N_{5}(r,s,t)$. 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 ${\mathcal {B}}(r,s,t)$ viene dado por

$N_{5}(2r,2s,2t)=N_{1}(r,s,t)^{2}$

$N_{5}(2r+1,2s,2t)=N_{1}(r,s,t)N_{1}(r+1,s,t)$

$N_{5}(2r+1,2s+1,2t)=N_{1}(r+1,s,t)N_{1}(r,s+1,t)$

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.​​ Las pruebas funcionan con funciones de Schur $s_{s^{r}}(x)$. La prueba de Stanley de la enumeración ordinaria de particiones planas autocomplementarias da el análogo q sustituyendo $x_{i}=q^{i}$ por $i=1,\ldots ,n$.​

Esto es un caso especial de la fórmula de Stanley.​ La función generatriz para particiones autocomplementarias es dada por

$s_{\gamma ^{\alpha }}(q,q^{2},\ldots ,q^{n})=q^{\gamma \alpha (\alpha +1)/2}\prod _{i=1}^{\alpha }\prod _{j=0}^{\gamma -1}{\frac {1-q^{i+n-\alpha +j}}{1-q^{i+j}}}$

Sustituyendo esta fórmula en

$s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r})^{2}\ {\textrm {for}}\ {\mathcal {B}}(2r,2s,2t)$

$s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r})s_{(s+1)^{r}}(x_{1},x_{2},\ldots ,x_{t+r})\ {\textrm {for}}\ {\mathcal {B}}(2r,2s+1,2t)$

$s_{s^{r+1}}(x_{1},x_{2},\ldots ,x_{t+r+1})s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r+1})\ {\textrm {for}}\ {\mathcal {B}}(2r+1,2s,2t+1)$

nos sirve para obtener el caso análogo q deseado.

Particiones planas autocomplementarias cíclicamente simétricas

Una partición plana $\pi$ 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.

Partición plana autocomplementaria cíclicamente simétrica

${\begin{matrix}4&4&4&1\\3&3&2&1\\3&2&1&1\\3&&&\end{matrix}}$

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 $N_{6}(2r,2r,2r)$​​ El número total de particiones autocomplementarias cíclicamente simétricas viene dada por

$N_{6}(2r,2r,2r)=D_{r}^{2}$

$D_{r}$ es el número de of $r\times r$ matrices de signo alterno. Una fórmula para $D_{r}$ viene dada por

$D_{r}=\prod _{j=0}^{r-1}{\frac {(3j+1)!}{(r+j)!}}$

Greg Kuperberg demostró que la fórmula para $N_{6}(r,r,r)$ en 1994. ​

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.

Partición plana autocomplementaria totalmente simétrica

${\begin{matrix}6&6&6&5&5&3\\6&5&5&3&3&1\\6&5&5&3&3&1\\5&3&3&1&1&\\5&3&3&1&1&\\3&1&1&&&\end{matrix}}$

La fórmula $N_{7}(r,r,r)$ fue conjeturada por William H. Mills, David Robbins y Howard Rumsey en su tratado Particiones planas autocomplementarias completamente simétricas.​ El número total de particiones planas autocomplementarias totalmente simétricas viene dado por

$N_{7}(2r,2r,2r)=D_{r}$

George Andrews demostró esta fórmula en 1994, en su tratado Particiones planas V: La conjetura TSSCPP.​

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

• Datos: Q7201015