The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486. 15
 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 (list; graph; refs; listen; history; text; internal format)
 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 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". LINKS 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. FORMULA 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] MAPLE 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; PROG (Scheme functions implementing this automorphism on S-expressions, three different variants): (define (*A057161 s) (cond ((null? s) s) (else (append (*A057161 (car s)) (list (cdr s)))))) (define (*A057161 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (car lt) (cons (cdr lt) nt)))))) (define (*A057161! s) (*A069769! s) (*A069767! s) s) ;; A version working directly on nonnegative integers (definec is a memoization macro from Antti Karttunen's IntSeq-library): (definec (A057161 n) (if (zero? n) n (A085201bi (A057161 (A072771 n)) (A057548 (A072772 n))))) ;; A085201bi, see: A085201. CROSSREFS 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). Sequence in context: A130396 A131010 A071657 * A130363 A089862 A125981 Adjacent sequences:  A057158 A057159 A057160 * A057162 A057163 A057164 KEYWORD nonn AUTHOR Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 18 23:16 EDT 2021. Contains 347548 sequences. (Running on oeis4.)