|
| |
|
|
A006265
|
|
Shapes of height-balanced AVL trees with n nodes.
(Formerly M0170)
|
|
3
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| 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
| S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, Arxiv preprint arXiv:1107.3472, 2011
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); # Alois P. Heinz, Aug 10 2008
|
|
|
CROSSREFS
| Cf. A036662, A134306.
Sequence in context: A143897 A036662 A134306 * A131452 A111104 A026190
Adjacent sequences: A006262 A006263 A006264 * 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.
|
| |
|
|
