A006265 Number of shapes of height-balanced AVL trees with n nodes. (Formerly M0170)

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, 341729616, 711634072, 1491256624

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

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Ricardo A. Baeza-Yates, Height balance distribution of search trees, Preprint. (Annotated scanned copy)

Ricardo A. Baeza-Yates, Height balance distribution of search trees, Information Processing Letters 39.6 (1991): 317-324.

S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv preprint arXiv:1107.3472 [math.CO], 2011 and Theor Comput. Sci. 420, 1-27 (2012)

R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.

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..40);  # Alois P. Heinz, Aug 10 2008

Mathematica

a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, x+B[x^2+2*x*y, x, d, a+b, a], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; Table[a[n], {n, 1, 39}] (* Jean-François Alcover, Mar 03 2014, after Alois P. Heinz *)

Crossrefs

Cf. A036662, A134306.

Column sums of A143897, A217298. - Alois P. Heinz, Mar 18 2013

Sequence in context: A217300 A036662 A134306 * A131452 A359898 A335920

Adjacent sequences: A006262 A006263 A006264 * A006266 A006267 A006268

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms, formula and comment from Christian G. Bower, Dec 15 1999

Status

approved