Locally oriented noncrossing trees

Abstract

We de ne an orientation on the edges of a noncrossing tree induced by the labels: for a noncrossing tree (i.e., the edges do not cross) with vertices 1; 2; : : : ; n arranged on a circle in this order, all edges are oriented towards the vertex whose label is higher. The main purpose of this paper is to study the distribution of noncrossing trees with respect to the indegree and outdegree sequence determined by this orientation. In particular, an explicit formula for the number of noncrossing trees with given indegree and outdegree sequence is proved and several corollaries are deduced from it. Sources (vertices of indegree 0) and sinks (vertices of outdegree 0) play a special role in this context. In particular, it turns out that noncrossing trees with a given number of sources and sinks correspond bijectively to ternary trees with a given number of middle- and right-edges, and an explicit bijection is provided for this fact. Finally, the in- and outdegree distribution of a single vertex is considered and explicit counting formulas are provided again.