Enumeration of k-plane trees and forests

Abstract

A k-plane tree is an ordered tree in which the vertices are labelled by integers {1, 2, . . . , k} and satisfies the condition i + j ⩽ k + 1 where i and j are adjacent vertices in the tree. These trees are known to be counted by Fuss-Catalan numbers. In this paper, we use generating functions and decomposition of trees to enumerate these trees according to degree of the root, label of the first child of the root and number of forests of k-plane trees. The results of this paper generalize known results for 2-plane trees and plane trees.