An Inelegant (but Short(!)) Proof of a Major Index Theorem of Garsia and Gessel

Doron ZEILBERGER^{1}

Recall Adriano Garsia’s favorite notation: χ(A) = 1 if A is true, and χ(A) = 0 if A is false. For example χ(MathIsF un) = 1, χ(HeleneBarceloIsAGoodEditor) = 0. Also recall that the major index of any list of integers π = (π_{1}, …, π_{n}) (in particular a permutation) is defined by maj(π) := ∑_{i=1}^{n−1} iχ(π_{i} > π_{i+1}). Let θ = θ_{1} … θ_{a} and π = π_{1} … π_{b} be two disjoint lists of distinct integers. Let S(θ, π) be the set of (a+b)!/(a!b!) mergings (suffles) of θ and π. Let (q)_{n} := (1 − q)(1 − q^{2}) ⋯ (1 − q^{n}). Moti Novick[N] has recently found an elegant bijective proof of the following

Theorem (Garsia and Gessel[GG]):

∑_{σ∈S(θ,π)} q^{maj(σ)} = \frac{(q)_{a+b}}{(q)_{a}(q)_{b}} q^{maj(θ)+maj(π)} .  (Moti)

In this short note I will present an inelegant, induction proof, by proving, more generally:

Lemma: Let S_{1}(θ, π) be the subset of S(θ, π) whose last entry is θ_{a}, and let S_{2}(θ, π) be the subset of S(θ, π) whose last entry is π_{b}, then

∑_{σ∈S_{1}(θ,π)} q^{maj(σ)} = \frac{(q)_{a+b−1}}{(q)_{a−1}(q)_{b}} q^{maj(θ)+maj(π)+bχ(π_{b}>θ_{a})} ,  (Adriano)

∑_{σ∈S_{2}(θ,π)} q^{maj(σ)} = \frac{(q)_{a+b−1}}{(q)_{a}(q)_{b−1}} q^{maj(θ)+maj(π)+aχ(π_{b}<θ_{a})} .  (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 ≥ 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)χ(θ_{a−1}>θ_{a})}X_{1}(a − 1, b) + q^{(a+b−1)χ(π_{b}>θ_{a})}X_{2}(a − 1, b)
X_{2}(a, b) = q^{(a+b−1)χ(θ_{a}>π_{b})}X_{1}(a, b − 1) + q^{(a+b−1)χ(π_{b−1}>π_{b})}X_{2}(a, b − 1) .

Remarks: 1. Moti Novick’s elegant bijection also preserves equidistribution over Inverse Descent Classes. 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.

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/ . First version: March 25, 2009. This version: March 29, 2009 (Thanks to Moti Novick). Supported in part by the NSF.

References:

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

[MZ] Philip Matchett Wood and Doron Zeilberger, A Translation Method for Finding Combinatorial Bijections, to appear in Annals of Combinatorics.

Available from http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/trans-method.html .

[N] Moti Novick, A Bijective proof of a major index theorem of Garsia and Gessel,

http://arxiv.org/abs/0906.0377 .