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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307941 Number of evolutionary duplication-loss-histories of the complete binary species tree with 4 leaves. 2
4, 34, 368, 4685, 66416, 1013268, 16279788, 271594611, 4660794200, 81747301898, 1458812278424, 26400987754054, 483374731032868, 8936983620559660, 166617056922535080, 3128790129161470470, 59124052722375912960, 1123458655726125274620, 21452847767668402271220 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

An evolutionary history of size n is an ordered rooted (incomplete) binary tree with n leaves describing the evolution of a gene family of a species in phylogenomics. The complete binary species tree S of size k is a complete binary tree with k leaves. Any node of the history is associated to a unique node of S, where specifically every leaf is associated to a leaf of S. A history is created by the following process (note that intermediate trees in this process may not be valid histories): Start with a root node associated to the root of S. For a given tree in the growth process, choose a leaf and perform a duplication, speciation, or (speciation-)loss event. A duplication event creates two children both associated to the same node as its parent. A speciation or (speciation-)loss event can only occur if the node is associated to an internal node in S. In that case, a speciation event creates two children associated to the children of the node in S. A (speciation-)loss event creates only a left or right child, associated to the left or right child in S, respectively.

LINKS

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

FORMULA

G.f.: 1/2-(1/2)*sqrt(1+6*sqrt(-5+6*sqrt(1-4*z)+4*z)-6*sqrt(1-4*z)-4*z).

EXAMPLE

The complete binary species tree with 4 leaves is equal to

     a

   /   \

  b     c

/ \   / \

1   2  3  4

For convenience the internal nodes are labeled by a,b,c and the leaves by 1,2,3,4. The associated nodes in the histories will be denoted by the same labels.

The a(1)=4 histories with n=1 leaf are created by the following growth process:

    a     a     a      a

   /     /       \      \

  b     b         c      c

/       \       /        \

1         2     3          4

after two loss events each.

PROG

(PARI) z='z+O('z^20); Vec(1/2-(1/2)*sqrt(1+6*sqrt(-5+6*sqrt(1-4*z)+4*z)-6*sqrt(1-4*z)-4*z)) \\ Jianing Song, Jul 29 2019

CROSSREFS

Cf. A000108 (caterpillar/complete binary species tree with 1 leaf, ordinary binary trees).

Cf. A307696, A307697, A307698, A307700 (caterpillar species tree with 2, 3, 4, 5 leaves).

Sequence in context: A274344 A199752 A264607 * A084973 A234313 A197921

Adjacent sequences:  A307938 A307939 A307940 * A307942 A307943 A307944

KEYWORD

nonn

AUTHOR

Cedric Chauve, May 07 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 January 23 22:16 EST 2020. Contains 331177 sequences. (Running on oeis4.)