Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PermutationExcedances

Source Notebook

Get the indices of a permutation where the value of the element is larger than its index

Contributed by: Shenghui Yang

ResourceFunction["PermutationExcedances"][perm]

gives the indices i where permi>i in perm={p1,p2,…,pn}.

ResourceFunction["PermutationExcedances"][perm,"BitVector"]

gives the indices in a "BitVector" data structure.

Details

The input must be a permutation of 1 to n.
The function works in both cloud and desktop environment. The desktop environment uses FunctionCompile and "BitVector" to speed up the computation. If the input is more than 50 items, the function switches to the compiled version in the desktop environment.
MacMahon observed that the descent/ascent number and excedance number are equidistributed, that is, the number of permutations in Sn with j descents equals the number of permutations with j excedances for all j (see Reference Citations).

Examples

Basic Examples (2) 

Consider the permutation:

In[1]:=
p = {2, 8, 1, 5, 4, 7, 6, 3, 9};

Its excedance indices are {1,2,4,6} because p[[1]]=2 >1, p[[2]]=8>2, p[[4]]=5 >4 and p[[6]]=7 >6:

In[2]:=
ex = ResourceFunction["PermutationExcedances"][p]
Out[2]=

Scope (1) 

For large permuted lists of integers, it is much more efficient to store the output in a "BitVector" than a list:

In[3]:=
base = Range[5*10^7]; perm = RandomSample[base, 5*10^7];
In[4]:=
(res1 = ResourceFunction["PermutationExcedances"][perm, "BitVector"]) // ByteCount
Out[4]=
In[5]:=
(res2 = ResourceFunction["PermutationExcedances"][perm]) // ByteCount
Out[5]=
In[6]:=
res1["BitList"] === res2
Out[6]=

Properties and Relations (2) 

MacMahon observed that the descent/ascent number and excedance number are equidistributed, that is, the number of permutations in Sn with j descents equals the number of permutations with j excedances for all j:

In[7]:=
allP = Permutations[Range[9]];

The number of permutations with 4 ascents is the same as those with 4 excedances:

In[8]:=
Parallelize@ Count[allP, _?(Length@ResourceFunction["PermutationAscents"][#] == 4 &)]
Out[8]=
In[9]:=
Parallelize@ Count[allP, _?(ResourceFunction["PermutationExcedances"][#, "BitVector"]["BitCount"] == 4 &)]
Out[9]=

Possible Issues (2) 

All input must be positive integers. Otherwise the function returns unevaluated:

In[10]:=
ResourceFunction["PermutationExcedances"][{1, 2, 3, 4, 5, 6.6}]
Out[10]=

The input must be a permutation of 1 to n, and include all numbers. Otherwise the function returns unevaluated:

In[11]:=
ResourceFunction["PermutationExcedances"][{1, 2, 3, 4, 5, 7}]
Out[11]=

Publisher

Shenghui Yang

Version History

  • 1.0.0 – 15 August 2025

Source Metadata

  • Citation:
    • Richard Ehrenborg, "The Excedance Set of a Permutation", Advances in Applied Mathematics 24, 284–299 (2000), doi:10.1006/aama.1999.0671
    • P. A. MacMahon, "Combinatory Analysis", Vol. 1, P. 186, Cambridge Univ. Press, Cambridge, UK, 1915 (reprinted by Chelsea, New York, 1955)
    • Weisstein, Eric W. Eulerian Number. From MathWorld--A Wolfram Resource.

Related Resources

License Information