Coalescent Histories for Caterpillar-Like Families

A coalescent history is an assignment of branches of a gene tree to branches of a species tree on which coalescences in the gene tree occur. The number of coalescent histories for a pair consisting of a labeled gene tree topology and a labeled species tree topology is important in gene tree probability computations, and more generally, in studying evolutionary possibilities for gene trees on species trees. Defining the T_r-caterpillar-like family as a sequence of n-taxon trees constructed by replacing the r-taxon subtree of n-taxon caterpillars by a specific r-taxon labeled topology T_r, we examine the number of coalescent histories for caterpillarlike families with matching gene tree and species tree labeled topologies. For each T_r with size r ≤ 8, we compute the number of coalescent histories for n-taxon trees in the T_r-caterpillar-like family. Next, as n → ∞, we find that the limiting ratio of the numbers of coalescent histories for the T_r family and caterpillars themselves is correlated with the number of labeled histories for T_r. The results support a view that large numbers of coalescent histories occur when a tree has both a relatively balanced subtree and a high tree depth, contributing to deeper understanding of the combinatorics of gene trees and species trees.