Solid partition explained
In mathematics, solid partitions are natural generalizations of integer partitions and plane partitions defined by Percy Alexander MacMahon.[1] A solid partition of
is a three-dimensional array of non-negative integers
(with indices
) such that
and
ni+1,j,k\leqni,j,k,
ni,j+1,k\leqni,j,k and
ni,j,k+1\leqni,j,k
for all
Let
denote the number of solid partitions of
. 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
Andrews.
[2] Ferrers diagrams for solid partitions
Another representation for solid partitions is in the form of Ferrers diagrams. The Ferrers diagram of a solid partition of
is a collection of
points or
nodes,
, with
satisfying the condition:
[3] Condition FD: If the node
, then so do all the nodes
with
for all
.
For instance, the Ferrers diagram
\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) ,
where each column is a node, represents a solid partition of
. There is a natural action of the permutation group
on a Ferrers diagram – this corresponds to permuting the four coordinates of all nodes. This generalises the operation denoted by conjugation on usual partitions.
Equivalence of the two representations
Given a Ferrers diagram, one constructs the solid partition (as in the main definition) as follows.
Let
be the number of nodes in the Ferrers diagram with coordinates of the form
where
denotes an arbitrary value. The collection
form a solid partition. One can verify that condition FD implies that the conditions for a solid partition are satisfied.
Given a set of
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
, add
nodes
for
to the Ferrers diagram. By construction, it is easy to see that condition FD is satisfied.
For example, the Ferrers diagram with
nodes given above corresponds to the solid partition with
n1,1,1=n2,1,1=n1,2,1=n1,1,2=n2,2,1=1
with all other
vanishing.
Generating function
Let
. Define the generating function of solid partitions,
, by
P3(q)
p3(n)qn=1+q+4q2+10q3+26q4+59q5+140q6+ … .
The generating functions of
integer partitions and
plane partitions have simple product formulae, due to
Euler and
MacMahon, respectively. However, a guess of
MacMahon fails to correctly reproduce the solid partitions of 6. It appears that there is no simple formula for the generating function of solid partitions; in particular, there cannot be any formula analogous to the product formulas of Euler and MacMahon.
[4] 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.[5] In 1970, Knuth proposed a different algorithm to enumerate topological sequences that he used to evaluate numbers of solid partitions of all integers
.
[6] Mustonen and Rajesh extended the enumeration for all integers
.
[7] In 2010, S. Balakrishnan proposed a parallel version of Knuth's algorithm that has been used to extend the enumeration to all integers
.
[8] One finds
p3(72)=3464274974065172792 ,
which is a 19 digit number illustrating the difficulty in carrying out such exact enumerations.
Asymptotic behavior
It is conjectured that there exists a constant
such that
[9] [10]
External links
Notes and References
- P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 2, p 332.
- G. E. Andrews, The theory of partitions, Cambridge University Press, 1998.
- 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.
- Book: Stanley, Richard P.. Richard P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press. 1999. 402.
- P. Bratley and J. K. S. McKay, "Algorithm 313: Multi-dimensional partition generator", Comm. ACM, 10 (Issue 10, 1967), p. 666.
- D. E. Knuth, "A note on solid partitions", Math. Comp., 24 (1970), 955–961.
- 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.cond-mat/0303607
- Srivatsan Balakrishnan, Suresh Govindarajan and Naveen S. Prabhakar, "On the asymptotics of higher-dimensional partitions", J.Phys. A: Math. Gen. 45 (2012) 055001 arXiv:1105.6231.
- Destainville, N., & Govindarajan, S. (2015). Estimating the asymptotics of solid partitions. Journal of Statistical Physics, 158, 950-967
- 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