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

%I #22 May 31 2019 06:53:09

%S 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,

%T 774,1111,1661,2545,3925,6012,9079,13480,19678,28296,40212,56701,

%U 79599,111469,155795,217301,302590,421396,588782,828633,1178919,1699502,2483695

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

%C 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.

%H Alois P. Heinz, <a href="/A296103/b296103.txt">Table of n, a(n) for n = 0..1000</a>

%H Katarzyna Matylla, <a href="/A296103/a296103.txt">Python program for A296103</a>

%p B:= proc(x, y, d, a, b) option remember; `if`(a+b<=d,

%p B(x^2+x*y, x, d, a+b, a)+x, x)

%p end:

%p a:= n-> coeff(B(z, 0, n+1, 1, 1), z, n+1):

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Dec 05 2017

%t 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];

%t a[n_] := Coefficient[B[z, 0, n+1, 1, 1], z, n+1];

%t Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, May 31 2019, after _Alois P. Heinz_ *)

%o (Python) # see link above

%Y Cf. A006265.

%K nonn

%O 0,6

%A _Katarzyna Matylla_, Dec 04 2017