%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}} \def1円{{\overline{1}}} \def2円{{\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

AltStyle によって変換されたページ (->オリジナル) /