login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307696 Number of evolutionary duplication-loss-histories with n leaves of the caterpillar species tree with 2 leaves. 6
2, 7, 34, 200, 1318, 9354, 69864, 541323, 4310950, 35066384, 290081932, 2432766082, 20635672664, 176727482860, 1526000459400, 13270616752680, 116124930068670, 1021736927603190, 9033726534916920, 80220639767921370, 715166816624282820, 6398357633173869600 (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

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

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

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

Sequence in context: A326560 A199475 A241599 * A237645 A117399 A145345

Adjacent sequences:  A307693 A307694 A307695 * A307697 A307698 A307699

KEYWORD

nonn

AUTHOR

Michael Wallner, Apr 22 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 28 18:24 EDT 2022. Contains 354122 sequences. (Running on oeis4.)