A154124 Signature permutation of a Catalan bijection: row 3748 of A089840.

0, 1, 2, 3, 6, 4, 5, 7, 8, 16, 19, 9, 10, 11, 15, 14, 12, 17, 18, 13, 20, 21, 22, 44, 47, 53, 56, 60, 23, 24, 25, 26, 27, 28, 29, 30, 33, 43, 52, 37, 38, 39, 40, 42, 31, 45, 46, 32, 48, 49, 50, 41, 51, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 128, 131, 137, 140, 144

Offset

0,3

Comments

This bijection of binary trees is obtained in the following way. (Inverse of Thompson's B!):

.B...C...............C...D

..\./.................\./

...x...D....-->....B...x.................()..C ........A...()

....\./.............\./...................\./....-->....\./...

.A...x...........A...x.................A...x.........C...x....

..\./.............\./...................\./...........\./.....

...x...............x.....................x.............x......

..............................................................

That is, (a . ((b . c) . d)) -> (a . (b . (c . d)))

or (a . (() . c)) -> (c . (a . ())) if the former is not possible.

Links

A. Karttunen, Table of n, a(n) for n = 0..2055

Index entries for signature-permutations of Catalan automorphisms

Prog

(Destructive version of this automorphism in Scheme:) (define (*A154124! s) (if (and (pair? s) (pair? (cdr s)) (pair? (cadr s))) (*A074680! (cdr s)) (*A089853! s)) s)

Crossrefs

Inverse: A154123. Cf. A154122.

Sequence in context: A131144 A131147 A130984 * A089853 A122306 A122309

Adjacent sequences: A154121 A154122 A154123 * A154125 A154126 A154127

Keyword

nonn

Author

Antti Karttunen, Jan 06 2009

Status

approved