OFFSET
1,2
COMMENTS
Consider a binary tree evolving in time from a single node until the tree has 2n labeled leaves. Color the 2n leaves in 2 colors, red and blue, assigning n leaves to each color. Suppose coalescences of pairs of leaves happen at distinct times (i.e., no simultaneous mergers). A coalescence sequence is a sequence of coalescence events backward in time, tracing the reduction of the 2n leaves to the single ancestral node. A paraphyletic coalescence sequence is a sequence in which (1) all n red leaves have a common ancestor node that is not the ancestor of any blue leaves; or (2) all n blue leaves have a common ancestor node that is not the ancestor of any red leaves; but not both (1) and (2).
LINKS
N. A. Rosenberg, The shapes of neutral gene genealogies in two species: probabilities of monophyly, paraphyly, and polyphyly in a coalescent model, Evolution 57 (2003), 1465-1477.
FORMULA
a(n) = 3*(n!)^2*(2*n-2)!*(n-1)/((n+1)*2^(2*n-3)).
a(n) ~ 24*exp(-4*n)*n^(4*n-1/2)*Pi^(3/2). - Stefano Spezia, Apr 30 2024
EXAMPLE
For n=2, consider two red leaves R1 and R2 and two blue leaves B1 and B2. The a(2)=4 paraphyletic coalescence sequences, separated by semicolons, are (R1,R2), ((R1,R2),B1), (((R1,R2),B1),B2); (R1,R2), ((R1,R2),B2), (((R1,R2),B2),B1); (B1,B2), ((B1,B2),R1), (((B1,B2),R1),R2); and (B1,B2), ((B1,B2),R2), (((B1,B2),R2),R1).
MATHEMATICA
Table[3*(n!)^2*(2n - 2)!*(n - 1)/((n + 1)(2^(2 n - 3))), {n, 1, 30}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Noah A Rosenberg, Feb 09 2019
STATUS
approved