The Joy of Brute Force: The Covariance of The number of Inversions and the Major Index

Doron ZEILBERGER^{1}

As usual, for a permutation π of length n, let inv π be the number of (i, j), such that 1 ≤ i < j ≤ n and π[i] > π[j], and maj π be the sum of i, such that 1 ≤ i < n and π[i] > π[i + 1]. Svante Janson asked Don Knuth, who asked me, about the covariance of inv and maj. The answer is \binom{n}{2}/4. To prove it, I asked Shalosh to compute the average of the quantity (inv π − E(inv))(maj π − E(maj)) over all permutations of a given length n, and it gave me, for n = 1, 2, 3, 4, 5, the values 0, 1/4, 3/4, 3/2, 5/2, respectively. Since we know a priori^{2} that this is a polynomial of degree ≤ 4, this must be it!

Exercises: 1. Find explicit expressions for the average of (inv π − E(inv))^{r}(maj π − E(maj))^{s}, for r, s ∈ {1, 2, 3}, by complete brute force.

2. Find an explicit expression for the sequence a_{n} := the average of (inv π − E(inv))(maj π − E(maj))(des π − E(des)), over all permutations of length n, where des π is the number of i, such that 1 ≤ i < n and π[i] > π[i + 1].

Moral: We mathematicians were brainwashed to be clever, and to think before computing. The conventional wisdom is that clever thinking can eliminate the need for computation. This was true in the old days, since thinking is more pleasant than rote computing. But thinking is still painful, and now that computers can do the job, we should train ourselves and our students to go the other way: replace thinking by computation, that we can delegate to our computers. Of course, in order to justify this, we need some meta-thinking, as was done in footnote 2. The next step would be to train our computers to do the meta-thinking, and free us to do the meta-meta-thinking, until, at the limit, computers and humans would be indistinguishable (except that humans would err at a much higher rate, and would be much slower).

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu . Sup-

ported in part by the NSF. This note is exclusively published in http://www.math.temple.edu/˜ zeilberg.

2 This is the old trick to compute moments of combinatorial ‘statistics’, described nicely in Graham, Knuth, and

Patashnik’s ‘Concrete Math’, section 8.2, by changing the order of summation. It applies equally well to covariance.

Rather than actually carrying out the gory details, we observe that this is always a polynomial whose degree is trivial to bound.