A296103 Number of shapes of left-leaning height-balanced AVL trees with n (inner) nodes.

1, 1, 1, 1, 1, 2, 2, 2, 3, 5, 7, 9, 11, 13, 17, 26, 42, 66, 97, 134, 180, 241, 321, 424, 564, 774, 1111, 1661, 2545, 3925, 6012, 9079, 13480, 19678, 28296, 40212, 56701, 79599, 111469, 155795, 217301, 302590, 421396, 588782, 828633, 1178919, 1699502, 2483695

Offset

0,6

Comments

A left-leaning AVL tree is a binary rooted tree where at any node, the height of left subtree is equal to the height of right subtree or greater by 1.

Links

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

Katarzyna Matylla, Python program for A296103

Maple

B:= proc(x, y, d, a, b) option remember; `if`(a+b<=d,
      B(x^2+x*y, x, d, a+b, a)+x, x)
    end:
a:= n-> coeff(B(z, 0, n+1, 1, 1), z, n+1):
seq(a(n), n=0..60);  # Alois P. Heinz, Dec 05 2017

Mathematica

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

Prog

(Python) # see link above

Crossrefs

Cf. A006265.

Sequence in context: A320786 A126111 A100142 * A247907 A122789 A291294

Adjacent sequences: A296100 A296101 A296102 * A296104 A296105 A296106

Keyword

nonn

Author

Katarzyna Matylla, Dec 04 2017

Status

approved