A065181 -id:A065181 - 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

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;

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

A055089 List of all finite permutations in reversed colexicographic ordering.

Original entry on oeis.org

1, 2, 1, 1, 3, 2, 3, 1, 2, 2, 3, 1, 3, 2, 1, 1, 2, 4, 3, 2, 1, 4, 3, 1, 4, 2, 3, 4, 1, 2, 3, 2, 4, 1, 3, 4, 2, 1, 3, 1, 3, 4, 2, 3, 1, 4, 2, 1, 4, 3, 2, 4, 1, 3, 2, 3, 4, 1, 2, 4, 3, 1, 2, 2, 3, 4, 1, 3, 2, 4, 1, 2, 4, 3, 1, 4, 2, 3, 1, 3, 4, 2, 1, 4, 3, 2, 1, 1, 2, 3, 5, 4, 2, 1, 3, 5, 4, 1, 3, 2, 5, 4, 3, 1, 2

Offset: 0

Antti Karttunen, Apr 18 2000

			In this table, each row consists of A001563(n) permutations of n+1 terms; i.e., we have (1/) 2,1/ 1,3,2; 3,1,2; 2,3,1; 3,2,1/ 1,2,4,3; 2,1,4,3; ... .
Append to each an infinite number of fixed terms and we get a list of rearrangements of the natural numbers, but with only a finite number of terms permuted:
1/2,3,4,5,6,7,8,9,...
2,1/3,4,5,6,7,8,9,...
1,3,2/4,5,6,7,8,9,...
3,1,2/4,5,6,7,8,9,...
2,3,1/4,5,6,7,8,9,...
3,2,1/4,5,6,7,8,9,...
1,2,4,3/5,6,7,8,9,...
2,1,4,3/5,6,7,8,9,...
Alternatively, if we take only the first n terms of each such infinite row, then the first n! rows give all permutations of the elements 1,2,...,n.

Antti Karttunen, Rows 0..719 of the irregular table, flattened.
Daniel Forgues, Tilman Piesk, et al., Orderings, OEIS Wiki.
Antti Karttunen, Ranking and unranking functions, OEIS Wiki.
Tilman Piesk, Permutations and partitions in the OEIS, Wikiversity.
Lorenzo Sauras-Altuzarra, Some arithmetical problems that are obtained by analyzing proofs and infinite graphs, arXiv:2002.03075 [math.NT], 2020.
Index entries for sequences related to factorial base representation
Index entries for sequences related to permutations

Inversion vectors: A007623, cycle counts: A055090, minimum number of transpositions: A055091, minimum number of adjacent transpositions: A034968, order of each permutation: A055092, number of non-fixed elements: A055093, positions of inverses: A056019, positions after Foata transform: A065181; positions of fixed-point-free involutions: A064640.
Cf. A057112, A060112, A060117, A060118, A060132, A060133.
Cf. A195663, array of the infinite rows.
This permutation list gives essentially the same information as A030298/A030299, but in a more compact way, by skipping those permutations of A030298 that start with a fixed element.
A220658(n) gives the rank r of the permutation of which the term at a(n) is an element.
A220659(n) gives the zero-based position (from the left) of that a(n) in that permutation of rank r.
A084558(r)+1 gives the size of the finite subsequence (of the r-th infinite, but finitary permutation) which has been included in this list.

factorial_base := proc(nn) local n,a,d,j,f; n := nn; if(0 = n) then RETURN([0]); fi; a := []; f := 1; j := 2; while(n > 0) do d := floor(`mod`(n,(j*f))/f); a := [d,op(a)]; n := n - (d*f); f := j*f; j := j+1; od; RETURN(a); end;
fexlist2permlist := proc(a) local n,b,j; n := nops(a); if(0 = n) then RETURN([1]); fi; b := fexlist2permlist(cdr(a)); for j from 1 to n do if(b[j] >= ((n+1)-a[1])) then b[j] := b[j]+1; fi; od; RETURN([op(b),(n+1)-a[1]]); end;
fac_base := n -> fac_base_aux(n,2); fac_base_aux := proc(n,i) if(0 = n) then RETURN([]); else RETURN([op(fac_base_aux(floor(n/i),i+1)), (n mod i)]); fi; end;
PermRevLexUnrank := n -> `if`((0 = n),[1],fexlist2permlist(fac_base(n)));
cdr := proc(l) if 0 = nops(l) then ([]) else (l[2..nops(l)]); fi; end; # "the tail of the list"
# Same algorithm in different guise, showing how permutations are composed of adjacent transpositions (compare to algorithm PermUnrank3R at A060117):
PermRevLexUnrankAMSDaux := proc(n,r, pp) local s,p,k; p := pp; if(0 = r) then RETURN(p); else s := floor(r/((n-1)!)); for k from n-s to n-1 do p := permul(p,[[k,k+1]]); od; RETURN(PermRevLexUnrankAMSDaux(n-1, r-(s*((n-1)!)), p)); fi; end;
PermRevLexUnrankAMSD := proc(r) local n; n := nops(factorial_base(r)); convert(PermRevLexUnrankAMSDaux(n+1,r,[]),'permlist',1+(((r+2) mod (r+1))*n)); end;

A055089L[n_] := Reverse@SortBy[DeleteCases[Permutations@Range@n, {, n}], Reverse]; Flatten@Array[A055089L, 4] (* JungHwan Min, Aug 28 2016 *)

[seq(op(PermRevLexUnrank(j)), j=0..)]; (see Maple code given below).

Name changed by Tilman Piesk, Feb 01 2012

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

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

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

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

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

A055089 List of all finite permutations in reversed colexicographic ordering.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A060112 Sums of nonconsecutive factorial numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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