A307700 Number of evolutionary duplication-loss-histories with n leaves of the caterpillar species tree with 5 leaves.

5, 69, 1230, 24843, 541315, 12426996, 296546600, 7292489761, 183702242491, 4719659859582, 123261298705663, 3263950145153931, 87452457544863592, 2366980142343757033, 64628573978046899555, 1778185743733577832862, 49254755849062502247446, 1372455474283175885070422

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

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

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(-4 - t*w + 3*t + 3*w) where t = sqrt(1 - 4*z), u = sqrt(-5 + 6*t + 4*z), v = sqrt(-t*u + 3*t + 3*u - 4) and w = sqrt(-t*v + 3*t + 3*v - 4).

Example

The caterpillar species tree with 5 leaves is equal to
          a
         / \
        b   5
       / \
      c   4
     / \
    d   3
   / \
  1   2
For convenience the internal nodes are labeled by a,b,c,d, and the leaves by 1,2,3,4,5. The associated nodes in the histories will be denoted by the same labels.
The a(1)=5 histories with n=1 leaf are created by the following growth process:
          a     a     a     a    a
         /     /     /     /      \
        b     b     b     b        5
       /     /     /       \
      c     c     c         4
     /     /       \
    d     d         3
   /       \
  1         2
after four loss events each.

Prog

(PARI) my(z = 'z + O('z^25), t = sqrt(1-4*z), u = sqrt(-5+6*t+4*z), v = sqrt(-t*u+3*t+3*u-4), w = sqrt(-t*v+3*t+3*v-4)); Vec(1/2-(1/2)*sqrt(-4-t*w+3*t+3*w)) \\ Michel Marcus, May 07 2019

Crossrefs

Caterpillar species tree sequences: A000108 (1 leaf), A307696 (2 leaves), A307697 (3 leaves), A307698 (4 leaves).

Sequence in context: A333035 A333459 A362101 * A326435 A377744 A231294

Adjacent sequences: A307697 A307698 A307699 * A307701 A307702 A307703

Keyword

nonn

Author

Michael Wallner, Apr 22 2019

Status

approved