A065161 -id:A065161 - cp's OEIS frontend

A065181 Permutation of nonnegative integers produced when the finite permutations listed by A055089 are subjected to inverse of Foata's transformation. Inverse of A065182.

0, 1, 2, 5, 3, 4, 6, 7, 14, 23, 17, 20, 8, 11, 12, 22, 13, 21, 9, 10, 16, 18, 15, 19, 24, 25, 26, 29, 27, 28, 54, 55, 86, 119, 95, 110, 62, 71, 78, 116, 79, 113, 65, 68, 92, 102, 89, 103, 30, 31, 38, 47, 41, 44, 48, 49, 84, 118, 94, 108, 50, 53, 80, 117, 83, 109, 51, 52

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Here we use the inverse of the left-right maxima variant of Foata's transformation, which works by rotating each cycle largest element first and then sorts the cycles to ascending order, according to that first (and largest) element of each.

I.M. Gessel and R. P. Stanley, Algebraic Enumeration, chapter 21 in Handbook of Combinatorics, Vol. 2, edited by R.L.Graham et al., The MIT Press, Mass, 1995, page 1045.

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065183, A065184 and A055089 and A056019 for the requisite Maple procedures.

[seq(PermRevLexRank(FoataInv(PermRevLexUnrank(j))),j=0..119)];
with(group); FoataInv := p -> map(op, sort([op(map(RotCycleLargestFirst,convert(p,`disjcyc`))),op(FixedCycles(p))], sortbyfirst));
sortbyfirst := (a,b) -> `if`((a[1] < b[1]),true,false);
FindLargest := proc(a) local i,m; m := 0; for i from 1 to nops(a) do if(0 = m) then m := i; else if(a[i] > a[m]) then m := i; fi; fi; od; RETURN(m); end;
RotCycleLargestFirst := proc(c) local x; x := FindLargest(c); if(x <= 1) then RETURN(c); else RETURN([op(c[x..nops(c)]),op(c[1..(x-1)])]); fi; end;
FixedCycles := proc(p) local a,i; a := []; for i from 1 to nops(p) do if(p[i] = i) then a := [op(a),[i]]; fi; od; RETURN(a); end;

A065163 Maximal orbit size in the symmetric group partitioned by the upper records version of the Foata transform (i.e., a(n) is the maximum cycle length found in the corresponding permutations A065181-A065184 in range [0, n!-1]).

Original entry on oeis.org

1, 1, 3, 7, 25, 216, 963, 23435, 92225, 2729205, 17313348, 182553725, 4235194171

Offset: 1

Antti Karttunen, Oct 19 2001

Note: the number of fixed terms in each successive range [0, n!-1] is given by A000045(n+1) (Fibonacci numbers) and the corresponding positions by A060112. (Foata transform fixes a permutation only if it is composed of disjoint adjacent transpositions.)

This version of the Foata transform is one of several. This map takes a permutation s in S_n with k cycles to a permutation t in S_n with k upper records, i.e., k indices i for which t(i) > max{t(j): j < i}. - Theodore Zhu, Aug 15 2014

Cf. A065161, A065162.

For the requisite Maple procedures see sequences A057502, A057542, A060117, A060125.

FoataPermutationCycleCounts_Lengths_and_LCM := proc(upto_n) local u,n,a,b,i,f; a := []; b := []; f := 1; for i from 0 to upto_n! -1 do b := [op(b),1+PermRank3R(Foata(PermUnrank3R(i)))]; if((f - 1) = i) then a := [op(a),[CountCycles(b), CycleLengths1(b), CyclesLCM(b)]]; print (a); f := f*(nops(a)+1); fi; od; RETURN(a); end;
lcmlist := proc(a) local z,e; z := 1; for e in a do z := ilcm(z,e); od; RETURN(z); end;
CyclesLCM := b -> lcmlist(map(nops,convert(b,'disjcyc')));

More terms from Theodore Zhu, Aug 15 2014

A065184 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the left-right maxima variant of Foata's transformation. Inverse of A065183.

Original entry on oeis.org

0, 1, 2, 5, 3, 4, 6, 7, 14, 23, 15, 22, 8, 21, 12, 16, 19, 11, 17, 10, 9, 13, 20, 18, 24, 25, 26, 29, 27, 28, 54, 55, 86, 119, 87, 118, 56, 117, 84, 88, 115, 59, 89, 58, 57, 85, 116, 114, 30, 31, 80, 107, 81, 106, 48, 49, 60, 67, 61, 66, 74, 92, 38, 113, 47, 101, 112, 100

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065181, A065182 for Maple procedure Foata and A060117 for PermUnrank3R and A060125 for PermRank3R.

[seq(PermRank3R(Foata(PermUnrank3R(j))),j=0..119)];

A065183 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the inverse of (variant of) Foata's transformation. Inverse of A065184.

Original entry on oeis.org

0, 1, 2, 4, 5, 3, 6, 7, 12, 20, 19, 17, 14, 21, 8, 10, 15, 18, 23, 16, 22, 13, 11, 9, 24, 25, 26, 28, 29, 27, 48, 49, 78, 108, 103, 91, 74, 111, 62, 69, 75, 104, 101, 94, 100, 83, 71, 64, 54, 55, 80, 109, 107, 90, 30, 31, 36, 44, 43, 41, 56, 58, 72, 110, 106, 77, 59, 57, 81

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065182, A065181 for Maple procedure FoataInv and A060117 for PermUnrank3R and A060125 for PermRank3R.

[seq(PermRank3R(FoataInv(PermUnrank3R(j))),j=0..119)];

A065182 Permutation of nonnegative integers produced when the finite permutations listed by A055089 are subjected to Foata transform. Inverse of A065181.

Original entry on oeis.org

0, 1, 2, 4, 5, 3, 6, 7, 12, 18, 19, 13, 14, 16, 8, 22, 20, 10, 21, 23, 11, 17, 15, 9, 24, 25, 26, 28, 29, 27, 48, 49, 72, 96, 97, 73, 74, 76, 50, 100, 98, 52, 99, 101, 53, 77, 75, 51, 54, 55, 60, 66, 67, 61, 30, 31, 84, 108, 109, 85, 78, 91, 36, 115, 102, 42, 103, 114, 43

Offset: 0

Antti Karttunen, Oct 19 2001

nonn

Here we use a variant of Foata's transformation, which forms a new permutation by "inserting parentheses" at each left-right maxima, to delimit cycles.

I. M. Gessel and R. P. Stanley, Algebraic Enumeration, chapter 21 in Handbook of Combinatorics, Vol. 2, edited by R.L.Graham et al., The MIT Press, Mass, 1995, page 1045.

Joe Buhler and R. L. Graham, Juggling Drops and Descents, Amer. Math. Monthly, 101, (no. 6) 1994, 507 - 519.
Index entries for sequences that are permutations of the natural numbers

A065161-A065163 give cycle counts and max lengths. Cf. also A065183, A065184 and A055089 and A056019 for the requisite Maple procedures.

[seq(PermRevLexRank(Foata(PermRevLexUnrank(j))),j=0..119)];
with(group); Foata := proc(p) local c,c1,i,m; c := []; c1 := []; m := 0; for i from 1 to nops(p) do if(p[i] > m) then if(nops(c1) > 1) then c := [op(c),c1]; fi; m := p[i]; c1 := []; fi; c1 := [op(c1),p[i]]; od; if(nops(c1) > 1) then c := [op(c),c1]; fi; RETURN(convert(c,'permlist',nops(p))); end;

A195924 The number of fixed points in S_n by the action of Foata's bijection.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 80, 256, 918, 3464

Offset: 0

Austin Roberts Oct 26 2011

Foata's bijection takes a permutation w with maj(w) = x to a permutation F(w) with inv(F(w)) = x. Applying F repeatedly partitions the symmetric group into distinct orbits. F also preserves inverse descent sets.

			Below are the orbits of S_4 in order of size. The first 10 are fixed points.
[(1, 2, 3, 4)]
[(2, 1, 3, 4)]
[(2, 3, 1, 4)]
[(2, 3, 4, 1)]
[(3, 2, 1, 4)]
[(3, 2, 4, 1)]
[(3, 4, 2, 1)]
[(4, 3, 2, 1)]
[(4, 1, 3, 2)]
[(1, 4, 2, 3)]
[(2, 4, 3, 1), (4, 2, 3, 1)]
[(1, 3, 2, 4), (3, 1, 2, 4)]
[(1, 4, 3, 2), (4, 3, 1, 2)]
[(1, 2, 4, 3), (4, 1, 2, 3)]
[(2, 1, 4, 3), (4, 2, 1, 3), (2, 4, 1, 3)]
[(1, 3, 4, 2), (3, 1, 4, 2), (3, 4, 1, 2)]

James Pfieffer, personal communication.

Dominique Foata and Marcel-Paul Schützenberger, Major Index and inversion number of permutations , Math. Nachr. 83 (1978), 143-159

Cf. A195924, A195931, A065161.

A065162 Least common multiple of all orbit sizes (cycle lengths in corresponding permutations A065181-A065184) into which the Foata transform partitions the symmetric group Sn.

Original entry on oeis.org

1, 1, 3, 84, 392700, 134303400, 144049802170012200, 20408430429061596071366416200, 44398211066986010729368646573034503961122478555908400, 265062009098171901647881980851886506540968043007100873153849200

Offset: 1

Antti Karttunen, Oct 19 2001

nonn

Counted with the Maple procedure FoataPermutationCycleCounts_Lengths_and_LCM given in A065163.

A065161, A065163.

More terms from Sean A. Irvine, Aug 19 2023

A195931 The number of orbits in S_n by the action of Foata's bijection.

Original entry on oeis.org

1, 1, 2, 5, 16, 56, 236, 998, 4544, 20346

Offset: 0

Austin Roberts, Oct 26 2011

Foata's bijection takes a permutation w with maj(w)=x to a permutation F(w) with inv(F(w))=x. Applying F repeatedly partitions the symmetric group into distinct orbits. F also preserves inverse descent sets.

			The orbits of S_4 are:
[(1, 2, 3, 4)]
[(2, 1, 3, 4)]
[(2, 3, 1, 4)]
[(2, 3, 4, 1)]
[(3, 2, 1, 4)]
[(3, 2, 4, 1)]
[(3, 4, 2, 1)]
[(4, 3, 2, 1)]
[(2, 1, 4, 3), (4, 2, 1, 3), (2, 4, 1, 3)]
[(2, 4, 3, 1), (4, 2, 3, 1)]
[(1, 3, 2, 4), (3, 1, 2, 4)]
[(1, 3, 4, 2), (3, 1, 4, 2), (3, 4, 1, 2)]
[(1, 4, 3, 2), (4, 3, 1, 2)]
[(4, 1, 3, 2)]
[(1, 2, 4, 3), (4, 1, 2, 3)]
[(1, 4, 2, 3)]

James Pfeiffer, personal communication.

Dominique Foata and Marcel-Paul Schützenberger, Major Index and inversion number of permutations, Math. Nachr. 83 (1978), 143-159

Cf. A195931, A195924, A065161

cp's OEIS Frontend

A065181 Permutation of nonnegative integers produced when the finite permutations listed by A055089 are subjected to inverse of Foata's transformation. Inverse of A065182.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

A065163 Maximal orbit size in the symmetric group partitioned by the upper records version of the Foata transform (i.e., a(n) is the maximum cycle length found in the corresponding permutations A065181-A065184 in range [0, n!-1]).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

A065184 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the left-right maxima variant of Foata's transformation. Inverse of A065183.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065183 Permutation of nonnegative integers produced when the finite permutations listed by A060117 are subjected to the inverse of (variant of) Foata's transformation. Inverse of A065184.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A065182 Permutation of nonnegative integers produced when the finite permutations listed by A055089 are subjected to Foata transform. Inverse of A065181.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

A195924 The number of fixed points in S_n by the action of Foata's bijection.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A065162 Least common multiple of all orbit sizes (cycle lengths in corresponding permutations A065181-A065184) into which the Foata transform partitions the symmetric group Sn.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A195931 The number of orbits in S_n by the action of Foata's bijection.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs