|
%I #8 Mar 26 2019 11:49:21
%S 1,1,4,169,1020100,270062420147776,686954819460520804489954417158400,
%T 3171571350979001722602021784038902498684386645982829438130935832126653601
%N Number of coalescent histories for a matching completely symmetric gene tree and completely symmetric species tree with 2^n leaves.
%C A completely symmetric tree with 2^n leaves is a tree recursively defined by subdividing the root into two descendant branches with equally many leaves. The number of coalescent histories for matching completely symmetric trees with 2^n leaves can be determined from a bivariate recursion that considers completely symmetric trees with 2^(n-1) leaves (Rosenberg 2007, Theorem 3.1).
%H N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2006.0109">Counting coalescent histories</a>, J. Comput. Biol. 14 (2007), 360-377.
%F a(n) = b(n,1), where b(n,k) is defined for integers n>=0 and k>=1, b(n,k) = Sum_{m=2..k+1} b(n-1,k+1)^2, and b(0,k)=1 for all k.
%e For n=2, the trees have 2^2=4 leaves. Labeling these leaves A, B, C, and D, suppose the gene tree and species tree have matching labeled topology ((A,B),(C,D)). Denote the species tree edges immediately ancestral to species tree nodes (A,B), (C,D), and ((A,B),(C,D)) by 1, 2, and 3 respectively. The 4 coalescent histories, representing the vector of the images of gene tree nodes ((A,B), (C,D), ((A,B),(C,D)) in the species tree, are (3,3,3), (1,3,3), (3,2,3), and (1,2,3).
%t b[0, k_] := 1
%t Do[b[n, k] = Sum[b[n - 1, m]^2, {m, 2, k + 1}], {k, 1, 11}, {n, 1, 10}]
%t Do[Print[b[n, 1]], {n, 0, 10}]
%t (* Note: this is a bivariate recursion in which b[n,1] is of interest. The largest value of k required for evaluating b[n,1] increases as n decreases; set the upper limit on k larger than the upper limit on n. *)
%Y Coalescent histories appear also in A306205, A306295.
%K nonn
%O 0,3
%A _Noah A Rosenberg_, Feb 13 2019
|
