|
Search: id:A006265
|
|
|
| A006265 |
|
Shapes of height-balanced AVL trees with n nodes.
(Formerly M0170)
|
|
+0
4
|
|
| 1, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 16088, 36900, 82984, 174374, 346048, 653096, 1199384, 2160732, 3812464, 6617304, 11307920, 18978577, 31327104, 51931296, 90400704, 170054336
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
An AVL tree is a complete ordered binary rooted tree where at any node, the height of both subtrees are within 1 of each other.
|
|
REFERENCES
|
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
This is the limit of A_k as k->inf, see F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79.
|
|
LINKS
|
Index entries for sequences related to trees
Index entries for sequences related to rooted trees
|
|
FORMULA
|
G.f.: A(x)=B(x, 0) where B(x, y) satisfies B(x, y)=x+B(x^2+2xy, x).
|
|
MAPLE
|
a := proc(n::posint) local B; B := proc (x, y, d, a, b) if a+b<=d then x+B(x^2+2*x*y, x, d, a+b, a) else x fi end; coeff (B (z, 0, n, 1, 1), z, n) end; seq (a(n), n=1..36); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Aug 10 2008]
|
|
CROSSREFS
|
Cf. A036662, A134306.
Sequence in context: A143897 A036662 A134306 this_sequence A131452 A111104 A026190
Adjacent sequences: A006262 A006263 A006264 this_sequence A006266 A006267 A006268
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms, formula and comment from Christian G. Bower (bowerc(AT)usa.net), Dec 15 1999.
|
|
|
Search completed in 0.002 seconds
|
