Bijections for classes of labelled trees

Abstract

Trees are acyclic connected graphs. Plane trees, d-ary trees, binary trees, non crossing trees and their generalizations, which are families of trees, have been enumerated by many authors using various statistics. These trees are known to be enumerated by Catalan or Catalan-like formulas (Fuss-Catalan numbers). One of the most common approaches to the enumeration of these trees is by means of generating functions. Another method that can be used to enumerate them is by constructing bijections between sets of the same cardinality. The bijective method is preferred to other methods by many combinatorialists. So, in this paper, we construct bijections relating k-plane trees, k-noncrossing increasing trees, k-noncrossing trees, k-binary trees and weakly labelled k-trees.