|
%I #56 Mar 16 2024 11:55:58
%S 1,1,2,1,4,4,4,1,8,16,32,16,32,16,8,1,16,64,256,256,1024,1024,1024,
%T 256,1024,1024,1024,256,256,64,16,1,32,256,2048,4096,32768,65536,
%U 131072,65536,524288,1048576,2097152,1048576,2097152,1048576,524288,65536,524288
%N a(n) is the number of different shapes of balanced binary trees with n nodes. The tree is balanced if the total number of nodes in the left and right branch of every node differ by at most one.
%C The value of a(n) is always a power of 2.
%D Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
%H Alois P. Heinz, <a href="/A110316/b110316.txt">Table of n, a(n) for n = 0..2047</a>
%H J. Barnett, <a href="http://notatt.com/btree-shapes.pdf">Counting Balanced Tree Shapes</a>
%H S. Giraudo, <a href="http://arxiv.org/abs/1107.3472">Intervals of balanced binary trees in the Tamari lattice</a>, arXiv preprint arXiv:1107.3472 [math.CO], 2011.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Blancmange_curve">Blancmange curve</a>
%F a(0) = a(1) = 1; a(2*n) = 2*a(n)*a(n-1); a(2*n+1) = a(n)*a(n).
%F a(n) = 1 <=> n in { A000225 }. - _Orson R. L. Peters_, Mar 12 2024
%p a:= proc(n) option remember; local r; `if`(n<2, 1,
%p `if`(irem(n, 2, 'r')=0, 2*a(r)*a(r-1), a(r)^2))
%p end:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Apr 10 2013
%t a[0] = a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2 a[n/2] a[n/2-1], a[(n-1)/2 ]^2]; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Jan 31 2016 *)
%o (Python)
%o def A110316(n): return 1<<(k:=n+1)-(sum(i.bit_count() for i in range(1,k))<<1)+k*(m:=k.bit_length())-(1<<m) # _Chai Wah Wu_, Mar 02 2023
%Y Column k=2 of A221857. - _Alois P. Heinz_, Apr 17 2013
%Y Cf. A000225.
%K easy,nonn,look
%O 0,3
%A _Jeffrey Barnett_, Jun 23 2007
|
