Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 InverseFoataTransform

Source Notebook

Convert a permutation into one whose number of excedances equals the number of descents in the original

Contributed by: Shenghui Yang

ResourceFunction["InverseFoataTransform"][perm]

generates a permutation whose number of excedances matches the number of descents in the original permutation perm.

Details

The inverse Foata transform is also known as the inverse of Foata's Fundamental Transformation, and is denoted by Φ-1.
In a permutation π=π1π2π3…πn (one-line notation), an index i (where 1<=i<n) is a descent if πi>πi+1. The number of descents (DES) is the count of such i.
In a permutation π=π1π2π3…πn (one-line notation), an index i (where 1<=i<=n) is an excedance if πi>i. The number of excedances (EXC) is the count of such i.
The inverse of Foata's Fundamental Transformation is a bijection on permutations that maps the distribution of descents to the distribution of excedances, DES(w)=EXC(Φ-1(w)). In short, given a permutation written in one-line notation, rearrange elements via a canonical cycle representation and flatten it in a specific order. The number of descents in the original permutation equals the number of excedances in the transformed permutation. It's mainly used to prove descents and excedances are equidistributed.

Examples

Basic Examples (1) 

Generate the corresponding permutation given a permutation displayed in two line notation:

In[1]:=
ResourceFunction["InverseFoataTransform"][{3, 8, 6, 9, 5, 1, 4, 2, 7}]
Out[1]=

Properties and Relations (2) 

The InverseFoataTransform is indeed the inverse of ResourceFunction["FoataTransform"]:

In[2]:=
ResourceFunction["FoataTransform"][{3, 8, 6, 9, 5, 1, 4, 2, 7}]
Out[2]=

The inverse transform converts the result above back into the input:

In[3]:=
ResourceFunction["InverseFoataTransform"][%]
Out[3]=

InverseFoataTransform produces a permutation Φ-1(p) whose number of excedances matches the number of descents in the original permutation p. Generate a random permutation:

In[4]:=
SeedRandom[1234]; p1 = Permute[Range[30], RandomPermutation[30]]
Out[5]=

Apply InverseFoataTransform onto the given permutation:

In[6]:=
p2 = ResourceFunction["InverseFoataTransform"][p1]
Out[6]=

Verify the equidistribution property between two permutations, DES(w)=EXC(Φ-1(w)):

In[7]:=
des[perm_] := Position[Differences[perm], _?(# < 0 &)] // Flatten
In[8]:=
exc[perm_] := Position[MapIndexed[{#, #2[[1]]} &, p1], _?(#[[1]] > #[[2]] &), 1, Heads -> False] // Flatten

Show the indices of descent from the original permutation and the indices of excedance of the transformed permutation:

In[9]:=
{des[p1], exc[p2]}
Out[9]=

The number of elements are the same in each list:

In[10]:=
Length /@ %
Out[10]=

Neat Examples (1) 

Find the correspondence that links the original permutation and the one after the application of the inverse transform:

In[11]:=
circleLayout[n_] := Table[{Cos[2. \[Pi]/n i], Sin[2. \[Pi]/n i]}, {i, 0, n - 1}]; n = 20; r = Range[n]; SeedRandom[17]; p1 = Permute[r, RandomPermutation[n]]; p2 = ResourceFunction["InverseFoataTransform"][p1]; cyc2 = FindPermutation[p1, p2]; Graph[Thread[r -> PermutationList[cyc2, n]], VertexLabels -> Placed[Automatic, Center], VertexCoordinates -> Thread[r -> circleLayout[n]], VertexSize -> .5, ImageSize -> 360 ]
Out[12]=

Publisher

Shenghui Yang

Version History

  • 1.0.0 – 20 August 2025

Source Metadata

Related Resources

Author Notes

In Wolfram Language, the canonical ordering of permutation cycles differs slightly from that in Foata's paper. In WL, each cycle is rotated so that it starts with its smallest element, and the cycles are then sorted in ascending order of these smallest elements. In contrast, Foata's approach rotates each cycle so that it starts with its largest element, and the cycles are then arranged in ascending order of these largest elements.

License Information