cp's OEIS Frontend

A057119 Iterative "rewrite" sequence of binary plane trees.

%I A057119 #10 Mar 24 2024 02:28:02
%S A057119 2,10,180,47940,3185189700,13760582141553025860,
%T A057119 254536428082497193743150874618461037380,
%U A057119 86730091025558229301371439971941296450524845723997443510460490068605668041540
%N A057119 Iterative "rewrite" sequence of binary plane trees.
%C A057119 This sequence is based on the 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.
%H A057119 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%e A057119 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:
%e A057119 ..0.0
%e A057119 .0.1. (whose rooted plane tree coding is 10110100 = 180 in decimal)
%e A057119 ..1.. etc.
%p A057119 a(n) = bt_df2tree_apply_k_times(2,n)
%p A057119 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;
%p A057119 bintree_depth_first2tree := n -> ((btdf2t(n*2,floor_log_2(n)+1)/2) - 2^(2*(floor_log_2(n)+1)));
%p A057119 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;
%Y A057119 Cf. A057120, A057121, A057122.
%K A057119 nonn
%O A057119 0,1
%A A057119 _Antti Karttunen_, Aug 11 2000