login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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.

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 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: A121926 A063499 A285381 * A307140 A254402 A060881

Adjacent sequences:  A082853 A082854 A082855 * A082857 A082858 A082859

KEYWORD

nonn

AUTHOR

Antti Karttunen May 06 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 10:03 EST 2020. Contains 332041 sequences. (Running on oeis4.)