Counting Solid Partitions

Partitions

A partition of an integer $n$, is a weakly decreasing sequence $(a_1,a_2,\ldots )$ such that

  • $\sum_i a_i= n$ and
  • $a_{i+1}\leq a_{i}\quad \forall i$ (this is the weakly decreasing condition).

For instance, $(2,1,1)$ is a partition of $4$. Define $p_1(n)$ to be the number of partitions of $n$. For instance,

(1)
\begin{align} 4=3+1=2+2=2+1+1=1+1+1+1 \quad \implies \quad p_1(4)=5\ . \end{align}

A slightly more formal way of defining a partition to be a map from $\mathbb{Z}_{>0}$ to $\mathbb{Z}_{\geq0}$ satisfying the two conditions mentioned above. This definition enables one to generalise to higher dimensional partitions. A d-dimensional partition of $n$ is defined to be a map from $\mathbb{Z}_{>0}^d$ to $\mathbb{Z}_{\geq0}$ such that it is weakly decreasing along all directions and the sum of all its entries add to $n$. Let us denote by $(a_{i_1,i_2,\ldots,i_d})$ the partition. The weakly decreasing condition along the $r$-th direction implies that

(2)
\begin{align} a_{i_1,i_2,\ldots,i_r+1,\ldots, i_d}\leq a_{i_1,i_2,\ldots,i_r,\ldots i_d}\quad \forall\ (i_1,i_2,\ldots,i_d)\ . \end{align}

Two-dimensional partitions are called plane partitions while three-dimensional partitions are called solid partitions.
For instance, the two-dimensional or plane partitions of $4$ are

(3)
\begin{align} \begin{smallmatrix} 4 \end{smallmatrix} \quad \begin{smallmatrix} 3 & 1 \end{smallmatrix} \quad \begin{smallmatrix} 3 \\ 1 \end{smallmatrix} \quad \begin{smallmatrix} 2 & 2 \end{smallmatrix} \quad \begin{smallmatrix} 2 \\ 2 \end{smallmatrix} \quad \begin{smallmatrix} 2 & 1 & 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} \quad \begin{smallmatrix} 1 & 1 \\ 1 &1 \end{smallmatrix} \quad \begin{smallmatrix} 1 & 1 \\ 1 \\ 1 \end{smallmatrix} \quad \begin{smallmatrix} 1 \\ 1 \\ 1 \\ 1 \end{smallmatrix} \quad \implies \quad p_2(4)=13\ . \end{align}

Let us denote by $p_d(n)$ the number of d-dimensional partitions of $n$. It is useful to define the generating function of these partitions by ($p_d(0)\equiv 1$)

(4)
\begin{align} \boxed{ g_d(q) \equiv \sum_{n=0}^\infty p_d(n)\ q^n\ . } \end{align}

The generating functions of one and two-dimensional partitions have very nice product representations. One has the Euler formula for the generating function of partitions

(5)
\begin{align} g_1(q) = \frac1{\prod_{n=1}^\infty (1-q^n)}\ , \end{align}

and the MacMahon formula for the generating function of plane partitions

(6)
\begin{align} g_2(q) = \frac1{\prod_{n=1}^\infty (1-q^n)^n}\ . \end{align}

MacMahon guessed a formula for the generating functions for $d>2$ that turned out to be incorrect.

(7)
\begin{align} \boxed{ g_d(q)\stackrel{?}{=} \frac1{\prod_{n=1}^\infty (1-q^n)^{\binom{n+d-2}{d-1}}}\ . } \end{align}

This guess fails for $d>2$. For instance, expanding the above product for solid partitions i.e., $d=3$

(8)
\begin{align} g_3(q)\neq 1+q+4 q^2 + 10 q^3 + 26 q^4 + 59 q^5 + \mathbf{141} q^6 + \cdots \end{align}

one see that the coefficient of $q^6$ comes with the wrong coefficient (see exact values given below). However, Rajesh and Mustonen seem to claim that the formula nevertheless captures the asymptotics correctly.

A general formula (given for instance in the book by Andrews) for the number of $d$-dimensional partitions of $6$ is

(9)
\begin{align} p_d(6)=1+ 10d + 27 \binom{d}2 + 28 \binom{d}3 + 11\binom{d}4 + \binom{d}5\ . \end{align}

Let us denote by $m_d(6)$, the number given by MacMahon's generating function. Then, one can show that

(10)
\begin{align} m_d(6)-p_d(6)=\binom{d}3+\binom{d}4\ , \end{align}

which is non-vanishing for $d\geq 3$. Thus the MacMahon generating function fails when $d\geq3$.

Statement of the problem

This was the problem posed to a bunch of IIT Madras undergraduates (in September 2010) who meet under the auspices of the Boltzmann group.

Write a program to compute $p_3(n)$ for $n\leq 100$.

Why bother enumerating solid partitions?

There are several answers to this important question.

  • because they are there to be enumerated (akin to the apocryphal response of Sir Edmund Hillary George Mallory as to why he attempted to climb Mt. Everest)
  • There might be structures/patterns that are waiting to be discovered.
  • A practical reason is that this problem is simple to state and is accessible to undergraduates. Their minds are uncluttered by too much knowledge and might open up fresh lines of thought.
  • I also like Doron Zeilberger's response to receiving the 1998 Steele Prize. Here is a quote from that response: "WZ theory has taught me that computers, by themselves, are not yet capable of creating the most beautiful math. Conversely, humans do much better math in collaboration with computers. More generally, combining different and sometimes opposite approaches and viewpoints will lead to revolutions. So the moral is: Don't look down on any activity as inferior, because two ugly parents can have beautiful children, and a narrow-minded or elitist attitude will lead nowhere."

History

  1. Atkin, Bratley, Macdonald and McKay showed that the MacMahon formula fails. For instance, for $p_3(6)$ the formula gives $141$ instead of $140$.
  2. Knuth computed the first 28 numbers using an Algol program.
  3. Mustonen and Rajesh extended this computation to obtain the number of solid partitions of numbers $\leq 50$.
  4. The numbers have been extended by a group at IIT Madras and now one knows the number of solid partitions of numbers $\leq 72$.

The number of solid partitions for the first sixty-two numbers are listed below. The first fifty (now it is seventy two as our numbers have been added) are listed in the On-Line Encyclopedia of Integer Sequences and twenty two new numbers have been added by the IITM Group.

1,1,4,10,26,59,140,307,684,1464,
3122,6500,13426,27248,54804,108802,214071,416849,805124,1541637,
2930329,5528733,10362312,19295226,35713454,65715094,120256653,218893580,396418699,714399381,
1281403841,2287986987,4067428375,7200210523,12693890803,22290727268,38993410516,67959010130,118016656268,
204233654229, 352245710866,605538866862,1037668522922,1772700955975,3019333854177,
5127694484375,8683676638832,14665233966068,24700752691832,41495176877972,69531305679518,

116221415325837, 193794476658112, 322382365507746, 535056771014674, 886033384475166,
1464009339299229, 2413804282801444, 3971409682633930, 6520649543912193,
10684614225715559, 17472947006257293, 28518691093388854

Estimates: $p_3(100)\sim 10^{24}$ Clearly, one needs to handle large numbers. Should one use the GNU MP Library?

References

  1. A O L Atkin, P Bratley, I G Macdonald and J K S McKay, Proc. Cambridge Philos. Soc. 63 (1967) 1097–1100.
  2. D E Knuth, A note on solid partitions, Mathematics of Computation Vol 24, No. 112 (1970) 955-961
  3. Ville Mustonen, R. Rajesh, Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer, arXiv:cond-mat/0303607
  4. Steven Finch, Integer partitions, pdf file
  5. Herbert S. Wilf, Lectures on integer partitions, PIMS lectures (pdf file)
  6. R. Rajesh's page on Partitions.
  7. G. E. Andrews, The theory of partitions, Cambridge University Press.

This page is maintained by Suresh Govindarajan

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License