en>Alvin Seville: removing and categorizing

2014-01-25T21:40:15Z

removing and categorizing

New page

In mathematics, '''solid partitions''' are natural generalizations of [[Partition_(number_theory)| partitions]] and [[plane partition]]s defined by [[Percy Alexander MacMahon]].<ref>P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 2, p 332.</ref> A solid partition of <math> n </math> is a three-dimensional array, <math> n_{i,j,k}</math>, of non-negative integers (the indices <math> i,\ j,\ k\geq 1</math>) such that
:<math> \sum_{i,j,k} n_{i,j,k}=n</math>
and
:<math>
n_{i+1,j,k} \leq n_{i,j,k}\quad,\quad
n_{i,j+1,k} \leq n_{i,j,k}\quad\text{and}\quad
n_{i,j,k+1} \leq n_{i,j,k}\quad,\quad \forall\ i,\ j \text{ and } k\ .
</math>
Let <math>p_3(n)</math> denote the number of solid partitions of <math>n</math>. As the definition of solid partitions involves three-dimensional arrays of numbers, they are also called '''three-dimensional partitions''' in notation where plane partitions are two-dimensional partitions and partitions are one-dimensional partitions. Solid partitions and their higher-dimensional generalizations are discussed in the book by [[George_Andrews_(mathematician)| Andrews]].<ref>G. E. Andrews, ''The theory of partitions'', Cambridge University Press, 1998.</ref>

== Ferrers diagrams for solid partitions ==

Another representation for solid partitions is in the form of [[Norman_Macleod_Ferrers|Ferrers]] diagrams. The Ferrers diagram of a solid partition of <math>n</math> is a collection of <math>n</math> points or ''nodes'', <math>\lambda=(\mathbf{y}_1,\mathbf{y}_2,\ldots,\mathbf{y}_n)</math>, with <math>\mathbf{y}_i\in \mathbb{Z}_{\geq0}^4</math> satisfying the condition:<ref name="Atkin1967">A. O. L. Atkin, P. Bratley, I. G. McDonald and J. K. S. McKay, Some computations for'' ''m-dimensional partitions, Proc. Camb. Phil. Soc., 63 (1967), 1097–1100.</ref>

:'''Condition FD:''' If the node <math>\mathbf{a}=(a_1,a_2,a_3, a_4)\in \lambda</math>, then so do all the nodes <math>\mathbf{y}=(y_1,y_2,y_4,y_4)</math> with <math>0\leq y_i\leq a_i</math> for all <math>i=1,2,3,4</math>.

For instance, the Ferrers diagram
:<math>
\left( \begin{smallmatrix} 0\\ 0\\ 0 \\ 0 \end{smallmatrix}
\begin{smallmatrix} 0\\ 0\\ 1 \\ 0 \end{smallmatrix}
\begin{smallmatrix} 0\\ 1\\ 0 \\ 0 \end{smallmatrix}
\begin{smallmatrix}1 \\ 0 \\ 0 \\ 0 \end{smallmatrix}
\begin{smallmatrix} 1 \\ 1\\ 0 \\ 0 \end{smallmatrix}
\right) \ ,
</math>
where each column is a node, represents a solid partition of <math>5</math>. There is a natural action of the permutation group <math>S_4</math> on a Ferrers diagram – this corresponds to permuting the four coordinates of all nodes. This generalizes the conjugation operation for partitions.

=== Equivalence of the two representations ===

Given a Ferrers diagram, one constructs the solid partition (as in the main definition) as follows.
:Let <math>n_{i,j,k}</math> be the number of nodes in the Ferrers diagram with coordinates of the form <math>(i-1,j-1,k-1,*)</math> where <math>*</math> denotes an arbitrary value. The collection <math>n_{i,j,k}</math> form a solid partition. One can verify that condition FD implies that the conditions for a solid partition are satisfied.

Given a set of <math>n_{i,j,k}</math> that form a solid partition, one obtains the corresponding Ferrers diagram as follows.
:Start with the Ferrers diagram with no nodes. For every non-zero <math>n_{i,j,k}</math>, add <math>n_{i,j,k}</math> nodes <math>(i-1,j-1,k-1,y_4)</math> for <math>0\leq y_4< n_{i,j,k}</math> to the Ferrers diagram. By construction, it is easy to see that condition FD is satisfied.

For example, the Ferrers diagram with <math>5</math> nodes given above corresponds to the solid partition with
:<math>n_{1,1,1}=n_{2,1,1}=n_{1,2,1}=n_{1,1,2}=n_{2,2,1}=1</math>
with all other <math>n_{i,j,k}</math> vanishing.

== Generating function ==

Let <math>p_3(0)\equiv 1</math>. Define the generating function of solid partitions, <math>P_3(q)</math>, by
:<math>
P_3(q) :=\sum_{n=0}^\infty p_3(n)\ q^n = 1+q+4\ q^2+10\ q^3+26\ q^4+59\ q^5+140\ q^6+\cdots
</math>
The generating functions of [[Partition_(number_theory)|partitions]] and [[Plane_partition|plane partitions]] have simple formulae due to [[Leonhard Euler|Euler]] and [[Percy Alexander MacMahon| MacMahon]] respectively. However, a guess of [[Percy Alexander MacMahon| MacMahon]] fails to correctly reproduce the solid partitions of 6 as shown by Atkin et. al.<ref name="Atkin1967" /> It appears that there is no simple formula for the generating function of solid partitions. Somewhat confusingly, Atkin et. al. refer to solid partitions as four-dimensional partitions as that is the dimension of the Ferrers diagram.<ref name="Atkin1967" />

== Exact enumeration using computers ==

Given the lack of an explicitly known generating function, the enumerations of the numbers of solid partitions for larger integers have been carried out numerically. There are two algorithms that are used to enumerate solid partitions and their higher-dimensional generalizations. The work of Atkin. et. al. used an algorithm due to Bratley and McKay.<ref>P. Bratley and J. K. S. McKay, "Algorithm 313: Multi-dimensional partition generator", Comm. ACM, 10 (Issue 10, 1967), p. 666.</ref> In 1970, Knuth proposed a different algorithm to enumerate topological sequences that he used to evaluate numbers of solid partitions of all integers <math>n\leq 28</math>.<ref>D. E. Knuth, "A note on solid partitions", Math. Comp., 24 (1970), 955–961.</ref> Mustonen and Rajesh extended the enumeration for all integers <math>n\leq 50</math>.<ref name="Mustonen">Ville Mustonen and R. Rajesh, "Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer", J. Phys. A: Math. Gen. '''36''' (2003), no. 24, 6651.[http://arxiv.org/abs/cond-mat/0303607 cond-mat/0303607]</ref> In 2010, S. Balakrishnan proposed a parallel version of Knuth's algorithm that has been used to extend the enumeration to all integers <math>n\leq 72</math>.<ref>Srivatsan Balakrishnan, Suresh Govindarajan and Naveen S. Prabhakar, "On the asymptotics of higher-dimensional partitions", J.Phys. A: Math. Gen. '''45''' (2012) 055001 [http://arxiv.org/abs/1105.6231 arXiv:1105.6231].</ref> One finds
:<math> p_3(72)=3464 27497 40651 72792\ ,</math>
which is a 19 digit number illustrating the difficulty in carrying out such exact enumerations.

== Asymptotic behavior ==

It is known that from the work of Bhatia et. al. that<ref>D P Bhatia, M A Prasad and D Arora, "Asymptotic results for the number of multidimensional partitions of an integer and directed compact lattice animals", J. Phys. A: Math. Gen. '''30''' (1997) 2281</ref>
:<math>
\lim_{n\rightarrow\infty} n^{-3/4}
\ln p_3(n) \rightarrow \text{a constant}.
</math>
The value of this constant was estimated using Monte-Carlo simulations by Mustonen and Rajesh to be <math>1.79\pm 0.01</math>.<ref name="Mustonen" />

== References ==


{{Reflist}}

== External links ==

* [http://oeis.org/A000293 OEIS entry for solid partitions]
* [http://boltzmann.wikidot.com/solid-partitions The Solid Partitions Project of IIT Madras]
* [http://mathworld.wolfram.com/SolidPartition.html The Mathworld entry for Solid Partitions]

[[Category:Enumerative combinatorics]]
[[Category:Number theory]]
[[Category:Combinatorics]]

Infinite loop space machine - Revision history

en>Alvin Seville: removing and categorizing