A349408 Number of planar tanglegrams of size n.
1, 1, 2, 11, 76, 649, 6173, 63429, 688898, 7808246, 91537482, 1102931565, 13594564857, 170804438005, 2181426973452, 28257128116954, 370581034530685, 4913238656392058, 65773613137623085, 888155942037325535, 12086555915234897267, 165641209243876120135
Offset: 1
Keywords
Examples
For n=4, there are 11 planar tanglegrams of size 4.
Links
- 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.
Programs
-
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} 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
Formula
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.
Extensions
Terms a(11) and beyond from Andrew Howroyd, Nov 18 2021