$\DeclareMathOperator\maj{maj}\DeclareMathOperator\inv{inv}$Major index, $\maj$, of a permutation on $1,2,\dotsc,n$ is defined as $$ \maj(\pi) \mathrel{:=} \sum_{i=1}^{n-1} i \cdot \chi(\pi(i)\gt \pi(i+1)) $$ where $\chi$ is 1 if the statement inside is true, 0 otherwise.

Let $t_{a,b}$ be the numbers $$ t_{a,b} \mathrel{:=} \lvert\{ \pi \in S_{a+b} : \maj(\pi)=a \text{ and } \maj(\pi^{-1})=b \}\rvert. $$ Here, $S_{a+b}$ denotes the set of permutations of $1,2,\dotsc,a+b$. By a result of Foata, one can also look at the pair of statistics $(\maj, \inv)$, and a few other combinations — these pairs of statistics will produce the same numbers.

Now, according to the OEIS entry A090806, it is proved by Garsia–Gessel that \begin{equation} \sum_{a,b} t_{a,b} q^a t^b = \prod_{i,j \geq 1} \frac{1}{1-q^i t^j} \qquad (\ast) \end{equation} I cannot see exactly where in their paper one can deduce this.

I have tried to prove this myself (mainly by resorting to RSK, the Cauchy identity, and some symmetric function identities). This leads to the following (which appears in Stanley's EC2): $$ \sum_{n \geq 0} \frac{z^n}{(1-q)^n[n]_q!(1-t)^n [n]_t!} \sum_{\pi \in S_n} t^{\maj(\pi)} q^{\maj(\pi^{-1})} = \prod_{i,j \geq 0} \frac{1}{1-z q^i t^j}, $$ where $[n]_q! \mathrel{:=} [1]_q [2]_q \dotsm [n]_q$, and $[n]_q = 1+q+q^2+\dotsb + q^{n-1}$. However, I do not see some short way to deduce the above generating function from this.

Question: Is there some alternative (more recent?) reference where $(\ast)$ is stated and easily referenced? Alternatively, someone who can see exactly where in the paper $(\ast)$ is proven?

Garsia, A. M.; Gessel, I., Permutation statistics and partitions, Adv. Math. 31, 288-305 (1979). ZBL0431.05007.

  • $\begingroup$ $maj(\pi)$ is $\mbox{definition}$? $\endgroup$
    – Turbo
    Feb 21, 2021 at 17:34
  • $\begingroup$ What is $\mathrm{maj}$? $\endgroup$
    – Wojowu
    Feb 21, 2021 at 17:50
  • $\begingroup$ Major index. $\endgroup$
    – LSpice
    Feb 21, 2021 at 17:59
  • 1
    $\begingroup$ @PerAlexandersson, certainly you are right, and I apologise for my error. I think I was applying the fix as you were converting it back to the static form. Anyway I try to edit with a light touch, and the preview seemed to confirm that everything was working, so I apologise that in the end it wound up being ugly. $\endgroup$
    – LSpice
    Feb 21, 2021 at 18:16
  • 1
    $\begingroup$ @LSpice I appreciate the effort - our edits simply collided as I was adding the definition of major index. $\endgroup$ Feb 21, 2021 at 18:17

1 Answer 1


Here is a derivation of $(\ast)$ from the displayed equation $$\sum \frac{z^n}{(1-q)^n [n]_q! (1-t)^n [n]_t!} \sum_{\pi \in S_n} q^{\mathrm{maj}(\pi)} t^{\mathrm{maj}(\pi^{-1})} = \prod_{i,j \geq 0} \frac{1}{1-zt^i q^j}.$$

Taking the coefficient of $z^n$ on both sides, we have $$\frac{\sum_{\pi \in S_n} q^{\mathrm{maj}(\pi)} t^{\mathrm{maj}(\pi^{-1})}}{\prod_{i=1}^n (1-q^i) \prod_{j=1}^n (1-t^j)} = h_n(\{t^i q^j : i,j \geq 0\}).$$ Here the RHS is the complete homogenous symmetric function evaluated on the set of monomials $\{t^i q^j : i,j \geq 0\}$.

Now, $h_n(1, u_1, u_2, u_3, \ldots) = \sum_{k=0}^n h_k(u_1, u_2,\ldots).$ So we can rewrite this RHS to get $$\frac{\sum_{\pi \in S_n} q^{\mathrm{maj}(\pi)} t^{\mathrm{maj}(\pi^{-1})}}{\prod_{i=1}^n (1-q^i) \prod_{j=1}^n (1-t^j)} = \sum_{k=0}^n h_k(\{ q^i t^j : i,j \geq 0,\ (i,j) \neq (0,0) \}). \qquad (\clubsuit)$$

According to the OEIS entry, the quantity $\# \{ \pi \in S_n : \mathrm{maj}(\pi) = a,\ \mathrm{maj}(\pi^{-1}) = b \}$ stabilizes at $t_{ab}$ as $n \to \infty$; the OP's mention of $n=a+b$ is just a particular value in the stable range. So we can take the limit of both sides of $(\clubsuit)$ as $n \to \infty$ to get $$\frac{\sum_{a,b \geq 0} t_{ab} q^a t^b}{\prod_{i=1}^{\infty} (1-q^i) \prod_{j=1}^{\infty} (1-t^j)} = \sum_{k=0}^{\infty} h_k(\{ q^i t^j : i,j \geq 0,\ (i,j) \neq (0,0) \}) = \prod_{\substack{i,j \geq 0 \\ (i,j) \neq (0,0)}} \frac{1}{1-q^i t^j} . \qquad (\diamondsuit)$$

Now cancel common factors from both sides of $(\diamondsuit)$ to get the claim.

Here is another approach, which suggests that something more interesting may be going on. Recall that the RS correspondence is a bijection between the symmetric group $S_n$ and pairs of SYT $(T,U)$ of the same shape $\lambda$, where $|\lambda| = n$. We define $\mathrm{maj}(T)$ for an SYT $T$ to be the sum of those $i$ such that $i$ occurs in a strictly higher row of $T$ than $i+1$ does. Then, if RS maps $\pi$ to $(T,U)$, we have $\mathrm{maj}(\pi)= \mathrm{maj}(T)$ and $\mathrm{maj}(\pi^{-1})= \mathrm{maj}(U)$.

Define $f^{\lambda}(q)$ to be the sum, over $SYT$ of shape $\lambda$, of $q^{\mathrm{maj}(T)}$. So $$\sum_{\pi \in S_n} q^{\mathrm{maj}(\pi)} t^{\mathrm{maj}(\pi^{-1})} = \sum_{|\lambda| = n} f^{\lambda}(q) f^{\lambda}(t).$$

Given a permutation $\mu$, and $n > |\mu| + \mu_1$, let $\mu[n]$ be the partition $(n-|\mu|, \mu_1, \mu_2, \ldots, \mu_k)$. So every partition of $n$ is of the form $\mu[n]$ for a unique $\mu$ and that, for any $\mu$, the partition $\mu[n]$ is well defined for $n$ large enough.

It is easy to see that $\lim_{n \to \infty} f^{\mu[n]}(q)$ exists. Set $f^{\mu[\infty]}(q)$ to be $\lim_{n \to \infty} f^{\mu[n]}(q)$. So we have $$\lim_{n \to \infty} \sum_{\pi \in S_n} q^{\mathrm{maj}(\pi)} t^{\mathrm{maj}(\pi^{-1})} = \sum_{\mu} f^{\mu[\infty]}(q) f^{\mu[\infty]}(t).$$

On the other hand, the Cauchy identity gives $$\prod_{i,j \geq 1} \frac{1}{1-q^i t^j} = \sum_{\mu} s_{\mu}(q,q^2, \cdots) s_{\mu}(t,t^2, \cdots).$$

So here is the weird thing: It turns out that $f^{\mu[\infty]}(q)$ and $s_{\mu}(q)$ are the same thing! This seems like it should have a combinatorial proof. We can clearly think of $f^{\mu[\infty]}(q)$ as a generating function for tableau of shape $\mu$ with distinct entries, counted by a variant of major index. And $s_{\mu}(q)$ is the generating function for semistandard tableau of shape $\mu$, counted by weight. It feels like there should be an easy bijection here.

Well, I couldn't find one. But it isn't hard to prove the equality using hook length formulas. Let $m = |\mu|$ and let $h_1$, $h_2$, ..., $h_m$ be the hook lengths of $\mu$. Set $M = \sum (i-1) \mu_i$. We have $$s_{\mu}(q) = \frac{q^M}{\prod_i (1-q^{h_i})} .$$

On the other hand, the hook lengths of $\mu[n]$ are $h_1$, $h_2$, ..., $h_m$ together with an $n-m$ additional hook lengths $S$. The exact set $S$ doesn't matter; what is important is $\{1,2,\ldots, n-\mu_1-m \} \subseteq S \subseteq \{1,2,\ldots, n \}$. So, by a formula of Stanley (EC2, Cor. 7.21.5), we have $$f^{\mu[n]}(q) = \frac{q^M (1-q)(1-q^2) \cdots (1-q^N)}{\prod_{s \in S} (1-q^s) \prod_i (1-q^{h_i})}.$$ In the limit as $n \to \infty$, both $(1-q)(1-q^2) \cdots (1-q^N)$ and $\prod_{s \in S} (1-q^s)$ approach $\prod_{k=1}^{\infty} (1-q^k)$, so they cancel and we are left with $$ f^{\mu[\infty]}(q) = \frac{q^M}{\prod_i (1-q^{h_i})} = s_{\mu}(q,q^2, \cdots).$$

  • 2
    $\begingroup$ FWIW, I think the stabilization is easy to see if you work with maj and inv instead of maj and imaj. Let $\pi = \pi_1\pi_2\ldots\pi_m \in S_m$ be a permutation, where $m \geq a+b$, and with $\mathrm{maj}(\pi)=a$ and $\mathrm{inv}(\pi)=b$. Since $\mathrm{maj}(\pi)=a$, no descents can occur after the first $a$ positions; since $\mathrm{inv}(\pi)=b$, no letter of $a+b+i$ for $i\geq 1$ can occur in the first $a$ positions. Together these force all $a+b+i$ for $i\geq 1$ to be fixed points. So $\pi$ is really only a permutation of $\{1,\ldots,a+b\}$. $\endgroup$ Feb 22, 2021 at 16:36
  • 1
    $\begingroup$ Should $\neq$ in the second equation be $\geq$? $\endgroup$
    – Will Sawin
    Feb 22, 2021 at 16:36
  • $\begingroup$ Thanks to both of you, you are both right. $\endgroup$ Feb 22, 2021 at 16:57
  • $\begingroup$ Great answer and comment, SamHopkins and @DavidESpeyer ! This now gives a nice record of this identity! I need this for some background in a paper, so I'll probably include this argument, with proper attributions $\endgroup$ Feb 22, 2021 at 17:53
  • $\begingroup$ You're welcome. I actually think there is more going on here; see the second proof I added below the horizontal line. $\endgroup$ Feb 22, 2021 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.