Dear Professor Zeilberger,
my name is Marko Thiel, and I am the newest PhD student of Christian Krattenthaler. He has recently given me your beautiful paper "The Number of Inversions and the Major Index of Permutations are Joint-Independently-Normal" to read, which I found a very enjoyable and enlightening experience.
However, one passage resisted my understanding longest: The sketch of a combinatorial proof that the mixed moments are polynomials in n. As I asked Christian to help me with this, we noticed an error:
You define a scenario to encode the placements of the indices and the order of the values of the permutation on them. But the indicator function whose sum over i and j gives the major index depends not only on i, j, and pi(j), but also on pi(j+1). This means that the indicator function being summed can take different values on different tuples of indices that belong to the same scenario. It is essential to the proof that this should not happen.
Now this can be fixed:
Have a scenario also encode {m | i[m]+1 = i[m+1]}, and the order of the values of pi on the union of {i[1],...,i[k]} and {i[1]+1,...,i[k]+1}. In order to avoid the problem of i[k]+1 > n, it is also necessary to distinguish between i[k] < n and i[k] = n.
Let l = |{m | i[m]+1 = i[m+1]}| be the amount of overlap. Then the contribution to the sum of each scenario with i[k] < n will be:
> (n-k)C(k-l) * (n)C(2k-l) * (n-(2k-l))! / n! = (n-k)C(k-l) / (2k-l)! ,
a polynomial in n of degree k-l, and for each scenario with i[k] = n the contribution will be:
(n-k)C(k-l-1) * (n)C(2k-l-1) * (n-(2k-l-1))! / n! = (n-k)C(k-l-1) / (2k-l-1)! ,
a polynomial in n of degree k-l-1.
In each formula, the first term gives the number of ways of choosing {i[1],...,i[k]} subject to the restrictions on i[k] and {m | i[m]+1 = i[m+1]}, the second gives the number of ways to pick the values of pi on the union of {i[1],...,i[k]} and {i[1]+1,...,i[k]+1}, and the third the number of ways to arrange the rest. This establishes the claim.
I have to admit, I like your version of the proof much better than this one, even though it is somewhat incorrect, since it contains all the essential ideas while being much nicer, but Christian encouraged me to send you this, so I did.
I hope you will find this useful.
Yours,
Marko Thiel
MathIsFun