%ggV.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
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
An Inelegant (but Short(!)) Proof of a Major Index Theorem of Garsia and Gessel
(Verbose Version)
}
\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/} .
First version: March 25, 2009. This verbose version: March 31, 2009.
Supported in part by the NSF.
}
}

Recall Adriano Garsia's favorite notation: $\chi(A)=1$ if $A$ is true, 
and $\chi(A)=0$ if $A$ is false.
For example $\chi(MathIsFun)=1$, $\chi(HeleneBarceloIsAGoodEditor)=0$. Also
recall that the {\it major index} of any list of integers $\pi=(\pi_1, \dots, \pi_n)$ 
(in particular a permutation) is defined by
$maj(\pi) :=\sum_{i=1}^{n-1} i \chi(\pi_{i} > \pi_{i+1})$.
Let $\theta=\theta_1 \dots \theta_a$  and $\pi=\pi_1 \dots \pi_b$  be two disjoint lists of distinct integers.
Let $S(\theta, \pi)$ be the set of (a+b)!/(a!b!) mergings (suffles) of $\theta$ and $\pi$.
Let $(q)_n:=(1-q)(1-q^2) \cdots (1-q^n)$.
Moti Novick[N] has recently found an elegant bijective proof of the following 

{\bf Theorem} (Garsia and Gessel[GG]): 
$$
\sum_{\sigma \in S(\theta, \pi)} q^{maj(\sigma)} =
{ {(q)_{a+b}}  \over {(q)_a (q)_b} } q^{maj(\theta)+maj(\pi)} \quad.
\eqno(Moti)
$$
In this short note I will present an {\it inelegant}, induction proof, by proving,
more generally:

{\bf Lemma}: Let $S_1(\theta, \pi)$ be the subset of $S(\theta, \pi)$ whose last entry is $\theta_a$, 
and let $S_2(\theta, \pi)$ be the subset of $S(\theta, \pi)$ whose last entry is $\pi_b$, then
$$
\sum_{\sigma \in S_1(\theta, \pi)} q^{maj(\sigma)} =
{ {(q)_{a+b-1}} \over {(q)_{a-1} (q)_b} } q^{maj(\theta)+maj(\pi)+ b \chi(\pi_b > \theta_a)} \quad ,
\eqno(Adriano)
$$
$$
\sum_{\sigma \in S_2(\theta, \pi)} q^{maj(\sigma)} =
{ {(q)_{a+b-1}} \over {(q)_a (q)_{b-1}} } q^{maj(\theta)+maj(\pi)+ a \chi(\pi_b < \theta_a)} \quad.
\eqno(Ira)
$$
Note that adding-up $(Adriano)$ and $(Ira)$ gives $(Moti)$.
Let's call the left-sides of $(Adriano)$ and $(Ira)$ $F_1(a,b)$ and $F_2(a,b)$ respectively, 
and let's call their right-sides $G_1(a,b)$ and $G_2(a,b)$ respectively. It is immediate that
$(F_1,F_2)=(G_1,G_2)$ when $a=0$ or $b=0$, and the fact that $(F_1,F_2)=(G_1,G_2)$ for all
$a,b \geq 0$ follows from the fact that both $(X_1,X_2)=(F_1,F_2)$ and $(X_1,X_2)=(G_1,G_2)$ satisfy the
recurrence
$$
X_1(a,b)=
q^{(a+b-1)\chi(\theta_{a-1} > \theta_a)}X_1(a-1,b)
+q^{(a+b-1)\chi( \pi_b > \theta_{a} )}X_2(a-1,b)
$$
$$
X_2(a,b)=q^{(a+b-1)\chi(\theta_{a} > \pi_b)}X_1(a,b-1)
+q^{(a+b-1)\chi(\pi_{b-1} > \pi_b)}X_2(a,b-1) \quad.
$$
The proof for $(F_1,F_2)$ is left to the reader. Let's prove it for $(G_1,G_2)$.
We will only prove the first identity. The second one is also left to the reader.

We have to prove that
$$
G_1(a,b)-
q^{(a+b-1)\chi(\theta_{a-1} > \theta_a)}
G_1(a-1,b)
-q^{(a+b-1)\chi( \pi_b > \theta_{a} )}G_2(a-1,b)=0 \quad.
\eqno(HaImEfes)
$$
By definition:
$$
G_1(a,b)=
{ {(q)_{a+b-1}} \over {(q)_{a-1} (q)_b} } q^{maj(\theta_1 \dots \theta_a)+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_a)} \quad ,
$$
$$
G_2(a,b)=
{ {(q)_{a+b-1}} \over {(q)_a (q)_{b-1}} } q^{maj(\theta_1 \dots \theta_a)+maj(\pi_1 \dots \pi_b)+ a \chi(\pi_b < \theta_a)} \quad.
$$
Replacing $a$ by $a-1$ we have
$$
G_1(a-1,b)=
{ {(q)_{a+b-2}} \over {(q)_{a-2} (q)_b} } q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_{a-1})} \quad ,
$$
$$
G_2(a-1,b)=
{ {(q)_{a+b-2}} \over {(q)_{a-1} (q)_{b-1}} } q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ (a-1) \chi(\pi_b < \theta_{a-1})} \quad.
$$
Substituting in the left side of $(HaImEfes)$, we have to prove:
$$
{ {(q)_{a+b-1}} \over {(q)_{a-1} (q)_b} } q^{maj(\theta_1 \dots \theta_a)+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_a)}
$$
$$
- q^{(a+b-1)\chi(\theta_{a-1} > \theta_a)} \cdot
{ {(q)_{a+b-2}} \over {(q)_{a-2} (q)_b} } q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_{a-1})}
$$
$$
-q^{(a+b-1)\chi( \pi_b > \theta_{a} )} \cdot
{ {(q)_{a+b-2}} \over {(q)_{a-1} (q)_{b-1}} } q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ (a-1) \chi(\pi_b < \theta_{a-1})}
=0
$$
Dividing by  ${ {(q)_{a+b-2}} \over {(q)_{a-1} (q)_b}} $, we have to prove
$$
(1-q^{a+b-1}) q^{maj(\theta_1 \dots \theta_a)+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_a)}
$$
$$
-q^{(a+b-1)\chi(\theta_{a-1} > \theta_a)} \cdot
(1-q^{a-1}) q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_{a-1})}
$$
$$
-q^{(a+b-1)\chi( \pi_b > \theta_{a} )} \cdot
(1-q^b) q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ (a-1) \chi(\pi_b < \theta_{a-1})} 
=0 \quad .
$$
But
$$
maj(\theta_1 \dots \theta_a)=maj(\theta_1 \dots \theta_{a-1})+(a-1)\chi(\theta_{a-1}>\theta_a) \quad ,
$$
so we have to prove:
$$
(1-q^{a+b-1}) q^{maj(\theta_1 \dots \theta_{a-1})+ (a-1)\chi(\theta_{a-1}>\theta_a)+maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_a)}-
$$
$$
q^{(a+b-1)\chi(\theta_{a-1} > \theta_a)} \cdot
(1-q^{a-1}) q^{maj(\theta_1 \dots \theta_{a-1})+  maj(\pi_1 \dots \pi_b)+ b \chi(\pi_b > \theta_{a-1})}
$$
$$
-q^{(a+b-1)\chi( \pi_b > \theta_{a} )} \cdot
(1-q^b) q^{maj(\theta_1 \dots \theta_{a-1})+maj(\pi_1 \dots \pi_b)+ a \chi(\pi_b < \theta_{a-1})}
=0
$$
Dividing both sides by $q^{maj(\theta_1 \dots \theta_{a-1})+ maj(\pi_1 \dots \pi_b)}$, we have to prove
$$
(1-q^{a+b-1}) q^{ (a-1)\chi(\theta_{a-1}>\theta_a)+ b \chi(\pi_b > \theta_a)}-
q^{(a+b-1)\chi(\theta_{a-1} > \theta_a)} \cdot
(1-q^{a-1}) q^{b \chi(\pi_b > \theta_{a-1})} 
$$
$$
-q^{(a+b-1)\chi( \pi_b > \theta_{a} )} \cdot
(1-q^b) q^{(a-1) \chi(\pi_b < \theta_{a-1})} =0
$$
Combining powers of $q$, we have to prove:
$$
(1-q^{a+b-1}) q^{ (a-1)\chi(\theta_{a-1}>\theta_a)+ b \chi(\pi_b > \theta_a)}-
(1-q^{a-1}) q^{b \chi(\pi_b > \theta_{a-1})+ (a+b-1)\chi(\theta_{a-1} > \theta_a)} 
$$
$$
-(1-q^b) q^{(a-1) \chi(\pi_b < \theta_{a-1})+(a+b-1)\chi( \pi_b > \theta_{a} )} =0
$$

We have {\bf six} cases to consider according to the relative rankings of $\theta_{a-1},\theta_a,\pi_b$.

{\bf Case 123}: $\theta_{a-1}<\theta_a<\pi_b$. We have to prove
$$
(1-q^{a+b-1}) q^{b}-(1-q^{a-1}) q^{b} -(1-q^b) q^{(a+b-1)} =0 \quad .
$$
Dividing by $q^b$, we have to prove
$$
(1-q^{a+b-1})-(1-q^{a-1}) -(1-q^b) q^{(a-1)} =0 \quad .
$$
Expanding, we have, to prove
$$
1-q^{a+b-1}-1+q^{a-1}-q^{a-1}+q^{a+b-1} =0 \quad,
$$
and this is indeed true.

{\bf Case 132}: $\theta_{a-1}<\pi_b<\theta_a$. We have to prove
$$
(1-q^{a+b-1}) q^{0}-(1-q^{a-1}) q^{b} -(1-q^b) q^0 =0
$$
Expanding, we get:
$$
1-q^{a+b-1}-q^b+q^{a+b-1} -1+q^b =0 \quad,
$$
and this is indeed true.


{\bf Case 213}: $\theta_{a}<\theta_{a-1}<\pi_b$:
$$
(1-q^{a+b-1}) q^{ (a-1)+ b}-(1-q^{a-1}) q^{b+ (a+b-1)} -(1-q^b) q^{a+b-1} =0 \quad,
$$
Dividing by $q^{a+b-1}$, we have to prove
$$
(1-q^{a+b-1})-(1-q^{a-1}) q^{b} -(1-q^b)=0 \quad,
$$
Expanding, we have to prove
$$
1-q^{a+b-1}-q^b+q^{a+b-1}-1+q^b=0 \quad,
$$
and this is indeed true.

{\bf Case 231}: $\theta_{a} < \pi_b < \theta_{a-1}$. We have to prove
$$
(1-q^{a+b-1}) q^{ (a-1)+ b}-(1-q^{a-1}) q^{a+b-1} -(1-q^b) q^{a-1+(a+b-1)} =0 \quad .
$$
Dividing by $q^{a+b-1}$, we have to prove
$$
(1-q^{a+b-1})-(1-q^{a-1})-(1-q^b) q^{a-1} =0 \quad .
$$
Expanding, we have to prove
$$
1-q^{a+b-1}-1+q^{a-1}-q^{a-1}+q^{a+b-1} =0 \quad ,
$$
and this is indeed true.

{\bf Case 312}: $\pi_b<\theta_{a-1}<\theta_a$:
$$
(1-q^{a+b-1}) q^{0}-(1-q^{a-1}) q^{0} -(1-q^b) q^{a-1} =0 \quad,
$$
Expanding, we have to prove
$$
1-q^{a+b-1}-1+q^{a-1}-q^{a-1}+ q^{a+b-1}=0 \quad,
$$
and this is indeed true.

{\bf Case 321}: $\pi_b<\theta_{a}<\theta_{a-1}$:
$$
(1-q^{a+b-1}) q^{a-1}-(1-q^{a-1}) q^{a+b-1} -(1-q^b) q^{a-1} =0 \quad .
$$
Dividing by $q^{a-1}$, we have to prove
$$
(1-q^{a+b-1})-(1-q^{a-1}) q^{b} -(1-q^b) =0 \quad .
$$
Expanding, we have to prove
$$
1-q^{a+b-1}-q^b+q^{a+b-1} -1+q^b =0 \quad ,
$$
and this is indeed true. \halmos

{\bf Remarks}: {\bf 1.} Moti Novick's elegant bijection also preserves
equidistribution over Inverse Descent Classes.
{\bf 2.} It would be interesting to bijectify the above inductive proof, along the lines of [MZ], and
see if the resulting bijection is identitical, or similar, to Moti Novick's elegant bijection.

{\bf References}:

[GG] Adriano M. Garsia and Ira Gessel, {\it Permutation statistics and partitions}, Advances in
Mathematics {\bf 31}(1979), 288-305.

[MZ] Philip Matchett Wood and Doron Zeilberger, 
{\it A Translation Method for Finding Combinatorial Bijections}, to appear in Annals of Combinatorics.
\hfill\break Available from {\eighttt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/trans-method.html} .

[N] Moti Novick, {\it A Bijective proof of a major index theorem of Garsia and Gessel}, preprint, Hebrew University of Jerusalem.



\end




















