OFFSET
1,5
COMMENTS
a(n) is the number of binary trees T with n internal nodes such that T is balanced (also called AVL tree) and there is no binary tree S greater than T for the Tamari order such that S is balanced.
LINKS
Joerg Arndt, Table of n, a(n) for n = 1..1000
S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv preprint arXiv:1107.3472 [math.CO], 2011.
S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, Theoretical Computer Science, 420, 1--27, 2012.
FORMULA
G.f.: A(x) = B(x, 0, 0) where B(x, y, z) satisfies B(x, y, z) = x + B(x^2 + x*y + y*z, x, x*y).
MATHEMATICA
m = 49; R = O[x]^(m+1);
B[x_, y_, z_, k_:0] = If[k >= m, x, x + R + B[x^2 + x y + y z + R, x + R, x y + R, k + 1] // Normal];
CoefficientList[B[x, 0, 0], x] // Rest (* Jean-François Alcover, Dec 16 2018, from Joerg Arndt's PARI code *)
PROG
(PARI)
N = 66; R = O('x^(N+1)); x = 'x+R;
B(x, y, z, k=0) = if( k>=N, x, x + R + B(x^2 + x*y + y*z + R, x + R, x*y + R, k+1) );
Vec(B(x, 0, 0)) \\ Joerg Arndt, May 01 2016
CROSSREFS
KEYWORD
nonn
AUTHOR
Samuele Giraudo, Apr 28 2016
EXTENSIONS
Terms a(35) and beyond from Joerg Arndt, May 01 2016
STATUS
approved
