login
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).
2
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
KEYWORD
nonn,tabl
AUTHOR
Kevin Liu, Nov 16 2021
STATUS
approved