On 2-noncrossing increasing trees

Author(s): Isaac Owino Okoth1
1Department of Pure and Applied Mathematics, Maseno University, Maseno, Kenya.
Copyright © Isaac Owino Okoth. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A \(2\)-noncrossing tree is a rooted tree drawn in the plane with its vertices (colored black or white) on the boundary of a circle such that the edges are line segments that do not intersect inside the circle and there is no black-black ascent in any path from the root. A rooted tree is said to be increasing if the labels of the vertices are increasing as one moves away from the root. In this paper, we use generating functions and bijections to enumerate \(2\)-noncrossing increasing trees by the number of blacks vertices and by root degree. Bijections with noncrossing trees, ternary trees, 2-plane trees, certain Dyck paths, and certain restricted lattice paths are established.

Keywords: 2-noncrossing tree; increasing tree; 2-plane tree; Dyck path; lattice path