A089864 Involution of natural numbers induced by the Catalan automorphism gma089864 acting on the binary trees/parenthesizations encoded by A014486/A063171.

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

Offset: 0

Author

Antti Karttunen, Nov 29 2003

Keywords

• nonn

Comments

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.)

.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.

Examples

			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,...
		

Links

• A. Karttunen, C-program for computing this sequence
• Index entries for signature-permutations induced by Catalan automorphisms

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).