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

Shalosh B. EKHAD and Doron ZEILBERGER^{1}

Consider lattice paths in the three-dimensional cubic lattice, with unit positive steps, that always stay in the region x ≥ y ≥ z. Let A_{b_{1},b_{2},b_{3}}(n) be the number of such walks of length n−(b_{1} +b_{2} +b_{3}) that start at [b_{1}, b_{2}, b_{3}]. For example, A_{0,0,0}(n) is the number of 3D-ballot paths (trivially isomorphic to ≤ 3-rowed Standard Young Tableaux with n cells).

In 1981 Amitai Regev[R1] (see also [S]) famously proved that A_{0,0,0}(n) is given by the Motzkin numbers: M(n) := ∑_{k=0}^{n/2} \frac{n!}{k!(k+1)!(n−2k)!}. A quarter-century later[R2], he conjectured (essentially) the following statement:

Regev’s Conjecture: A_{2,1,0}(n) = M(n − 1) − M(n − 3).

In this note we prove this conjecture. More generally, we present an algorithm to (automatically!) conjecture and then, immediately, rigorously (and automatically!) prove such statements for any given starting point [b_{1}, b_{2}, b_{3}]. It turns out that for all the starting points we looked at (b_{3} ≤ b_{2} ≤ b_{1} ≤ 20), there are similar expressions as linear combination of negative shifts of the Motzkin sequence M(n) (with constant coefficients).

Note that any such statement, in any dimension, once conjectured, is decidable via Wilf-Zeilberger theory and the holonomic ansatz, at least in principle. In practice, however, because of the multisums (or multi-integrals), it becomes unwieldy. We do know, however, that for any such conjecture, there exists a (computable!) number N_{0} (depending on the conjecture, of course) such that if we verify our conjecture for n ≤ N_{0}, then it is true for ever after. Since we are too lazy to actually find the N_{0}, we are content to verify the conjecture for say, n ≤ 200, and call that verification a semi-rigorous proof.

All our proofs for the three-dimensional case are fully rigorous, but the analogous statements for four dimensions are only semi-rigorous. In the four-dimensional case it turns out that for all the starting points we looked at (b_{4} ≤ b_{3} ≤ b_{2} ≤ b_{1} ≤ 10), there are expressions as linear combination of negative shifts of the sequence A_{0,0,0,0}(n) (with coefficients that are polynomials of degree 1 in n).

k-dimensions

Let

F (a_{1}, …, a_{k}) := \frac{(a_{1} + … + a_{k})!}{a_{1}! ⋯ a_{k}!} .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg . Dec. 8, 2006. Accompanied by Maple package AMITAI downloadable from Zeilberger’s website. Supported in part by the NSF.

Recall that the number of lattice paths from the origin to [a_{1}, …, a_{k}] is F (a_{1}, …, a_{k}). Hence the number of such paths from [b_{1}, …, b_{k}] to [a_{1}, …, a_{k}] is F (a_{1} −b_{1}, …, a_{k} −b_{k}). Introducing the shift operators A_{i} defined by A_{i}F := subs(a_{i} = a_{i} + 1 , F), this becomes A_{1}^{−b_{1}} ⋯ A_{k}^{−b_{k}}F (a_{1}, …, a_{k}). Now André’s famous and lovely reflection argument (generalized to many dimensions in [Z]) shows that the number of walks from b to a that never touch the hyperplanes x_{i}−x_{i+1} = −1, i = 1 … k−1, let’s call it G_{b}(a), equals

G_{b}(a) = ∑_{π∈S_{n}}(−1)^{inv(π)}F (a − π(b)) ,

where S_{n} is identified in a natural way with the group generated by the reflections about these hyperplanes, and π(b) is the image of the point b.

It follows that there exists an easily computable partial recurrence operator with constant coefficients P_{b}(A_{1}, …, A_{k}) (for each particular b) such that G_{b}(a) = P_{b}(A_{1}, …, A_{k})F (a_{1}, …, a_{k}).

Back to 3 dimensions

So for any starting point b, there is an operator P_{b}(A_{1}, A_{2}, A_{3}) such that G_{b}(a) = P_{b}(A_{1}, A_{2}, A_{3})F (a_{1}, a_{2}, a_{3}). By anti-symmetry, P_{b} is divisible by 1 − A_{1}A_{3}^{−1}, so we can write P_{b} = (1 − A_{1}A_{3}^{−1})Q_{b}(A_{1}, A_{2}, A_{3}), where Q_{b}(A_{1}, A_{2}, A_{3}) is another (just as easily computable!) operator.

Define H_{b}(a_{1}, a_{2}, a_{3}) = Q_{b}(A_{1}, A_{2}, A_{3})F (a_{1}, a_{2}, a_{3}), that for any specific b is a certain (easilycomputable!) rational function of (a_{1}, a_{2}, a_{3}) times (a_{1} + a_{2} + a_{3})!/(a_{1}!a_{2}!a_{3}!). So G_{b}(a_{1}, a_{2}, a_{3}) = H_{b}(a_{1}, a_{2}, a_{3}) − H_{b}(a_{1} + 1, a_{2}, a_{3} − 1). We now need a

Simple Lemma: Let f(a_{1}, a_{2}, a_{3}) be any discrete function defined on a_{1} ≥ a_{2} ≥ a_{3} that vanishes for negative arguments, and let g(a_{1}, a_{2}, a_{3}) = f(a_{1}, a_{2}, a_{3}) − f(a_{1} + 1, a_{2}, a_{3} − 1), then ∑ g(a_{1}, a_{2}, a_{3}), where the sum ranges over all triples with a_{1} ≥ a_{2} ≥ a_{3} ≥ 0 and a_{1} + a_{2} + a_{3} = n, equals

∑_{0≤k<n/3} f(n − 2k, k, k) + ∑_{n/3≤k≤n/2} f(k, k, n − 2k) .

Proof: First write it as a double-sum where the outer sum is w.r.t. a_{2} (ranging from 0 to n/2), and the inner sum w.r.t. all pairs a_{1}, a_{3} such that a_{1} + a_{3} = n − a_{2} and a_{1} ≥ a_{2} and a_{3} ≤ a_{2}. The inner sum telescopes to f(n−2a_{2}, a_{2}, a_{2}) for a_{2} < n/3 and to f(a_{2}, a_{2}, n−2a_{2}) for n/3 ≤ a_{2} ≤ n/2.

It follows that for any b = [b_{1}, b_{2}, b_{3}], A_{b}(n) can be written as a single-sum ∑_{k=0}^{n/3} H_{b}(n−2k, k, k)+ ∑_{k=n/3}^{n/2} H_{b}(k, k, n − 2k). For b = [0, 0, 0] it turns out that (both!) summands are F (n, k) := n!/(k!(k + 1)!(n − 2k)!), and we get Regev’s famous result. For b = [2, 1, 0] we get that (both!) summands, let’s call it, G(n, k) equals a certain (easily computable) rational function times F (n, k). We have to prove that a(n) := ∑_{k} G(n, k) − (F (n − 1, k) − F (n − 3, k)) is identically 0, but the summand of a(n), that is yet another rational function of (n, k) times F (n, k), turns out to be gosperable, (telescoping) as Maple testifies (applying sum to it gives a closed-form answer), and hence a(n) is indeed zero. QED.

You don’t have to be a Regev to make such conjectures (once you know, thanks to Regev, where to look!), and the Maple package AMITAI, accompanying this paper, automatically(!) makes such conjectures for any starting point b, and then proceeds to automatically(!!) prove them, using the approach outlined above for the original Regev conjecture.

Analogous conjectures (generalizing [G], where the starting point is the origin), alas, this time with only semi-rigorous proofs, can be made for the four-dimensional case and this is also implemented

in AMITAI.

Finally, we can easily use the above to derive explicit expressions (as linear combinations with constant coefficients of shifts, M(n − i), of the Motzkin sequence) for the number of n-celled Standard Young tableaux with at most three rows, where the entry at any given cell happens to be any given integer. This follows from the fact that this quantity can be written as a linear combination (that AMITAI can easily figure out for itself) of the quantities A_{b}(n) discussed previously.

The Maple package AMITAI, as well as sample input and output can be found in the webpage of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/regev.html .

In particular the file

http://www.math.rutgers.edu/~zeilberg/tokhniot/oAmitaiSipur310

lists all the explicit expressions, in terms of the Motzkin number sequence M(n), for the number of walks starting at [b_{1}, b_{2}, 0] for all 0 ≤ b_{2} ≤ b_{1} ≤ 10 (all rigorously proved!), while the file

http://www.math.rutgers.edu/~zeilberg/tokhniot/oAmitaiSipur45

lists all the explicit expressions, in terms of the sequence A_{0,0,0,0}(n) (that was proved in [G] to be C_{(n+1)/2}^{2} for n odd and C_{n/2}C_{n/2+1} for n even), for the number of walks starting at [b_{1}, b_{2}, b_{3}, 0] for all 0 ≤ b_{3} ≤ b_{2} ≤ b_{1} ≤ 5 ( semi-rigorously proved).

Finally the file

http://www.math.rutgers.edu/~zeilberg/tokhniot/oAmitaiSipur3with15

lists explicit expressions, in terms of the Motzkin numbers, for the number of three-rowed Standard Young Tableaux whose (i, j)-cell is occupied by the integer m for 1 ≤ m ≤ 15 and all feasible cells (i, j) (of course ij ≤ m).

Final Remarks

Regev[R2] raises the question of finding a bijective proof of his M(n − 1) − M(n − 3) conjecture. Similar questions can be raised for each of the many, more complicated, analogs, outputted by AMITAI. It would be interesting to find a uniform way of constructing such bijective proofs. It would be even more interesting to prove that there is no “natural” bijection (in a certain natural sense of natural), and the identities are true just because. References

[G] D. Gouyou-Beauchamps, Standard Young tableaux of height 4 and 5, Europ. J. Combin. 10 (1989) 69-82.

[R1] A. Regev, Asymptotic values for degrees associated with stripes of Young diagrams, Adv. Math. 41 (1981) 115-136.

[R2] A. Regev, Probabilities in the (k,l) Hook, preprint.

[S] R. Stanley, “Enumerative Combinatorics, Volume 2”, Cambridge studies in applied mathematics 62 , Cambridge University Press (1999).

[Z] D. Zeilberger, André’s reflection proof generalized to the many-candidate ballot problem, Discrete Math 44, 325-326 (1983).