The Number of Inversions and the Major Index of Permutations are Asymptotically Joint-Independently Normal (Second Edition!)

Written By Andrew Baxter and Doron Zeilberger


Refereed by: Mireille Bousquet-Mélou, Guoniu Han, Emilie Hogan, Svante Janson, Ilias Kotsireas, Christian Krattenthaler, Dan Romik, Vince Vatter, and Herbert Wilf
.pdf   .ps   .tex  
Second Edition (Fully (non-anonymously!) refereed) Published: Feb. 4, 2011.
First Editon Written: April 7, 2010.
Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger (and arxiv.org)
Current version of this webpage (AND article): Feb. 4, 2011, posting the long-awaited second edition, incorporating the wise and insightful suggestions of nine world-class (non-anonymous!) expert referees.
All the reports are in! We have now writen a new edition, obtained in the links above. Historians of mathematics may wish to also see the first edition.
Added Oct. 5, 2010: DZ is hereby offering a reward of $1000 for the first person to point out a serious error in the argument of this article, that would invalidate its main result. See Doron Zeilberger's Opinion 112  
Ever since Don Knuth asked me (after being asked by Svante Janson) about the asymptotic covariance of the Number of Inversions and the Major Index, that Shalosh B. Ekhad answered   so brilliantly, I dreamed of proving the much stronger result that they are asymptotically independent (we already know that they are both normal, thanks to my academic great-grandfather Willi Feller). Finally, in collaboration with my brilliant human disciple, Andrew Baxter, and also with the great help of Shalosh B. Ekhad (who was asked to be a coauthor, but gracefully declined), we did it!

Non-Anonymous Referee Reports

We have asked several people to openly review this article, for correctness, novelty, and if they wish of its "significance" (or lack of!) (but that's optional, history would be the ultimate judge in that respect, but some of the people that I have contacted, and kindly agreed to participate didn't only want to be "correctness/novelty" checkers) .

The first person we asked was Herbert Wilf who very promptly (Oct. 22, 2010) sent us the following general report, commenting on the paper as a whole.

In addition we have asked the following people, with the following division of labor:


Added Nov. 4, 2011: Marko Thiel has kindly discovered a (minor!) error in one of the "hand-waving" arguments in the paper. He also kindly fixed it! See Marko Thiel's message


Added Dec. 5, 2013: Marko Thiel has just posted this beautiful generalization


Maple Package

Important: This article is accompanied by Maple package


Sample Input and Output for InvMaj

  • If you want to see a (pre-computed, to save you time!) table of all mixed-factorial moments FM(r,s)(n,i) (about the mean) of the pair of random variables (inv,maj) defined over the set of permutations of {1, ..., n} that end in i (for symbolic(!) n and i) but numeric r and s with 1 ≤ r,s, ≤ 8, the input gives the output.

  • If you want to see a (pre-computed, to save you time!) table of all leading terms of the mixed-factorial moments FM(r,s)(n,i) (about the mean) of the pair of random variables (inv,maj) defined over the set of permutations of {1, ..., n} that end in i (for symbolic(!) n and i) but numeric r and s with 1 ≤ r,s, ≤ 8, the input gives the output.

  • If you want to see the first 20 generating functions (weight-enumerators) for the pair (inv,maj) defined over permutations, the input gives the output.

  • If you want to get FM(1,1)(n,i) ab initio the input gives the output.

  • If you want to see the (beginnings, up to order 5) of the infinite-dimensional operators annihilating FM(r,s)(n,i) mentioned on p. 10 of the article (2nd ed.), and given there only to first-order, the input gives the output.
    [the page numberings in the input and output files refer to the first edition]

  • If you want to see the empirical-yet-rigorous proof of the explicit expressions for the leading terms of the mixed-factorial moments FM(r,s)(n,i) mentioned on p. 9 of the article (2nd ed.), equation (RecG') the input gives the output.
    [the page numberings in the input and output files refer to the first edition]

  • If you want to see the empirical-yet-rigorous proof of the explicit expressions for the leading terms of the mixed-factorial moments FM(r,s)(n,i) mentioned on p. 9 of the article (2nd ed.), equation (Gnn') the input gives the output.
    [the page numberings in the input and output files refer to the first edition]


Page History

Previous version: Jan. 27, 2011. Posting Guoniu Han's report
(Previous)2 version: Jan. 13, 2011. Posting Mireille Bousquet-Mélou's report.

(Previous)3 version: Jan. 10, 2011 (incorporating Emilie Hogan's suggestions).

(Previous)4 version of this webpage (NOT of article): Jan. 3, 2011. (Posting the reports of Vince Vatter, Emilie Hogan, and Ilias Kotsireas. Vince's suggestions will be incroporated once all the reports would arrive, Emilie's suggestions were already made);

(Previous)5 Dec. 14, 2010, posting Svante Janson's non-anoymous referee report on the probablistic part. His minor suggested changes (α should be a) would be incorporated once all the other reports arrive.


(Previous)6 Version (NOT of article): Nov. 30, 2010, posting Dan Romik's non-anoymous referee report on the probablistic part. His suggested changes (those that we agree with), would be incorporated once all the other reports arrive.


(Previous)7 Version: Nov. 5, 2011, incorporating the Christian Krattenthaler's careful and insightful non-anoymous referee report.


Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page