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.
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
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms, formula and comment from Christian G. Bower, Dec 15 1999
STATUS
approved