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 denote the set of permutations of . Our goal is to describe a statitistic on which is equidistributive with length.
Definitions: For a permutation let be the set of descents of , and let denote the set of inversions, Recall that is just the length of our permutaiton.
As an example, let be our permutation. Then since we have descents in position and position . Therefore . Since 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 , therefore . Looking at every pair, we see Therefore, the length of is as there are inversions.
Definition: The major index of is the sum of all the descents.
In our example, we had whose descents were . Therefore, to calculate the major index, we just need to sum up all the descents: .
The major index is actually equidistributive with length! What this means is that for every with length there is a with major index . Note that 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 is equal to
Theorem [Mac60] Both major index and length are Mahonian. In other words,
As an example, let's look at 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 be the following recursive map.
For if then . Else we induct on length of and define and inductively. For our initial step, let . Then, to find we start with and if then we draw a bar after each element of which is strictly greater than , else we draw a bar after each element of which is stricly less than . These bars will denote blocks of numbers. In each block, take the last number and move it to the front. This new permutation is . We continue until and let .
This works best with an example. Let . Then Then . Since we place a bar after , giving . As every element is in its own block, we have nothing to do giving us Then . Since we place a bar after and , giving . As every element is in its own block, we have nothing to do, giving us Then . Since we place a bar after , giving us . As is a block, we move the last number to the front, giving us: . Therefore Then . Since we have . Moving the last element of each block to the front gives and therefore Then . Since we have since every number is bigger than . Therefore Then . Since we have . Here we have two blocks, and putting the last number in the front gives . In other words
Therefore . Notice that and which is exactly what we want this map to do.
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 is a multi-set. Notice that it is not a set since appears twice. Looking at permutations of we get the following permutations: Notice that every number appears twice!
That's cause there are two s which can swap places without the number changing! That means there are half as many permutations; or in other words number of permutations.
But notice that we have one and one , 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 be a multi-set with number of s, number of s, \etc. where . Then the number of permutations of the multi-set is given by: Let and let denote the set of all permutations of the multiset with number of 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 where . Then where
Let's look at our example to see how this major index and inversion sets are calculated. Let 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 s, two s and one , then we have and , giving us:
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:
These are called type and type as they are normally associated to the type and Coxeter groups. The type Coxeter groups are the permutation groups we looked at previously.
Let's look at an example of signed permutations of . There are only two (standard) permutations in : So for each one, we can assign signs: where stands for .
As we can see, there are elements in the signed permutation group of type , and looking at only the even signed permutations (first and last columns), we have elements in the signed permutation group of type .
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 or in type , but both of them use inversions, negatives and negative sum pairs which we define next.
Definitions: Let be a signed permutation. Let be the total number of negatives in . 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 and type signed permutations are given by the following: This is whole type versus type thing is slightly confusing, so let's look at an example. Again we restrict to in order to keep things simple.
Let's first look at . Notice that this is both a type and a type signed permutation and therefore we can look at its length in both regards. It has exactly one inversion: since . It has two negative numbers, . And since the negative sum pair is equal to . Therefore, and
Playing this game with every element gives us the following information: In the cases where is not an even signed permutation then we can never look at them as type and therefore we have put in the final column for these permutations.
Just as we did for standard permutations, we now want to create a new statistic that is equidistributive with length in types and . This turns out to be a generalization of major index in both cases.
Definition 1: The flag-major index of a signed permutation is given by where is defined in the same way as except that we look at our descents using the order:
As an example of calculating , let's look at the signed permutation . It's easy to see that since we have two negative numbers, the difficulty for this one lies in calculating . Note that if we were looking at then we would have exactly one descent at since , BUT for we look at our descents in the new order which means and therefore has no descents! Therefore . In other words,
Let's look at a slightly bigger example. Let . We easily see that as there are three negative numbers. Regular descents give us a descent at , at and at since . In other words . But, our new descents occur at , and at since . In other words . Therefore
It turns out that fmaj gives us our equidistributivity for both types and types .
Theorem [ABR00] Let be the set of signed permutations of type . Then
Theorem [Bia06] Let be the set of even signed permutations of type . For , let where we take the absolute value of the last number. Then