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

Author

Katarzyna Matylla, Dec 04 2017

Keywords

• nonn

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

Crossrefs

Cf. A006265.

Programs

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

Python

# see link above