Counting Standard Young Tableaux With Restricted Runs

Counting Standard Young Tableaux With Restricted Runs
By Manuel Kauers and Doron Zeilberger

.pdf .ps .tex

First Written: June 21, 2020. This version (version 2): Aug. 8, 2020.

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)
Dedicated to the legendary enumerators Ian Goulden and David Jackson

Added July 27, 2020: This article was originally submitted to the electronic journal ``Algebraic Combinatorics'' founded by Goulden and Jackson, following a solicitation for a special issue in honor of Goulden and Jackson. On July 27, 2020 we got an email message from one of the editors-in-chief, Akihiro Munemasa, informing us that, after an initial review, it is ``unlikely to meet the standards of depth and originality that the journal is seeking''. Consequently this article will remain in the `Personal journal of Shalosh B. Ekhad and Doron Zeilberger', the homepage of Manuel Kauers, and of course arxiv.org. Let the readers decide about its depth and originality. We are disappointed at the editors of Algebraic Combinatorics for their erroneous and misguided decision.
Regarding this unfortunate decision, read this recent opinion .
Added Aug. 11, 2018: read the appendix to the above opinion Why co-EIC Akihiro MUNEMASA and Steering Committee Head Sara BILLEY of the Electronic Journal ALCO (Algebraic Combinatorics) Seriously Erred in Rejecting (w/o Refereeing) the Kauers-Zeilberger submission about Counting Young Tableaux".

Added Oct. 22, 2020: Watch my lecture at the Manuel Kauers seminar, Oct. 22, 2020, How the Beautiful Duckling of Enumerative Combinatorics turned into the Ugly Swan of Algebraic Combinatorics

The number of Young Tableaux whose shape is a k by n rectangle is famously (nk)! 0! ... (k-1)!/((n+k-1)!(n+k-2)!... n!) implying that for each specific k, that sequence satisfies a linear recurrence equation with polynomial coefficients of the FIRST order. But what about counting Young tableaux where certain "run lengths" are forbidden? Then things seem to get much more complicated. In this tribute to the legendary enumerative pair "Goulden-Jackson" we investigate these intriguing sequences. We conclude with four intriguing conjectures, and will be happy to donate $200 dollars to the OEIS in honor of the first prover, for each of them.

Maple packages

YoungT.txt
A Maple package to count both words and tableaux where certain run-lentghs are forbidden.

Tableaux3R.txt A short Maple package, a very special case of the above, but faster for the special case of generating the first N terms of the sequence enumearting Young tableaux of shape [n,n,n] where there is no run of length 1 (given by procedure SeqG(N)) and the first N term of the enumerating sequence where all runs are odd, given by procedure SeqH(N).

C programs

Gseq.c A C program to compute many terms of the G-sequence of our paper modulo primes

Hseq.c A C program to compute many terms of the H-sequence of our paper modulo primes

Sample Input and Output Files for YoungT.txt

If you want to see various such sequences in 2, 3, and 4 dimensions
the input file yields the output file

If you want to see the first 100 terms of sequences of various sequences enumerating 3 by n Young tableaux where each row is either unrestricted or can't have a run of length 1 (altogether 8 cases), together with their ESTIMATED (non-rigorous) asympototics
the input file yields the output file

If you want to see the first 100 terms of sequences of various sequences enumerating 3 by n Young tableaux where each row is not allowed to have run-lengths that belong to some arithmetical progression and their ESTIMATED (non-rigorous) asympototics
the input file yields the output file

Added Aug. 10, 2020: As beautifully proved in the paper, the analogous family of sequences counting Lattice Walks from the origin to [n,...,n] with restricted runs is P-recursive, albeit possibly fairly complex. To see the linear recurrence of order 13 (and degree 10) satisfied by the sequence: number of lattice walks from [0,0,0] to [n,n,n] where each run (consecutive segment in one direction) is of length 2.
the input file yields the output file

Sample Input and Output Files for Tableaux3R.txt

If you want to see the first 200 terms of the sequence enumerating Young Tableaux of shape [n,n,n] where no row can have no consecutive integers
the input file yields the output file
Here are the the first 995 terms (using a larger computer)
If you want to see the first 200 terms of the sequence enumerating Young Tableaux of shape [n,n,n] where no row can have even-lengths runs (in other words every run in every row is of odd length)
thhe input file yields the output file
Here are the the first 965 terms (using a larger computer)

Papers of Doron Zeilberger
Doron Zeilberger's Home Page