A036662 -id:A036662 - cp's OEIS frontend

A143897 Triangle read by rows: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 28, 8, 1, 128, 448, 864, 1552, 2720, 4288, 6312, 9004, 11992, 14372, 15400, 14630, 11968, 8104, 4376, 1820, 560, 120, 16, 1, 4096, 22528, 67584, 159744, 334080, 644992, 1195008, 2158912, 3811904, 6617184

Offset: 0

Alois P. Heinz, Sep 04 2008

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Rows n = 0..10, flattened
Ralf Hinze, Functional Pearls: Purely functional 1-2 brother trees, Journal of Functional Programming, 19(6):633-644, 2009, DOI: 10.1017/S0956796809007333.
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Row sums give: A029758.
Column sums give: A006265.
Column sums of first 5 or 6 rows give: A036662 or A134306.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Triangle read by columns gives: A217298.
Cf. A000045, A000079.

T:= proc(n,k) local B, z; B:= proc(x,y,d) if d>=1 then x+B(x^2+2*x*y, x, d-1) else x fi end; if n=0 then if k=1 then 1 else 0 fi else coeff(B(z,0,n), z,k) -coeff(B(z,0,n-1), z,k) fi end: fib:= m-> (Matrix([[1,1], [1,0]])^m)[1,2]: seq(seq(T(n,k), k=fib(n+2)..2^n), n=0..6);

t[n_, k_] := Module[{ b, z }, b[x_, y_, d_] := If[d >= 1, x + b[x^2 + 2*x*y, x, d-1], x]; If[n == 0, If[k == 1, 1, 0], Coefficient[b[z, 0, n], z, k] - Coefficient [b[z, 0, n-1], z, k]]]; fib[m_] := MatrixPower[{{1, 1}, {1, 0}}, m][[1, 2]]; Table[Table[t[n, k], {k, fib[n+2], 2^n}], {n, 0, 6}] // Flatten (* Jean-François Alcover, Dec 05 2013, translated from Alois P. Heinz's Maple program *)

See program.

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

Original entry on oeis.org

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

N. J. A. Sloane

nonn

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.

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.

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

Cf. A036662, A134306.

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

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

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 *)

G.f.: A(x) = B(x,0) where B(x,y) satisfies B(x,y) = x + B(x^2+2xy,x).

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

A134306 Number of shapes of height-balanced AVL trees of height at most 6 with n nodes.

Original entry on oeis.org

0, 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, 50882720, 80963520, 125489856, 188637520, 273984664

Offset: 0

Alois P. Heinz, Aug 27 2008

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.

Alois P. Heinz, Table of n, a(n) for n = 0..64
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Cf. A006265, A036662.

a:= proc(n) local B,z; B:= proc(x,y,d) if d>=1 then x+B(x^2+2*x*y, x,d-1) else x fi end; coeff(B(z,0,6), z,n) end: seq(a(n), n=0..64);

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

a(n) = Sum_{h=0..6} A143897(h,n).

cp's OEIS Frontend

A143897 Triangle read by rows: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A134306 Number of shapes of height-balanced AVL trees of height at most 6 with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula