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
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.
-
\\ 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
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
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;
...
-
\\ 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
A335729
Number of "coprime" pairs of binary trees with n carets (see comments).
Original entry on oeis.org
1, 2, 10, 68, 546, 4872, 46782, 474180, 5010456, 54721224, 613912182, 7042779996, 82329308040, 978034001472
Offset: 1
A coprime tree-pair with 5 carets:
. .
/ \ / \
/ \ \ / \
/ / \ \ / \ \
/ / \ \ \ / \ \ \
/ / \ \ \ \ / \ \ \ / \
1 2 3 4 5 6 1 2 3 4 5 6
A non-coprime tree-pair (both have a subtree on leaves 1-2-3-4):
. .
/ \ / \
/ \ \ / \
/ \ \ \ / \ \
/ \ \ \ / / \ \
/ \ / \ \ \ / / \ \ / \
1 2 3 4 5 6 1 2 3 4 5 6
Below we will represent a binary tree by a bracketing of the leaf labels 1 through n + 1 (a vertex of an associahedron). A tree is represented by a balanced string, and its left and right child subtrees are represented by two maximal balanced proper substrings, in order.
For n = 2, the a(2) = 2 coprime tree-pairs are:
([[12]3], [1[23]]),
([1[23]], [[12]3]).
For n = 3, the a(3) = 10 coprime tree-pairs are:
([1[2[34]]], [[1[23]]4]),
([1[2[34]]], [[[12]3]4]),
([1[[23]4]], [[12][34]]),
([1[[23]4]], [[[12]3]4]),
([[12][34]], [1[[23]4]]),
([[12][34]], [[1[23]]4]),
([[1[23]]4], [1[2[34]]]),
([[1[23]]4], [[12][34]]),
([[[12]3]4], [1[2[34]]]),
([[[12]3]4], [1[[23]4]]).
a(n) counts a subset of the tree-pairs that
A111713 counts; "coprime" is a stronger condition than "reduced". It appears that for n > 1, a(n)/2 coincides with
A257887.
A371659
Triangle read by rows: T(n,k) is the number of planar tanglegrams of size n with irreducible component of size k.
Original entry on oeis.org
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
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;
...
Showing 1-4 of 4 results.
Comments