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



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A057119 Iterative "rewrite" sequence of binary plane trees. 4
2, 10, 180, 47940, 3185189700, 13760582141553025860, 254536428082497193743150874618461037380, 86730091025558229301371439971941296450524845723997443510460490068605668041540 (list; graph; refs; listen; history; text; internal format)



This sequence is based on observation that the terms of A014486 (2n-digit balanced binary sequences) encode rooted plane trees with n+1 vertices (n edges), but also rooted binary plane trees with n+1 leaves, i.e. 2n edges, 2n+1 vertices.


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

Index entries for sequences related to rooted trees


We start from the simplest such binary tree: 0.0 (binary depth-first encoding = 2, from left-to-right, 1 with the zero of the last leaf ignored); then encode it as an ordinary rooted plane tree (depth-first wise) to get the code 1010 = decimal 10, which in turn, when interpreted as an encoding of binary tree is:


.0.1. (whose rooted plane tree coding is 10110100 = 180 in decimal)

..1.. etc.


a(n) = bt_df2tree_apply_k_times(2, n)

bt_df2tree_apply_k_times := proc(n, k) option remember; if(0 = k) then (n) else bt_df2tree_apply_k_times(bintree_depth_first2tree(n), k-1); fi; end;

bintree_depth_first2tree := n -> ((btdf2t(n*2, floor_log_2(n)+1)/2) - 2^(2*(floor_log_2(n)+1)));

btdf2t := proc(n, ii) local i, e, x, y; i := ii; if(n >= (2^i)) then x := btdf2t(n - (2^i), i-1); i := i - ((floor_log_2(x)+1)/2); y := btdf2t((n mod (2^i)), i-1); RETURN((2^(floor_log_2(y)+2))*((2^(floor_log_2(x)+1)) + x) + 2*y); else RETURN(2); fi; end;


Cf. A057120, A057121, A057122.

Sequence in context: A063573 A086675 A319607 * A226563 A037267 A177399

Adjacent sequences:  A057116 A057117 A057118 * A057120 A057121 A057122




Antti Karttunen, Aug 11 2000



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 May 13 08:08 EDT 2021. Contains 343836 sequences. (Running on oeis4.)