Computational and Theoretical Challenges on Counting Solid Standard Young Tableaux

By
Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)

First Written: Feb. 20, 2012

Version of Feb. 28, 2012 [Thanks for Manuel Kauers and Fredrik Johansson]

In how many ways can you place n chocolate pieces all of different sizes in an n by n chocolate box, in such a way that when you go from left to right and from top to bottm, there are no gaps AND the sizes increase along each row and each column? The answer is the well-known Sloane Sequence Number 85. To our amazement, the analogous sequence for a three-dimensional chocolate box is not yet (Feb. 20, 2012) in Sloane. Here we fill this gap that was in great need of being filled, and more importantly, offer some computational and theoretical challenges that carry cash prizes ranging from 1 cent to 100 dollars. Good luck!

# Maple Package

• SolidSYT For counting and exploring Solid Standard Young Tableaux, and generating them at random.

The Maple package GreeneNijenhuisWilf is also mentioned in the article. It implements the amazing Greene-Nijenhuis-Wilf algorithm for generating, uniformly at random, a (usual, 2D) Standard Young Tableau.

# Sample Input and Output for SolidSYT

• If you want to see the first 30 terms (i.e. for n=1..30) of the sequence "number of Solid Standard Young Tableaux with n cells" (the 3D analog of the famous A00085, that counts the number of 2D Standard Young Tableaux with n cells, alias (thanks to Robinson-Schensted) the number of involutions on {1,...,n}, then
the input file would yield the output file

• If you want to see the number of Solid Young Tableaux of cylindrical 3D shapes for floors with at most 6 cells and up to height 20, then
the input file would yield the output file

• If you want to see the linear recurrence operator with polynomial coefficients (using the shift operator in n, N) annihilating the sequence "the number of Solid Standard Young Tableaux of shape [[n,n],[n,1]]" (which is the same as the "number of ways of walking, with positive unit steps in the 4D square lattice from the origin to the point (n,n,n,1) always staying in x1 ≥ x2, x1 ≥ x3, x2 ≥ x4, x3 ≥ x4") then
the input file would yield the output file

• If you want to see ten typical, uniformly-at-random Solid Standard Young Tableaux residung in the whose shape is a 5 by 5 by 3 box (so we have to place the integers 1 through 75 in the box such that they are increasing in each of the three directions), then
the input file would yield the output file

• If you want to see ten typical, but NOT QUITE uniformly-at-random, Solid Standard Young Tableaux whose shape is a 10 by 10 by 10 cube (so we have to place the integers 1 through 1000 in the cube such that they are increasing in each of the three directions), using the 3D analog of the amazing Greene-Nijenhus-Wilf algorithm, then
the input file would yield the output file

• If you want to see a polynomial expression, in n, for the number of Solid Standard Young Tableaux if shape
[[n,3,3],[3,3,3],[3,3,3]]
valid starting (of course) with n=3, and to see how one can get a the exact value (rigorusly!) for the number of SSYTs of shape
[[10100,3,3],[3,3,3],[3,3,3]]
the input file would yield the output file

• If you want to see the "number of Solid Standard Young Tableaux" of shape
[[n,n,n],[n]]
for 1 ≤ n ≤ 121
the input file would yield the output file
Added Feb. 28, 2012: Manuel Kauers, and his student, Fredrik Johansson, supplied much more data.

Added March 2, 2012: Manuel Kauers and Fredrik Johansson informed us that 6000 terms do not suffice to find a linear recurrence, in other words, if there is such a linear recurrence equation with polynomial coefficients of order ORDER and degree DEGREE, then
(1+ORDER)(1+DEGREE) ≥ 2999

# Sample Input and Output for the Maple package GreeneNijenhisWilf

• If you want to see ten "typical", uniformly-at-random (usual, 2D) Standard Young Tableaux whose shape is a 20 by 20 square, using the (original) amazing Greene-Nijenhuis-Wilf algorithm, then
the input file would yield the output file .

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger