login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

%I

%S 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 49,50,54,55,57,58,59,61,62,63,64,31,32,34,35,36,40,41,43,44,47,52,53,

%U 56,60,26,27,29,30,33,38,39,42,51,24,25,28,37,23,129,130,132,133,134

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

%C 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 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 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 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 A. Karttunen, <a href="/A057161/b057161.txt">Table of n, a(n) for n = 0..2055</a>

%H 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 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 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 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>

%F 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 As a composition of related permutations:

%F a(n) = A069767(A069769(n)).

%F a(n) = A057163(A057162(A057163(n))).

%F a(n) = A057164(A057504(A057164(n))). [For a proof, see pp. 53-54 in the "Introductory survey ..." draft]

%p a(n) = CatalanRankGlobal(RotateTriangularization(A014486[n]))

%p CatalanRankGlobal given in A057117 and the other Maple procedures in A038776.

%p 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 BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));

%p BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+binwidth(BinTreeLeftBranch(n))))));

%p 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 (Scheme functions implementing this automorphism on S-expressions, three different variants):

%o (define (*A057161 s) (cond ((null? s) s) (else (append (*A057161 (car s)) (list (cdr s))))))

%o (define (*A057161 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (car lt) (cons (cdr lt) nt))))))

%o (define (*A057161! s) (*A069769! s) (*A069767! s) s)

%o ;; A version working directly on nonnegative integers (definec is a memoization macro from _Antti Karttunen_'s IntSeq-library):

%o (definec (A057161 n) (if (zero? n) n (A085201bi (A057161 (A072771 n)) (A057548 (A072772 n))))) ;; A085201bi, see: A085201.

%Y Inverse: A057162.

%Y Also, a "SPINE"-transform of A069774, and thus occurs as row 12 of A130403.

%Y Other related permutations: A057163, A057164, A057501, A057504, A057505.

%Y Cf. A001683 (cycle counts), A057544 (max cycle lengths).

%K nonn

%O 0,3

%A _Antti Karttunen_, Aug 18 2000; entry revised Jun 06 2014

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 10:59 EST 2019. Contains 329389 sequences. (Running on oeis4.)