Generalization of a formula for marked plane trees

Abstract

Deutsch, Munarin and Rinaldi derived a formula for counting marked plane trees while investigating the enumeration of skew Dyck paths. The formula involves the Catalan numbers, which count plane trees among other classical combinatorial structures. In this paper, we generalize their result by enumerating families of noncrossing trees and recently introduced -dimensional plane trees in which certain edges are marked. The resulting formulas are shown to also count: noncrossing trees that allow multi-edges, plane trees in which each internal vertex has outdegree at most 3 and some edges may be marked, and ternary trees in which certain edge type are coloured using two colours. These generalizations provide new combinatorial interpretations and extend the scope of the original enumeration.