Major Index

I'm assuming that everyone knows what a permutation is. If not, there's a nice wikipedia article on it here that you can check out. ::wink::

Let $\sym_n$ denote the set of permutations of $[n] = \left\{1,2,\ldots,n\right\}$ . Our goal is to describe a statitistic on $\sym_n$ which is equidistributive with length.

Definitions: For a permutation $\sigma \in \sym_n$ let $D(\sigma)$ be the set of descents of $\sigma$ , $\ie$ $\text{[math]}$ and let $N(\sigma)$ denote the set of inversions, $\ie$ $\text{[math]}$ Recall that $\abs{N(\sigma)} = \ell(\sigma)$ is just the length of our permutaiton.

As an example, let $\sigma = 631245 \in \sym_6$ be our permutation. Then since $6 > 3 > 1$ we have descents in position $1$ and position $2$ . Therefore $D(\sigma) = \left\{1,2\right\}$ . Since $1 < 2 < 4 < 5$ we have no other descents. To find the inversions, we compare every two elements and see when the one on the left is bigger than the one on the right. For example, since $\sigma_ 1 = 6 > 3 = \sigma_2$ , therefore $(1,2) \in N(\sigma)$ . Looking at every pair, we see $\text{[math]}$ Therefore, the length of $\sigma$ is $\ell(\sigma) = 6$ as there are $6$ inversions.

Definition: The major index of $\sigma$ is the sum of all the descents. $\text{[math]}$

In our example, we had $\sigma = 631245$ whose descents were $D(\sigma) = \left\{1,2\right\}$ . Therefore, to calculate the major index, we just need to sum up all the descents: $maj(\sigma) = 1 + 2 = 3$ .

Equidistributivity

The major index is actually equidistributive with length! What this means is that for every $\sigma \in \sym_n$ with length $k$ there is a $\sigma' \in \sym_n$ with major index $k$ . Note that $\sigma \neq \sigma'$ in general, as we will see.

The way this was proved was by showing that both statistics (length and major index) are Mahonian.

Definition: A statistic is Mahonian if its distribution over $\sym_n$ is equal to $\text{[math]}$

Theorem [Mac60] Both major index and length are Mahonian. In other words, $\text{[math]}$

As an example, let's look at $\sym_3$ and let's verify that we have the above equality. $\text{[math]}$ Therefore, in all cases we have $\text{[math]}$

Since the distributions are equal, one might wonder whether we can find a way to associate to each permutation another permutation where the number of inversions is sent to the major index. This turns out to be true using a map given by Foata in [Foa68]: Let $\phi : \sym_n \to \sym_n$ be the following recursive map.

For $\sigma = \sigma_1\sigma_2\ldots \sigma_n \in \sym_n$ if $n = 2$ then $\phi(\sigma) = \sigma$ . Else we induct on length of $\sigma$ and define $\phi^{(i)}$ and $\phi^{(i)'}$ inductively. For our initial step, let $\sigma_1 = \phi^{(1)} = \phi^{(1)'}$ . Then, to find $\phi^{(i)'}$ we start with $\phi^{(i)}=\phi^{(i-1)'}\sigma_i$ and if $\phi^{(i)}_i > \phi^{(i)}_{i-1}$ then we draw a bar after each element of $\phi^{(i)}$ which is strictly greater than $\sigma_i$ , else we draw a bar after each element of $\phi^{(i)}$ which is stricly less than $\sigma_i$ . These bars will denote blocks of numbers. In each block, take the last number and move it to the front. This new permutation is $\phi^{(i)'}$ . We continue until $n$ and let $\phi(\sigma) = \phi^{(n)'}(\sigma)$ .

This works best with an example. Let $\sigma = 2376514 \in \sym_7$ . Then $\text{[math]}$ Then $\phi^{(2)} = \phi^{(1)'}\sigma_2 = 23$ . Since $2 < 3$ we place a bar after $2$ , giving $2|3$ . As every element is in its own block, we have nothing to do giving us $\text{[math]}$ Then $\phi^{(3)} = \phi^{(2)'}\sigma_3 = 237$ . Since $3 < 7$ we place a bar after $2$ and $3$ , giving $2|3|7$ . As every element is in its own block, we have nothing to do, giving us $\text{[math]}$ Then $\phi^{(4)} = \phi^{(3)'}\sigma_4 = 2376$ . Since $7 > 6$ we place a bar after $7$ , giving us $237|6$ . As $237$ is a block, we move the last number to the front, giving us: $723|6$ . Therefore $\text{[math]}$ Then $\phi^{(5)} = \phi^{(4)'}\sigma_5 = 72365$ . Since $6 > 5$ we have $7|236|5$ . Moving the last element of each block to the front gives $7|623|5$ and therefore $\text{[math]}$ Then $\phi^{(6)} = \phi^{(5)'}\sigma_6 = 762351$ . Since $5 > 1$ we have $7|6|2|3|5|1$ since every number is bigger than $1$ . Therefore $\text{[math]}$ Then $\phi^{(7)} = \phi^{(6)'}\sigma_7 = 762351$ . Since $1 < 4$ we have $762|3|51|4$ . Here we have two blocks, and putting the last number in the front gives $276|3|15|4$ . In other words $\text{[math]}$

Therefore $\phi(2376514) = 2763154$ . Notice that $\text{[math]}$ and $\text{[math]}$ which is exactly what we want this map to do.

Multi-set Permutations

There are two ways we can generalize these results further. We can look at signed permutations (which we do in the next section) or we can look at permutations of mult-sets. Recall that a multi-set is a set where we allow elements to repeat themselves. Just as with regular permutations, we can look at permutations of multi-sets!

As an example $M = \left\{0, 1, 1, 2\right\}$ is a multi-set. Notice that it is not a set since $1$ appears twice. Looking at permutations of $M$ we get the following permutations: $\text{[math]}$ Notice that every number appears twice! $\text{[math]}$

That's cause there are two $1$ s which can swap places without the number changing! That means there are half as many permutations; or in other words $\frac{4!}{2!}$ number of permutations.

But notice that we have one $0$ and one $2$ , so we can rewrite this further as: $\text{[math]}$ which is also the multi-set number (the multi-set version of the binomial coefficient). This is normally denoted as: $\text{[math]}$

Let $M$ be a multi-set with $\alpha_0$ number of $0$ s, $\alpha_1$ number of $1$ s, \etc. where $\sum \alpha_i = n$ . Then the number of permutations of the multi-set is given by: $\text{[math]}$ Let $\alpha = (\alpha_0, \alpha_1, \ldots)$ and let $\mcM_\alpha$ denote the set of all permutations of the multiset with $\alpha_0$ number of $0$ s, etc.

It turns out we can use the exact same definition of inversions and major index for these permutations as well! And if we do, then we get the following distribution:

**Theorem [Mac60] Let $n = \sum \alpha_i$ where $\alpha = (\alpha_0, \alpha_1, \ldots)$ . Then $\text{[math]}$ where $\text{[math]}$

Let's look at our example to see how this major index and inversion sets are calculated. Let $\sigma = 1210$ be the permutation we want to look at. Then $\text{[math]}$ and $\text{[math]}$ implying $\text{[math]}$

Playing this game with every permutation gives us the following: $\text{[math]}$

Which means we have $\text{[math]}$ Finally, notice that since we have one $0$ s, two $1$ s and one $2$ , then we have $\alpha = (1,2,1)$ and $n = 1 + 2 + 1 = 4$ , giving us: $\text{[math]}$

Signed Permutations

We next consider signed permutations. These are permutations where we allow some of our numbers to be negative. There are two types of signed permutations:

Type $B$ - All signed permutations
Type $D$ - Even signed permutations (signed permutations with an even number of negatives)

These are called type $B$ and type $D$ as they are normally associated to the type $B$ and $D$ Coxeter groups. The type $A$ Coxeter groups are the permutation groups we looked at previously.

Let's look at an example of signed permutations of $\sym_2$ . There are only two (standard) permutations in $\sym_2$ : $\text{[math]}$ So for each one, we can assign signs: $\text{[math]}$ where $\overline{1}$ stands for $-1$ .

As we can see, there are $8$ elements in the signed permutation group of type $B$ , and looking at only the even signed permutations (first and last columns), we have $4$ elements in the signed permutation group of type $D$ .

We want to now look at a length function on signed permutations. It turns out the length function depends on whether we are in type $B$ or in type $D$ , but both of them use inversions, negatives and negative sum pairs which we define next.

Definitions: Let $\sigma = \sigma_1 \sigma_2 \ldots \sigma_n$ be a signed permutation. Let $neg(\sigma)$ be the total number of negatives in $\sigma$ . $\text{[math]}$ The inversion set for a signed permutation is exactly the same as for normal inversions: $\text{[math]}$ And finally, the negative sum pairs are the pairs of indies whos components sum to a negative number: $\text{[math]}$

It turns out that the length function for type $B$ and type $D$ signed permutations are given by the following: $\text{[math]}$ This is whole type $B$ versus type $D$ thing is slightly confusing, so let's look at an example. Again we restrict to $\sym_2$ in order to keep things simple.

Let's first look at $\sigma = \overline{1}\overline{2}$ . Notice that this is both a type $B$ and a type $D$ signed permutation and therefore we can look at its length in both regards. It has exactly one inversion: $N(\sigma) = (1,2)$ since $-1 > -2$ . It has two negative numbers, $neg(\sigma) = 2$ . And since $-1 + -2 = -3 < 0$ the negative sum pair is equal to $1$ . Therefore, $\text{[math]}$ and $\text{[math]}$

Playing this game with every element gives us the following information: $\text{[math]}$ In the cases where $\sigma$ is not an even signed permutation then we can never look at them as type $D$ and therefore we have put $-$ in the final column for these permutations.

Equidistributivity

Just as we did for standard permutations, we now want to create a new statistic that is equidistributive with length in types $B$ and $D$ . This turns out to be a generalization of major index in both cases.

Definition 1: The flag-major index of a signed permutation $\sigma$ is given by $\text{[math]}$ where $maj'$ is defined in the same way as $maj$ except that we look at our descents using the order: $\text{[math]}$

As an example of calculating $fmaj$ , let's look at the signed permutation $\sigma = \ov{1}\ov{2}34$ . It's easy to see that $neg(\sigma) = 2$ since we have two negative numbers, the difficulty for this one lies in calculating $maj'$ . Note that if we were looking at $maj$ then we would have exactly one descent at $1$ since $-1 > -2$ , BUT for $maj'$ we look at our descents in the new order which means $-1 < -2$ and therefore $\sigma$ has no descents! Therefore $maj'(\sigma) = 0$ . In other words, $\text{[math]}$

Let's look at a slightly bigger example. Let $\sigma = 21\ov{3}\ov{5}\ov{4}$ . We easily see that $neg(\sigma) = 3$ as there are three negative numbers. Regular descents give us a descent at $1$ , at $2$ and at $3$ since $2 > 1 > -3 > -5 < -4$ . In other words $maj(\sigma) = 1 + 2 + 3 = 6$ . But, our new descents occur at $1$ , $2$ and at $4$ since $2 > 1 > -3 < -5 > -4$ . In other words $maj'(\sigma) = 1 + 2 + 4 = 7$ . Therefore $\text{[math]}$

It turns out that fmaj gives us our equidistributivity for both types $B$ and types $D$ .

Theorem [ABR00] Let $W$ be the set of signed permutations of type $B$ . Then $\text{[math]}$

Theorem [Bia06] Let $W$ be the set of even signed permutations of type $D$ . For $\sigma = \sigma_1 \sigma_2 \ldots \sigma_n \in W$ , let $\sigma' = \sigma_1 \sigma_2 \ldots \sigma_{n-1} \abs{\sigma_n}$ where we take the absolute value of the last number. Then $\text{[math]}$

References

[ABR00] R. Adin, F. Brenti, Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Special issue in honor of Dominique Foata's 65th birthday (Philadelpha, PA 2000), Adv. Appl. Math. [27] (2001), 210-224. DOI
[Bia06] R. Biagioli, Signed Majonian polynomials for classical Weyl groups, Eur. J. Comb. [27]-2 (2006) 207-217. DOI
[Foa68] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. [19] (1968), 236-240. DOI
[Mac60] P.A MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York., 1960.

The Cali Garmo

Table of Contents

Equidistributivity

Multi-set Permutations

Signed Permutations

Equidistributivity

References