Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PermutationMajorIndex

Source Notebook

Compute the major index of a permutation

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["PermutationMajorIndex"][p]

gives the major index of the permutation p.

Details and Options

The major index of a permutation p={p1,p2,…} is the sum of the positions of the descents of the permutation. A descent occurs at position j when pj>pj+1.

Examples

Basic Examples (2) 

Since descents of this permutation are at positions 2 and 4, the major index is 2+4=6:

In[1]:=
ResourceFunction["PermutationMajorIndex"][{3, 5, 1, 6, 2, 4}]
Out[1]=

There are six permutations of length 4 with major index 3:

In[2]:=
Select[Permutations[ Range[4]], (ResourceFunction["PermutationMajorIndex"][#] == 3) &]
Out[2]=
In[3]:=
Length[%]
Out[3]=

There is an equal number of permutations of length 4 with three inversions:

In[4]:=
Select[Permutations[ Range[4]], (ResourceFunction["InversionCount"][#] == 3) &]
Out[4]=
In[5]:=
Length[%]
Out[5]=

Properties and Relations (1) 

The number of permutations of length n with major index k and inversion count i is the same as the number of permutations of length n with major index i and inversion count k:

In[6]:=
n = 7; k = 10; i = 4;
In[7]:=
p = Permutations[Range[n]];
In[8]:=
Length[Select[ p, (ResourceFunction["PermutationMajorIndex"][#] == k && ResourceFunction["InversionCount"][#] == i) &]] === Length[Select[ p, (ResourceFunction["PermutationMajorIndex"][#] == i && ResourceFunction["InversionCount"][#] == k) &]]
Out[8]=

Neat Examples (1) 

The number of permutations of length 4 with given major index and inversion count:

In[9]:=
p = Permutations[Range[4]];
In[10]:=
Table[Length[ Select[p, (ResourceFunction["PermutationMajorIndex"][#] == k && ResourceFunction["InversionCount"][#] == i) &]], {k, 0, 6}, {i, 0, 6}] // MatrixForm
Out[10]=

Version History

  • 1.0.0 – 06 July 2020

Related Resources

License Information