

A306402


Number of coalescent histories for a matching completely symmetric gene tree and completely symmetric species tree with 2^n leaves.


0




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^(n1) leaves (Rosenberg 2007, Theorem 3.1).


LINKS

Table of n, a(n) for n=0..7.
N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360377.


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(n1,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. *)


CROSSREFS

Coalescent histories appear also in A306205, A306295.
Sequence in context: A283566 A221083 A181191 * A057140 A245323 A348085
Adjacent sequences: A306399 A306400 A306401 * A306403 A306404 A306405


KEYWORD

nonn


AUTHOR

Noah A Rosenberg, Feb 13 2019


STATUS

approved



