|
Search: id:A089864
|
|
|
| A089864 |
|
Involution of natural numbers induced by the Catalan automorphism gma089864 acting on the binary trees/parenthesizations encoded by A014486/A063171. |
|
+0
10
|
|
| 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, 35, 36, 30, 33, 28, 23, 24, 29, 25, 26, 27, 40, 41, 39, 37, 38, 52, 51, 56, 58, 59, 60, 62, 63, 64, 43, 42, 53, 57, 61, 44, 54, 45, 46, 47, 55, 48, 49, 50, 87, 88, 90, 91, 92, 96, 97, 99
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
This "gatomorphism" 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.)
.A..B.C..D.....B..A.D..C.......B...C.......C...B.......A...B........B...A...
..\./.\./.......\./.\./.........\./.........\./.........\./..........\./....
...x...x....-->..x...x.......()..x..-->..()..x...........x..()...-->..x..().
....\./...........\./.........\./.........\./.............\./..........\./..
.....x.............x...........x...........x...............x............x...
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.
|
|
LINKS
|
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms
|
|
EXAMPLE
|
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:
...................one tree of one internal........2 trees of 2 internal nodes
..empty tree.........(non-leaf) node.................................
........................................................\/.......\/..
......x......................\/........................\/.........\/.
n=....0......................1..........................2..........3.
a(n)=.0......................1..........................2..........3.(all these trees are fixed by this transformation)
however, the next 5 trees, with 3 internal nodes, in range [A014137[2], A014138[2]] = [4,8] change as follows:
........\/.....\/.................\/.....\/...
.......\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\_/.......\/.......\/.
n=.....4........5........6........7........8..
....................|.........................
....................|.........................
....................V.........................
......\/.........\/.............\/.........\/.
.......\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\_/.......\/.......\/.
a(n)=..5........4........6........8........7..
thus we obtain the first nine terms of this sequence: 0,1,2,3,5,4,6,8,7,...
|
|
PROGRAM
|
(Scheme functions implementing this automorphism on list-structures:)
(define (gma089864! s) (cond ((pair? s) (if (pair? (car s)) (swap! (car s))) (if (pair? (cdr s)) (swap! (cdr s))))) s)
(define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
|
|
CROSSREFS
|
a(n) = A089859(A089859(n)) = A089863(A089863(n)). Row 1654694 of A089840.
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).
Sequence in context: A075169 A138606 A166013 this_sequence A073290 A073299 A073298
Adjacent sequences: A089861 A089862 A089863 this_sequence A089865 A089866 A089867
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Antti Karttunen (Firstname.Surname(AT)iki.fi), Nov 29 2003
|
|
|
Search completed in 0.002 seconds
|
