Seminar: On a variant of \(k\)-plane trees
Speaker: Fidel Ochieng Oduol, PhD student, Moi University, Kenya.
Abstract: A new class of labelled plane trees, called \(k_1\)-plane trees, is introduced by imposing an additional ordering condition on the classical k-plane trees. Specifically, the vertices are labelled by elements of \(\{1, 2, . . . , k\}\) such that the sum of the labels of every pair of adjacent vertices does not exceed k + 1, while all children labelled 1 are required to appear to the left of all other children of the same parent. This family extends the previously studied non-decreasing 2-plane trees. Using generating function techniques, explicit enumeration formulas are derived with respect to the number of vertices, the root label and degree, the labels of the root’s children, and labelled forests with a prescribed number of components. The resulting formulas recover the Catalan, Little Schröder, Large Schröder, and Fuss–Catalan numbers as special cases, thereby unifying several classical enumerative results for labelled plane trees.
Keywords:labelled plane trees, non-decreasing 2-plane trees, generating function