The Cali Garmo

does Math

Major Index

By Cali G , Published on Tue 12 November 2019
Category: math / symmetric functions

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. 😉

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 and let N(\sigma) denote the set of inversions, \ie 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 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.

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

Theorem [Mac60] Both major index and length are Mahonian. In other words,

As an example, let's look at \sym_3 and let's verify that we have the above equality. Therefore, in all cases we have

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 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 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 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 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 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 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

Therefore \phi(2376514) = 2763154. Notice that and 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: Notice that every number appears twice!

That's cause there are two 1s 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: which is also the multi-set number (the multi-set version of the binomial coefficient). This is normally denoted as:

Let M be a multi-set with \alpha_0 number of 0s, \alpha_1 number of 1s, \etc. where \sum \alpha_i = n. Then the number of permutations of the multi-set is given by: 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 0s, 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 where

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 and implying

Playing this game with every permutation gives us the following:

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

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: So for each one, we can assign signs: 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. The inversion set for a signed permutation is exactly the same as for normal inversions: And finally, the negative sum pairs are the pairs of indies whos components sum to a negative number:

It turns out that the length function for type B and type D signed permutations are given by the following: 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, and

Playing this game with every element gives us the following information: 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 where maj' is defined in the same way as maj except that we look at our descents using the order:

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,

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

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

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

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.