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:
MAPLE
a(n) = CatalanRankGlobal(RotateTriangularization(A014486[n]))
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 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (car lt) (cons (cdr lt) nt))))))
;; A version working directly on nonnegative integers (definec is a memoization macro from Antti Karttunen's IntSeq-library):
CROSSREFS
Inverse: A057162.
KEYWORD
nonn
AUTHOR
Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014
STATUS
approved