OFFSET
0,3
COMMENTS
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).
LINKS
N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.
FORMULA
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.
EXAMPLE
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).
MATHEMATICA
b[0, k_] := 1
Do[b[n, k] = Sum[b[n - 1, m]^2, {m, 2, k + 1}], {k, 1, 11}, {n, 1, 10}]
Do[Print[b[n, 1]], {n, 0, 10}]
(* 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. *)
KEYWORD
nonn
AUTHOR
Noah A Rosenberg, Feb 13 2019
STATUS
approved