A306391 Number of polyphyletic coalescence sequences for 2n lineages, n each in 2 species.

0, 12, 2484, 1557792, 2560572000, 9326330280000, 66250877823900000, 834917902101803520000, 17373747843395915811840000, 564479089176417832085760000000, 27382950623629177584815808000000000, 1912097851374544604017590025267200000000, 186429568131038636125345650494922854400000000

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

Table of n, a(n) for n=1..13.

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

The total number of coalescence sequences for n leaves, from among which the polyphyletic coalescence sequences are identified, follows A006472. The sum of a(n), A306266(n), and A306350(n) is A006472(2n).

Sequence in context: A268589 A372343 A228289 * A195536 A010053 A092299

Adjacent sequences: A306388 A306389 A306390 * A306392 A306393 A306394

Keyword

nonn,changed

Author

Noah A Rosenberg, Feb 12 2019

Extensions

a(12)-a(13) from Stefano Spezia, Apr 30 2024

Status

approved