

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)



OFFSET

0,1


COMMENTS

This sequence is based on the observation that the terms of A014486 (2ndigit 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.


LINKS



EXAMPLE

We start from the simplest such binary tree: 0.0 (binary depthfirst encoding = 2, from left to right, 1 with the zero of the last leaf ignored); then encode it as an ordinary rooted plane tree (depthfirstwise) to get the code 1010 = decimal 10, which in turn, when interpreted as an encoding of binary tree is:
..0.0
.0.1. (whose rooted plane tree coding is 10110100 = 180 in decimal)
..1.. etc.


MAPLE

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), k1); 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), i1); i := i  ((floor_log_2(x)+1)/2); y := btdf2t((n mod (2^i)), i1); RETURN((2^(floor_log_2(y)+2))*((2^(floor_log_2(x)+1)) + x) + 2*y); else RETURN(2); fi; end;


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



