A101489 Square array T(n,k), read by antidiagonals: number of binary trees, with n nodes that have no label greater than k.

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 4, 1, 1, 2, 5, 10, 10, 1, 1, 2, 5, 13, 26, 26, 1, 1, 2, 5, 14, 37, 73, 73, 1, 1, 2, 5, 14, 41, 109, 213, 213, 1, 1, 2, 5, 14, 42, 126, 334, 645, 645, 1, 1, 2, 5, 14, 42, 131, 398, 1050, 2007, 2007, 1, 1, 2, 5, 14, 42, 132, 422, 1289, 3377, 6391, 6391

Offset

0,9

Links

Table of n, a(n) for n=0..77.

M. Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.

Formula

G.f. of k-th row: A(t) = B(t)*(1-C(t)^(k+2))*(1-C(t)^(k+7))/((1-C(t)^(k+4))*(1-C(t)^(k+5))), with B(t) the g.f. of A000108 and C(t) the g.f. of A101490.

Example

1, 1, 1, 2,  4, 10,  26,  73,  213,  645, ...
1, 1, 2, 4, 10, 26,  73, 213,  645, 2007, ...
1, 1, 2, 5, 13, 37, 109, 334, 1050, 3377, ...
1, 1, 2, 5, 14, 41, 126, 398, 1289, 4253, ...
1, 1, 2, 5, 14, 42, 131, 422, 1390, 4664, ...
1, 1, 2, 5, 14, 42, 132, 428, 1422, 4812, ...
1, 1, 2, 5, 14, 42, 132, 429, 1429, 4853, ...
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, ...

Mathematica

nmax = 11;
b[t_] = Sum[Binomial[2n, n]/(n + 1) t^n, {n, 0, nmax}] ;
c[t_] = 1; Do[c[t_] = t (1 + c[t]^2)^2/(1 - c[t] + c[t]^2) + O[t]^(nmax + 1), {nmax + 1}];
a[n_, t_] := a[n, t] = b[t] (1 - c[t]^(n + 2)) ((1 - c[t]^(n + 7))/((1 - c[t]^(n + 4)) (1 - c[t]^(n + 5)))) + O[t]^(nmax + 1);
T[n_, k_] := SeriesCoefficient[a[n, t], {t, 0, k}];
Table[T[n - k, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 25 2018 *)

Crossrefs

Rows converge to A000108. First row is A101488.

Cf. A101490.

Sequence in context: A135229 A257543 A081372 * A104156 A070166 A131373

Adjacent sequences: A101486 A101487 A101488 * A101490 A101491 A101492

Keyword

nonn,tabl

Author

Ralf Stephan, Jan 21 2005

Status

approved