login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006265 Shapes of height-balanced AVL trees with n nodes.
(Formerly M0170)
6
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 (list; graph; refs; listen; history; text; 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

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.

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 A111104 A026190

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 12 22:57 EST 2018. Contains 318081 sequences. (Running on oeis4.)