|
| |
|
|
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.
|
|
7
|
|
|
|
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
|
S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, Arxiv preprint arXiv:1107.3472, 2011
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..2047
|
|
|
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
|
|
|
PROG
|
a(0) := 1; a(1) := 1; for n from 1 by 1 { a(2*n) := 2*a(n)*a(n-1); a(2*n+1) := a(n)*a(n)}
|
|
|
CROSSREFS
|
Column k=2 of A221857. - Alois P. Heinz, Apr 17 2013
Sequence in context: A091335 A140946 A008741 * A111975 A117250 A136692
Adjacent sequences: A110313 A110314 A110315 * A110317 A110318 A110319
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
Jeffrey A. Barnett (jbb(AT)notatt.com), Jun 23 2007
|
|
|
STATUS
|
approved
|
| |
|
|
