publication . Article . Other literature type . Preprint . 2017

A bijection between phylogenetic trees and plane oriented recursive trees

Prodinger, Helmut;
Open Access
  • Published: 18 Sep 2017
  • Country: Italy
Abstract
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 representations as 2- partitions and trapezoidal words.
Persistent Identifiers
Subjects
arXiv: Computer Science::Computational Geometry
free text keywords: Phylogenetic tree, plane oriented recursive tree, trapezoidal word, bijection, Mathematics - Combinatorics, 05A19, 05A10
Related Organizations

[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. [OpenAIRE]

[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. [OpenAIRE]

[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

Any information missing or wrong?Report an Issue