Wolfram Research

Function Repository Resource:

InversionVectorQ

Source Notebook

Check if a list is the inversion vector of a permutation written as a list

Contributed by: Wolfram Staff

ResourceFunction["InversionVectorQ"][iv]

checks if iv is the inversion vector of a permutation list.

Details and Options

The inversion vector of a permutation of length n lists the number of times k is preceded by a number greater than k, where k runs from 1 to n.
The definition amounts to checking whether the entries of the vector are the digits of a number in base-factorial.

Examples

Basic Examples

This permutation has three numbers greater than 1 before 1, two numbers greater than 2 before 2 and so on:

Therefore this is its inversion vector:

Here is a check:

In[1]:=
ResourceFunction["InversionVectorQ"][{3, 2, 1, 0}]
Out[1]=

The positive integer 23 gives {3,2,1,0} in the factorial base, so {3,2,1,0} is an inversion vector:

In[2]:=
IntegerDigits[23, MixedRadix[{4, 3, 2, 1}]]
Out[2]=

Every inversion vector must end in 0 because the largest entry in a permutation list has nothing but smaller entries before it:

In[3]:=
ResourceFunction["InversionVectorQ"][{0, 1, 2, 3}]
Out[3]=

Resource History

See Also

License Information