Enumeration of rooted binary perfect phylogenies

Rooted binary perfect phylogenies provide a generalization of rooted binary unlabeled trees. In a rooted binary perfect phylogeny, 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 enumerate rooted binary perfect phylogenies with $n\ge 1$ leaves and sample size $s$ , $s\ge n$ : the rooted binary unlabeled trees with $n$ leaves in which a sample of size $s\ge n$ lineages is distributed across the $n$ leaves. (1) First, we recursively enumerate rooted binary perfect phylogenies with sample size $s$ , summing over all possible $n$ , $1\le n\le s$ . We obtain an equation for the generating function, showing that asymptotically, the number of rooted binary perfect phylogenies with sample size $s$ grows with $\approx 0.3519{\left(3.2599\right)}^s{s}^{-3/2}$ , faster than the rooted binary unlabeled trees, which grow with ≈ $\approx 0.3188{\left(2.4833\right)}^s{s}^{-3/2}$ . (2) Next, we recursively enumerate rooted binary perfect phylogenies with a specific number of leaves $n$ and sample size $s\ge n$ . We report closed-form counts of the rooted binary perfect phylogenies with sample size $s\ge n$ and $n=2,3,\text{and}4$ leaves. We provide a recurrence for the generating function describing, for each number of leaves $n$ , the number of rooted binary perfect phylogenies with $n$ leaves as the sample size $s$ increases. We also obtain an equation satisfied by the bivariate generating function counting rooted binary perfect phylogenies with $n$ leaves and sample size $s$ , as well as an asymptotic normal distribution for the number of leaves in a randomly chosen perfect phylogeny with sample size $s$ . (3) We find a generating function for the number of rooted binary perfect phylogenies with the $n$ -leaf caterpillar shape, growing with $s$ . We also find a generating function and exact count $\left(2^s/3\right)$ for the number of rooted binary perfect phylogenies with sample size $s$ and any caterpillar tree shape. A bivariate generating function counting rooted binary perfect phylogenies with $n$ leaves, sample size $s$ , and a caterpillar shape produces an asymptotic normal distribution for the number of leaves in a randomly chosen caterpillar perfect phylogeny with sample size $s$ . (4) Finally, we provide initial results recursively enumerating rooted binary perfect phylogenies with any specific unlabeled tree shape and sample size $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.