On symmetries in phylogenetic trees (Q311529)

Summary: \textit{S. Billey} et al. [``On the enumeration of tanglegrams and tangled chains'', Preprint, \url{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\geqslant 1\) leaves, fixed (for the relabelling action) by a given permutation \(\sigma\in\mathfrak{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.