Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PermutationCountByInversions

Source Notebook

Get the number of permutations having a specified length and number of inversions

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

ResourceFunction["PermutationCountByInversions"][n,k]

gives the number of permutations of length n with exactly k inversions.

ResourceFunction["PermutationCountByInversions"][n]

gives a List for all k starting at zero.

Details and Options

ResourceFunction["PermutationCountByInversions"][n,k] is also the number of inversion vectors of n-permutations that sum up to k, or equivalently, the number of n-permutations with inversion count k.
ResourceFunction["PermutationCountByInversions"] effectively uses generating functions to find the number of permutations.
ResourceFunction["PermutationCountByInversions"][n,All] is equivalent to ResourceFunction["PermutationCountByInversions"][n].

Examples

Basic Examples (2) 

The number of permutations of length 7 with 16 inversions:

In[1]:=
ResourceFunction["PermutationCountByInversions"][7, 16]
Out[1]=

The list of 7-permutations for all possible k:

In[2]:=
ResourceFunction["PermutationCountByInversions"][7]
Out[2]=

Scope (1) 

Using All as the second argument is equivalent to the single-argument form:

In[3]:=
ResourceFunction["PermutationCountByInversions"][7, All]
Out[3]=
In[4]:=
ResourceFunction["PermutationCountByInversions"][7]
Out[4]=

Properties and Relations (4) 

Select 4-permutations with inversion count 3:

In[5]:=
n = 4; k = 3;
In[6]:=
Select[Permutations[ Range[n]], (ResourceFunction["InversionCount"][#] == k) &]
Out[6]=

The number of selected permutations is the permutation count by inversions:

In[7]:=
Length[%]
Out[7]=
In[8]:=
ResourceFunction["PermutationCountByInversions"][n, k]
Out[8]=

The list of permutation counts for all k is long:

In[9]:=
n = 5;
In[10]:=
ResourceFunction["PermutationCountByInversions"][n]
Out[10]=
In[11]:=
Length[%] == Binomial[n, 2] + 1
Out[11]=

There is always a single permutation with zero inversions:

In[12]:=
n = 5;
In[13]:=
ResourceFunction["ToInversionVector"][Range[n]]
Out[13]=
In[14]:=
ResourceFunction["InversionCount"][Range[n]]
Out[14]=
In[15]:=
ResourceFunction["PermutationCountByInversions"][n, 0]
Out[15]=

The number of permutations with k inversions is equal to the number of permutations with inversions:

In[16]:=
n = 10; k = 4;
In[17]:=
ResourceFunction["PermutationCountByInversions"][n, k] == ResourceFunction["PermutationCountByInversions"][n, Binomial[n, 2] - k]
Out[17]=
In[18]:=
ListPlot[ResourceFunction["PermutationCountByInversions"][n]]
Out[18]=

Version History

  • 1.0.0 – 06 July 2020

Related Resources

License Information