A307696 -id:A307696 - cp's OEIS frontend

A307697 Number of Evolutionary Duplication-Loss-histories with n leaves of the caterpillar species tree with 3 leaves.

3, 19, 159, 1565, 17022, 197928, 2413494, 30490089, 395828145, 5250493688, 70863932052, 970121212741, 13439019867456, 188038364992270, 2653560128625570, 37723174042204665, 539726553801797610, 7765849268430279390

Offset: 1

Michael Wallner, Apr 22 2019

nonn

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.

			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.

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.

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

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).

A307698 Number of evolutionary duplication-loss-histories with n leaves of the caterpillar species tree with 4 leaves.

Original entry on oeis.org

4, 39, 495, 7235, 115303, 1948791, 34379505, 626684162, 11722058693, 223870302588, 4349161774626, 85701267415112, 1709101664822416, 34432888701965454, 699810795294490974, 14331183304458656628, 295434131968070459359, 6125911207605272841753, 127680054133385458855845

Offset: 1

Michael Wallner, Apr 22 2019

nonn

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.

			The caterpillar species tree with 4 leaves is equal to
        a
       / \
      b   4
     / \
    c   3
   / \
  1   2
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     b        4
     /     /       \
    c     c         3
   /       \
  1         2
after three loss events each.

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.

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

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)); Vec(1/2-(1/2)*sqrt(-4-t*v+3*t+3*v)) \\ Michel Marcus, May 07 2019

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

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

Original entry on oeis.org

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

Offset: 1

Michael Wallner, Apr 22 2019

nonn

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.

			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.

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.

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

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

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).

A307941 Number of evolutionary duplication-loss-histories of the complete binary species tree with 4 leaves.

Original entry on oeis.org

4, 34, 368, 4685, 66416, 1013268, 16279788, 271594611, 4660794200, 81747301898, 1458812278424, 26400987754054, 483374731032868, 8936983620559660, 166617056922535080, 3128790129161470470, 59124052722375912960, 1123458655726125274620, 21452847767668402271220

Offset: 1

Cedric Chauve, May 07 2019

nonn

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.

			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.

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).

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

G.f.: 1/2-(1/2)*sqrt(1+6*sqrt(-5+6*sqrt(1-4*z)+4*z)-6*sqrt(1-4*z)-4*z).

A307943 Number of evolutionary duplication-loss-histories of the complete binary species tree with 16 leaves.

Original entry on oeis.org

16, 616, 28832, 1556780, 93017264, 5971377672, 403667945712, 28346017000314, 2048467088599520, 151362953286590792, 11383212160213595696, 868385902978402717696, 67032303753464250574432, 5225869642113491897295040, 410865063418648682500317120

Offset: 1

Cedric Chauve, May 07 2019

nonn

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.

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

Sean A. Irvine, Java program (github)

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).

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

A307942 Number of evolutionary duplication-loss-histories of the complete binary species tree with 8 leaves.

Original entry on oeis.org

8, 148, 3376, 89390, 2624872, 82866636, 2755019736, 95135709027, 3380416782760, 122798718575216, 4539685792433848, 170225552910292438, 6458330316575589176, 247456381334355675220, 9561546562984390785960, 372141845574597078971490, 14575950501012888889866120

Offset: 1

Cedric Chauve, May 07 2019

nonn

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.

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

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).

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

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).

cp's OEIS Frontend

A307697 Number of Evolutionary Duplication-Loss-histories with n leaves of the caterpillar species tree with 3 leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A307698 Number of evolutionary duplication-loss-histories with n leaves of the caterpillar species tree with 4 leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A307941 Number of evolutionary duplication-loss-histories of the complete binary species tree with 4 leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A307943 Number of evolutionary duplication-loss-histories of the complete binary species tree with 16 leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A307942 Number of evolutionary duplication-loss-histories of the complete binary species tree with 8 leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula