%regev.tex:
%%a Plain TeX file by Doron Zeilberger (4 pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%end macros
\bf
\centerline
{
Proof of a Conjecture of Amitai Regev about Three-Rowed
Young Tableaux (and much more!)
}
\rm
\bigskip
\centerline{ {\it
Shalosh B. EKHAD and Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg} .
Dec. 8, 2006.
Accompanied by Maple package {\eighttt AMITAI}
downloadable from Zeilberger's website.
Supported in part by the NSF.
}
}

Consider lattice paths in the three-dimensional cubic
lattice, with unit positive steps, that always
stay in the region $x \geq y \geq 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 $\leq 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 {\it Motzkin numbers}:
$M(n):=\sum_{k=0}^{n/2} {{n!} \over {k!(k+1)!(n-2k)!}}$.
A quarter-century later[R2], he conjectured (essentially) the
following statement:

{\bf 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!) {\it conjecture} and then, immediately, {\bf rigorously}
(and automatically!)
prove such statements for {\it any} given starting point $[b_1,b_2,b_3]$.
It turns out that for all the starting points we looked
at ($b_ 3 \leq b_2\leq b_1 \leq 20$), there are similar expressions
as linear combination of negative shifts of the Motzkin sequence $M(n)$
(with {\bf constant} coefficients). 

Note that any such statement, in any {\it dimension}, once conjectured,
is decidable via Wilf-Zeilberger theory and the {\it 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 {\it 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 \leq 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 \leq 200$, and call that verification
a {\bf 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 \leq b_ 3 \leq b_2\leq b_1 \leq 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$). 

{\bf k-dimensions}

Let
$$
F(a_1, \dots, a_k):=
{{(a_1+ \dots + a_k)!} \over {a_1! \cdots a_k!}} \quad.
$$
Recall that the number of lattice paths from
the origin to $[a_1, \dots , a_k]$ is $F(a_1, \dots, a_k)$.
Hence the number of such paths from $[b_1, \dots, b_k]$
to $[a_1, \dots , a_k]$ is $F(a_1-b_1, \dots , 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} \cdots A_k^{-b_k} F(a_1, \dots , a_k)$.
Now Andr\'e'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 \dots k-1$,
let's call it $G_b(a)$, equals
$$
G_b(a)=\sum_{\pi \in S_n} (-1)^{inv(\pi)} F(a-\pi(b)) \quad ,
$$
where $S_n$ is identified in  a natural way with the group 
generated by the reflections about these hyperplanes,
and $\pi(b)$ is the image of the point $b$.

It follows that there exists an easily
computable {\it partial recurrence operator
with constant coefficients} $\P_b(A_1, \dots , A_k)$ 
(for each particular $b$)
such that $G_b(a)=\P_b(A_1, \dots, A_k) F(a_1, \dots , a_k)$.

{\bf 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_1A_3^{-1}$, so we can write
$\P_b=(1-A_1A_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 {\it specific} $b$ is a certain
(easily-computable!) 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

{\bf Simple Lemma}: Let $f(a_1,a_2,a_3)$ be any discrete
function defined on $a_1 \geq a_2 \geq 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 $\sum g(a_1,a_2,a_3)$,
where the sum ranges over all triples with $a_1 \geq a_2 \geq a_3 \geq 0$
and $a_1+a_2+a_3=n$, equals
$$
\sum_{0 \leq k < n/3} f(n-2k,k,k)+
\sum_{n/3 \leq k \leq n/2} f(k,k,n-2k) \quad.
$$

{\bf 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 \geq a_2$ and $a_3 \leq 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 \leq a_2 \leq n/2$.

It follows that for {\it any} $b=[b_1,b_2,b_3]$,
$A_b(n)$ can be written as a {\bf single-sum} 
$\sum_{k=0}^{n/3} H_b(n-2k,k,k)+\sum_{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):=\sum_{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 {\it gosperable},
(telescoping) as Maple testifies (applying {\tt 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 {\tt AMITAI}, accompanying this paper,
{\it automatically}(!) makes such conjectures
for {\it any} starting point $b$, and then proceeds
to {\it 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 {\tt 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 {\it any} given cell happens to be {\it any} given integer.
This follows from the fact that this quantity can be
written as a linear combination (that {\tt AMITAI} can
easily figure out for itself) of the quantities 
$A_b(n)$ discussed previously.

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

{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/regev.html} .

In particular the file

{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/oAmitaiSipur310} 

lists {\it 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 \leq b_2 \leq b_1 \leq 10$
(all rigorously proved!), while the file

{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/oAmitaiSipur45} 

lists {\it 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 \leq b_3 \leq b_2 \leq b_1 \leq 5$
( semi-rigorously proved).

Finally the file 

{\eighttt 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 \leq m \leq 15$
and all feasible cells $(i,j)$ (of course $ij \leq m$).

{\bf Final Remarks}

Regev[R2] raises the question of finding a {\it 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 {\tt AMITAI}.
It would be {\it interesting} to find a {\it uniform } way of
constructing such bijective proofs. It would be even {\bf more interesting}
to prove that there is no ``natural'' bijection (in a certain natural
sense of natural), and the identities are true {\bf just because}.

{\bf References}

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

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

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

[S] R. Stanley, ``{\it Enumerative Combinatorics, Volume 2}'',
Cambridge studies in applied mathematics {\bf 62} ,
Cambridge University Press (1999).

[Z] D. Zeilberger, {\it  Andr\'e's reflection proof generalized to 
the many-candidate ballot problem}, Discrete Math {\bf 44}, 325-326 (1983). 

\end




 
