|
|
A307697
|
|
Number of Evolutionary Duplication-Loss-histories with n leaves of the caterpillar species tree with 3 leaves.
|
|
6
|
|
|
3, 19, 159, 1565, 17022, 197928, 2413494, 30490089, 395828145, 5250493688, 70863932052, 970121212741, 13439019867456, 188038364992270, 2653560128625570, 37723174042204665, 539726553801797610, 7765849268430279390
(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 caterpillar species tree S of size k is a binary tree with k leaves, where any left child is a leaf. 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(-4 - t*u + 3*t + 3*u) where t = sqrt(1 - 4*z) and u = sqrt(-5 + 6*t + 4*z).
|
|
EXAMPLE
|
The caterpillar species tree with 3 leaves is equal to
a
/ \
b 3
/ \
1 2
For convenience the internal nodes are labeled by a,b, and the leaves by 1,2,3. The associated nodes in the histories will be denoted by the same labels.
The a(1)=3 histories with n=1 leaf are created by the following growth process:
a a a
/ / \
b b 3
/ \
1 2
after two loss events each.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|