A349409 Triangle read by rows: T(n,k) is the number of planar tanglegrams of size n with 0 <= k < n leaf-matched pairs. A leaf matched pair is a pair of non-leaf vertices (u,v) in the tanglegram such that the induced subtrees rooted and u and v also form a tanglegram (equivalently, the leaves in these two subtrees are matched by the matching that forms the original tanglegram).

1, 0, 1, 0, 1, 1, 0, 5, 4, 2, 0, 34, 28, 11, 3, 0, 273, 239, 102, 29, 6, 0, 2436, 2283, 1045, 325, 73, 11, 0, 23391, 23475, 11539, 3852, 968, 181, 23, 0, 237090, 254309, 133690, 47640, 12923, 2756, 444, 46, 0, 2505228, 2864283, 1605280, 607743, 175976, 40903, 7650, 1085, 98

Offset

1,8

Comments

The generating function can be proven using a generalization of the proof for A349408.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Kevin Liu, Planar Tanglegram Layouts and Single Edge Insertion, Séminaire Lotharingien de Combinatoire (2022) Vol. 86, Issue B, Art. No. 45.

Formula

G.f.: F(x,q) = q*H(F(x,q)) + x + q*(F(x,q)^2 + F(x^2,q^2))/2 where coefficient of x^n*q^k is the number of planar tanglegrams with size n and k leaf-matched pairs, and H(x)/x^2 is the g.f. for A257887.

Example

Triangle begins
      1;
      0,      1;
      0,      1,     1;
      0,      5,     4,     2;
      0,     34,    28,    11,    3;
      0,    273,   239,   102,   29,   6;
      0,   2436,  2283,  1045,  325,  73,  11;
      0,  23391, 23475, 11539, 3852, 968, 181, 23;
      ...

Prog

(PARI) \\ here H(n)/x^2 is g.f. of A257887.
H(n)={(x - x^2 - serreverse(sum(k=0, n+1, (binomial(2*k, k)/(k+1))^2*x^(k+1)) + O(x^(n+3))))/2}
F(n)={my(h=H(n-2), p=O(x)); for(n=1, n, p = x + y*subst(h + O(x*x^n), x, p) + y*(p^2 + subst(subst(p, x, x^2), y, y^2))/2); p}
T(n)={[Vecrev(p) | p<-Vec(F(n))]}
{my(v=T(10)); for(n=1, #v, print(v[n]))} \\ Andrew Howroyd, Nov 18 2021

Crossrefs

Cf. A257887 (2nd column), A349408 (row sums), A001190 (diagonal).

Sequence in context: A224228 A286680 A201680 * A109430 A085917 A180130

Adjacent sequences: A349406 A349407 A349408 * A349410 A349411 A349412

Keyword

nonn,tabl

Author

Kevin Liu, Nov 16 2021

Status

approved