Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In 1913 Percy MacMahon proved that the distribution of the major index on all permutations of a fixed length is the same as the distributin of inversions. I'm trying to understand the identity $$ \sum_{w\in S_n\cdot(1^{k_1},2^{k_2},\dots,r^{k_r})}x^{\text{maj}(w)}=\sum_{w\in S_n\cdot(1^{k_1},2^{k_2},\dots,r^{k_r})}x^{\text{inv}(w)} $$ where $k_1+\cdots+k_r=n$, and $w\in[r]^n$. With help, I've come to understand that if $w(n)=s$, then $w'=(1 2 \cdots r)^{r-s}\circ w$ has $\text{maj}(w')=\text{maj}(w)-(k_{s+1}+\cdots+k_r)$. I don't see how that leads to the result however. I've been searching around for MacMahon's theorem, but haven't found anything that actually proves this identity, and was hoping it could be resolved here. Thank you.

share|cite|improve this question
It seems you are after the bijective proof due to D. Foata and M. P. Schützenberger in Major index and inversion number of permutations, Math. Nachr. 83 (1970), 143–159. – Did Feb 17 '12 at 9:28
@Didier: I think that the 1970 paper deals only with permutations of $[n]$; Nastassja is looking at permutations of $n$-tuples from $[r]$, where $r\le n$. – Brian M. Scott Feb 17 '12 at 10:57
up vote 1 down vote accepted

This paper by Dominique Foata gives a combinatorial proof of MacMahon’s result. It’s actually not horrendously complicated; take a look at it, and if you get stuck, feel free to ask for help.

share|cite|improve this answer
Thanks for finding a reference. – Nastassja Feb 27 '12 at 23:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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