A bijection between phylogenetic trees and plane oriented recursive trees

Preprint English OPEN
Prodinger, Helmut;
(2017)
  • Subject: Mathematics - Combinatorics

Phylogenetic trees are binary nonplanar trees with labelled leaves, and plane oriented recursive trees are planar trees with an increasing labelling. Both families are enumerated by double factorials. A bijection is constructed, using the respective representations a 2-... View more
  • References (6)

    [1] M. Bona. On the number of vertices of each rank in phylogenetic trees and their generalizations. Discrete Mathematics and Theoretical Computer Science, 18:7 pages, 2016.

    [2] D. Callan. A combinatorial survey of identities for the double factorial. arXiv:0906.1317v1, 2009.

    [3] H.-K. Hwang. Profiles of random trees: Plane-oriented recursive trees. Random Structures and Algorithms, 30:380-413, 2006.

    [4] J. Riordan. The blossoming of Schröder's fourth problem. Acta. Math., 137:1-16, 1976.

    [5] R. Stanley. Enumerative Combinatorics, Volume 2. Cambridge University Press, 1999.

    (Helmut Prodinger) DEPARTMENT OF MATHEMATICAL SCIENCES, STELLENBOSCH UNIVERSITY, 7602 STELLENBOSCH, SOUTH AFRICA E-mail address: hproding@sun.ac.za

  • Similar Research Results (1)
  • Metrics
Share - Bookmark