A082856 - OEIS

A082856

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

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 binary-AND (A004198) (or respectively: binary-OR, A003986) of the corresponding codes. See A082858-A082860.

LINKS

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

Antti 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 bit-0, which is always 1 for nonempty trees) the codes for the left and right hand side subtrees of the tree.

PROG

(Scheme-functions showing the essential idea. For the full source, follow the "Alternative Catalan Orderings" link.)

(define A082856 (compose-funs bin-interleave binexp->parenthesization A014486))

(define (bin-interleave bt) (cond ((not (pair? bt)) 0) (else (1+ (* 2 (+ (* 2 (A000695 (bin-interleave (car bt)))) (A000695 (bin-interleave (cdr bt)))))))))

CROSSREFS

Inverse: A082857. Cf. A072634-A072637, A075173-A075174, A000695.

Sequence in context: A063499 A285381 A372255 * A307140 A254402 A060881

Adjacent sequences: A082853 A082854 A082855 * A082857 A082858 A082859

KEYWORD

nonn

AUTHOR

Antti Karttunen, May 06 2003

STATUS

approved