A306402 Number of coalescent histories for a matching completely symmetric gene tree and completely symmetric species tree with 2^n leaves.
1, 1, 4, 169, 1020100, 270062420147776, 686954819460520804489954417158400, 3171571350979001722602021784038902498684386645982829438130935832126653601
Offset: 0
Keywords
Examples
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).
Links
- N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.
Programs
-
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. *)
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.
Comments