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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 8
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 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 FORMULA a(0) = a(1) = 1; a(2*n) = 2*a(n)*a(n-1); a(2*n+1) = a(n)*a(n). 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 *) CROSSREFS Column k=2 of A221857. - Alois P. Heinz, Apr 17 2013 Sequence in context: A274883 A140946 A008741 * A111975 A117250 A296337 Adjacent sequences:  A110313 A110314 A110315 * A110317 A110318 A110319 KEYWORD easy,nonn,look AUTHOR Jeffrey Barnett, Jun 23 2007 STATUS approved

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.

Last modified June 7 05:20 EDT 2020. Contains 334837 sequences. (Running on oeis4.)