Counting formulas and bijections of nondecreasing 2-noncrossing trees

Abstract

In this paper, we introduce nondecreasing 2-noncrossing trees and enumerate them according to their number of vertices, root degree, and number of forests. We also introduce nondecreasing 2-noncrossing increasing trees and count them by considering their number of vertices, label of the root, label of the leftmost child of the root, root degree, and forests. We observe that the formulas enumerating the newly introduced trees are generalizations of little and large Schroder ¨ numbers. Furthermore, we establish bijections between the sets of nondecreasing 2-noncrossing trees, locally oriented noncrossing trees, labelled complete ternary trees, and 3-Schroder paths.