A038776 -id:A038776 - cp's OEIS frontend

A057542 Maximum cycle length in each permutation between A038776(1) and A038776(A000108(n)).

1, 1, 1, 3, 4, 16, 87, 202, 607, 1441, 4708, 41888, 44741, 339108, 1617551

Offset: 0

Antti Karttunen, Sep 07 2000

Sean A. Irvine, Java program (github)

Cycle lengths of permutation A038776 given in A038774.
Cf. A057543, A057544, A057545.
LCM's of all cycles: A060113.

map(lmax,Bf2DfBinTreePermutationCycleLengths(some_value)); (e.g. 10)
bf2df := s -> (btbf2df(binrev(s),0,1)/2); # btbf2df and binrev given in A038776
Bf2DfBinTreePermutationCycleLengths := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,bf2df(CatalanUnrank(n,r)))]; od; a := [op(a),CycleLengths1(b)]; od; RETURN(a); end;
CycleLengths1 := b -> [[(nops(b)-convert(map(nops,convert(b,'disjcyc')),`+`)),`*`,1],op(map(nops,convert(b,'disjcyc')))];
last_term := proc(l) local n: n := nops(l); if(0 = n) then ([]) else (op(n,l)): fi: end:
lmax := proc(a) local e,z; z := 0; for e in a do if whattype(e) = list then e := last_term(e); fi; if e > z then z := e; fi; od; RETURN(z); end;

a(11)-a(14) from Sean A. Irvine, Jun 13 2022

A060113 Least common multiple of all orbit lengths of the permutation A038776.

Original entry on oeis.org

1, 1, 1, 3, 12, 48, 1392, 214402800, 3817990510765200, 4738197524832401740110000, 1091118722532825192362856035208963090000, 2182237445065650384725712070417926180000, 507772214574105904772762129719909048054921244582661534399180000

Offset: 0

Antti Karttunen, Mar 01 2001

nonn

Sean A. Irvine, Java program (github)

Cf. A060114, A060115.

More terms from Sean A. Irvine, Oct 25 2022

A057501 Signature-permutation of a Catalan Automorphism: Rotate non-crossing chords (handshake) arrangements; rotate the root position of general trees as encoded by A014486.

Original entry on oeis.org

0, 1, 3, 2, 7, 8, 5, 4, 6, 17, 18, 20, 21, 22, 12, 13, 10, 9, 11, 15, 14, 16, 19, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 31, 32, 34, 35, 36, 26, 27, 24, 23, 25, 29, 28, 30, 33, 40, 41, 38, 37, 39, 43, 42, 44, 47, 52, 51, 53, 56, 60, 129, 130, 132, 133, 134

Offset: 0

Antti Karttunen, Sep 03 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when "noncrossing handshakes", i.e., Stanley's interpretation (n), "n nonintersecting chords joining 2n points on the circumference of a circle", are rotated.
The same permutation is induced when the root position of plane trees (Stanley's interpretation (e)) is successively changed around the vertices.
For a good illustration how the rotation of the root vertex works, please see the Figure 6, "Rotation of an ordered rooted tree" in Torsten Mütze's paper (on page 24 in 20 May 2014 revision).
For yet another application of this permutation, please see the attached notes for A085197.
By "recursivizing" either the left or right hand side argument of A085201 in the formula, one ends either with A057161 or A057503. By "recursivizing" the both sides, one ends with A057505. - Antti Karttunen, Jun 06 2014

Antti Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 56-57.
A. Karttunen et al, Combinatorial interpretations of Catalan numbers, OEIS Wiki.
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014 (p. 24).
R. P. Stanley, Exercises on Catalan and Related Numbers (This sequence is concerned with rotations of the interpretations (e) and (n) in the Exercise 19)
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057502.
Also, a "SPINE"-transform of A074680, and thus occurs as row 17 of A122203. (Also as row 65167 of A130403.)
Successive powers of this permutation, a^2(n) - a^6(n): A082315, A082317, A082319, A082321, A082323.
Other related permutations: A057161, A057163, A057503, A057505, A057508, A057509, A057511, A069770, A069771, A069772, A069773, A069888, A069889, A082313, A082314, A085173, A086427, A123501, A127291, A127292.
Cf. also A057548, A072771, A072772, A085201, A002995 (cycle counts), A057543 (max cycle lengths), A085197, A129599, A057517, A064638, A064640.

map(CatalanRankGlobal,map(RotateHandshakes, A014486));
RotateHandshakes := n -> pars2binexp(RotateHandshakesP(binexp2pars(n)));
RotateHandshakesP := h -> `if`((0 = nops(h)),h,[op(car(h)),cdr(h)]); # This does the trick! In Lisp: (defun RotateHandshakesP (h) (append (car h) (list (cdr h))))
car := proc(a) if 0 = nops(a) then ([]) else (op(1,a)): fi: end: # The name is from Lisp, takes the first element (head) of the list.
cdr := proc(a) if 0 = nops(a) then ([]) else (a[2..nops(a)]): fi: end: # As well. Takes the rest (the tail) of the list.
PeelNextBalSubSeq := proc(nn) local n,z,c; if(0 = nn) then RETURN(0); fi; n := nn; c := 0; z := 0; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN((z - 2^(floor_log_2(z)))/2); fi; od; end;
RestBalSubSeq := proc(nn) local n,z,c; n := nn; c := 0; while(1 = 1) do c := c + (-1)^n; n := floor(n/2); if(c >= 0) then break; fi; od; z := 0; c := -1; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN(z/2); fi; od; end;
pars2binexp := proc(p) local e,s,w,x; if(0 = nops(p)) then RETURN(0); fi; e := 0; for s in p do x := pars2binexp(s); w := floor_log_2(x); e := e * 2^(w+3) + 2^(w+2) + 2*x; od; RETURN(e); end;
binexp2pars := proc(n) option remember; `if`((0 = n),[],binexp2parsR(binrev(n))); end;
binexp2parsR := n -> [binexp2pars(PeelNextBalSubSeq(n)),op(binexp2pars(RestBalSubSeq(n)))];
# Procedure CatalanRankGlobal given in A057117, other missing ones in A038776.

a(0) = 0, and for n>=1, a(n) = A085201(A072771(n), A057548(A072772(n))). [This formula reflects directly the given non-destructive Lisp/Scheme function: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some dialects), and A057548 corresponds to unary form of function 'list'].
As a composition of related permutations:
a(n) = A057509(A069770(n)).
a(n) = A057163(A069773(A057163(n))).
Invariance-identities:
A129599(a(n)) = A129599(n) holds for all n.

A057117 Permutation of nonnegative integers obtained by mapping each forest of A000108[n] rooted binary plane trees from breadth-first to depth-first encoding.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 8, 6, 9, 10, 12, 13, 11, 17, 18, 21, 22, 20, 14, 15, 16, 19, 23, 24, 26, 27, 25, 31, 32, 35, 36, 34, 28, 29, 30, 33, 45, 46, 49, 50, 48, 58, 59, 63, 64, 62, 54, 55, 57, 61, 37, 38, 40, 41, 39, 44, 47, 42, 43, 56, 60, 51, 52, 53, 65, 66, 68, 69, 67, 73, 74

Offset: 0

Antti Karttunen, Aug 11 2000

nonn

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Restriction of the automorphism A072088 to the plane binary trees.

Add one to each term and "overlay" each successive subpermutation of A000108[n] terms and one obtains A038776. Inverse permutation is A057118.

a(n) = CatalanRankGlobal(btbf2df(binrev(A014486[n]),0,1)/2)
Maple procedure CatalanRank is adapted from the algorithm 3.23 of the CAGES book, see A014486
CatalanRank := proc(n,aa) local x,y,lo,a; a := binrev(aa); y := 0; lo := 0; for x from 1 to (2*n)-1 do lo := lo + (1-(a mod 2))*Mn(n,x,y+1); y := y - ((-1)^a); a := floor(a/2); od; RETURN((binomial(2*n,n)/(n+1))-(lo+1)); end;
CatalanRankGlobal := proc(a) local n; n := floor(binwidth(a)/2); RETURN(add((binomial(2*j,j)/(j+1)),j=0..(n-1))+CatalanRank(n,a)); end;

A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.

Original entry on oeis.org

0, 1, 3, 2, 7, 8, 5, 6, 4, 17, 18, 20, 21, 22, 12, 13, 15, 16, 19, 10, 11, 14, 9, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 31, 32, 34, 35, 36, 40, 41, 43, 44, 47, 52, 53, 56, 60, 26, 27, 29, 30, 33, 38, 39, 42, 51, 24, 25, 28, 37, 23, 129, 130, 132, 133, 134

Offset: 0

Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated counterclockwise.
The number of cycles in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+2), otherwise the same sequence as for Catalan bijections *A074679/*A074680, but shifted once left (for an explanation, see the related notes in OEIS Wiki).
E.g., in range [A014137(0)..A014138(1)] = [1,1] there is one cycle (as a(1)=1), in range [A014137(1)..A014138(2)] = [2,3] there is one cycle (as a(2)=3 and a(3)=2), in range [A014137(2)..A014138(3)] = [4,8] there is also one cycle (as a(4) = 7, a(7) = 6, a(6) = 5, a(5) = 8 and a(8) = 4), and in range [A014137(3)..A014138(4)] = [9,22] there are A001683(4+2) = 4 cycles.
From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505 by the same method, when the other side of the formula is also "recursivized".

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 51-54.
A. Karttunen, Notes on the orbits of the related permutations A074679/A074680, OEIS Wiki.
A. Karttunen, Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057162.
Also, a "SPINE"-transform of A069774, and thus occurs as row 12 of A130403.
Other related permutations: A057163, A057164, A057501, A057504, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularization(A014486[n]))
CatalanRankGlobal given in A057117 and the other Maple procedures in A038776.
NextSubBinTree := proc(nn) local n,z,c; n := nn; c := 0; z := 0; while(c < 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); od; RETURN(z); end;
BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+binwidth(BinTreeLeftBranch(n))))));
RotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := BinTreeRightBranch(n); z := z + (2^w)*s; w := w + binwidth(s); z := z + (2^w); w := w + 1; n := floor(n/2); od; RETURN(z); end;

a(0) = 0, and for n>=1, a(n) = A085201(a(A072771(n)), A057548(A072772(n))). [This formula reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to unary form of function 'list'.]
As a composition of related permutations:
a(n) = A069767(A069769(n)).
a(n) = A057163(A057162(A057163(n))).
a(n) = A057164(A057504(A057164(n))). [For a proof, see pp. 53-54 in the "Introductory survey ..." draft]

A070041 Permutation of natural numbers induced by the automorphism df->bf (from the depth-first to breadth-first encoding) acting on the rooted planar binary trees encoded by A014486. (with one-based indexing).

Original entry on oeis.org

1, 2, 5, 3, 4, 11, 12, 13, 6, 7, 14, 10, 8, 9, 29, 30, 33, 31, 32, 36, 37, 34, 15, 16, 35, 19, 17, 18, 40, 41, 42, 25, 26, 38, 27, 20, 21, 39, 28, 24, 22, 23, 85, 86, 89, 87, 88, 95, 96, 97, 90, 91, 98, 94, 92, 93, 104, 105, 112, 108, 109, 106, 110, 99, 43, 44, 100, 47, 45

Offset: 1

Antti Karttunen, Apr 16 2002

nonn

A. Karttunen, Table of n, a(n) for n = 1..1430
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Compare to the plot of A082363 and A072620.

Inverse of A038776. Cf. also A057118.

A082364 Permutation of natural numbers induced by the contraction of Catalan bijection signature-permutation A082356.

Original entry on oeis.org

0, 1, 3, 4, 2, 8, 9, 12, 13, 11, 5, 6, 7, 10, 22, 23, 26, 27, 25, 35, 36, 40, 41, 39, 31, 32, 34, 38, 14, 15, 17, 18, 16, 19, 20, 21, 24, 28, 29, 33, 37, 30, 64, 65, 68, 69, 67, 77, 78, 82, 83, 81, 73, 74, 76, 80, 105, 106, 110, 111, 109, 124, 125, 130, 131, 129, 119, 120, 123

Offset: 0

Antti Karttunen, Apr 17 2003

nonn

A. Karttunen, Table of n, a(n) for n = 0..1429
A. Karttunen, Gatomorphisms (with the complete Scheme source)
Index entries for signature-permutations induced by Catalan automorphisms

Compare to the plot of A038776.

Inverse of A082363. Cf. also A082361-A082362.

a(n) = A082853(A082356(A081291(n))).

A072619 Permutation of natural numbers obtained from the permutation A072088 (zero-based).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 10, 7, 8, 9, 6, 11, 12, 13, 14, 28, 15, 33, 37, 19, 24, 21, 22, 23, 30, 25, 26, 27, 16, 18, 20, 31, 38, 17, 34, 35, 36, 29, 32, 39, 40, 41, 42, 84, 43, 98, 112, 44, 46, 45, 103, 107, 85, 117, 121, 126, 56, 70, 89, 75, 79, 61, 66, 63, 64, 65, 72, 67, 68, 69

Offset: 0

Antti Karttunen, Jun 25 2002

See the comment at A072088.

A. Karttunen, Table of n, a(n) for n = 0..1429
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Compare to the plot of A038776.

A072619(n) = A072621(n+1)-1. Inverse permutation: A072620. Cf. also A072088, A038776.

A072621 Permutation of natural numbers obtained from the permutation A072088 (one-based).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 11, 8, 9, 10, 7, 12, 13, 14, 15, 29, 16, 34, 38, 20, 25, 22, 23, 24, 31, 26, 27, 28, 17, 19, 21, 32, 39, 18, 35, 36, 37, 30, 33, 40, 41, 42, 43, 85, 44, 99, 113, 45, 47, 46, 104, 108, 86, 118, 122, 127, 57, 71, 90, 76, 80, 62, 67, 64, 65, 66, 73, 68, 69, 70

Offset: 1

Antti Karttunen, Jun 25 2002

nonn

See the comment at A072088.

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

A072621(n) = A072619(n-1)+1. Inverse permutation: A072622. Cf. also A038776.

A038774 Cycle lengths of the permutation that converts the forest of depth-first planar planted binary trees into breadth-first representation.

Original entry on oeis.org

1, 1, 3, 4, 3, 2, 16, 8, 2, 2, 87, 3, 202, 25, 5, 4, 61, 607, 63, 165, 127, 12, 8, 10, 4, 5, 927, 1441, 283, 625, 91, 52, 8, 5, 4708, 592, 1890, 86, 3505, 482, 471, 34, 84, 17, 22, 25, 5, 9, 3, 1

Offset: 1

Wouter Meeussen, May 04 2000

nonn

			The first 6 terms add up to 14=cat[4], so the cycle lengths of the permutation for forest[4] are {1, 1, 3, 4, 3, 2}. The sequence as given (50 terms) was generated on forest[10].

Cf. A038775, A038776. Max cycle lengths: A057542.

cp's OEIS Frontend

A057542 Maximum cycle length in each permutation between A038776(1) and A038776(A000108(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Extensions

A060113 Least common multiple of all orbit lengths of the permutation A038776.

Views

Author

Keywords

Links

Crossrefs

Extensions

A057501 Signature-permutation of a Catalan Automorphism: Rotate non-crossing chords (handshake) arrangements; rotate the root position of general trees as encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057117 Permutation of nonnegative integers obtained by mapping each forest of A000108[n] rooted binary plane trees from breadth-first to depth-first encoding.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A070041 Permutation of natural numbers induced by the automorphism df->bf (from the depth-first to breadth-first encoding) acting on the rooted planar binary trees encoded by A014486. (with one-based indexing).

Views

Author

Keywords

Links

Crossrefs

A082364 Permutation of natural numbers induced by the contraction of Catalan bijection signature-permutation A082356.

Views

Author

Keywords

Links

Crossrefs

Formula

A072619 Permutation of natural numbers obtained from the permutation A072088 (zero-based).

Views

Author

Keywords

Comments

Links

Crossrefs

A072621 Permutation of natural numbers obtained from the permutation A072088 (one-based).

Views

Author

Keywords

Comments

Links

Crossrefs

A038774 Cycle lengths of the permutation that converts the forest of depth-first planar planted binary trees into breadth-first representation.

Views

Author

Keywords

Examples

Crossrefs