A089864 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

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.

LINKS

Table of n, a(n) for n=0..72.

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

PROG

(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: A366474 A138606 A166013 * A073290 A073299 A073298

Adjacent sequences: A089861 A089862 A089863 * A089865 A089866 A089867

KEYWORD

nonn

AUTHOR

Antti Karttunen, Nov 29 2003

STATUS

approved