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

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,3

Comments

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.

Links

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

Formula

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

Maple

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.

Prog

(Scheme functions implementing this automorphism on S-expressions, three different variants):
(define (*A057162 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (cdr lt) (cons nt (car lt)))))))
(define (*A057162 s) (fold-right (lambda (x y) (*A057163 (append (*A057163 y) (list (*A057163 x))))) (quote ()) s))
(define (*A057162! s) (*A057508! s) (*A069768! s) s)

Crossrefs

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

Sequence in context: A089860 A130960 A130927 * A125982 A125983 A130364

Adjacent sequences: A057159 A057160 A057161 * A057163 A057164 A057165

Keyword

nonn

Author

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

Status

approved