On Symmetries in Phylogenetic Trees

Abstract

Billey et al. [arXiv:1507.04976] have recently discovered a surprisingly simple formula for the number $a_n(\sigma)$ of leaf-labelled rooted non-embedded binary trees (also known as phylogenetic trees) with $n\geq 1$ leaves, fixed (for the relabelling action) by a given permutation $\sigma\in\frak{S}_n$. Denoting by $\lambda\vdash n$ the integer partition giving the sizes of the cycles of $\sigma$ in non-increasing order, they show by a guessing/checking approach that if $\lambda$ is a binary partition (it is known that $a_n(\sigma)=0$ otherwise), then
$$
a_n(\sigma)=\prod_{i=2}^{\ell(\lambda)}(2(\lambda_i+\cdots+\lambda_{\ell(\lambda)})-1),
$$
and they derive from it a formula and random generation procedure for tanglegrams (and more generally for tangled chains). Our main result is a combinatorial proof of the formula for $a_n(\sigma)$, which yields a simplification of the random sampler for tangled chains.