Proof of a Conjecture of Amitai Regev about Three-Rowed Young Tableaux (and much more!)

By Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex  
Written: Dec. 8, 2006.
Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
I grew up in Kiryat Motzkin, so I particularly like the Motzkin numbers. (The town is named after Leo Motzkin, the numbers after his son Theodore Motzkin). Amitai Regev, back in 1981, proved that the number of three-rowed Young-tableaux witb n cells equals the Motzkin number M(n), and very recently, he conjectured that the number of three-rowed Young tableaux of n cells where the "3" entry occupies the (1,2)-cell is M(n-1)-M(n-3). In this paper, Shalosh and I prove this conjecture, and make lots of similar conjectures and prove them at the same time.
Important: This article is accompanied by Maple package AMITAI that automatically conjectures and then automatically proves closed-form expressions for the number of ballot paths of n steps starting at an arbitrary point in three dimensions. It also makes conjectures for such expressions in four dimensions but only proves them semi-rigorously.

Sample Input and Output
  • If you want a verbose proof of the original conjecture, the input file will produce the output file
  • If you want the statement and its verbose proof for the number of walks starting at [4,2,0] the input file will produce the output file
  • If you want the statement and its verbose proof for the number of walks starting at [6,4,0] the input file will produce the output file
  • If you want closed-formed expressions, phrased in terms of the Motzkin sequence M(n), that are completely rigorously proved for n-step walks that start at points [b1,b2,0] with b1 ranging from 0 to 10 and b2 from 0 to b1, the input file will produce the output file
  • If you want closed-formed expressions, completely rigorously proved, phrased in terms the Motzkin sequence for the number of Young tableaux with n cells and at most 3 rows, and such that the [i,j] entry has m in it, for m between 1 and 15 and all possible [i,j] (of course i<=3 and i*j<=m) the input file will produce the output file
  • If you want closed-formed expressions, completely rigorously proved for n-step walks that start at points [b1,b2,b3,0] with b1 ranging from 0 to 5 and b2 from 0 to b1, and b3 from 0 to b2, the input file will produce the output file
Added Jan. 15, 2007: This article was submitted to Journal of Integer Sequences, and accepted subject to minor revisions, and to reformatting it in LaTeX. Since we didn't agree with the minor revisions, and do not have time to reformat it in LaTeX, we decided to publish it in our Personal Journal.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page