Enumeration of skew 2-Dyck paths, non-decreasing 2-plane trees, non-decreasing 2-noncrossing trees and related combinatorial structures

Abstract

Graphs, lattice paths and trees have a widespread application in various fields such as Biology, Computer Science and Physics. While the study of these structures has gained significant attention, several gaps in understanding specific variants re- main, limiting the ability to fully leverage their potential. The main goal of this study was to enumerate Dyck paths, plane trees and noncrossing trees in addi- tion to characterizing their properties. The specific objectives of this study were to: Derive enumeration formulas for skew 2-Dyck paths, Evaluate the structural properties of non-decreasing 2-plane trees by analyzing their number of vertices, root degree and label of eldest child, Examine and assess the combinatorial be- havior of weakly labelled k-plane trees through occurrences of vertices of certain labels, root degree, label of eldest child, number of leaves, forests and outdegree sequence, Synthesize counting methods for non-decreasing 2-noncrossing trees and non-decreasing 2-noncrossing increasing trees based on their number of vertices, root degree, forests and label of leftmost child of the root and Create bijections between plane Husimi graphs and various combinatorial structures. The generating functions of skew 2-Dyck paths were obtained by path decomposition followed by application of Lagrange inversion formula and various identities. Symbolic method was applied to derive generating functions for non-decreasing 2-plane trees. For non-decreasing 2-noncrossing trees and their increasing counterparts, the study utilized tree butter- fly decomposition method, symbolic method and the Lagrange-Burmann theorem. Weakly labelled k-plane trees were analyzed by symbolic method and bijections between sets were established through sequential injective and surjective mappings. Categorized by length, skew 2-Dyck paths were enumerated by generalized Narayana numbers. Non-decreasing 2-plane and 2-noncrossing trees with roots labeled 1 or 2 corresponded to and extend large and little Schröder numbers, respectively. A bijection between weakly labelled k-plane trees, enumerated by vertex count, and k-ary Husimi graphs was then constructed. Notably, many of the studied structures were found to be enumerated by Little and Large Schröder paths and their exten- sions. These findings established connections between the examined structures and various combinatorial constructs of similar cardinality, addressing Stanley’s open question on interpretations of structures enumerated by little and large Schröder numbers through bijections. This study expanded combinatorial knowledge, with potential applications in various fields, including genealogy through the introduction of non-decreasing sibling labels in plane and noncrossing trees. Further research is thus recommended on the enumeration of skew k-Dyck paths and non-decreasing k-noncrossing trees where k ≥ 2.