cp's OEIS Frontend

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

%I A057161 #49 Sep 09 2017 19:48:20
%S A057161 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,
%T A057161 49,50,54,55,57,58,59,61,62,63,64,31,32,34,35,36,40,41,43,44,47,52,53,
%U A057161 56,60,26,27,29,30,33,38,39,42,51,24,25,28,37,23,129,130,132,133,134
%N A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.
%C A057161 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.
%C A057161 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).
%C A057161 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.
%C A057161 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".
%H A057161 A. Karttunen, <a href="/A057161/b057161.txt">Table of n, a(n) for n = 0..2055</a>
%H A057161 A. Karttunen, <a href="http://web.archive.org/web/20121004142217/http://ndirty.cute.fi/~karttu/matikka/Nekomorphisms/CatBijections.pdf">Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft)</a>, pp. 51-54.
%H A057161 A. Karttunen, <a href="http://oeis.org/wiki/User:Antti_Karttunen/Notes_on_the_orbits_of_A074679-A074680">Notes on the orbits of the related permutations A074679/A074680</a>, OEIS Wiki.
%H A057161 A. Karttunen, <a href="/A057161/a057161.svg">Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees</a>
%H A057161 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%F A057161 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'.]
%F A057161 As a composition of related permutations:
%F A057161 a(n) = A069767(A069769(n)).
%F A057161 a(n) = A057163(A057162(A057163(n))).
%F A057161 a(n) = A057164(A057504(A057164(n))). [For a proof, see pp. 53-54 in the "Introductory survey ..." draft]
%p A057161 a(n) = CatalanRankGlobal(RotateTriangularization(A014486[n]))
%p A057161 CatalanRankGlobal given in A057117 and the other Maple procedures in A038776.
%p A057161 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;
%p A057161 BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
%p A057161 BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+binwidth(BinTreeLeftBranch(n))))));
%p A057161 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;
%o A057161 (Scheme functions implementing this automorphism on S-expressions, three different variants):
%o A057161 (define (*A057161 s) (cond ((null? s) s) (else (append (*A057161 (car s)) (list (cdr s))))))
%o A057161 (define (*A057161 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (car lt) (cons (cdr lt) nt))))))
%o A057161 (define (*A057161! s) (*A069769! s) (*A069767! s) s)
%o A057161 ;; A version working directly on nonnegative integers (definec is a memoization macro from _Antti Karttunen_'s IntSeq-library):
%o A057161 (definec (A057161 n) (if (zero? n) n (A085201bi (A057161 (A072771 n)) (A057548 (A072772 n))))) ;; A085201bi, see: A085201.
%Y A057161 Inverse: A057162.
%Y A057161 Also, a "SPINE"-transform of A069774, and thus occurs as row 12 of A130403.
%Y A057161 Other related permutations: A057163, A057164, A057501, A057504, A057505.
%Y A057161 Cf. A001683 (cycle counts), A057544 (max cycle lengths).
%K A057161 nonn
%O A057161 0,3
%A A057161 _Antti Karttunen_, Aug 18 2000; entry revised Jun 06 2014