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
Doron Zeilberger's Home Page