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\ge 1$ leaves, fixed (for the relabelling action) by a given permutation $\sigma \in {\mathfrak{S}}_n$. Denoting by $\lambda ⊢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, which yields a simplification of the random sampler for tangled chains.

6 pages