Bijections of k-plane trees

Abstract

A k-plane tree is a tree drawn in the plane such that the vertices are labeled by integers in the set {1, 2, . . . , k}, the children of all vertices are ordered, and if (i, j) is an edge in the tree, where i and j are labels of adjacent vertices in the tree, then i + j ≤ k + 1. In this paper, we construct bijections between these trees and the sets of k-noncrossing increasing trees, locally oriented (k − 1)-noncrossing trees, Dyck paths, and some restricted lattice paths.