| dc.description.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. | en_US |
