A057503 -id:A057503 - cp's OEIS frontend

A073200 Number of simple Catalan bijections of type B.

0, 1, 0, 3, 1, 0, 2, 2, 1, 0, 7, 3, 3, 1, 0, 8, 4, 2, 3, 1, 0, 6, 6, 8, 2, 3, 1, 0, 4, 5, 7, 7, 2, 3, 1, 0, 5, 7, 6, 6, 8, 2, 3, 1, 0, 17, 8, 5, 8, 7, 7, 2, 2, 1, 0, 18, 9, 4, 4, 6, 8, 7, 3, 3, 1, 0, 20, 10, 22, 5, 5, 5, 8, 4, 2, 2, 1, 0, 21, 14, 21, 17, 4, 4, 6, 5, 8, 3, 3, 1, 0

Offset: 0

Antti Karttunen, Jun 25 2002

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.
The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:
0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)
1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)
2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)
3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)
4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)
The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Four other tables giving the corresponding cycle-counts: A073201, counts of the fixed elements: A073202, the lengths of the largest cycles: A073203, the LCM's of all the cycles: A073204. The ordinary compositions are encoded using the N X N -> N bijection A054238 (which in turn uses the bit-interleaving function A000695).
The first 21 rows of this table:.
Row 0: A069770. Row 1: A072796. Row 2: A057163. Row 3: A073269, Row 4: A057163 (duplicate), Row 5: A073270, Row 6: A069767, Row 7: A001477 (identity perm.), Row 8: A069768, Row 9: A073280.
Row 10: A069770 (dupl.), Row 11: A072796 (dupl.), Row 12: A057511, Row 13: A073282, Row 14: A057512, Row 15: A073281, Row 16: A057509, Row 17: A073280 (dupl.), Row 18: A057510, Row 19: A073283, Row 20: A073284.
Other Catalan bijection-induced EIS-permutations which occur in this table. Only the first known occurrence is given. Involutions are marked with *, others paired with their inverse:.
Row 164: A057164*, Row 168: A057508*, Row 179: A072797*.
Row 41: A073286 - Row 69: A073287. Row 105: A073290 - Row 197: A073291. Row 416: A073288 - Row 696: A073289.
Row 261: A057501 - Row 521: A057502. Row 2618: A057503 - Row 5216: A057504. Row 2614: A057505 - Row 5212: A057506.
Row 10435: A073292 - Row ...: A073293. Row 17517: A057161 - Row ...: A057162.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

This is equivalent to map M given by Donaghey on page 81 of his paper "Automorphisms on ..." and also equivalent to the transformation procedure depicted in the picture (23) of Donaghey-Shapiro paper.

This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

Antti Karttunen, Table of n, a(n) for n = 0..2055
Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, Vol. 23, No. 3 (1977), pp. 291-301.
Indranil Ghosh, Python program for computing this sequence (after the functions mentioned in the OEIS wiki).
Antti Karttunen, Illustration of symmetric general trees whose A057163-reflection is also symmetric (ones that occur in 2-cycles of A057505/A057506)
Antti Karttunen, On the fixed points of A071661 (Notes in OEIS Wiki regarding the 2-cycles of this automorphism)
D. E. Knuth, Pre-Fascicle 4a: Generating All Trees, Exercise 17, 7.2.1.6.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057506.
The 2nd, 3rd, 4th, 5th and 6th "power": A071661, A071663, A071665, A071667, A071669.
Other related permutations: A057501, A057503, A057161.
Cycle counts: A057507. Maximum cycle lengths: A057545. LCM's of all cycles: A060114. See A057501 for other Maple procedures.
Row 17 of table A122288.
Cf. A080981 (the "primitive elements" of this automorphism), A079438, A079440, A079442, A079444, A080967, A080968, A080972, A080272, A080292, A083929, A080973, A081164, A123050, A125977, A126312.

map(CatalanRankGlobal,map(DonagheysM, A014486)); or map(CatalanRankGlobal,map(DeepRotateTriangularization, A014486));
DonagheysM := n -> pars2binexp(DonagheysMP(binexp2pars(n)));
DonagheysMP := h -> `if`((0 = nops(h)),h,[op(DonagheysMP(car(h))),DonagheysMP(cdr(h))]);
DeepRotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := DeepRotateTriangularization(BinTreeRightBranch(n))*2; 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(a(A072772(n)))). [This recurrence 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) = A057164(A057163(n)).
a(n) = A057163(A057506(A057163(n))).

A057506 Signature-permutation of a Catalan Automorphism: (inverse of) "Donaghey's map M", acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

This is inverse of A057505, which is a signature permutation of Catalan automorphism (bijection) known as "Donaghey's map M". See A057505 for more comments, links and references.

Antti Karttunen, Table of n, a(n) for n = 0..23713
A. Karttunen (et al) at OEIS Wiki, Maple implementations of CatalanRankGlobal, CatalanSequences, car, cdr, binexp2pars and pars2binexp functions
A. Karttunen at OEIS WIki, Scheme implementations of CatalanRankSexp and CatalanUnrankSexp
Indranil Ghosh, Python program for computing this sequence (after the functions mentioned in the OEIS wiki)
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057505.
Cf. A057161, A057162, A057163, A057164, A057501, A057502, A057503, A057504 (for similar signature permutations of simple Catalan automorphisms).
Cf. A057507 (cycle counts).
The 2nd, 3rd, 4th, 5th and 6th "powers" of this permutation: A071662, A071664, A071666, A071668, A071670.
Row 12 of table A122287.
Cf. also A014486, A080300, A080069, A080070.

map(CatalanRankGlobal,map(DonagheysA057506,CatalanSequences(196))); # Where CatalanSequences(n) gives the terms A014486(0..n).
DonagheysA057506 := n -> pars2binexp(deepreverse(DonagheysA057505(deepreverse(binexp2pars(n)))));
DonagheysA057505 := h -> `if`((0 = nops(h)), h, [op(DonagheysA057505(car(h))), DonagheysA057505(cdr(h))]);
# The following corresponds to automorphism A057164:
deepreverse := proc(a) if 0 = nops(a) or list <> whattype(a) then (a) else [op(deepreverse(cdr(a))), deepreverse(a[1])]; fi; end;
# The rest of required Maple-functions: see the given OEIS Wiki page.

(define (A057506 n) (CatalanRankSexp (*A057506 (CatalanUnrankSexp n))))
(define (*A057506 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (cdr lt) (cons nt (*A057506 (car lt))))))))
;; Functions CatalanRankSexp and CatalanUnrankSexp can be found at OEIS Wiki page.

a(n) = A057163(A057164(n)).

a(n) = A057163(A057505(A057163(n))) = A057164(A057505(A057164(n))).

Entry revised by Antti Karttunen, May 30 2017

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.

A122285 Signature permutations of ENIPS-transformations of Catalan automorphisms in table A122203.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 2, 2, 1, 0, 5, 8, 3, 2, 1, 0, 6, 7, 4, 3, 2, 1, 0, 7, 6, 6, 5, 3, 2, 1, 0, 8, 5, 5, 4, 5, 3, 2, 1, 0, 9, 4, 7, 6, 6, 6, 3, 2, 1, 0, 10, 22, 8, 7, 4, 5, 6, 3, 2, 1, 0, 11, 21, 9, 8, 7, 4, 4, 4, 3, 2, 1, 0, 12, 20, 14, 13, 8, 7, 5, 5, 4, 3, 2, 1, 0, 13, 18, 11, 12, 13

Offset: 0

Antti Karttunen, Sep 01 2006, Jun 20 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122203 with the recursion scheme "ENIPS", or equivalently row n is obtained as ENIPS(SPINE(n-th row of A089840)). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A122286. This table contains also all the rows of A122204 and A089840.

A. Karttunen, paper in preparation, draft available by e-mail.

Index entries for signature-permutations of Catalan automorphisms

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A082348, 2: A057508, 3: A131141, 4: A131143, 5: A131145, 6: A131147, 7: A131173, 8: A131169, 9: A131149, 10: A131151, 11: A131153, 12: A131171, 13: A131155, 14: A131157, 15: A131159, 16: A131161, 17: A057503, 18: A131163, 19: A131165, 20: A131167, 21: A069768. Other rows: row 251: A130360, 3608: A130339, 3613: A057510, 65352: A074686.

See also tables A089840, A122200, A122201-A122204, A122283-A122284, A122286-A122288, A122289-A122290, A130400-A130403. As a sequence differs from A122286 for the first time at n=92, where a(n)=18, while A122286(n)=17.

A073202 Array of fix-count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 3, 0, 1, 1, 2, 8, 1, 0, 1, 1, 0, 20, 0, 0, 0, 1, 1, 5, 60, 2, 0, 1, 0, 1, 1, 0, 181, 0, 0, 0, 0, 0, 1, 1, 14, 584, 5, 0, 2, 0, 1, 2, 1, 1, 0, 1916, 0, 0, 0, 0, 0, 5, 0, 1, 1, 42, 6476, 14, 0, 5, 0, 0, 14, 1, 2, 1, 1, 0, 22210, 0, 0, 0, 0, 0, 42, 0, 1, 0, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of elements fixed by the Catalan bijection (given in the corresponding row of A073200) when it acts on A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Cf. also A073201, A073203.
Few EIS-sequences which occur in this table. Only the first known occurrence(s) given (marked with ? if not yet proved/unclear):
Rows 0, 2, 4, etc.: "Aerated Catalan numbers" shifted right and prepended with 1 (Cf. A000108), Row 1: A073190, Rows 3, 5, 261, 2614, 2618, 17517, etc: A019590 but with offset 0 instead of 1 (means that the Catalan bijections like A073269, A073270, A057501, A057505, A057503 and A057161 never fix any Catalan structure of size larger than 1).
Row 6: A036987, Row 7: A000108, Rows 12, 14, 20, ...: A057546, Rows 16, 18: A034731, Row 41: A073268, Row 105: essentially A073267, Row 57, ..., 164: A001405, Row 168: A073192, Row 416: essentially A023359 ?, Row 10435: also A036987.

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]

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

Original entry on oeis.org

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

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 clockwise.

In A057161 and A057162, the cycles between A014138(n-1)-th and A014138(n)-th term partition A000108(n) objects encoded by the corresponding terms of A014486 into A001683(n+2) equivalence classes of flexagons (or unlabeled plane boron trees), thus the latter sequence can be counted with the Maple procedure A057162_CycleCounts given below. Cf. also the comments in A057161.

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

Inverse: A057161.
Also, an "ENIPS"-transform of A069773, and thus occurs as row 17 of A130402.
Other related permutations: A057163, A057164, A057501, A057503, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularizationR(A014486[n]))
RotateTriangularizationR := n -> ReflectBinTree(RotateTriangularization(ReflectBinTree(n)));
with(group); A057162_CycleCounts := 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,RotateTriangularization(CatalanUnrank(n,r)))]; od; a := [op(a),(`if`((n < 2),1,nops(convert(b,'disjcyc'))))]; od; RETURN(a); end;
# See also the code in A057161.

As a composition of related permutations:
a(n) = A069768(A057508(n)).
a(n) = A057163(A057161(A057163(n))).
a(n) = A057164(A057503(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 143.]

A057504 Signature-permutation of the inverse of Deutsch's 1998 bijection on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
Antti Karttunen, C program which computes this sequence.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057503. Row 12 of A122286.

A080237(n) = A057515(a(n)) holds for all n. See comment at A057503.

Equivalence with Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

A057544 Maximum cycle length (orbit size) in the rotation permutation of n+2 side polygon triangularizations.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 07 2000

I.e., in permutations A057161 and A057162 (also A057503 and A057504), the longest cycle among all cycles between the (A014138(n-2)+1)-th and (A014138(n-1))-th terms.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A057542, A057543, A057545.

a(n)=if(n>2,n+2,1) \\ Charles R Greathouse IV, Jun 20 2024

a(0)=1, a(1)=1, a(2)=2, a(n)=n+2.
From Chai Wah Wu, Jul 28 2022: (Start)
a(n) = 2*a(n-1) - a(n-2) for n > 4.
G.f.: (-2*x^4 + 2*x^3 + x^2 - x + 1)/(x - 1)^2. (End)

More terms from Sean A. Irvine, Jun 13 2022

cp's OEIS Frontend

A073200 Number of simple Catalan bijections of type B.

Views

Author

Keywords

Comments

Links

Crossrefs

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

A057506 Signature-permutation of a Catalan Automorphism: (inverse of) "Donaghey's map M", acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Scheme

Formula

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

A122285 Signature permutations of ENIPS-transformations of Catalan automorphisms in table A122203.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A073202 Array of fix-count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057504 Signature-permutation of the inverse of Deutsch's 1998 bijection on Dyck paths.

Views

Author

Keywords