A Pairing Rule for Tandem Duplication Trees

William Y. C. Chen, Nancy S.S. Gu, Yi Hu, and Louxin Zhang}
Center for Combinatorics and LPMC,
Nankai University, Tianjin 300071, P.R. China

Abstract

We give a purely combinatorial proof of the fact that the number of rooted tandem duplication trees with n leaves equals twice the number of unrooted duplication trees with n leaves. We find a pairing rule for rooted tandem duplication trees. For each pair of rooted trees, exactly one of them is canonical which corresponds to an unrooted duplication tree in a unique way. The notion of canonical trees is introduced by O. Gascuel, M. Hendy, A. Jean-Marie, and R. McLachlan in their study of the combinatorics of tandem duplication trees.