A272371 Maximal balanced binary trees in the Tamari lattices.

1, 1, 1, 1, 2, 2, 2, 4, 6, 9, 11, 13, 22, 38, 60, 89, 128, 183, 256, 353, 512, 805, 1336, 2221, 3594, 5665, 8774, 13433, 20359, 30550, 45437, 67086, 98491, 144492, 213876, 322912, 500320, 793981, 1280684, 2080743, 3379956, 5462816, 8763837, 13948663, 22041664, 34622880, 54126792, 84292070, 130838126

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

Cf. A272372, A263446.

Sequence in context: A241576 A306749 A338286 * A191651 A010558 A365717

Adjacent sequences: A272368 A272369 A272370 * A272372 A272373 A272374

Keyword

nonn

Author

Samuele Giraudo, Apr 28 2016

Extensions

Terms a(35) and beyond from Joerg Arndt, May 01 2016

Status

approved