cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A006265 Number of shapes of height-balanced AVL trees with n nodes.

This page as a plain text file.
%I A006265 M0170 #55 Jun 11 2019 04:45:07
%S A006265 1,1,2,1,4,6,4,17,32,44,60,70,184,476,872,1553,2720,4288,6312,9004,
%T A006265 16088,36900,82984,174374,346048,653096,1199384,2160732,3812464,
%U A006265 6617304,11307920,18978577,31327104,51931296,90400704,170054336,341729616,711634072,1491256624
%N A006265 Number of shapes of height-balanced AVL trees with n nodes.
%C A006265 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.
%D A006265 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006265 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.
%H A006265 Alois P. Heinz, <a href="/A006265/b006265.txt">Table of n, a(n) for n = 1..1000</a>
%H A006265 Ricardo A. Baeza-Yates, <a href="/A006265/a006265.pdf">Height balance distribution of search trees</a>, Preprint. (Annotated scanned copy)
%H A006265 Ricardo A. Baeza-Yates, <a href="http://dx.doi.org/10.1016/0020-0190(91)90005-3">Height balance distribution of search trees</a>, Information Processing Letters 39.6 (1991): 317-324.
%H A006265 S. Giraudo, <a href="http://arxiv.org/abs/1107.3472">Intervals of balanced binary trees in the Tamari lattice</a>, arXiv preprint arXiv:1107.3472 [math.CO], 2011 and <a href="https://doi.org/10.1016/j.tcs.2011.11.020">Theor Comput. Sci. 420, 1-27 (2012)</a>
%H A006265 R. C. Richards, <a href="http://dx.doi.org/10.1016/0020-0190(83)90085-6">Shape distribution of height-balanced trees</a>, Info. Proc. Lett., 17 (1983), 17-20.
%H A006265 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A006265 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A006265 G.f.: A(x) = B(x,0) where B(x,y) satisfies B(x,y) = x + B(x^2+2xy,x).
%p A006265 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
%t A006265 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_ *)
%Y A006265 Cf. A036662, A134306.
%Y A006265 Column sums of A143897, A217298. - _Alois P. Heinz_, Mar 18 2013
%K A006265 nonn
%O A006265 1,3
%A A006265 _N. J. A. Sloane_
%E A006265 More terms, formula and comment from _Christian G. Bower_, Dec 15 1999