%I #8 Oct 15 2015 10:55:25
%S 0,1,2,3,5,4,6,8,7,12,13,11,9,10,15,14,19,21,22,16,20,17,18,31,32,34,
%T 35,36,30,33,28,23,24,29,25,26,27,40,41,39,37,38,52,51,56,58,59,60,62,
%U 63,64,43,42,53,57,61,44,54,45,46,47,55,48,49,50,87,88,90,91,92,96,97,99
%N Involution of natural numbers induced by the Catalan automorphism gma089864 acting on the binary trees/parenthesizations encoded by A014486/A063171.
%C This "Catalan bijection" effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)
%C .A..B.C..D.....B..A.D..C.......B...C.......C...B.......A...B........B...A...
%C ..\./.\./.......\./.\./.........\./.........\./.........\./..........\./....
%C ...x...x....-->..x...x.......()..x..-->..()..x...........x..()...-->..x..().
%C ....\./...........\./.........\./.........\./.............\./..........\./..
%C .....x.............x...........x...........x...............x............x...
%C i.e. we apply A069770 (that is, the corresponding automorphism) both to the left and right subtree of a binary tree and fix both the empty tree and the tree of one internal node.
%H A. Karttunen, <a href="/A089408/a089408.c.txt">C-program for computing this sequence</a>
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a>
%e To obtain this signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree transforms to, as follows:
%e ...................one tree of one internal........2 trees of 2 internal nodes
%e ..empty tree.........(non-leaf) node.................................
%e ........................................................\/.......\/..
%e ......x......................\/........................\/.........\/.
%e n=....0......................1..........................2..........3.
%e a(n)=.0......................1..........................2..........3.(all these trees are fixed by this transformation)
%e however, the next 5 trees, with 3 internal nodes, in range [A014137[2], A014138[2]] = [4,8] change as follows:
%e ........\/.....\/.................\/.....\/...
%e .......\/.......\/.....\/.\/.....\/.......\/..
%e ......\/.......\/.......\_/.......\/.......\/.
%e n=.....4........5........6........7........8..
%e ....................|.........................
%e ....................|.........................
%e ....................V.........................
%e ......\/.........\/.............\/.........\/.
%e .......\/.......\/.....\/.\/.....\/.......\/..
%e ......\/.......\/.......\_/.......\/.......\/.
%e a(n)=..5........4........6........8........7..
%e thus we obtain the first nine terms of this sequence: 0,1,2,3,5,4,6,8,7,...
%o (Scheme functions implementing this automorphism on list-structures:)
%o (define (gma089864! s) (cond ((pair? s) (if (pair? (car s)) (swap! (car s))) (if (pair? (cdr s)) (swap! (cdr s))))) s)
%o (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
%Y a(n) = A089859(A089859(n)) = A089863(A089863(n)). Row 1654694 of A089840.
%Y Number of cycles: A089402. Number of fixed points: A089408. Max. cycle size & LCM of all cycle sizes: A046698 (in range [A014137(n-1)..A014138(n-1)] of this permutation).
%K nonn
%O 0,3
%A _Antti Karttunen_, Nov 29 2003