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



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307942 Number of evolutionary duplication-loss-histories of the complete binary species tree with 8 leaves. 0
8, 148, 3376, 89390, 2624872, 82866636, 2755019736, 95135709027, 3380416782760, 122798718575216, 4539685792433848, 170225552910292438, 6458330316575589176, 247456381334355675220, 9561546562984390785960, 372141845574597078971490, 14575950501012888889866120 (list; graph; refs; listen; history; text; internal format)



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.


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


G.f.: 1/2-(1/2)*sqrt(-5+6*v-6*u+6*t+4*z) where t = sqrt(1-4*z), u = sqrt(-5+6*t+4*z) and v = sqrt(1+6*u-6*t-4*z).


See A307941 (complete binary species tree with 4 leaves).


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


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: A259991 A212732 A220297 * A116876 A218305 A244028

Adjacent sequences:  A307939 A307940 A307941 * A307943 A307944 A307945




Cedric Chauve, May 07 2019



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 September 29 10:06 EDT 2020. Contains 337428 sequences. (Running on oeis4.)