%regevHook.tex: Proof of a Conjecture of Amitai Regev About Hook multi-sets
%%a Plain TeX file by Doron Zeilberger (x 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
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Proof of a Conjecture of Amitai Regev About Hook Multi-Sets
}
\rm
\bigskip
\centerline{ {\it
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} .
Sept. 13, 2009.
Exclusive to the Personal Journal of Ekhad and Zeilberger and arxiv.org .
Supported in part by the NSF.
}
}

Given an integer-partition $\lambda \vdash n$ and a box (a cell) $v=[i,j] \in \lambda$ 
it determines the arm length $a_v$ ($=\lambda_i-j$), the leg length $l_v$
(=$\lambda'_j-i$), and the left length $f_v$ ($=j-1$). Fill $v$ with a pair of numbers in
two different ways:

{\bf First Filling}: Fill $v$ with $(a_v,l_v)$.

{\bf Second Filling}: Fill $v$ with $(a_v,f_v)$.

This yields the following two multi-sets of pairs:
$$
A_1(n)= \bigcup_{\lambda \vdash n} \{ ( a_v,l_v ) \vert v \in \lambda \} \quad ,
$$
$$
A_2(n)= \bigcup_{\lambda \vdash n} \{ ( a_v,f_v ) \vert v \in \lambda \} \quad .
$$


The purpose of this short note is to prove Amitai Regev[R]' intriguing

{\bf Conjecture:} For all non-negative integers $n$, $A_1(n)=A_2(n)$.

As usual, $(z)_a:=(1-z)(1-qz) \cdots (1-q^{a-1} z)$.

The conjecture would follow from the following two lemmas.

{\bf Lemma 1}: Let $M_1(c,d)(n)$ be the number of times the pair $(c,d)$ shows up in $A_1(n)$, then
$$
\sum_{n=0}^{\infty} M_1(c,d)(n)q^n = {{q^{c+d+1}} \over {1-q^{c+d+1}}} \cdot {{1} \over {(q)_\infty}} \quad.
\eqno(1)
$$

{\bf Lemma 2}: Let $M_2(c,d)(n)$ be the number of times the pair $(c,d)$ shows up in $A_2(n)$, then
$$
\sum_{n=0}^{\infty} M_2(c,d)(n)q^n = {{q^{c+d+1}} \over {1-q^{c+d+1}} } \cdot {{1} \over {(q)_\infty}} \quad.
\eqno(2)
$$


{\bf Proof of Lemma 2}: $M_2(c,d)(n)$ counts the number of Ferrers diagrams of $n$ where one of the cells
that has (right) arm $c$ and left-arm $d$ is {\bf marked}.
Obviously it belongs to a row of length $c+d+1$, and each such row
has exactly one such cell. Hence this is the same as counting the number of Ferrers diagrams of $n$ where one
of the rows of length $c+d+1$ is marked. We can construct such a Ferrers diagram (with any number of cells)
by first drawing that row of length $c+d+1$ (weight $q^{c+d+1}$) then putting {\bf below} it an arbitrary
Ferrers diagram with largest part $\leq c+d+1$, whose generating function is
$1/((1-q)(1-q^2) \cdots (1-q^{c+d+1}))$, and then placing {\bf above} the above-mentioned fixed row
any Ferrers diagram whose {\it smallest} part is $\geq c+d+1$, 
whose generating function is
$1/((1-q^{c+d+1})(1-q^{c+d+2}) \cdots )$. Combining, we get that the 
generating function
of such marked creatures, which is the left side of $(2)$, is the right side of $(2)$ \halmos.


Before proving Lemma 1 we have to recall certain basic facts from $q$-land.


{\bf Fact 1} (The $q$-Binomial Theorem)
$$
{{1} \over {(z)_{a+1}}}=
\sum_{j=0}^{\infty} {{ (q)_{a+j}} \over {(q)_a (q)_j}} z^j \quad .
$$
(This is easily proved by induction on $a$).

When $a=\infty$ this simplifies to

{\bf Fact 2} 
$$
{{1} \over {(z)_{\infty}}}=
\sum_{j=0}^{\infty} { {z^j} \over {(q)_j}} \quad .
$$

{\bf Fact 3}: The generating function for Ferrers diagrams bounded in an
$m$ by $n$ rectangle is ${ {(q)_{m+n}} \over {(q)_m (q)_n}}$.


(Let's recall the proof of this elementary fact.
Let the generating function be $F(m,n;q)$. Consider the last cell of the top row. 
If it is occupied, the generating function of these diagrams is $q^nF(m-1,n)$ (remove the fully-occupied top row), if it is not, it is $F(m,n-1)$
(delete the empty rightmost column), getting the recurrence $F(m,n;q)=q^nF(m-1,n;q)+F(m,n-1;q)$. Then verify that the same
recurrence is satisfied by ${ {(q)_{m+n}} \over {(q)_m (q)_n}}$, and check the trivial initial conditions $m=0$ and $n=0$.)

{\bf Proof of Lemma 1}: The left-side of $(1)$ is the generating function for Ferrers diagrams where one {\bf hook}
with arm-length $c$ and leg-length $d$ is {\bf marked}. Let's figure out the generating function (weight-enumerator)
for all such $(c,d)$-hook-marked Ferrers  diagrams.

  Suppose  the corner of that hook is at cell $(i+1,j+1)$ (i.e. the $(i+1)$-row and the $(j+1)$-column).
Here $0 \leq i < \infty$ and  $0 \leq j < \infty$.
Let's look at its {\it anatomy}. It consists of {\bf seven parts}.

{\bf 1.} Strictly {\bf left of} {\it and} {\bf above} cell $(i+1,j+1)$. 
This is a fully occupied  $i$ by $j$ rectangle with weight $q^{ij}$.

{\bf 2.} Above the arm (of length $c+1$). 
This is a fully occupied  $i$ by $c+1$ rectangle with weight $q^{(c+1)i}$ .

{\bf 3.} To the left of the leg (of length $d+1$). 
This is a fully occupied  $d+1$ by $j$ rectangle with weight $q^{(d+1)j}$ .

{\bf 4.} The Ferrers diagram with $\leq i$ rows lying {\bf above and to the right} of the arm.
The generating function of this is $1/(q)_i$.

{\bf 5.} The Ferrers diagram with $\leq j$ columns lying {\bf below and to the left} of the leg.
The generating function of this is $1/(q)_j$.

{\bf 6.} The hook itself. This gives generating function $q^{c+d+1}$.

{\bf 7.} The Ferrers diagram formed {\bf inside} the hook, i.e. lying below the
arm and to the right of the leg. By Fact 3 its generating function is
${ {(q)_{c+d}} \over {(q)_c (q)_d}}$.

Combining, we see that the generating function for these $(c,d)$-hook-marked Ferrers diagrams is
$$
{ {(q)_{c+d}} \over {(q)_c (q)_d} } \cdot q^{c+d+1} \cdot q^{ij+i(c+1)+j(d+1)} \cdot {{1} \over {(q)_i}}
\cdot {{1} \over {(q)_j}} \quad .
$$

Summing over {\bf all} $0 \leq i,j < \infty$, we get that the generating function on the left of $(1)$ equals
$$
{ {(q)_{c+d}} \over {(q)_c (q)_d} }  q^{c+d+1} 
\sum_{i=0}^{\infty} \sum_{j=0}^{\infty}
 q^{ij+i(c+1)+j(d+1)} {{1} \over {(q)_i}}
 {{1} \over {(q)_j}}
$$
$$
=
{ {(q)_{c+d}} \over {(q)_c (q)_d} } q^{c+d+1} 
\sum_{i=0}^{\infty} 
{{1} \over {(q)_i}}
q^{i(c+1)} 
\sum_{j=0}^{\infty}
q^{j(i+d+1)} 
{{1} \over {(q)_j}} \quad
$$
$$
=
{ {(q)_{c+d}} \over {(q)_c (q)_d} } q^{c+d+1} 
\sum_{i=0}^{\infty} 
{{1} \over {(q)_i}}
q^{i(c+1)} {{1} \over {(q^{d+i+1})_\infty}} \quad ,
$$
by Fact 2 with $z=q^{d+i+1}$). This equals
$$
{ {(q)_{c+d}} \over {(q)_c } } q^{c+d+1} 
\sum_{i=0}^{\infty} q^{i(c+1)} {{1} \over {(q)_{\infty}}} {{(q^{i+1})_d} \over {(q)_d} }
$$
$$
=
{{q^{c+d+1}} \over {(q)_\infty}}
{ {(q)_{c+d}} \over {(q)_c } } \sum_{i=0}^{\infty}  q^{i(c+1)} {{(q)_{i+d}} \over {(q)_d (q)_i} }
$$
$$
={{q^{c+d+1}} \over {(q)_\infty}}
{ {(q)_{c+d}} \over {(q)_c } }    {{1} \over {(q^{c+1})_{d+1} } } \quad ,
$$
by Fact 1 with $z=q^{c+1}$. Finally, this equals
$$
={{q^{c+d+1}} \over {(q)_\infty}} \cdot { {(1-q)(1-q^2) \cdots (1-q^{c+d}) } \over {(1-q)(1-q^2) \cdots (1-q^{c+d+1})} }
={{q^{c+d+1}} \over {(q)_\infty}} \cdot {{1} \over {(1-q^{c+d+1})} } \quad \halmos .
$$

{\bf Reference}

[R] A. Regev, {\it private communication} .





\end





