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
C. Chauve, Y. Ponty, M. Wallner, Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models, arXiv preprint arXiv:1905.04971 [math-CO], 2019.
FORMULA
G.f.: 1/2 - (1/2)*sqrt(-5 + 6*sqrt(1-4*z) + 4*z).
EXAMPLE
The caterpillar species tree with 2 leaves is equal to
a
/ \
1 2
For convenience the internal node is labeled by a, and the leaves by 1,2. The associated nodes in the histories will be denoted by the same labels.
The a(1)=2 histories with n=1 leaf are created by the following growth process:
a a
/ \
1 2
after one loss event each.
The a(2)=7 histories with n=2 leaves are created by the following growth process:
a a a a a a a
/ \ / \ / \ / \ / \ / \
1 2 1 2 a a a a a a a a
/ \ / \ / / / \ \ \ \ /
1 1 2 2 1 1 1 2 2 2 2 1
PROG
(PARI) my(z='z+O('z^30)); Vec(1/2-(1/2)*sqrt(-5+6*sqrt(1-4*z)+4*z)) \\ Michel Marcus, Apr 22 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael Wallner, Apr 22 2019
STATUS
approved