  Evolutionary models used for describing molecular sequence variation suppose
that at a non-recombining genomic segment, sequences share ancestry that can be
represented as a genealogy--a rooted, binary, timed tree, with tips
corresponding to individual sequences. Under the infinitely-many-sites mutation
model, mutations are randomly superimposed along the branches of the genealogy,
so that every mutation occurs at a chromosomal site that has not previously
mutated; if a mutation occurs at an interior branch, then all individuals
descending from that branch carry the mutation. The implication is that
observed patterns of molecular variation from this model impose combinatorial
constraints on the hidden state space of genealogies. In particular, observed
molecular variation can be represented in the form of a perfect phylogeny, a
tree structure that fully encodes the mutational differences among sequences.
For a sample of n sequences, a perfect phylogeny might not possess n distinct
leaves, and hence might be compatible with many possible binary tree structures
that could describe the evolutionary relationships among the n sequences. Here,
we investigate enumerative properties of the set of binary ranked and unranked
tree shapes that are compatible with a perfect phylogeny, and hence, the binary
ranked and unranked tree shapes conditioned on an observed pattern of mutations
under the infinitely-many-sites mutation model. We provide a recursive
enumeration of these shapes. We consider both perfect phylogenies that can be
represented as binary and those that are multifurcating. The results have
implications for computational aspects of the statistical inference of
evolutionary parameters that underlie sets of molecular sequences.
