A bijection between phylogenetic trees and plane oriented recursive trees

Article, Preprint English OPEN
Prodinger, Helmut; (2017)
  • Publisher: EUT Edizioni Università di Trieste
  • Related identifiers: doi: 10.13137/2464-8728/22432
  • Subject: bijection | Phylogenetic tree | Mathematics - Combinatorics | 05A10 | plane oriented recursive tree | trapezoidal word | 05A19
    arxiv: Computer Science::Computational Geometry

Phylogenetic trees are binary non-plane trees with labelled leaves, and plane oriented recursive trees are planar trees with an in- creasing labelling. Both families are enumerated by double factorials. A bijection is constructed, using the respective represent... 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

  • Metrics
    No metrics available
Share - Bookmark