login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306423 Number of coalescent histories for pseudocaterpillar gene trees G and caterpillar species trees S. 0
11, 37, 124, 420, 1441, 5005, 17576, 62322, 222870, 802978, 2912168, 10623470, 38956365, 143521725, 530985360, 1971965490, 7348812570, 27472909590, 103002205800, 387205269360, 1459146890058, 5511120747282, 20858962792624, 79103096214100 (list; graph; refs; listen; history; text; internal format)
OFFSET

5,1

COMMENTS

Consider a binary, rooted, leaf-labeled caterpillar species tree G = (...((((A_1, A_2), A_3), A_4), A_5),..., A_n) and a binary, rooted, leaf-labeled pseudocaterpillar gene tree (...(((A_1, A_2), (A_3, A_4)), A_5),..., A_n). The pseudocaterpillar family of trees is defined for n>=5 leaves (Rosenberg 2007). Sequence a(n) gives the number of coalescent histories for (G,S).

LINKS

Table of n, a(n) for n=5..28.

N. A. Rosenberg and J. H. Degnan, Coalescent histories for discordant gene trees and species trees. Theor. Pop. Biol. 77 (2010), 145-151.

FORMULA

a(n) = (19*n-40)*(n-3)*(2*n-2)!/(4*n!*(n-1)!*(2*n-3)*(2*n-5)).

a(n) = (19*n-40)*(n-3)*C(n-1)/((2*n-3)*(2*n-5)), where C(n) is the Catalan numbers A000108.

G.f.: ((2 -7*x +x^2 -6*x^4) +(-2 +3*x +x^2)*sqrt(1-4*x))/2. - G. C. Greubel, Mar 07 2019

EXAMPLE

For n=5, consider species tree ((((A_1, A_2), A_3), A_4), A_5) and gene tree ((((A_1, A_2), (A_3, A_4)), A_5). Label the nodes of the species tree 1, 2, 3, 4, from the cherry to the root, identifying each node with its immediate ancestral edge. Annotate the coalescent histories by vectors whose entries, in order, denote the locations of the coalescences of (A_1, A_2), (A_3, A_4), ((A_1, A_2), (A_3, A_4)), and ((((A_1, A_2), (A_3, A_4)), A_5). The a(5)=11 coalescent histories are (1,3,3,4), (1,3,4,4), (1,4,4,4), (2,3,3,4), (2,3,4,4), (2,4,4,4), (3,3,3,4), (3,3,4,4), (3,4,4,4), (4,3,4,4), and (4,4,4,4).

MATHEMATICA

Table[(19n-40)(n-3) Binomial[2n-2, n-1]/(4n(2n-3)(2n-5)), {n, 5, 30}]

PROG

(PARI) {a(n)=(19*n-40)*(n-3)*binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5))};

for(n=5, 30, print1(a(n), ", ")) \\ G. C. Greubel, Mar 07 2019

(MAGMA) [(19*n-40)*(n-3)*Binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5)): n in [5..30]]; // G. C. Greubel, Mar 07 2019

(Sage) [(19*n-40)*(n-3)*binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5)) for n in (5..30)] # G. C. Greubel, Mar 07 2019

(GAP) List([5..30], n-> (19*n-40)*(n-3)*Binomial(2*n-2, n-1)/(4*n*(2*n-3)*(2*n-5))) # G. C. Greubel, Mar 07 2019

CROSSREFS

A000108 gives the number of coalescent histories for matching caterpillar gene trees and species trees. A070031 gives the number of coalescent histories for matching pseudocaterpillar gene trees and species trees.

Sequence in context: A229612 A297797 A210321 * A287018 A152094 A227412

Adjacent sequences:  A306420 A306421 A306422 * A306424 A306425 A306426

KEYWORD

nonn

AUTHOR

Noah A Rosenberg, Feb 14 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 19 08:48 EDT 2019. Contains 325155 sequences. (Running on oeis4.)