A258620 Number of tanglegrams of size n.

1, 1, 2, 13, 114, 1509, 25595, 535753, 13305590, 382728552, 12515198465, 458621603279, 18619063906689, 829607273337513, 40253392454978755, 2112878091130119496, 119296114546292088543, 7209829960147215492897, 464413707136960430809460, 31762965767675300603026848

Offset: 1

Author

Matjaz Konvalinka, Jun 18 2015

Keywords

• nonn

References

• R. Page, Tangled trees: phylogeny, cospeciation, and coevolution, The University of Chicago Press, 2002.

Links

• Matjaz Konvalinka, Table of n, a(n) for n = 1..366
• S. C. Billey, M. Konvalinka, and F. A. Matsen IV, On the enumeration of tanglegrams and tangled chains, arXiv:1507.04976 [math.CO], 2015.
• Sara Billey, Matjaž Konvalinka, Frederick A. Matsen IV, On trees, tanglegrams, and tangled chains, hal-02173394 [math.CO], 2020.
• M. Konvalinka, S. Wagner, The shape of random tanglegrams, arXiv preprint arXiv:1512.01168, 2015.
• Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, Stephan Wagner, Counting Planar Tanglegrams, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Article 32.

Programs

Mathematica

r[h_, n_, s_] :=
  r[h, n, s] =
   If[n == 0, 1,
    Sum[Product[(2 (s + j 2^h) - 1)^2/(j 2^h), {j, m}] r[
       h + 1, (n - m)/2, s + m 2^h], {m, n, 0, -2}]];
tang[n_] := r[0, n, 0]/(2 n - 1)^2;

Formula

a(n) = Sum_{lambda binary partition of n} (Product_{i=2..l(lambda)} (2(lambda_i+...+lambda_l)-1)^2)/z_lambda.

a(n) ~ 2^(2*n-3/2) * n^(n-5/2) / (sqrt(Pi) * exp(n-1/8)).