

A082856


Recursive binary interleaving code for rooted plane binary trees, as ordered by A014486.


4



0, 1, 3, 5, 11, 35, 7, 21, 69, 139, 2059, 43, 547, 8227, 15, 39, 23, 277, 4117, 71, 85, 1093, 16453, 32907, 8388747, 2187, 526347, 134219787, 171, 2091, 555, 131619, 33554979, 8235, 8739, 2105379, 536879139, 143, 2063, 47, 551, 8231, 31, 55, 279, 65813, 16777493, 4119, 4373, 1052693, 268439573, 79, 103, 87, 341, 4181, 1095, 1109
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

This encoding has a property that the greatest common subtree i.e. the intersect (or the least common supertree, the union) of any two trees can be obtained by simply computing the binaryAND (A004198) (or respectively: binaryOR, A003986) of the corresponding codes. See A082858A082860.


LINKS

Table of n, a(n) for n=0..57.
A. Karttunen, Alternative Catalan Orderings (with the complete Scheme source)


EXAMPLE

The empty tree . has code 0, the tree of two edges (and leaves) \/ has code 1 and in general tree's code is obtained by interleaving into odd and even bits (above bit0, which is always 1 for nonempty trees) the codes for the left and right hand side subtrees of the tree.


PROG

(Schemefunctions showing the essential idea. For the full source, follow the "Alternative Catalan Orderings" link.)
(define A082856 (composefuns bininterleave binexp>parenthesization A014486))
(define (bininterleave bt) (cond ((not (pair? bt)) 0) (else (1+ (* 2 (+ (* 2 (A000695 (bininterleave (car bt)))) (A000695 (bininterleave (cdr bt)))))))))


CROSSREFS

Inverse: A082857. Cf. A072634A072637, A075173A075174, A000695.
Sequence in context: A121926 A063499 A285381 * A307140 A254402 A060881
Adjacent sequences: A082853 A082854 A082855 * A082857 A082858 A082859


KEYWORD

nonn


AUTHOR

Antti Karttunen May 06 2003


STATUS

approved



