Kevin Liu - cp's OEIS frontend

User: Kevin Liu

Kevin Liu has authored 3 sequences.

A371659 Triangle read by rows: T(n,k) is the number of planar tanglegrams of size n with irreducible component of size k.

1, 0, 1, 0, 1, 1, 0, 3, 3, 5, 0, 13, 9, 20, 34, 0, 90, 46, 70, 170, 273, 0, 747, 312, 360, 680, 1638, 2436, 0, 7040, 2580, 2435, 3570, 7371, 17052, 23391, 0, 71736, 24056, 19800, 23970, 39858, 85260, 187128, 237090, 0, 774738, 243483, 182850, 193664, 267813, 477456, 1029204, 2133810, 2505228

Offset: 1

Kevin Liu, Apr 01 2024

A proper subtanglegram of a planar tanglegram is a pair of subtrees whose leaves are matched in the tanglegram, and the irreducible component of a planar tanglegram is formed by contracting each maximal proper subtanglegram into a pair of matched leaves.

			Triangle begins
  1;
  0,    1;
  0,    1,    1;
  0,    3,    3,    5;
  0,   13,    9,   20,   34;
  0,   90,   46,   70,  170,  273;
  0,  747,  312,  360,  680, 1638,  2436;
  0, 7040, 2580, 2435, 3570, 7371, 17052, 23391;
  ...

Alexander E. Black, Kevin Liu, Alex McDonough, Garrett Nelson, Michael C. Wigal, Mei Yin, and Youngho Yoo, Sampling planar tanglegrams and pairs of disjoint triangulations, Advances in Applied Mathematics 149 (2023), Paper No. 102550.

Cf. A349408 (diagonal), A257887 (row sums).

G.f.: F(x,y) = H(F(x),y) + x*y + y^2*(F(x)^2 + F(x^2))/2 where the coefficient of x^n*y^k is the number of planar tanglegrams of size n with irreducible component of size k, F(x) is the g.f. for A349408, and H(x)/x^2 is the g.f. for A257887.

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).

Original entry on oeis.org

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

Kevin Liu, Nov 16 2021

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

			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;
      ...

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.

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

\\ 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

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.

A349408 Number of planar tanglegrams of size n.

Original entry on oeis.org

1, 1, 2, 11, 76, 649, 6173, 63429, 688898, 7808246, 91537482, 1102931565, 13594564857, 170804438005, 2181426973452, 28257128116954, 370581034530685, 4913238656392058, 65773613137623085, 888155942037325535, 12086555915234897267, 165641209243876120135

Offset: 1

Kevin Liu, Nov 16 2021

nonn

			For n=4, there are 11 planar tanglegrams of size 4.

Andrew Howroyd, Table of n, a(n) for n = 1..500
Alexander E. Black, Kevin Liu, Alex Mcdonough, Garrett Nelson, Michael C. Wigal, Mei Yin, and Youngho Yoo, Sampling planar tanglegrams and pairs of disjoint triangulations, arXiv:2304.05318 [math.CO], 2023.
Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana and Stephan Wagner, Counting Planar Tanglegrams, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Article 32.

Row sums of A349409.

Cf. A257887, A258620.

\\ 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}
seq(n)={my(h=H(n-2), p=O(x)); for(n=1, n, p = subst(h + O(x*x^n), x, p) + x + (p^2 + subst(p,x,x^2))/2); Vec(p)} \\ Andrew Howroyd, Nov 18 2021

G.f.: F(x) satisfies F(x) = H(F(x)) + x + (F(x)^2 + F(x^2))/2 where H(x)/x^2 is the g.f. of A257887.

Terms a(11) and beyond from Andrew Howroyd, Nov 18 2021

cp's OEIS Frontend

User: Kevin Liu

A371659 Triangle read by rows: T(n,k) is the number of planar tanglegrams of size n with irreducible component of size k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A349408 Number of planar tanglegrams of size n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions