login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306402 Number of coalescent histories for a matching completely symmetric gene tree and completely symmetric species tree with 2^n leaves. 0
1, 1, 4, 169, 1020100, 270062420147776, 686954819460520804489954417158400, 3171571350979001722602021784038902498684386645982829438130935832126653601 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A completely symmetric tree with 2^n leaves is a tree recursively defined by subdividing the root into two descendant branches with equally many leaves. The number of coalescent histories for matching completely symmetric trees with 2^n leaves can be determined from a bivariate recursion that considers completely symmetric trees with 2^(n-1) leaves (Rosenberg 2007, Theorem 3.1).

LINKS

Table of n, a(n) for n=0..7.

N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.

FORMULA

a(n) = b(n,1), where b(n,k) is defined for integers n>=0 and k>=1, b(n,k) = Sum_{m=2..k+1} b(n-1,k+1)^2, and b(0,k)=1 for all k.

EXAMPLE

For n=2, the trees have 2^2=4 leaves. Labeling these leaves A, B, C, and D, suppose the gene tree and species tree have matching labeled topology ((A,B),(C,D)). Denote the species tree edges immediately ancestral to species tree nodes (A,B), (C,D), and ((A,B),(C,D)) by 1, 2, and 3 respectively. The 4 coalescent histories, representing the vector of the images of gene tree nodes ((A,B), (C,D), ((A,B),(C,D)) in the species tree, are (3,3,3), (1,3,3), (3,2,3), and (1,2,3).

MATHEMATICA

b[0, k_] := 1

Do[b[n, k] = Sum[b[n - 1, m]^2, {m, 2, k + 1}], {k, 1, 11}, {n, 1, 10}]

Do[Print[b[n, 1]], {n, 0, 10}]

(* Note: this is a bivariate recursion in which b[n, 1] is of interest. The largest value of k required for evaluating b[n, 1] increases as n decreases; set the upper limit on k larger than the upper limit on n. *)

CROSSREFS

Coalescent histories appear also in A306205, A306295.

Sequence in context: A283566 A221083 A181191 * A057140 A245323 A348085

Adjacent sequences:  A306399 A306400 A306401 * A306403 A306404 A306405

KEYWORD

nonn

AUTHOR

Noah A Rosenberg, Feb 13 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 November 28 00:12 EST 2021. Contains 349395 sequences. (Running on oeis4.)