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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn></mml:mrow> </mml:math> leaves and sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>n</mml:mi></mml:mrow> </mml:math> : the rooted binary unlabeled trees with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> leaves in which a sample of size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>n</mml:mi></mml:mrow> </mml:math> lineages is distributed across the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> leaves. (1) First, we recursively enumerate rooted binary perfect phylogenies with sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> , summing over all possible <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>s</mml:mi></mml:mrow> </mml:math> . We obtain an equation for the generating function, showing that asymptotically, the number of rooted binary perfect phylogenies with sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> grows with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>≈</mml:mo> <mml:mn>0.3519</mml:mn> <mml:msup> <mml:mrow> <mml:mfenced><mml:mrow><mml:mn>3.2599</mml:mn></mml:mrow> </mml:mfenced> </mml:mrow> <mml:mi>s</mml:mi></mml:msup> <mml:msup><mml:mi>s</mml:mi> <mml:mrow><mml:mo>-</mml:mo> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn></mml:mrow> </mml:msup> </mml:mrow> </mml:math> , faster than the rooted binary unlabeled trees, which grow with ≈ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>≈</mml:mo> <mml:mn>0.3188</mml:mn> <mml:msup> <mml:mrow> <mml:mfenced><mml:mrow><mml:mn>2.4833</mml:mn></mml:mrow> </mml:mfenced> </mml:mrow> <mml:mi>s</mml:mi></mml:msup> <mml:msup><mml:mi>s</mml:mi> <mml:mrow><mml:mo>-</mml:mo> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn></mml:mrow> </mml:msup> </mml:mrow> </mml:math> . (2) Next, we recursively enumerate rooted binary perfect phylogenies with a specific number of leaves <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> and sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>n</mml:mi></mml:mrow> </mml:math> . We report closed-form counts of the rooted binary perfect phylogenies with sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>s</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>n</mml:mi></mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mtext>and</mml:mtext> <mml:mspace></mml:mspace> <mml:mn>4</mml:mn></mml:mrow> </mml:math> leaves. We provide a recurrence for the generating function describing, for each number of leaves <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> , the number of rooted binary perfect phylogenies with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> leaves as the sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> increases. We also obtain an equation satisfied by the bivariate generating function counting rooted binary perfect phylogenies with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi></mml:mrow> </mml:math> leaves and sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> , as well as an asymptotic normal distribution for the number of leaves in a randomly chosen perfect phylogeny with sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> . (3) We find a generating function for the number of rooted binary perfect phylogenies with the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> -leaf caterpillar shape, growing with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> . We also find a generating function and exact count <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfenced> <mml:mrow><mml:msup><mml:mn>2</mml:mn> <mml:mi>s</mml:mi></mml:msup> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn></mml:mrow> </mml:mfenced> </mml:mrow> </mml:math> for the number of rooted binary perfect phylogenies with sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> and any caterpillar tree shape. A bivariate generating function counting rooted binary perfect phylogenies with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> leaves, sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> , and a caterpillar shape produces an asymptotic normal distribution for the number of leaves in a randomly chosen caterpillar perfect phylogeny with sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> . (4) Finally, we provide initial results recursively enumerating rooted binary perfect phylogenies with any specific unlabeled tree shape and sample size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>s</mml:mi></mml:math> . 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.