# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a089864
Showing 1-1 of 1
%I A089864 #8 Oct 15 2015 10:55:25
%S A089864 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 A089864 35,36,30,33,28,23,24,29,25,26,27,40,41,39,37,38,52,51,56,58,59,60,62,
%U A089864 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 A089864 Involution of natural numbers induced by the Catalan automorphism gma089864 acting on the binary trees/parenthesizations encoded by A014486/A063171.
%C A089864 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 A089864 .A..B.C..D.....B..A.D..C.......B...C.......C...B.......A...B........B...A...
%C A089864 ..\./.\./.......\./.\./.........\./.........\./.........\./..........\./....
%C A089864 ...x...x....-->..x...x.......()..x..-->..()..x...........x..()...-->..x..().
%C A089864 ....\./...........\./.........\./.........\./.............\./..........\./..
%C A089864 .....x.............x...........x...........x...............x............x...
%C A089864 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 A089864 A. Karttunen, C-program for computing this sequence
%H A089864 Index entries for signature-permutations induced by Catalan automorphisms
%e A089864 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 A089864 ...................one tree of one internal........2 trees of 2 internal nodes
%e A089864 ..empty tree.........(non-leaf) node.................................
%e A089864 ........................................................\/.......\/..
%e A089864 ......x......................\/........................\/.........\/.
%e A089864 n=....0......................1..........................2..........3.
%e A089864 a(n)=.0......................1..........................2..........3.(all these trees are fixed by this transformation)
%e A089864 however, the next 5 trees, with 3 internal nodes, in range [A014137[2], A014138[2]] = [4,8] change as follows:
%e A089864 ........\/.....\/.................\/.....\/...
%e A089864 .......\/.......\/.....\/.\/.....\/.......\/..
%e A089864 ......\/.......\/.......\_/.......\/.......\/.
%e A089864 n=.....4........5........6........7........8..
%e A089864 ....................|.........................
%e A089864 ....................|.........................
%e A089864 ....................V.........................
%e A089864 ......\/.........\/.............\/.........\/.
%e A089864 .......\/.......\/.....\/.\/.....\/.......\/..
%e A089864 ......\/.......\/.......\_/.......\/.......\/.
%e A089864 a(n)=..5........4........6........8........7..
%e A089864 thus we obtain the first nine terms of this sequence: 0,1,2,3,5,4,6,8,7,...
%o A089864 (Scheme functions implementing this automorphism on list-structures:)
%o A089864 (define (gma089864! s) (cond ((pair? s) (if (pair? (car s)) (swap! (car s))) (if (pair? (cdr s)) (swap! (cdr s))))) s)
%o A089864 (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
%Y A089864 a(n) = A089859(A089859(n)) = A089863(A089863(n)). Row 1654694 of A089840.
%Y A089864 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 A089864 nonn
%O A089864 0,3
%A A089864 _Antti Karttunen_, Nov 29 2003
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE