1._CRD Introduction_NN1 
In_PRP mathematical_AJ0 phylogenetics_NN2 ,_PUN a_AT0 coalescent_AJ0 history_NN1 represents_VVZ the_AT0 paired_AJ0 list_NN1 of_PRF coalescences_NN2 in_PRP a_AT0 gene_NN1 tree_NN1 together_AV0 with_PRP their_DPS associated_AJ0 edges_NN2 of_PRF a_AT0 species_NN0 tree_NN1 ._SENT Consider_VVB two_CRD binary_AJ0 ,_PUN rooted_AJ0 ,_PUN leaf-labeled_AJ0 trees_NN2 ,_PUN G_ZZ0 and_CJC S_ZZ0 ,_PUN with_PRP leaves_NN2 labeled_VVN by_PRP the_AT0 same_DT0 label_NN1 set_NN1 X_ZZ0 ,_PUN such_DT0 that_CJT each_DT0 label_NN1 in_PRP X_ZZ0 is_VBZ associated_VVN with_PRP exactly_AV0 one_CRD leaf_NN1 of_PRF G_ZZ0 and_CJC exactly_AV0 one_CRD leaf_NN1 of_PRF S._NP0 We_PNP regard_VVB G_ZZ0 as_PRP a_AT0 gene_NN1 tree_NN1 representing_VVG the_AT0 evolution_NN1 of_PRF genealogical_AJ0 lineages_NN2 in_PRP a_AT0 group_NN1 of_PRF species_NN0 ,_PUN and_CJC S_ZZ0 as_PRP the_AT0 species_NN0 tree_NN1 representing_VVG the_AT0 evolutionary_AJ0 descent_NN1 of_PRF the_AT0 species_NN0 themselves_PNX ._SENT 
For_PRP a_AT0 gene_NN1 tree_NN1 G_ZZ0 evolving_VVG on_PRP a_AT0 species_NN0 tree_NN1 S_ZZ0 ,_PUN a_AT0 coalescent_AJ0 history_NN1 is_VBZ a_AT0 mapping_NN1 from_PRP the_AT0 set_NN1 of_PRF internal_AJ0 nodes_NN2 of_PRF G_ZZ0 to_PRP the_AT0 set_NN1 of_PRF internal_AJ0 edges_NN2 of_PRF S_ZZ0 ,_PUN such_DT0 that_DT0 two_CRD rules_NN2 are_VBB followed_VVN :_PUN (_PUL i_ZZ0 )_PUR the_AT0 image_NN1 of_PRF an_AT0 internal_AJ0 node_NN1 v_ZZ0 of_PRF G_ZZ0 is_VBZ ancestral_AJ0 in_PRP S_ZZ0 to_PRP each_DT0 leaf_NN1 of_PRF S_ZZ0 that_CJT shares_VVZ a_AT0 label_NN1 with_PRP some_DT0 leaf_NN1 descended_VVN from_PRP v_ZZ0 in_PRP G_ZZ0 ;_PUN (_PUL ii_CRD )_PUR the_AT0 image_NN1 of_PRF an_AT0 internal_AJ0 node_NN1 v_ZZ0 of_PRF G_ZZ0 is_VBZ ancestral_AJ0 in_PRP S_ZZ0 to_PRP the_AT0 images_NN2 of_PRF each_DT0 of_PRF its_DPS descendant_NN1 nodes_NN2 ._SENT The_AT0 biological_AJ0 interpretation_NN1 of_PRF (_PUL i_ZZ0 )_PUR is_VBZ that_CJT a_AT0 set_NN1 of_PRF gene_NN1 lineages_NN2 can_VM0 only_AV0 find_VVI a_AT0 common_AJ0 ancestor_NN1 on_PRP a_AT0 species_NN0 tree_NN1 edge_NN1 that_CJT it_PNP is_VBZ possible_AJ0 for_PRP them_PNP all_DT0 to_TO0 reach_VVI ;_PUN the_AT0 interpretation_NN1 of_PRF (_PUL ii_CRD )_PUR is_VBZ that_CJT the_AT0 gene_NN1 lineages_NN2 descended_VVN from_PRP a_AT0 descendant_NN1 node_NN1 coalesce_VVB at_PRP least_AV0 as_CJS recently_AV0 as_CJS do_VDB the_AT0 gene_NN1 lineages_NN2 descended_VVN from_PRP its_DPS ancestral_AJ0 nodes_NN2 ._SENT Note_VVB that_CJT we_PNP regard_VVB a_AT0 node_NN1 as_CJS trivially_AV0 ancestral_AJ0 to_PRP and_CJC descended_VVD from_PRP itself_PNX ._SENT The_AT0 coalescent_AJ0 histories_NN2 for_PRP (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR can_VM0 be_VBI viewed_VVN as_PRP describing_VVG a_AT0 discrete_AJ0 class_NN1 of_PRF evolutionary_AJ0 scenarios_NN2 for_PRP the_AT0 lineages_NN2 of_PRF G_ZZ0 on_PRP the_AT0 edges_NN2 of_PRF S._NP0 
A_AT0 variety_NN1 of_PRF studies_NN2 have_VHB enumerated_VVN the_AT0 coalescent_AJ0 histories_NN2 for_PRP pairs_NN2 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR ,_PUN both_AV0 by_PRP a_AT0 recursive_AJ0 approach_NN1 that_CJT applies_VVZ for_PRP all_DT0 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR ,_PUN and_CJC by_PRP closed-form_AJ0 formulas_NN2 and_CJC bijective_AJ0 constructions_NN2 suited_VVN to_PRP particular_AJ0 families_NN2 of_PRF trees_NN2 ._SENT These_DT0 enumeration_NN1 studies_NN2 ,_PUN primarily_AV0 considering_VVG matching_AJ0 gene_NN1 trees_NN2 and_CJC species_NN0 trees_NN2 with_PRP G_ZZ0 =_NN1 S_ZZ0 and_CJC having_VHG particular_AJ0 emphasis_NN1 on_PRP shapes_NN2 such_DT0 as_PRP caterpillars_NN2 ,_PUN 4-pseudocaterpillars_NN2 ,_PUN and_CJC caterpillar-like_AJ0 families_NN2 (_PUL Fig._NN1 1_CRD )_PUR ,_PUN have_VHB informally_AV0 observed_VVN that_CJT in_PRP specified_AJ0 classes_NN2 of_PRF trees_NN2 ,_PUN the_AT0 largest_AJS number_NN1 of_PRF coalescent_AJ0 histories_NN2 tends_VVZ to_TO0 occur_VVI when_CJS the_AT0 pair_NN0 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR has_VHZ two_CRD features_NN2 :_PUN multiple_AJ0 sequences_NN2 exist_VVB in_PRP which_DTQ the_AT0 coalescences_NN2 of_PRF G_ZZ0 can_VM0 be_VBI arranged_VVN ,_PUN and_CJC many_DT0 edges_NN2 of_PRF S_ZZ0 exist_VVB on_PRP which_DTQ those_DT0 coalescences_NN2 can_VM0 take_VVI place_NN1 ._SENT 
Rosenberg_NP0 observed_VVD that_CJT for_PRP small_AJ0 trees_NN2 with_PRP at_PRP most_AV0 n_ZZ0 =_NN1 9_CRD leaves_NN2 and_CJC G_ZZ0 =_NN1 S_ZZ0 ,_PUN the_AT0 largest_AJS numbers_NN2 of_PRF coalescent_AJ0 histories_NN2 among_PRP tree_NN1 pairs_NN2 (_PUL G_ZZ0 ,_PUN G_ZZ0 )_PUR with_PRP fixed_AJ0 n_ZZ0 were_VBD seen_VVN for_PRP trees_NN2 that_CJT had_VHD structure_NN1 similar_AJ0 to_PRP caterpillar_NN1 trees_NN2 ,_PUN but_CJC that_DT0 unlike_AJ0 caterpillars_NN2 ,_PUN had_VHD more_AV0 than_CJS one_CRD possible_AJ0 sequence_NN1 of_PRF coalescences_NN2 ._SENT Rosenberg_NP0 and_CJC Disanto_NP0 &_NP0 Rosenberg_NP0 examined_VVD tree_NN1 families_NN2 (_PUL G_ZZ0 ,_PUN G_ZZ0 )_PUR ,_PUN with_PRP n_XX0 growing_VVG arbitrarily_AV0 large_AJ0 in_PRP specified_AJ0 caterpillar-like_AJ0 tree_NN1 families_NN2 ._SENT Beginning_VVG with_PRP a_AT0 seed_NN1 tree_NN1 ,_PUN these_DT0 studies_NN2 generated_VVN families_NN2 of_PRF increasingly_AV0 large_AJ0 trees_NN2 by_PRP sequentially_AV0 adding_VVG taxa_NN2 so_AV0 that_CJT the_AT0 next_ORD tree_NN1 in_PRP a_AT0 family_NN1 was_VBD formed_VVN by_PRP placing_VVG the_AT0 current_AJ0 tree_NN1 and_CJC a_AT0 single_AJ0 leaf_NN1 on_PRP opposite_AJ0 sides_NN2 of_PRF a_AT0 new_AJ0 root_NN1 ._SENT They_PNP saw_VVD that_CJT across_PRP all_DT0 seed_NN1 trees_NN2 of_PRF a_AT0 fixed_AJ0 small_AJ0 size_NN1 ,_PUN as_CJS the_AT0 number_NN1 of_PRF leaves_NN2 grew_VVD without_PRP bound_NN1 ,_PUN the_AT0 largest_AJS numbers_NN2 of_PRF coalescent_AJ0 histories_NN2 were_VBD achieved_VVN when_CJS the_AT0 seed_NN1 tree_NN1 had_VHD many_DT0 different_AJ0 sequences_NN2 in_PRP which_DTQ its_DPS coalescences_NN2 could_VM0 be_VBI arranged_VVN ._SENT Disanto_NP0 &_NP0 Rosenberg_NP0 constructed_VVD a_AT0 tree_NN1 family_NN1 ,_PUN the_AT0 lodgepole_NN1 family_NN1 ,_PUN that_DT0 ,_PUN unlike_PRP caterpillar_NN1 families_NN2 ,_PUN grows_VVZ so_AV0 that_DT0 as_CJS the_AT0 number_NN1 of_PRF leaves_NN2 increases_NN2 ,_PUN trees_NN2 accumulate_VVB both_DT0 new_AJ0 sequences_NN2 in_PRP which_DTQ coalescences_NN2 can_VM0 be_VBI arranged_VVN and_CJC new_AJ0 places_NN2 for_PRP them_PNP to_TO0 occur_VVI ._SENT This_DT0 family_NN1 is_VBZ the_AT0 family_NN1 of_PRF matching_AJ0 tree_NN1 pairs_NN2 (_PUL G_ZZ0 ,_PUN G_ZZ0 )_PUR with_PRP the_AT0 largest-known_AJ0 number_NN1 of_PRF coalescent_AJ0 histories_NN2 as_CJS n_ZZ0 increases_VVZ without_PRP bound_NN1 ._SENT 
Despite_PRP many_DT0 observations_NN2 suggesting_VVG that_CJT coalescent_AJ0 histories_NN2 tend_VVB to_TO0 increase_VVI in_PRP number_NN1 when_CJS G_ZZ0 has_VHZ many_DT0 sequences_NN2 in_PRP which_DTQ coalescences_NN2 can_VM0 be_VBI arranged_VVN and_CJC many_DT0 edges_NN2 on_PRP which_DTQ those_DT0 coalescences_NN2 can_VM0 occur_VVI ,_PUN existing_AJ0 results_NN2 in_PRP support_NN1 of_PRF this_DT0 view_NN1 have_VHB focused_VVN on_PRP small_AJ0 trees_NN2 and_CJC on_PRP informal_AJ0 interpretations_NN2 of_PRF specific_AJ0 families_NN2 with_PRP large_AJ0 limits_NN2 as_PRP n_ZZ0 →_NP0 ∞_NP0 ;_PUN no_AT0 result_NN1 has_VHZ formally_AV0 demonstrated_VVN the_AT0 observation_NN1 in_PRP a_AT0 class_NN1 of_PRF trees_NN2 for_PRP a_AT0 fixed_AJ0 finite_AJ0 n_ZZ0 of_PRF arbitrary_AJ0 size_NN1 ._SENT We_PNP devise_VVB a_AT0 scenario_NN1 to_TO0 formalize_VVI this_DT0 idea_NN1 characterizing_VVG cases_NN2 with_PRP the_AT0 largest_AJS numbers_NN2 of_PRF coalescent_AJ0 histories_NN2 ._SENT We_PNP fix_VVB the_AT0 species_NN0 tree_NN1 S_ZZ0 to_TO0 be_VBI a_AT0 caterpillar_NN1 ,_PUN and_CJC we_PNP consider_VVB a_AT0 family_NN1 of_PRF non-matching_AJ0 gene_NN1 trees_NN2 G_ZZ0 ,_PUN the_AT0 p-pseudocaterpillars_NN2 ._SENT We_PNP show_VVB that_CJT in_PRP this_DT0 class_NN1 of_PRF non-matching_AJ0 pairs_NN2 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR with_PRP fixed_AJ0 n_ZZ0 ,_PUN the_AT0 largest_AJS number_NN1 of_PRF coalescent_AJ0 histories_NN2 is_VBZ achieved_VVN precisely_AV0 when_CJS G_ZZ0 combines_VVZ the_AT0 two_CRD elements_NN2 :_PUN many_DT0 coalescence_NN1 sequences_NN2 ,_PUN and_CJC many_DT0 edges_NN2 on_PRP which_DTQ those_DT0 coalescences_NN2 can_VM0 take_VVI place_NN1 ._SENT 
Our_DPS approach_NN1 is_VBZ one_CRD of_PRF relatively_AV0 few_DT0 to_TO0 examine_VVI enumerations_NN2 of_PRF coalescent_AJ0 histories_NN2 in_PRP the_AT0 case_NN1 that_CJT G_ZZ0 is_VBZ not_XX0 necessarily_AV0 equal_AJ0 to_PRP S._NP0 The_AT0 strategy_NN1 employs_VVZ a_AT0 construction_NN1 that_CJT enumerates_VVZ coalescent_AJ0 histories_NN2 for_PRP non-matching_AJ0 caterpillar_NN1 trees_NN2 ._SENT Generalizing_VVG a_AT0 result_NN1 of_PRF Degnan_NP0 for_PRP enumeration_NN1 of_PRF coalescent_AJ0 histories_NN2 for_PRP matching_AJ0 caterpillar_NN1 trees_NN2 ,_PUN Himwich_NP0 &_NP0 Rosenberg_NP0 produced_VVD a_AT0 bijection_NN1 with_PRP monotonic_AJ0 paths_NN2 for_PRP use_NN1 in_PRP enumerating_VVG coalescent_AJ0 histories_NN2 for_PRP non-matching_AJ0 caterpillar_NN1 pairs_NN2 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR ._SENT We_PNP use_VVB this_DT0 monotonic-path_NN1 construction_NN1 to_TO0 enumerate_VVI coalescent_AJ0 histories_NN2 for_PRP the_AT0 class_NN1 of_PRF non-matching_AJ0 trees_NN2 that_CJT considers_VVZ a_AT0 caterpillar_NN1 species_NN0 tree_NN1 S_ZZ0 and_CJC a_AT0 p-pseudocaterpillar_AJ0 gene_NN1 tree_NN1 G_ZZ0 ._SENT 
Section_NN1 2_CRD introduces_VVZ definitions_NN2 and_CJC notation_NN1 ._SENT Section_NN1 3_CRD gives_VVZ an_AT0 example_NN1 that_CJT mo-_NN1 tivates_VVZ the_AT0 general_AJ0 calculation_NN1 ._SENT In_PRP Section_NN1 4_CRD ,_PUN we_PNP enumerate_VVB coalescent_AJ0 histories_NN2 in_PRP the_AT0 general_AJ0 case_NN1 ._SENT Section_NN1 5_CRD gives_VVZ special_AJ0 cases_NN2 with_PRP specified_AJ0 values_NN2 of_PRF p._NN0 Finally_AV0 ,_PUN in_PRP Section_NN1 6_CRD ,_PUN for_PRP a_AT0 specified_AJ0 caterpillar_NN1 species_NN0 tree_NN1 S_ZZ0 of_PRF fixed_AJ0 size_NN1 n_ZZ0 ,_PUN considering_VVG all_DT0 possible_AJ0 values_NN2 of_PRF p_ZZ0 ,_PUN we_PNP obtain_VVB the_AT0 maximal_AJ0 number_NN1 of_PRF coalescent_AJ0 histories_NN2 across_PRP all_DT0 non-matching_AJ0 p-pseudocaterpillar_AJ0 trees_NN2 G_ZZ0 ._SENT Section_NN1 7_CRD discusses_VVZ a_AT0 symmetry_NN1 in_PRP p_ZZ0 for_PRP fixed_AJ0 n_ZZ0 ,_PUN and_CJC we_PNP conclude_VVB with_PRP a_AT0 discussion_NN1 in_PRP Section_NN1 8._CRD The_AT0 computations_NN2 illustrate_VVB how_AVQ the_AT0 monotonic_AJ0 path_NN1 approach_NN1 of_PRF Himwich_NP0 &_NP0 Rosenberg_NP0 in_PRP the_AT0 case_NN1 of_PRF caterpillar_NN1 species_NN0 trees_NN2 can_VM0 be_VBI extended_VVN to_TO0 enumerate_VVI coalescent_AJ0 histories_NN2 in_PRP more_DT0 cases_NN2 beyond_PRP that_DT0 of_PRF caterpillar_NN1 gene_NN1 trees_NN2 ._SENT 
2._CRD Preliminaries_NN2 
We_PNP formally_AV0 define_VVB coalescent_AJ0 histories_NN2 and_CJC p-pseudocaterpillars_NN2 in_PRP Sections_NN2 2.1_CRD and_CJC 2.2_CRD ,_PUN and_CJC we_PNP introduce_VVB results_NN2 concerning_PRP the_AT0 Catalan_AJ0 numbers_NN2 in_PRP Section_NN1 2.3_CRD ._SENT In_PRP Section_NN1 2.4_CRD ,_PUN we_PNP describe_VVB the_AT0 use_NN1 of_PRF monotonic_AJ0 paths_NN2 to_TO0 enumerate_VVI coalescent_AJ0 histories_NN2 for_PRP caterpillar_NN1 tree_NN1 pairs_NN2 ._SENT 
2.1_CRD ._SENT Coalescent_AJ0 histories_NN2 
The_AT0 definitions_NN2 in_PRP this_DT0 article_NN1 closely_AV0 follow_VVB Himwich_NP0 &_NP0 Rosenberg_NP0 ._SENT Henceforth_AV0 ,_PUN we_PNP treat_VVB all_DT0 "_PUQ trees_NN2 "_PUQ as_PRP binary_AJ0 and_CJC rooted_AJ0 ;_PUN trees_NN2 are_VBB leaf-labeled_AJ0 ,_PUN but_CJC the_AT0 labels_NN2 are_VBB sometimes_AV0 omitted_VVN for_PRP convenience_NN1 ._SENT The_AT0 set_NN1 of_PRF vertices_NN2 or_CJC nodes_NN2 of_PRF a_AT0 tree_NN1 can_VM0 be_VBI divided_VVN into_PRP leaf_NN1 nodes_NN2 and_CJC non-leaf_AJ0 internal_AJ0 nodes_NN2 ._SENT For_PRP tree_NN1 G_ZZ0 ,_PUN we_PNP say_VVB that_CJT a_AT0 node_NN1 v1_NN1 is_VBZ descended_VVN from_PRP a_AT0 node_NN1 v2_NN1 if_CJS the_AT0 path_NN1 from_PRP v1_CRD to_PRP the_AT0 root_NN1 of_PRF G_ZZ0 travels_VVZ through_PRP v2_CRD ;_PUN v2_CRD is_VBZ then_AV0 ancestral_AJ0 to_PRP v1_CRD ._SENT Ancestor_NN1 –_PUN descendant_NN1 relationships_NN2 also_AV0 apply_VVB to_PRP edge_NN1 –_PUN edge_NN1 pairs_NN2 and_CJC edge_NN1 –_PUN node_NN1 pairs_NN2 ._SENT A_AT0 node_NN1 or_CJC edge_NN1 is_VBZ trivially_AV0 descended_VVN from_PRP and_CJC ancestral_AJ0 to_PRP itself_PNX ._SENT Each_DT0 internal_AJ0 node_NN1 ,_PUN including_PRP the_AT0 root_NN1 ,_PUN possesses_VVZ an_AT0 associated_AJ0 internal_AJ0 edge_NN1 immediately_AV0 ancestral_AJ0 to_PRP it_PNP ._SENT Thus_AV0 ,_PUN viewed_VVN forward_AV0 in_PRP time_NN1 ,_PUN the_AT0 root_NN1 —_PUN like_PRP other_AJ0 internal_AJ0 nodes_NN2 —_PUN has_VHZ in-degree_AJ0 1_CRD and_CJC out-degree_AJ0 2._CRD 
We_PNP consider_VVB pairs_NN2 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR in_PRP which_DTQ G_ZZ0 represents_VVZ a_AT0 gene_NN1 tree_NN1 ,_PUN describing_VVG the_AT0 descent_NN1 of_PRF a_AT0 set_NN1 of_PRF genealogical_AJ0 lineages_NN2 ,_PUN and_CJC S_ZZ0 represents_VVZ a_AT0 species_NN0 tree_NN1 ,_PUN describing_VVG the_AT0 descent_NN1 of_PRF a_AT0 set_NN1 of_PRF species_NN0 ._SENT G_ZZ0 and_CJC S_ZZ0 are_VBB assumed_VVN to_TO0 have_VHI the_AT0 same_DT0 number_NN1 of_PRF leaves_NN2 ,_PUN n_ZZ0 ._SENT We_PNP assume_VVB that_CJT the_AT0 leaf_NN1 set_NN1 of_PRF G_ZZ0 and_CJC the_AT0 leaf_NN1 set_NN1 of_PRF S_ZZ0 are_VBB labeled_VVN by_PRP the_AT0 same_DT0 label_NN1 set_NN1 X_ZZ0 ,_PUN and_CJC that_CJT each_DT0 label_NN1 in_PRP X_ZZ0 is_VBZ assigned_VVN to_PRP exactly_AV0 one_CRD leaf_NN1 of_PRF G_ZZ0 and_CJC to_PRP exactly_AV0 one_CRD leaf_NN1 of_PRF S._NP0 This_DT0 assumption_NN1 corresponds_VVZ to_PRP an_AT0 assumption_NN1 that_CJT exactly_AV0 one_CRD gene_NN1 lineage_NN1 is_VBZ sampled_VVN in_PRP each_DT0 of_PRF the_AT0 n_ZZ0 species_NN0 ._SENT 
For_PRP the_AT0 pair_NN0 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR ,_PUN we_PNP can_VM0 formally_AV0 define_VVI the_AT0 functions_NN2 known_VVN as_PRP coalescent_AJ0 histories_NN2 ._SENT 
Definition_NN1 1._CRD Consider_VVB a_AT0 pair_NN0 of_PRF trees_NN2 (_PUL G_ZZ0 ,_PUN S_ZZ0 )_PUR that_CJT are_VBB binary_AJ0 ,_PUN rooted_AJ0 ,_PUN and_CJC leaf-labeled_AJ0 ,_PUN with_PRP the_AT0 labels_NN2 in_PRP bijective_AJ0 correspondence_NN1 ._SENT A_AT0 coalescent_AJ0 history_NN1 is_VBZ a_AT0 function_NN1 α_NN1 from_PRP the_AT0 set_NN1 of_PRF internal_AJ0 nodes_NN2 of_PRF G_ZZ0 to_PRP the_AT0 set_NN1 of_PRF internal_AJ0 edges_NN2 of_PRF S_NP0 ,_PUN satisfying_VVG two_CRD conditions_NN2 :_PUN 
(_PUL a_AT0 )_PUR For_PRP each_DT0 internal_AJ0 node_NN1 v_ZZ0 in_PRP G_ZZ0 ,_PUN all_DT0 labels_NN2 for_PRP leaves_NN2 descended_VVN from_PRP v_ZZ0 in_PRP G_ZZ0 label_NN1 leaves_NN2 descended_VVN from_PRP edge_NN1 α_NN1 (_PUL v_ZZ0 )_PUR in_PRP S._NP0 
(_PUL b_ZZ0 )_PUR For_PRP each_DT0 pair_NN0 of_PRF internal_AJ0 nodes_NN2 v1_CRD and_CJC v2_CRD in_PRP G_ZZ0 ,_PUN if_CJS v2_NN1 is_VBZ descended_VVN from_PRP v1_CRD ,_PUN then_AV0 α_NP0 (_PUL v2_CRD )_PUR is_VBZ descended_VVN from_PRP α_NP0 (_PUL v1_CRD )_PUR in_PRP S._NP0 
In_PRP this_DT0 definition_NN1 ,_PUN nodes_NN2 of_PRF G_ZZ0 represent_VVB coalescent_AJ0 events_NN2 for_PRP the_AT0 gene_NN1 lineages_NN2 ,_PUN and_CJC edges_NN2 of_PRF S_ZZ0 represent_VVB species_NN0 tree_NN1 edges_NN2 along_PRP which_DTQ the_AT0 gene_NN1 lineages_NN2 evolve_VVB ._SENT A_AT0 coalescent_AJ0 history_NN1 reflects_VVZ the_AT0 biological_AJ0 process_NN1 of_PRF coalescence_NN1 ,_PUN in_PRP which_DTQ descendants_NN2 cannot_NP0 coalesce_VVB farther_AV0 back_AVP in_PRP time_NN1 than_CJS their_DPS ancestors_NN2 ._SENT Ancestor_NN1 –_PUN descendant_NN1 relations_NN2 are_VBB preserved_VVN under_PRP the_AT0 mapping_NN1 α_NN1 ._SENT 
Informally_AV0 ,_PUN considering_VVG the_AT0 biological_AJ0 process_NN1 of_PRF coalescence_NN1 ,_PUN we_PNP often_AV0 refer_VVB to_PRP internal_AJ0 nodes_NN2 as_PRP coalescences_NN2 ._SENT We_PNP refer_VVB to_PRP gene_NN1 tree_NN1 coalescences_NN2 "_PUQ happening_VVG ,_PUN "_PUQ "_PUQ occurring_VVG ,_PUN "_PUQ or_CJC "_PUQ taking_VVG place_NN1 "_PUQ on_PRP species_NN0 tree_NN1 edges_NN2 ._SENT For_PRP example_NN1 ,_PUN a_AT0 gene_NN1 tree_NN1 coalescence_NN1 v_ZZ0 in_PRP G_ZZ0 "_PUQ can_VM0 occur_VVI "_PUQ on_PRP a_AT0 species_NN0 tree_NN1 edge_NN1 w_ZZ0 in_PRP S_ZZ0 if_CJS and_CJC only_AV0 if_CJS there_EX0 exists_VVZ a_AT0 coalescent_AJ0 history_NN1 α_NN1 with_PRP α_NP0 (_PUL v_ZZ0 )_PUR =_NP0 w_ZZ0 ._SENT 
2.2_CRD ._SENT Caterpillars_NN2 and_CJC p-pseudocaterpillars_NN2 
As_CJS our_DPS goal_NN1 is_VBZ to_TO0 enumerate_VVI the_AT0 coalescent_AJ0 histories_NN2 in_PRP the_AT0 case_NN1 that_CJT G_ZZ0 has_VHZ a_AT0 p-_AJ0 pseudocaterpillar_AJ0 topology_NN1 and_CJC S_ZZ0 has_VHZ a_AT0 caterpillar_NN1 topology_NN1 ,_PUN we_PNP define_VVB caterpillar_NN1 and_CJC p-pseudocaterpillar_AJ0 shapes_NN2 for_PRP binary_AJ0 ,_PUN rooted_AJ0 tree_NN1 topologies_NN2 ._SENT 
Definition_NN1 2._CRD A_AT0 caterpillar_NN1 tree_NN1 is_VBZ a_AT0 binary_AJ0 ,_PUN rooted_AJ0 tree_NN1 that_CJT has_VHZ an_AT0 internal_AJ0 node_NN1 that_DT0 is_VBZ descended_VVN from_PRP all_DT0 other_AJ0 internal_AJ0 nodes_NN2 ._SENT 
In_PRP a_AT0 caterpillar_NN1 tree_NN1 ,_PUN each_DT0 internal_AJ0 node_NN1 has_VHZ at_PRP least_AV0 one_CRD leaf_NN1 as_PRP an_AT0 immediate_AJ0 descen-_NN1 dant_NN1 (_PUL Fig._NN1 1A_CRD )_PUR ._SENT Equivalently_AV0 ,_PUN a_AT0 caterpillar_NN1 tree_NN1 is_VBZ a_AT0 tree_NN1 that_CJT has_VHZ only_AV0 one_CRD cherry_NN1 node_NN1 :_PUN an_AT0 internal_AJ0 node_NN1 with_PRP exactly_AV0 two_CRD descendant_NN1 leaves_NN2 ._SENT Rosenberg_NP0 defined_VVD binary_AJ0 ,_PUN rooted_AJ0 pseudocaterpillar_AJ0 trees_NN2 with_PRP n_ZZ0 ≥_NN1 4_CRD leaves_NN2 as_PRP trees_NN2 in_PRP which_DTQ all_DT0 internal_AJ0 nodes_NN2 except_CJS one_PNI have_VHB at_PRP least_AV0 one_CRD immediate_AJ0 leaf_NN1 descendant_NN1 ._SENT The_AT0 node_NN1 that_CJT provides_VVZ the_AT0 exception_NN1 has_VHZ two_CRD cherry_NN1 nodes_NN2 as_PRP its_DPS immediate_AJ0 descendants_NN2 ._SENT We_PNP generalize_VVB the_AT0 earlier_AJC definition_NN1 of_PRF pseudocaterpillar_AJ0 trees_NN2 to_TO0 consider_VVI generalized_AJ0 pseudocaterpillar_AJ0 trees_NN2 ._SENT To_TO0 define_VVI this_DT0 concept_NN1 ,_PUN we_PNP denote_VVB by_PRP vL_NN1 and_CJC vR_NN1 the_AT0 left_AJ0 and_CJC right_AJ0 descendant_NN1 nodes_NN2 of_PRF an_AT0 internal_AJ0 node_NN1 v._NN0 
Definition_NN1 3._CRD A_AT0 generalized_AJ0 pseudocaterpillar_AJ0 tree_NN1 is_VBZ a_AT0 binary_AJ0 ,_PUN rooted_AJ0 tree_NN1 that_CJT has_VHZ at_PRP least_AV0 four_CRD leaves_NN2 and_CJC that_DT0 satisfies_VVZ two_CRD conditions_NN2 ._SENT (_PUL i_ZZ0 )_PUR The_AT0 tree_NN1 possesses_VVZ exactly_AV0 two_CRD cherry_NN1 nodes_NN2 ._SENT (_PUL ii_CRD )_PUR For_PRP each_DT0 internal_AJ0 node_NN1 v_ZZ0 ,_PUN at_PRP least_AV0 one_CRD of_PRF vL_NN1 ,_PUN vR_NN1 has_VHZ no_AV0 more_AV0 than_CJS two_CRD descendant_NN1 leaves_NN2 ._SENT 
In_PRP other_AJ0 words_NN2 ,_PUN a_AT0 generalized_AJ0 pseudocaterpillar_AJ0 tree_NN1 is_VBZ formed_VVN from_PRP a_AT0 caterpillar_NN1 tree_NN1 ,_PUN replacing_VVG one_CRD of_PRF the_AT0 leaves_NN2 not_XX0 descended_VVN from_PRP the_AT0 unique_AJ0 cherry_NN1 node_NN1 by_PRP a_AT0 second_ORD cherry_NN1 node_NN1 (_PUL Fig._NN1 1B_CRD )_PUR ._SENT 
A_AT0 generalized_AJ0 pseudocaterpillar_NN1 can_VM0 be_VBI described_VVN by_PRP two_CRD numbers_NN2 :_PUN the_AT0 total_AJ0 number_NN1 of_PRF leaves_NN2 n_ZZ0 and_CJC the_AT0 position_NN1 p_ZZ0 of_PRF the_AT0 "_PUQ second_ORD "_PUQ cherry_NN1 ._SENT To_TO0 precisely_AV0 identify_VVI p_ZZ0 for_PRP a_AT0 generalized_AJ0 pseudocaterpillar_AJ0 tree_NN1 ,_PUN we_PNP label_VVB the_AT0 leaves_NN2 by_PRP natural_AJ0 numbers_NN2 starting_VVG from_PRP left_NN1 to_PRP right_NN1 ,_PUN placing_VVG the_AT0 "_PUQ first_ORD "_PUQ cherry_NN1 —_PUN the_AT0 one_CRD present_NN1 in_PRP the_AT0 caterpillar_NN1 from_PRP which_DTQ the_AT0 generalized_AJ0 pseudocaterpillar_NN1 has_VHZ been_VBN generated_VVN —_PUN on_PRP the_AT0 left_NN1 ._SENT We_PNP define_VVB the_AT0 position_NN1 of_PRF the_AT0 second_ORD cherry_NN1 as_PRP the_AT0 number_NN1 corresponding_VVG to_PRP its_DPS second_ORD leaf_NN1 from_PRP the_AT0 left_NN1 (_PUL Fig._NN1 2A_NN1 )_PUR ._SENT A_AT0 generalized_AJ0 pseudocaterpillar_AJ0 tree_NN1 with_PRP a_AT0 second_ORD cherry_NN1 in_PRP position_NN1 p_ZZ0 ,_PUN 4_CRD ≤_NP0 p_ZZ0 ≤_NN1 n_ZZ0 ,_PUN is_VBZ termed_VVN a_AT0 p-pseudocaterpillar_AJ0 tree_NN1 ._SENT The_AT0 pseudocaterpillar_AJ0 trees_NN2 in_PRP the_AT0 sense_NN1 of_PRF Rosenberg_NP0 are_VBB 4-pseudocaterpillars_NN2 ._SENT 
Note_VVB that_CJT for_PRP convenience_NN1 ,_PUN our_DPS description_NN1 of_PRF the_AT0 value_NN1 of_PRF p_ZZ0 in_PRP a_AT0 p-pseudocaterpillar_AJ0 tree_NN1 relies_VVZ on_PRP a_AT0 canonical_AJ0 orientation_NN1 of_PRF the_AT0 tree_NN1 ._SENT This_DT0 value_NN1 of_PRF p_ZZ0 can_VM0 also_AV0 be_VBI identified_VVN as_PRP the_AT0 number_NN1 of_PRF leaves_NN2 in_PRP the_AT0 smallest_AJS subtree_NN1 that_CJT contains_VVZ both_DT0 cherries_NN2 of_PRF the_AT0 tree_NN1 ._SENT 
Our_DPS interest_NN1 is_VBZ in_PRP the_AT0 case_NN1 in_PRP which_DTQ the_AT0 gene_NN1 tree_NN1 has_VHZ a_AT0 p-pseudocaterpillar_AJ0 topology_NN1 for_PRP some_DT0 p_ZZ0 ,_PUN and_CJC the_AT0 species_NN0 tree_NN1 has_VHZ a_AT0 caterpillar_NN1 topology_NN1 ._SENT A_AT0 species_NN0 tree_NN1 with_PRP n_ZZ0 leaves_NN2 has_VHZ n_ZZ0 −_NN1 1_CRD edges_NN2 on_PRP which_DTQ gene_NN1 tree_NN1 coalescences_NN2 can_VM0 happen_VVI ;_PUN we_PNP also_AV0 label_VVB these_DT0 edges_NN2 with_PRP natural_AJ0 numbers_NN2 ,_PUN following_VVG the_AT0 order_NN1 from_PRP Degnan_NP0 &_NP0 Salter_NP0 (_PUL Fig._NN1 2B_NN1 )_PUR ._SENT 
