Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy

Abstract

We develop a unified framework for the exact enumeration and asymptotic analysis of the three most studied classes of phylogenetic networks: tree-child (TC), reticulation-visible (RV) and orchard networks, whose cardinalities satisfy the strict ordering $|{\mathrm{TC}}_{\ell ,k}|<|{\mathrm{RV}}_{\ell ,k}|<|{\mathrm{Orch}}_{\ell ,k}|$ for reticulation number $k\ge 2$ (with $\mathrm{TC}⊊\mathrm{RV}$ and $\mathrm{TC}⊊\mathrm{Orch}$, while $\mathrm{RV}$ and $\mathrm{Orch}$ are incomparable as sets). Using the Chang--Fuchs structural theorem, we derive a two-level master functional equation for the RV bivariate generating function and obtain exact closed-form identities for the differences ${\Delta }_k(\ell ):=|R{V}_{\ell ,k}|-|T{C}_{\ell ,k}|$ for $k=2,3$, with the asymptotic universality ${\Delta }_k(\ell )/|T{C}_{\ell ,k}|\sim k!/\ell$. For orchard networks, we prove a \emph{universal hypergeometric law} that resolves the exact enumeration problem for all $\ell$: the column generating function $F_{\ell }(v)$ is rational with denominator $D_{\ell }(v)={\prod }_{j=2}^{\ell }{X}_j(v)$, where \[ X_\ell(v) = \sum_{k=0}^{\lfloor\ell/2\rfloor}(-1)^k\, \frac{\ell!}{(\ell-2k)!\,k!}\,v^k \] is the matching polynomial of the complete graph $K_{\ell }$ and a rescaled Jacobi polynomial. This immediately resolves the intractable $\ell =9$ case: $D_9$ has degree 20, dominant growth rate $\approx 40.73$, and all spectral roots are positive real. A complete enumeration table is provided extending the published data of Cardona, Ribas and Pons.

Extended version with corrected references