Bender-Knuth Correspondence

Theorem[Bender-Knuth]: There is a one-to-one correspondence between plane partitions of $N$, on the one hand, and infinite matrices $a_{ij}$ ($i,j\geq 1$) of non-negative integer entries which satisfy

(1)
\begin{align} \sum_{r=1}^\infty r\ \left(\sum_{i+j=r+1} a_{ij}\right)=N\ , \end{align}

on the other.
Exercise: Construct a bjiection between the above matrices and plane partitions of $N$. See page 83 upwards of the book, Combinatorial Algorithms by Nijenhuis and Wilf to see details of how the bijection works.

The natural generalization for a matrix analog of solid partitions would be the following. Consider the infinite hypermatrices $a_{ijk}$ ($i,j,k\geq 1$) of non-negative integer entries which satisfy

(2)
\begin{align} \sum_{r=1}^\infty r\ \left(\sum_{i+j+k=r+1} a_{ijk}\right)=N\ . \end{align}

Claim: The number of hypermatrices is generated by MacMahon's formula i.e., the one that gave the wrong answer for solid partitions.

Exercise: Attempt to construct a bjiection between the above matrices and solid partitions of $N$. See if it fails precisely where the MacMahon formula fails i.e., at $N=6$.

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