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]).

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

Offset: 1

Author

Antti Karttunen, Oct 19 2001

Keywords

• nonn
• more

Comments

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

Crossrefs

Cf. A065161, A065162.

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

Programs

Maple

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')));

Extensions

More terms from Theodore Zhu, Aug 15 2014