Enumeration of rooted binary perfect phylogenies

Abstract

Rooted binary perfect phylogenies provide a generalization of rooted binary unlabeled trees in which each leaf is assigned a positive integer value that corresponds in a biological setting to the count of the number of indistinguishable lineages associated with the leaf. For the rooted binary unlabeled trees, these integers equal 1. We address a variety of enumerative problems concerning rooted binary perfect phylogenies with sample size $s$: the rooted binary unlabeled trees in which a sample of size $s$ lineages is distributed across the leaves of an unlabeled tree with $n$ leaves, $1\le n\le s$. The enumerations further characterize the rooted binary perfect phylogenies, which include the rooted binary unlabeled trees, and which can provide a set of structures useful for various biological contexts.