A110316 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.

1, 1, 2, 1, 4, 4, 4, 1, 8, 16, 32, 16, 32, 16, 8, 1, 16, 64, 256, 256, 1024, 1024, 1024, 256, 1024, 1024, 1024, 256, 256, 64, 16, 1, 32, 256, 2048, 4096, 32768, 65536, 131072, 65536, 524288, 1048576, 2097152, 1048576, 2097152, 1048576, 524288, 65536, 524288

Offset: 0

Author

Jeffrey Barnett, Jun 23 2007

Keywords

• easy
• nonn
• look

Comments

The value of a(n) is always a power of 2.

References

• 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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2047
• J. Barnett, Counting Balanced Tree Shapes
• S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv preprint arXiv:1107.3472 [math.CO], 2011.
• Wikipedia, Blancmange curve

Crossrefs

Column k=2 of A221857. - Alois P. Heinz, Apr 17 2013

Cf. A000225.

Programs

Maple

a:= proc(n) option remember; local r; `if`(n<2, 1,
      `if`(irem(n, 2, 'r')=0, 2*a(r)*a(r-1), a(r)^2))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 10 2013

Mathematica

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 *)

Python

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<Chai Wah Wu, Mar 02 2023

Formula

a(0) = a(1) = 1; a(2*n) = 2*a(n)*a(n-1); a(2*n+1) = a(n)*a(n).

a(n) = 1 <=> n in { A000225 }. - Orson R. L. Peters, Mar 12 2024