A272372 Maximal intervals of balanced binary trees in the Tamari lattices.

1, 1, 1, 1, 3, 2, 2, 6, 9, 15, 15, 17, 41, 77, 125, 178, 252, 376, 531, 740, 1192, 2179, 4273, 7738, 13012, 20776, 32389, 49841, 75457, 113011, 168888, 252881, 379348, 577608, 913792, 1530412, 2684825, 4806985, 8593097, 15157149, 26260805, 44625070, 74457290, 122401132, 199122077, 321812711, 517791532

Offset

1,5

Comments

a(n) is the number of maximal intervals of balanced binary trees in the Tamari lattice of binary trees with n internal nodes. An interval of balanced binary trees in the Tamari lattice is maximal if it is not strictly included in another interval of balanced binary trees.

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, 0) where B(x, y, z, t) satisfies B(x, y, z, t) = x + B(x^2 + 2*y*t + y*z, x, x^2 + x*y, y*t + y*z).

Mathematica

m = 47; R = O[x]^(m + 1);
B[x_, y_, z_, t_, k_:0] = If[k >= m, x, x + R + B[x^2 + 2 y t + y z + R,  x + R, x^2 + x y + R,  y t + y z + R, k + 1] // Normal];
CoefficientList[B[x, 0, 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, t, k=0) = if( k>=N, x, x + R +  B(x^2 + 2*y*t + y*z + R,  x + R,  x^2 + x*y + R,  y*t + y*z + R, k+1) );
Vec( B(x, 0, 0, 0) ) \\ Joerg Arndt, May 01 2016

Crossrefs

Cf. A263446, A272371.

Sequence in context: A283558 A234713 A091029 * A354002 A280850 A296508

Adjacent sequences: A272369 A272370 A272371 * A272373 A272374 A272375

Keyword

nonn

Author

Samuele Giraudo, Apr 28 2016

Extensions

Term a(33) and beyond from Joerg Arndt, May 01 2016

Status

approved