Permutations everywhere

This is a great exercise for alternating sums using 'killing involution'. A great resource can be found here: D.I.E. . In fact, I am going to follow the format as described in that article.

Quick overview: The motivation for this solution is seeing that $(-1)^{\text{inv}(\pi)}$ term in the sum. Alternating sums can usually be solved with sign-reversing involution, and so we have to find the rule that maps between positive and negative weights. The simplest rule is to just swap the first and the second elements, thus changing the inversion number by one (and hence the sign changes); however, this comes at the cost that the major index might also be changed. After breaking down the major index into its components, a lot of the components indeed remain the same after the involution (e.g. if 3 contributes to the major index before mapping, then 3 also contributes after mapping, and vice versa); the only remaining ones are indices 1 and 2, which get canceled in a different way.

---

I will also appeal to the well-known fact that the parity of a permutation shares the same parity with the involution number. It is also known that swapping two terms in a permutation alters this parity. Ivan has already provided a proof that I shall omit.

Description: $\sum _{ \pi \in { S }_{ 16 } }^{ }{\text{maj}(\pi )}$ sums the sums of the indices of the ascents across all permutations of size $16$ , which is taken straight from the given definition.

Involution: Simply swap the values of $\pi (1)$ and $\pi (2)$ ! This ensures that the parity is swapped and an involution can occur. For clarity's sake, let this swap be interpreted as applying a function $f$ on a permutation $\pi$ . Then $f(f(\pi))=\pi$ , $\text{inv}(\pi)=\text{inv}(f(\pi) ) \pm 1$ .

Exception: Consider $(-1)^{\text{inv}(X)}\text{maj}(\pi)+(-1)^{\text{inv}(f(\pi))}\text{maj}(f(\pi))$ for all even permutations $\pi$ . This simplifies to $\text{maj}(\pi)-\text{maj}(f(\pi))$ . Most of the indices would kill each other off, with these exceptions of some extra terms:

• $+\pi_A(1)$ if $\pi_A(1)>\pi_A(2)$ by considering how the 1-2 adjacency changes

• $-\pi_B(2)$ if $\pi_B(2)>\pi_B(1)$ by considering how the 1-2 adjacency changes

• $+\pi_C(2)$ if $\pi_C(2)>\pi_C(3)$ by considering how the 2-3 adjacency changes

• $-\pi_D(1)$ if $\pi_D(1)>\pi_D(3)$ by considering how the 2-3 adjacency changes

We claim that after summing through all permutations, these exceptions all sum to zero. Define subset $A=\{\pi_A\in S|\pi_A(1)>\pi_A(2) \text{ and } (-1)^{\text{inv}(\pi_A)}=1\}$ . Define subsets $B,C,D$ similarly according to the inequalities above, ensuring that the permutations are even.

Consider the bijection $g:A\rightarrow B$ , where $g$ swaps $\pi(1)\leftrightarrow \pi(2)$ and $\pi(3)\leftrightarrow \pi(4)$ . This bijection, (its inverse is itself) keeps the permutations to be even. So the first two exceptions kill each other off, in the sense that $\pi_A(1)=\pi_B(2)$ .

Consider the bijection $h:C\rightarrow D$ , where $h$ replaces $(\pi(1),\pi(2),\pi(4))$ with $(\pi(4),\pi(1),\pi(2))$ . This bijection (its inverse is just taking the replacement backwards) keeps the permutations to be even (because of how this is achieved by two swaps: $(2,4)(1,2)$ ). So the last two exceptions kill each other off too, in the sense that $\pi_C(2)=\pi_D(1)$ .

Hence the claim is justified, and the answer is $\boxed{0}$ .

The trick is to note that we can consider each index for the major index separately. For those who contribute a 1 to the major index, half of them have even inversion number and half have odd, so they add up to 0. Likewise for those who contribute a 2 to the major index, and so on. In total, they all cancel each other, for a total of 0.

---

First, we need a simple lemma.

Lemma : If $\pi'$ is obtained from a permutation $\pi$ by transposing (exchanging) two elements, then $\text{inv}(\pi)$ and $\text{inv}(\pi')$ have different parities.

Suppose we exchange $\pi(a)$ and $\pi(b)$ . Clearly if $(a,b)$ is an inversion in $\pi$ , then it isn't in $\pi'$ , since $\pi'(a) = \pi(b) < \pi(a) = \pi'(b)$ , and vice versa. So that's a change of one inversion. Any other pair that doesn't involve the indices $a,b$ remain the same; if $(i,j)$ is an inversion in $\pi$ where $i,j \not\in \{a, b\}$ , then it's also an inversion in $\pi'$ , and vice versa.

Now, consider the two pairs $(a,i), (i,b)$ . (We assume $a < i < b$ ; the other two cases $i < a$ and $b < i$ are handled similarly.) If $(a,i), (i,b)$ are inversions in $\pi$ , then $\pi(a) > \pi(i) > \pi(b)$ , so in $\pi'$ , we have $\pi'(a) < \pi'(i) < \pi'(b)$ , so they aren't inversions in $\pi'$ . Similarly, if $(a,i), (i,b)$ are not inversions in $\pi$ , then they are inversions in $\pi'$ . If $(a,i)$ is an inversion in $\pi$ and $(i,b)$ isn't, then $\pi(a) > \pi(i)$ and $\pi(i) < \pi(b)$ , so in $\pi'$ we have $\pi'(a) = \pi(b) > \pi(i) = \pi'(i)$ and $\pi'(i) = \pi(i) < \pi(a) = \pi'(b)$ , so $(a,i)$ is also an inversion and $(i,b)$ is also not an inversion in $\pi'$ . The other case where $(i,b)$ is an inversion and $(a,i)$ isn't is similar. In all cases, the number of inversions changes by either $-2, 0, +2$ , so they don't change the parity.

Summing over all $i$ , we see that the parity is only changed on the pair $(a,b)$ . Since that's a total of one parity change, the net result is $\text{inv}(\pi')$ has a different parity from $\text{inv}(\pi)$ .

---

We will generalize the claim: for any $n \ge 4$ ,

$\sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot \text{maj}(\pi) = 0$

For $\pi \in S_n$ and $i \in \{1, 2, \ldots, n-1\}$ , define $f(\pi, i)$ as 1 if $\pi(i) > \pi(i+1)$ and 0 otherwise. Then $\text{maj}(\pi) = \displaystyle\sum_{i=1}^{n-1} i \cdot f(\pi, i)$ . The sought sum is then

$\begin{aligned} \sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot \text{maj}(\pi) &= \sum_{\pi \in S_n} \left( (-1)^{\text{inv}(\pi)} \cdot \sum_{i=1}^{n-1} \left( i \cdot f(\pi, i) \right) \right) \\ &= \sum_{\pi \in S_n} \sum_{i=1}^{n-1} (-1)^{\text{inv}(\pi)} \cdot i \cdot f(\pi, i) \\ &= \sum_{i=1}^{n-1} \sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot i \cdot f(\pi, i) \\ &= \sum_{i=1}^{n-1} \left( i \cdot \sum_{\pi \in S_n} \left( (-1)^{\text{inv}(\pi)} \cdot f(\pi, i) \right) \right) \end{aligned}$

(The first equality is by substitution. The second equality is by distributive property. The third equality is valid because they are finite sums. The fourth equality is factoring $i$ out.)

Now, if we can show that $\displaystyle \sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot f(\pi, i) = 0$ for all $i$ , we're done.

Define $g_i(\pi, j, k)$ to be 1 if $\pi(i) = j, \pi(i+1) = k$ , and 0 otherwise. Then $f(\pi, i) = \displaystyle \sum_{j=2}^n \sum_{k=1}^{j-1} g_i(\pi, j, k)$ ; $f(\pi, i)$ is 1 exactly if for some $j,k$ where $j > k$ , we have $\pi(i) = j, \pi(i+1) = k$ .

So what do we do now? Why, of course.

$\begin{aligned} \sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot f(\pi, i) &= \sum_{\pi \in S_n} \left( (-1)^{\text{inv}(\pi)} \cdot \sum_{j=2}^n \sum_{k=1}^{j-1} g_i(\pi, j, k) \right) \\ &= \sum_{\pi \in S_n} \sum_{j=2}^n \sum_{k=1}^{j-1} (-1)^{\text{inv}(\pi)} \cdot g_i(\pi, j, k) \\ &= \sum_{j=2}^n \sum_{k=1}^{j-1} \sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot g_i(\pi, j, k) \\ &= \sum_{j=2}^n \sum_{k=1}^{j-1} \sum_{\pi \in S_n, g_i(\pi, j, k) = 1} (-1)^{\text{inv}(\pi)} \\ \end{aligned}$

(The first equality is by substitution again. The second equality is by distributive property again. The third equality is because it's a finite sum again. The fourth equality is because $g_i(\pi, j, k)$ is either 0 or 1; the terms that contribute to the sum are precisely those when $g_i(\pi, j, k) = 1$ , and for them, we can just remove $g_i(\pi, j, k)$ .)

Now, $\displaystyle \sum_{\pi \in S_n, g_i(\pi, j, k) = 1} (-1)^{\text{inv}(\pi)}$ asks that, among all permutations $\pi$ such that $\pi(i) = j, \pi(i+1) = k$ , what is the signed difference between the number of permutations with even inversion number to the number of permutations with odd inversion number? If we show that these two are equal, we're done, since this sum becomes 0.

For this, we use sign-reversing involution . We pair off permutations with even inversion number to permutations with odd inversion number in a reversible manner (thus "involution", a bijection that is its own inverse). For each pair, one of them contributes $+1$ to the sum and the other $-1$ , so they cancel each other out (thus "sign-reversing"); thus, if we can pair off everything, all of them cancel out with each other, for a total of 0.

This involution is simple. Because $n \ge 4$ , there are at least two indices besides $i, i+1$ . Take the two smallest ones. For $i = 1$ , this means the indices $3, 4$ ; for $i = 2$ , this means the indices $1, 4$ ; for other $i$ , this means the indices $1, 2$ . The involution is then to transpose the two elements on these indices. This is an involution, since applying it again gives the original permutation. This is sign-reversing, because transposing two elements means we change the parity of the inversion number (by the lemma). And this pairs off all permutations, so there's nothing missing.

Thus we have proven that $\displaystyle \sum_{\pi \in S_n, g_i(\pi, j, k) = 1} (-1)^{\text{inv}(\pi)} = 0$ for any $i, j, k$ . Walking back through the equations, we end up with our claim:

$\sum_{\pi \in S_n} (-1)^{\text{inv}(\pi)} \cdot \text{maj}(\pi) = 0$

Substituting for $n = 16$ gives our answer.

---

The approach above doesn't work for $n = 2, 3$ precisely because the involution doesn't exist. (When we fix two elements, there is only one permutation, so we can't pair it off to cancel it.) For $n = 1$ , the sum is also 0, but for another reason: because there's not enough space for the major index to be anything other than 0.