On symmetries in phylogenetic trees

Éric Fusy¹

¹LIX, École Polytechnique 91220 Palaiseau cedex

The electronic journal of combinatorics, Tome 23 (2016) no. 3

Résumé

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.

Détail

DOI : 10.37236/5994

Classification : 05C05
Mots-clés : phylogenetic trees, bijection, random generation, tanglegrams