Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FoataTransform

Source Notebook

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

Contributed by: Shenghui Yang

ResourceFunction["FoataTransform"][perm]

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

Details

The Foata tranform is also known as Foata's Fundamental Transformation, and is denoted by Φ.
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.
Foata's Fundamental Transformation is a bijection on permutations that maps the distribution of descents to the distribution of excedances, EXC(w)=DES(Φ(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 with the two line notation:

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

Properties and Relations (2) 

FoataTransform produces a permutation Φ(p) whose number of descents matches the number of excedances in the original permutation p.

Generate a random permutation:

In[2]:=
p1 = Permute[Range[30], RandomPermutation[30]]
Out[2]=

Apply FoataTransform onto the given permutation:

In[3]:=
p2 = ResourceFunction["FoataTransform"][p1]
Out[3]=

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

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

The indices of excedance from the original permutation and the descendent of the transformed permutation:

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

The number of elements are the same in each list:

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

Apply Foata transformation to all permutations in each symmetric group with n elements:

Count the number of permutation cycles by their length in each permutation group:

Largest cycle in each symmetric group:

In[8]:=
(Last@KeyValueMap[List, #] & /@ connectCt)[[All, 1]]
Out[8]=

Tabulate the occurrence of permutation cycle in each symmetric group:

In[9]:=
Tabular[KeyMap[ExtendedKey["Cycle Length", ToString[#]] &, #] & /@ Map[If[Head[#] === Missing, 0, #] &, SortBy[#, Key] & /@ KeyUnion[connectCt], {2}]]
Out[9]=

Possible Issues (1) 

The input must be a valid permutation of {1,2,3,…,n}, including all elements and no duplication. Otherwise the function returns unevaluated:

In[10]:=
{ResourceFunction["FoataTransform"][{5, 3, 2, 1}], ResourceFunction["FoataTransform"][{5, 4, 3, 2, 1, \[Pi]}]}
Out[10]=

Neat Examples (1) 

Find the correspondence that links the original permutation and the one after the application of the Foata 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["FoataTransform"][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