

A307941


Number of evolutionary duplicationlosshistories 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



FORMULA

G.f.: 1/2(1/2)*sqrt(1+6*sqrt(5+6*sqrt(14*z)+4*z)6*sqrt(14*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(14*z)+4*z)6*sqrt(14*z)4*z)) \\ Jianing Song, Jul 29 2019


CROSSREFS

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


KEYWORD

nonn


AUTHOR



STATUS

approved



