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

Author

Noah A Rosenberg, Feb 14 2019

Keywords

• nonn
• more

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

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