Function Repository Resource:

# PermutationCountByInversions

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]:=
 Out[1]=

The list of 7-permutations for all possible k:

 In[2]:=
 Out[2]=

### Scope (1)

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

 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=

### Properties and Relations (4)

Select 4-permutations with inversion count 3:

 In[5]:=
 In[6]:=
 Out[6]=

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

 In[7]:=
 Out[7]=
 In[8]:=
 Out[8]=

The list of permutation counts for all k is long:

 In[9]:=
 In[10]:=
 Out[10]=
 In[11]:=
 Out[11]=

There is always a single permutation with zero inversions:

 In[12]:=
 In[13]:=
 Out[13]=
 In[14]:=
 Out[14]=
 In[15]:=
 Out[15]=

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

 In[16]:=
 In[17]:=
 Out[17]=
 In[18]:=
 Out[18]=

## Version History

• 1.0.0 – 06 July 2020