Seminar: Marked Noncrossing Trees
Speaker: Nyariaro Albert Oloo, Department of Mathematics, Moi University, Kenya.
Abstract: We introduce marked noncrossing trees, a new class of noncrossing trees whose (l, r)-representation is a rooted plane tree in which, for each internal vertex, the edge to its rightmost child in a wing may be marked if and only if that child is not a leaf. This construction extends the marking rule of Deutsch, Munarini and Rinaldi (2010) to the setting of noncrossing trees. Using generating functions and the symbolic method, we derive a closed-form formula for the number of marked noncrossing trees on $n ≥ 2$ vertices, obtaining a previously unrecorded integer sequence: 1, 5, 29, 186, 1277, ... (not found in the OEIS). We further refine this enumeration according to the number of marked edges, root degree, and number of leaves, deriving explicit formulas for each statistic via Lagrange inversion. We also establish a structural correspondence between marked noncrossing trees and two other combinatorial families -- labelled plane trees with maximum outdegree 3, and a class of ternary trees with labelled edges -- showing that all three satisfy the same underlying functional equation, $y = x((1 + y)^3 + y(2 + y))$. These results open avenues for further work, including enumeration by forest components and vertex levels, bijective proofs linking marked noncrossing trees to labelled plane and ternary trees, and extensions to marked d-dimensional plane trees and k-noncrossing trees.
Keywords:Noncrossing trees, Lagrange inversion, labelled plane trees.