A306422 Maximal number of coalescent histories among matching pairs of binary, rooted leaf-labeled gene trees and species trees with n leaves.

1, 1, 2, 5, 14, 42, 138, 462, 1663

Offset

1,3

Comments

Consider the unlabeled binary, rooted, leaf-labeled tree topologies with n leaves (A001190). For each unlabeled topology, choose an arbitrary labeling with distinct labels for the n leaves, and assign it to both gene tree and species tree. Compute the number of coalescent histories for that matching (gene tree, species tree) pair according to a recursion (Rosenberg 2007, Theorem 3.1). The sequence a(n) gives the largest number observed among all unlabeled topologies.

Links

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

N. A. Rosenberg, Counting coalescent histories, J. Comput. Biol. 14 (2007), 360-377.

Crossrefs

Cf. A001190.

A000108 and A005817 give the numbers of coalescent histories for specific families of matching gene trees and species trees.

Sequence in context: A165146 A360708 A148331 * A052853 A149877 A149878

Adjacent sequences: A306419 A306420 A306421 * A306423 A306424 A306425

Keyword

nonn,more

Author

Noah A Rosenberg, Feb 14 2019

Status

approved