OFFSET
1,3
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.
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)).
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;
CROSSREFS
KEYWORD
nonn
AUTHOR
Matjaz Konvalinka, Jun 18 2015
STATUS
approved