A258620 - OEIS

%I #46 Aug 04 2020 19:15:54

%S 1,1,2,13,114,1509,25595,535753,13305590,382728552,12515198465,

%T 458621603279,18619063906689,829607273337513,40253392454978755,

%U 2112878091130119496,119296114546292088543,7209829960147215492897,464413707136960430809460,31762965767675300603026848

%N Number of tanglegrams of size n.

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

%H Matjaz Konvalinka, <a href="/A258620/b258620.txt">Table of n, a(n) for n = 1..366</a>

%H S. C. Billey, M. Konvalinka, and F. A. Matsen IV, <a href="http://arxiv.org/abs/1507.04976">On the enumeration of tanglegrams and tangled chains</a>, arXiv:1507.04976 [math.CO], 2015.

%H Sara Billey, Matjaž Konvalinka, Frederick A. Matsen IV, <a href="https://hal.archives-ouvertes.fr/hal-02173394">On trees, tanglegrams, and tangled chains</a>, hal-02173394 [math.CO], 2020.

%H M. Konvalinka, S. Wagner, <a href="http://arxiv.org/abs/1512.01168">The shape of random tanglegrams</a>, arXiv preprint arXiv:1512.01168, 2015.

%H Dimbinaina Ralaivaosaona, Jean Bernoulli Ravelomanana, Stephan Wagner, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.32">Counting Planar Tanglegrams</a>, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Article 32.

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

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

%t r[h_, n_, s_] :=

%t   r[h, n, s] =

%t    If[n == 0, 1,

%t     Sum[Product[(2 (s + j 2^h) - 1)^2/(j 2^h), {j, m}] r[

%t        h + 1, (n - m)/2, s + m 2^h], {m, n, 0, -2}]];

%t tang[n_] := r[0, n, 0]/(2 n - 1)^2;

%K nonn

%O 1,3

%A _Matjaz Konvalinka_, Jun 18 2015