On non-decreasing 2-plane trees

Abstract

In this paper, we have introduced the set of non-decreasing 2-plane trees. These are plane trees whose vertices receive labels from the set {1, 2} such that the sum of labels of adjacent vertices is at most 3 and that the labels of siblings are weakly increasing from left to right. We have obtained the formula for the number of these trees with a given number of vertices and label of the root. Further, we have obtained the number of these trees given root degrees and label of the eldest child of the root. We have also constructed bijections between the set of non-decreasing 2-plane trees with roots labelled 2 and the sets of little Schröder paths, plane trees in which leaves receive two labels, restricted lattice paths and increasing tableaux. For non-decreasing 2-plane trees with roots labelled 1, we have obtained bijections between the set of these trees and the sets of large Schröder paths and row-increasing tableaux.