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. Consider two possible features of the resulting tree: (1) all n red leaves have a common ancestor node that is not the ancestor of any blue leaves; (2) all n blue leaves have a common ancestor node that is not the ancestor of any red leaves. A reciprocally monophyletic sequence satisfies both (1) and (2). A paraphyletic coalescence sequence satisfies (1) or (2) but not both. A polyphyletic coalescence sequence does not satisfy either (1) or (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) = (1 - (2 n! n!/(2n)!)(7n-5)/((n+1)(2n-1))) (2n)! (2n-1)!/2^(2n-1).
a(n) ~ exp(-4*n)*n^(4*n-1)*(4^n + 3*4^(1+n)*n - 84*sqrt(n*Pi))*Pi/3. - 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)=12 polyphyletic coalescence sequences, separated by semicolons, are (B1,R1), ((B1,R1),B2), (((B1,R1),B2),R2); (B1,R1), ((B1,R1),R2), (((B1,R1),R2),B2); (B1,R2), ((B1,R2),B2), (((B1,R2),B2),R1); (B1,R2), ((B1,R2),R1), (((B1,R2),R1),B2); (B2,R1), ((B2,R1),B1), (((B2,R1),B1),R2); (B2,R1), ((B2,R1),R2), (((B2,R1),R2),B1); (B2,R2), ((B2,R2),B1), (((B2,R2),B1),R1); (B2,R2), ((B2,R2),R1), (((B2,R2),R1),B1); (B1,R1), (B2,R2), ((B1,R1),(B2,R2)); (B1,R2), (B2,R1), ((B1,R2),(B2,R1)); (B2,R1), (B1,R2), ((B2,R1),(B1,R2)); (B2,R2), (B1,R1), ((B2,R2),(B1,R1)).
MATHEMATICA
Table[(1 - (2 n! n!/(2 n)!) (7 n - 5)/((n + 1) (2 n - 1))) (2 n)! (2 n - 1)!/2^(2 n - 1), {n, 1, 30}]
PROG
(PARI) a(n) = (1 - (2*n!*n!/(2*n)!)*(7*n-5)/((n+1)*(2*n-1)))*(2*n)!*(2*n-1)!/2^(2*n-1); \\ Michel Marcus, Feb 12 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Noah A Rosenberg, Feb 12 2019
EXTENSIONS
a(12)-a(13) from Stefano Spezia, Apr 30 2024
STATUS
approved