|
|
A306423
|
|
Number of coalescent histories for pseudocaterpillar gene trees G and caterpillar species trees S.
|
|
1
|
|
|
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
|
|
|
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
D-finite with recurrence: +2*n*a(n) +(-11*n+18)*a(n-1) +(11*n-38)*a(n-2) +2*(2*n-11)*a(n-3)=0. - R. J. Mathar, Jan 27 2020
|
|
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))};
(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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|