A065184 -id:A065184 - cp's OEIS frontend

A065161 Number of orbits into which the Foata transform partitions the symmetric group Sn, i.e., a(n) is the number of cycles in the permutations A065181 - A065184 found in range [0,n!-1].

Original entry on oeis.org

1, 2, 4, 10, 24, 60, 138, 336, 820, 2114, 5340, 14136

Offset: 1

Antti Karttunen, Oct 19 2001

Counted with the Maple procedure FoataPermutationCycleCounts_Lengths_and_LCM given in A065163.

Cf. A065162, A065163.

a(9)-a(12) from Sean A. Irvine, Aug 19 2023

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

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

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

A060112 Sums of nonconsecutive factorial numbers.

Original entry on oeis.org

0, 1, 2, 6, 7, 24, 25, 26, 120, 121, 122, 126, 127, 720, 721, 722, 726, 727, 744, 745, 746, 5040, 5041, 5042, 5046, 5047, 5064, 5065, 5066, 5160, 5161, 5162, 5166, 5167, 40320, 40321, 40322, 40326, 40327, 40344, 40345, 40346, 40440, 40441, 40442

Offset: 1

Antti Karttunen, Mar 01 2001

Zeckendorf (Fibonacci) expansion of n (A003714) reinterpreted as a factorial expansion.
Also positions in A055089, A060117 and A060118 of the permutations that are composed of disjoint adjacent transpositions only. (That these positions are same can be seen by comparing algorithms PermRevLexUnrankAMSD, PermUnrank3R, PermUnrank3L in the respective sequences). Thus also positions of the fixed terms in A065181-A065184. See comment at A065163.
Written as disjoint cycles the permutations are: (), (1 2), (2 3), (3 4), (1 2)(3 4), (4 5), (1 2)(4 5), (2 3)(4 5), etc. Apart from the first one (the identity), these are the only kind of permutations used in campanology when moving from one "change" to next.

			Zeckendorf Expansions of first few natural numbers and the corresponding values when interpreted as factorial expansions: 0 = 0 = 0, 1 = 1 = 1, 2 = 10 = 2, 3 = 100 = 6, 4 = 101 = 7, 5 = 1000 = 24, 6 = 1001 = 25, 7 = 1010 = 26, 8 = 10000 = 120, etc.,

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Arthur T. White, Ringing the Changes, Math. Proc. Camb. Phil. Soc., September 1983, Vol. 94, part 2, pp. 203-215.
Index entries for sequences related to bell ringing

Subset of A059590. Cf. also A001611, A064640.

For PermRevLexRank, see A056019, for fibbinary see A048679 and A003714.

CampanoPerm := proc(n) local z,p,i; p := []; z := fibbinary(n); i := 1; while(z > 0) do if(1 = (z mod 2)) then p := permul(p,[[i,i+1]]); fi; i := i+1; z := floor(z/2); od; RETURN(convert(p,'permlist',i)); end;

With[{b = MixedRadix[Range[12, 2, -1]]}, FromDigits[#, b] & /@ Select[Tuples[{0, 1}, 8], SequenceCount[#, {1, 1}] == 0 &]] (* Michael De Vlieger, Jun 26 2017 *)

fill(lim,k,val)=if(k>#f, return); my(t=val+f[k]); if(t<=lim, listput(v,t); fill(lim,k+2,t)); fill(lim,k+1,val)
list(lim)=my(k,t=1); local(f=List(),v=List([0])); while((t*=k++)<=lim, listput(f,t)); f=Vecrev(f); fill(lim,1,0); Set(v) \\ Charles R Greathouse IV, Jun 25 2017

first(n) = my(res = [0, 1], k = 1, t = 1, p = 1); while(#res < n, k++; t++; p *= t; res = concat(res, vector(fibonacci(k), i, res[i]+p))); vector(n, i, res[i]) \\ David A. Corneth, Jun 26 2017

a(n) = PermRevLexRank(CampanoPerm(n))

a(A001611(n)) = (n-1)! for n > 2. - David A. Corneth, Jun 25 2017

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

Original entry on oeis.org

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;

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;

cp's OEIS Frontend

A065161 Number of orbits into which the Foata transform partitions the symmetric group Sn, i.e., a(n) is the number of cycles in the permutations A065181 - A065184 found in range [0,n!-1].

Views

Author

Keywords

Comments

Crossrefs

Extensions

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

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

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

A060112 Sums of nonconsecutive factorial numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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

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