Refined counting of higher-dimensional partitions

It is useful to think of partitions in all dimensions on the same footing. This enables one to find structures and hence simpler counting problems. Many of these simpler counting problems can be reduced to counting skew partitions or equivalently all partitions that contain a fixed partition. This page will discuss aspects of this problem — both theoretical as well as computational.

The binomial transformation of $d$-dimensional partitions of $n$, $p_d(n)$, leads to a triangular matrix, $A=(a_{n,r})$. Explicitly, one has

(1)
\begin{align} p_d(n) = \sum_{r=0}^{n-1} \binom{d+1}{r}\ a_{n,r}\ , \end{align}

with $r=0,1,2,\ldots$, $a_{r+1,r}=1$ and $a_{n~r}=0$ when $r\geq n$. The A-matrix appeared for the first time in the 1967 work of Atkin et. al. [1]. It has been shown in [2] that $a_{n~r}$ counts the number of skew partitions/Ferrers diagrams of a particular kind. Using this combinatorial picture, the Bratley-McKay algorithm[3] has been modified by me to directly compute the triangle $A$. The matrix $A$ appears in the OEIS as sequence A119271.

Our Results

The major advance in [2] is the introduction of a new triangle, $F=(f_{n,r})$ defined by the following transform:

(2)
\begin{align} a_{m+r+1,r} = \sum_{x=0}^r \sum_{p=x}^{m} \binom{r}{x} \binom{\tbinom{r-x}2}{m-p} \ f_{p+x+1,\ x}\ . \end{align}

with $r=0,1,2,\ldots$ and more importantly $f_{n,r}=0$ when $r<[(n-1)/2]$. Thus, the F-matrix has roughly half the number of entries as the A-matrix. The F-matrix removes some reducible parts in the A-matrix that are easy to count. Hence, one ends up with the explicit transform given above. The first few rows of both matrices are given below for comparison.

(3)
\begin{align} A=\left( \begin{smallmatrix} 1 \\ 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 3 & 1 \\ 0 & 1 & 5 & 6 & 1 \\ 0 & 1 & 9 & 18 & 10 & 1 \\ 0 & 1 & 13 & 44 & 49 & 15 & 1 \\ 0 & 1 & 20 & 97 & 172 & 110 & 21 & 1 \\ 0 & 1 & 28 & 195 & 512 & 550 & 216 & 28 & 1 \\ 0 & 1 & 40 & 377 & 1370 & 2195 & 1486 & 385 & 36 & 1 \\ 0 & 1 & 54 & 694 & 3396 & 7603 & 7886 & 3514 & 638 & 45 & 1 \\ \end{smallmatrix} \right)\quad,\quad F=\left(\begin{smallmatrix} 1\\ 0 \\ 0&1 \\ 0& 1 \\ 0&1 & 3 \\ 0&1 & 7 \\ 0&1 & 11 & 16 \\ 0&1 & 18 & 58 \\ 0& 1 & 26 & 135 & 125 \\ 0& 1 & 38 & 293 & 618 \\ 0& 1 & 52 & 574 & 1927 & 1296 \end{smallmatrix}\right) \ . \end{align}

Online Partition Generator

Below a javascript (written by Arun Chaganty) computes partitions of all positive integers $n \leq 26$ in any dimension. You need to enter values of d and n and click on the compute button. The number of partitions then appears to the right.

Current state of the project — ongoing

  • [June 22, 2011] Arun K. Jayaraman implements the Bratley-McKay algorithm to generate higher-dimensional partitions in C. It is tested to reproduce known numbers. This is slower than the Knuth algorithm (as expected) that was used in the solid-partitions project but is more adaptable to the structures that appear in a forthcoming paper of mine[2].
  • [June 27, 2011] The Bratley-McKay algorithm is modified to count skew-partitions of a particular type and is working correctly. Further tests are being run.
  • [July 14, 2011] The modified BM algorithm generates a new number. One has $p_8(23)=578\ 16727\ 44441$.
  • [July 31, 2011] The modified BM algorithm generates a new number. $p_9(23)=30461884866225$
  • [Sept 22, 2011] Two new numbers produced by the modified BM algorithm. $p_{10}(23) = 135758936765513$ and $p_7(25)=7861971702653$. The first $23$ rows of the $A$-matrix are now determined without using conjectures. This implies that partitions of all positive integers $\leq 23$ in any dimension are determined by the formula given above. However, the data will be released once the manuscript is submitted to the arXiv.
  • [Feb 21, 2012] Preliminary draft of the manuscript titled Notes on higher-dimensions partitions is ready and will be posted on the arXiv in a week's time. Until then, enjoy experimenting with the javascript above (written by Arun Chaganty) which lets you find out what $p_{100}(23)$ might be.
  • [Feb 24, 2012] I got an unexpected email from Prof. Paul Bratley a few days back. He sends me a java implementation of the BM algorithm with some tricks as he put it. Among other things, his program directly enumerates the A-matrix — he calls partitions that contribute to the A-matrix strict partitions. This is a name that I like very much and will hereafter refer to them as such. So I have spent the last few days playing with his code and I find that it is a lot faster than my implementation. Here are two results using his code: $p_8(25)=60673478894826$ and $p_9(24)=107358976330035$.
  • [Feb 26, 2012] Paul Bratley's code generates one more number: $p_{10}(24)=514399682236550$. We have fully determined row 24 of the A-matrix — this is based in part on some conjectural formulae and hence will not be revealed. This ‘gap’ is being filled and the result will be incorporated into the above javascript. The current set of runs will continue until row 25 and hence partitions of 25 in any dimension will be determined. Meanwhile, we will be working on improving the algorithms so that we can determine partitions of integers $\leq 32=2^5$ in all dimensions.
  • [Feb 29, 2012] My attention is drawn to a fun note that predicts the existence of our results[4].
  • [Mar 20, 2012] Many of the conjectural formulae are proved and paves the way for the introduction of a new triangle that is denoted by $F$ — we have now completed determined 25 rows of the F-matrix and as a consequence 25 rows of the A-matrix. Hence partitions of 25 in any dimension have been determined. Row 26 is missing one entry, $f_{26,12}$.
  • [Mar 21, 2012] Paper [2] finally appears on the arXiv. The javascript now provides partitions of all integers up to 25. I plan on computing $f_{26,12}$ by hand!
  • [Mar 23, 2012] v2.0 of the code implementing the Bratley-McKay algorithm for the A-matrix is ready (thanks to Srivatsan) — it incorporates the parallelization suggested by Bratley in his java implementation. While it is somewhat slower than Bratley's java code, it is much faster than v1.0. We hope to make use of different data structures to get further improvement — that will be in the next version. It is being used to compute $a_{26,12}$, the only undetermined element in row 26.
  • [April 24, 2012] Took around 2 months to generate the number given below using Bratley's code and squeaked passed a scheduled downtime for the vega supercluster later this week. With this new data, I have determined partitions of all integers <=26 in any dimension. I will not be adding any more numbers until I am able to implement a direct enumeration of entries in the F-matrix.
(4)
\begin{align} a_{26,12}=594968843586906 \textrm{ and hence } p_{11}(26)=34248798860693371\ . \end{align}
  • [Aug 2, 2012] I have a working implementation of code that directly enumerates entries in the F-matrix in low dimensions (2 and 3 to be precise). As it stands one needs to treat each dimension separately but the main hope is that things can be automated. It would be nice to get help in figuring out this algorithm.
  • [Aug 15, 2012] Turned out to be more complicated than I expected. Now I have code that directly enumerates the F-matrix in 4 dimensions. The next step is to redo this code in a manner that might generalise to higher dimensions instead of the current scheme where one is writing a new program for each dimension.

Credits

Arun K. Jayaraman (for writing code for the modified Bratley-McKay algorithm), Paul Bratley (for his awesome Java code that is blazing fast), B. Srivatsan (for his code implementing Knuth's algorithm for solid partitions that was modifed to work for higher dimensions).

A couple of undergraduate students have expressed interest in implementing variations of the Bratley-McKay algorithm for me but I am yet to see any results. If you wish to help out, you can send an email to me at solidpartitions at gmail.com

Bibliography
1. A.O.L. Atkin, P. Bratley, I.G. Macdonald, and J.K.S. McKay, Some computations for $m$-dimensional partitions, Proc. Cambridge Philos. Soc. 63 (1967) 1097—1100. pdf
2. S. Govindarajan, Notes on higher-dimensional partitions arXiv:1203.4419 J. of Combinatorial Theory A (accepted).
3. P. Bratley and J. K. S. McKay, Algorithm 313: Multi-dimensional partition generator, Commun. ACM 10 (1967) 666

Page maintained by Suresh Govindarajan

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