\documentclass[12pt,a4paper]{article} \usepackage{e-jc} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage[T1]{fontenc} \usepackage{tkz-graph} \usepackage{color} \usepackage{float} \usetikzlibrary{decorations.pathreplacing} \theoremstyle{plain} \newtheorem{theorem}{{Theorem}}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}{Remark} \numberwithin{equation}{section} \usepackage{hyperref} \hypersetup{colorlinks,citecolor=red,linkcolor=blue,urlcolor=blue} \title{Locally oriented noncrossing trees} \author{ Isaac Owino Okoth\\ \small Department of Mathematical Sciences \\[-0.8ex] \small Stellenbosch University \\[-0.8ex] \small Private Bag X1, Matieland 7602, South Africa \\[-0.8ex] \small \texttt{owino@aims.ac.za}\\ \and Stephan Wagner\\ \small Department of Mathematical Sciences \\[-0.8ex] \small Stellenbosch University \\[-0.8ex] \small Private Bag X1, Matieland 7602, South Africa \\[-0.8ex] \small \texttt{swagner@sun.ac.za} } \date{\dateline{4 April 2015}{}{} \\ \small Mathematics Subject Classifications: 05A15; 05A19, 05C05, 05C30} \begin{document} \maketitle \begin{abstract} We define 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,\ldots,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. \end{abstract} \section{Introduction} A classical refinement of Cayley's formula for the number of labelled trees with $n$ vertices is obtained by taking the vertex degrees into account as well. One version can be described by considering an orientation of the edges: fix a vertex (e.g., vertex $1$) as the root, and assume that all edges are oriented to point away from the root. This gives rise to an \emph{outdegree sequence} $0^{e_0}1^{e_1}2^{e_2} \cdots$, where $e_i$ is the number of vertices of outdegree $i$ (of course, every vertex, with the exception of the root, has indegree $1$). The number of rooted labelled trees on $n$ vertices with fixed root label and outdegree sequence $\lambda = 0^{e_0}1^{e_1}2^{e_2} \cdots$ is given by $$\frac{(n-1)!^2}{e_0!(0!)^{e_0} e_1!(1!)^{e_1}e_2!(2!)^{e_2} \cdots},$$ see \cite[Corollary 5.3.5]{Stanley1999enumerative}. Recently, Du and Yin \cite{Du2010counting} as well as Shin and Zeng \cite{Shin2011bijective} by another method proved that this expression also counts the number of labelled trees on $n$ vertices whose outdegree sequence is $\lambda = 0^{e_0}1^{e_1}2^{e_2} \cdots$ with respect to a \emph{local orientation} of the vertices (as opposed to the \emph{global orientation} away from the root), where every edge is oriented towards the end vertex whose label is higher. By symmetry, it also counts trees with given indegree sequence with respect to this local orientation. This formula was originally conjectured by Cotterill \cite{Cotterill2011geometry} in the context of algebraic geometry, and an extension to rooted forests was proven in \cite{Wagner2011labeled}. The aim of this paper is to obtain an analogous counting formula for \emph{noncrossing trees}, which also form a very classical combinatorial class. In fact, we will be able to obtain even more, namely a surprisingly simple formula that gives the number of noncrossing trees where both indegree and outdegree sequence are prescribed at the same time. There does not seem to be a simple counting formula of this kind for ordinary labelled trees, see \cite{Okoth2015counting}. \begin{figure}[htp!] \begin{center} \begin{tikzpicture}[scale=1.2,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.2] (1) at (0,3) [label=above:\small $1$] {1}; \node[fill,circle,scale=0.2] (2) at (3,0) [label=right:\small $4$] {2}; \node[fill,circle,scale=0.2] (3) at (-3,0) [label=left:\small $10$] {3}; \node[fill,circle,scale=0.2] (4) at (0,-3) [label=below:\small $7$] {4}; \node[fill,circle,scale=0.2] (5) at (2.6,1.5) [label=right:\small $3$] {5}; \node[fill,circle,scale=0.2] (6) at (1.6,2.5) [label=above:\small $2$] {5}; \node[fill,circle,scale=0.2] (7) at (2.6,-1.5) [label=right:\small $5$] {5}; \node[fill,circle,scale=0.2] (8) at (1.6,-2.5) [label=below:\small $6$] {5}; \node[fill,circle,scale=0.2] (9) at (-2.6,-1.5) [label=left:\small $9$] {5}; \node[fill,circle,scale=0.2] (10) at (-1.6,-2.5) [label=below:\small $8$] {5}; \node[fill,circle,scale=0.2](11) at (-2.6,1.5) [label=left:\small $11$] {5}; \node[fill,circle,scale=0.2] (12) at (-1.6,2.5) [label=above:\small $12$] {5}; \draw (0,0) circle (3cm); \path (1) edge[->] (8) (1) edge[->] (2) (8) edge[->] (4) (1) edge[->] (5) (6) edge[->] (5) (2) edge[->] (7) (10) edge[->] (11) (11) edge[->] (12) (1) edge[->] (11) (3) edge[->] (11) (10) edge[->] (9); \end{tikzpicture} \end{center} \caption{An example of a noncrossing tree with the orientation induced by its labels.} \label{fig_nc-example} \end{figure} Recall that a noncrossing tree (see Figure~\ref{fig_nc-example} for an example) is a tree that can be drawn in the plane with its vertices on the boundary of a circle (labelled from $1$ to $n$ in clockwise direction around the circle) such that the edges are straight line segments that do not cross. The number of noncrossing trees on $n$ labelled vertices (where $n \geq 2$ throughout this paper) is known to be given by \begin{align}\label{lnc} \dfrac{1}{n-1}{3n-3\choose n-2}, \end{align} see \cite{Deutsch2002statistics, Noy1998enumeration} for details. In \cite{Flajolet1999analytic}, Flajolet and Noy obtained a formula for the number of noncrossing trees on $n$ vertices with a given outdegree sequence with respect to the aforementioned global orientation, where all edges are oriented to point away from the root. They showed that the number of noncrossing trees on $n$ vertices with outdegree sequence $0^{e_0}1^{e_{1}}2^{e_{2}}\cdots$ is given by \begin{align*} \frac{(n-2)!}{e_0!e_1! e_2! \cdots}1^{e_0}2^{e_1}\cdots(n+1)^{e_n}\sum_{i=1}^{n}\frac{i}{i+1}e_i. \end{align*} Several other statistics on noncrossing trees have been considered in the literature, such as degree of a fixed vertex \cite{Noy1998enumeration}, number of end-points or boundary edges \cite{Deutsch2002statistics}, maximum degree \cite{Deutsch2002statistics}, height of vertices \cite{Panholzer2003height}, edge cuts \cite{Panholzer2003non-crossing}, descents \cite{Hough2003descents} or left and right leaves \cite{Pang2013refinement}. Let us now state our main result. We will equip noncrossing trees with the aforementioned local orientation induced by its labels, i.e.~edges are always oriented towards the higher label, as in Figure~\ref{fig_nc-example}. We will use the abbreviation ``lnc-trees'' for locally oriented noncrossing trees throughout the paper. We also remark on this occasion that a valid in- or outdegree sequence $0^{e_0}1^{e_{1}}2^{e_{2}} \cdots$ of a tree of order $n$ always has to satisfy the coherence condition \begin{align}\label{nc-indeg-cond} \sum_{i \geq 0} e_i = n\qquad \text{and}\qquad \sum_{i\geq 1}ie_i=n-1, \end{align} and we will always assume that this condition is satisfied. \begin{theorem}\label{thm:main} The number of lnc-trees of order $n$ with outdegree sequence $0^{e_0}1^{e_{1}}2^{e_{2}}\cdots $ and indegree sequence $ 0^{d_0} 1^{d_{1}}2^{d_{2}}\cdots $ (both satisfying \eqref{nc-indeg-cond}) is equal to \begin{align}\label{ncEq1} (n-1)\cdot\dfrac{(n-e_0-1)!(n-d_0-1)!}{e_1!e_2!\cdots d_1!d_2!\cdots}{n-1\choose e_0+d_0-1}. \end{align} \end{theorem} We will prove this theorem by means of generating functions in the following section and obtain a number of corollaries from it in Section~\ref{sec:cor}. One of these corollaries, regarding vertices of in- or outdegree $0$ (which we call \emph{sources} and \emph{sinks} respectively), yields a formula that also occurs in the enumeration of ternary trees by their edge types, and we will provide a bijection that illustrates this fact. The paper concludes with a discussion of the in- or outdegree of an individual vertex in Section~\ref{sec:single}. \begin{remark}\label{rem:independence} What makes Theorem~\ref{thm:main} quite surprising is the fact that in- and outdegree sequence are almost completely separated from each other in formula~\eqref{ncEq1}. To make this precise, if we consider a random lnc-tree of order $n$ with a given number $d_0$ of sources (vertices of indegree $0$) and a given number $e_0$ of sinks (vertices of outdegree $0$), the in- and outdegree sequence are independent random variables. \end{remark} \section{Proof of the main theorem} We prove Theorem~\ref{thm:main} by means of a generating functions approach. In all our generating functions, $x_i$ marks vertices whose outdegree is $i$, $y_j$ marks vertices whose indegree is $j$, and $z$ marks the total number of vertices. We let $A$ be the generating function for lnc-trees rooted at vertex $1$ such that the root has degree $1$ (we will refer to such trees as ``type A'' trees), and $B$ the corresponding generating function for lnc-trees rooted at vertex $n$ (the highest label), which is again assumed to have degree $1$ (``type B'' trees). In both cases, we do not let the root count towards the total number of vertices (i.e., the exponent of $z$ in the generating functions $A$ and $B$ actually represents the number of non-root vertices), which turns out to be convenient for us. Finally, $T$ will be the generating function for all noncrossing trees. If we consider vertex $1$ as the root, then we have the decomposition of an lnc-tree shown in Figure \ref{Fig_indeg_1} into the root and its branches $R_1,R_2,\ldots,R_r$, which are noncrossing subtrees. \begin{figure}[htp!] \begin{center} \begin{tikzpicture}[scale=0.6,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.4] (1)at (0,3) [label=above:\small $1$] {}; \node[fill,circle,scale=0.4] (5) at (2.6,1.5) [label=below:\small ] {}; \node[fill,circle,scale=0.4] (11) at (-2.6,1.5) [label=below:\small ] {}; \node[fill,circle,scale=0.4] (12) at (-1,1.5) [label=below:\small ] {}; \node[fill,circle,scale=0.1] (2) at (1,1.5) [label=below:\small ] {}; \node (3)[fill,circle,scale=0.1] at (0.5,1.5) [label=below:\small ] {}; \node (8)[fill,circle,scale=0.1] at (1.5,1.5) [label=below:\small ] {}; \node (4) at (-2.7,1) [label=below:\small $R_1$] {}; \node (6) at (-0.5,1) [label=below:\small $R_2$] {}; \node (7) at (3,1) [label=below:\small $R_r$] {}; \path (11) edge[<-] (1) (5) edge[<-] (1) (12)edge[<-] (1) ; \draw (-2.6,1.5)--(-4,-0.5)--(-2,-0.5)--(-2.6,1.5); \draw (-1,1.5)--(-1.5,-0.5)--(0.5,-0.5)--(-1,1.5); \draw (2.6,1.5)--(2,-0.5)--(4,-0.5)--(2.6,1.5); \end{tikzpicture} \end{center} \caption{Decomposition of a noncrossing tree rooted at vertex 1.} \label{Fig_indeg_1} \end{figure} Each of the subtrees $R_j$, together with the edge to the root, can be considered as an lnc-tree whose root has label $1$ and degree $1$, and those trees are counted by the generating function $A$. Therefore, \begin{align}\label{nc_trees12} T=zy_0\sum_{k\geq 1}x_kA^{k}. \end{align} Similarly, if we consider vertex $n$ as the root, then we obtain \begin{align}\label{nc_trees13} T=zx_0\sum_{k\geq 1}y_kB^{k}. \end{align} Moreover, we have \begin{align}\label{nc_trees14} A=z\sum_{k\geq 0}x_kA^{k}\sum_{\ell\geq 0}y_{\ell+1}B^{\ell}. \end{align} This follows from the decomposition of noncrossing trees of type $A$ shown in Figure~\ref{fig:butterfly} (a so-called ``butterfly''): such a tree can be decomposed into the root edge from $1$ to some vertex $v$, the branches with labels greater than $v$, and the branches with labels less than $v$. Trees of type $B$ can be decomposed analogously. \begin{figure}[H] \begin{center} \begin{tikzpicture}[scale=0.6,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.2] (1)at (0,4) [label=above:\small $1$] {}; \node[fill,circle,scale=0.2] (5) at (2.6,3) [label=below:\small ] {}; \node[fill,circle,scale=0.2] (21) at (2.6,2) [label=below:\small ] {}; \node[fill,circle,scale=0.2] (23) at (2.6,0) [label=below:\small labels $ < v$] {}; \node[fill,circle,scale=0.1] (2) at (2.6,1) [label=below:\small ] {}; \node[fill,circle,scale=0.2] (20) at (0,1) [label=below:\small $v$] {}; \node (3)[fill,circle,scale=0.1] at (2.6,1.5) [label=below:\small ] {}; \node (8)[fill,circle,scale=0.1] at (2.6,0.5) [label=below:\small ] {}; \node[fill,circle,scale=0.2] (6) at (-2.6,3) [label=below:\small ] {}; \node[fill,circle,scale=0.2] (11) at (-2.6,2) [label=below:\small ] {}; \node[fill,circle,scale=0.2] (13) at (-2.6,0) [label=below:\small labels $ > v$] {}; \node[fill,circle,scale=0.1] (7) at (-2.6,1) [label=below:\small ] {}; \node (9)[fill,circle,scale=0.1] at (-2.6,1.5) [label=below:\small ] {}; \node (10)[fill,circle,scale=0.1] at (-2.6,0.5) [label=below:\small ] {}; \node (30) at (8,2.5) [label=below:\small $\ell \text{ lnc-trees of type }B$] {}; \node (31) at (-8,2.5) [label=below:\small $k \text{ lnc-trees of type }A$] {}; \path (20) edge[<-] (1) (20) edge[<-] (5) (20) edge[<-] (21) (20)edge[<-] (23) (20) edge[->] (6) (20) edge[->] (11) (20)edge[->] (13) ; \draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt] (4.3,4.0) -- (4.3,-0.2) node [black,midway,xshift=-0.6cm] {}; \draw [decorate,decoration={brace,amplitude=10pt},xshift=4pt,yshift=0pt] (-4.3,-0.2) -- (-4.3,4.0) node [black,midway,xshift=0.6cm] {}; \draw (-2.6,3)--(-4,3.8)--(-3.8,3)--(-2.6,3); \draw (-2.6,2)--(-4,2.8)--(-3.8,2)--(-2.6,2); \draw (-2.6,0)--(-4,0.8)--(-3.8,0)--(-2.6,0); \draw (2.6,3)--(4,3.8)--(3.8,3)--(2.6,3); \draw (2.6,2)--(4,2.8)--(3.8,2)--(2.6,2); \draw (2.6,0)--(4,0.8)--(3.8,0)--(2.6,0); \end{tikzpicture} \end{center} \caption{Noncrossing tree rooted at vertex 1 with degree 1.}\label{fig:butterfly} \end{figure} \noindent From Equations \eqref{nc_trees12}, \eqref{nc_trees13} and \eqref{nc_trees14}, we get \begin{align*} A=z\left(x_0+\dfrac{T}{zy_0}\right)\left(\dfrac{T}{zx_0B}\right). \end{align*} Thus, \begin{align}\label{nc_main0} x_0y_0zAB=T\left(T+zx_0y_0\right). \end{align} Setting $T=x_0y_0zW$ in Equation \eqref{nc_main0}, we obtain \begin{align}\label{nc_main1} AB=x_0y_0z W\left(1+W\right). \end{align} Equations \eqref{nc_trees12} and \eqref{nc_trees13} yield \begin{align}\label{nc_main2} x_0W=\sum_{k\geq 1}x_kA^{k} \end{align} and \begin{align}\label{nc_main3} y_0W=\sum_{k\geq 1}y_kB^{k}. \end{align} Equation \eqref{nc_main2} implies that $A=\phi(x_0W),$ where $\phi$ is implicitly given by \begin{align}\label{nc_main4} t=\sum_{k\geq 1}x_k\phi(t)^{k}. \end{align} Likewise, Equation \eqref{nc_main3} implies that $B=\psi(y_0W),$ where $\psi$ is implicitly given by \begin{align*} u=\sum_{k\geq 1}y_k\psi(u)^{k}. \end{align*} Thus equation \eqref{nc_main1} becomes \begin{align*} \phi(x_0W)\psi(x_0W)=x_0y_0zW\left(1+W\right), \end{align*} and it follows that \begin{align*} W=z\cdot\left(1+W\right)\cdot \dfrac{x_0W}{\phi(x_0W)}\cdot \dfrac{y_0W}{\psi(y_0W)}. \end{align*} By the Lagrange Inversion Formula \cite[Theorem 5.4.2]{Stanley1999enumerative}, one has \begin{align}\label{lnc1} \nonumber [z^{n}x_0^{e_0}y_0^{d_0}]T&=[z^{n-1}x_0^{e_0-1}y_0^{d_0-1}]W\\\nonumber &=\dfrac{1}{n-1}[w^{n-2}x_0^{e_0-1}y_0^{d_0-1}]\left(\left(1+w\right)\cdot \dfrac{x_0w}{\phi(x_0w)}\cdot \dfrac{y_0w}{\psi(y_0w)}\right)^{n-1}\\ &=\dfrac{1}{n-1}{n-1\choose n-e_0-d_0}[t^{e_0-1}]\left(\dfrac{t}{\phi(t)}\right)^{n-1}[u^{d_0-1}]\left(\dfrac{u}{\psi(u)}\right)^{n-1}. \end{align} Applying the Lagrange Inversion Formula again, we obtain \begin{align*} \nonumber [t^{e_0-1}]\left(\dfrac{t}{\phi(t)}\right)^{n-1} &=[t^{-(n-e_0)}]{\phi(t)}^{-(n-1)}\\ \nonumber &=\dfrac{n-1}{n-e_0}[t^{n-1}]{\left(\phi^{\langle -1\rangle}(t)\right)}^{n-e_0}. \end{align*} Now by the definition of the formal power series $\phi$ in \eqref{nc_main4}, this equals \begin{align}\label{lnc2} \nonumber [t^{e_0-1}]\left(\dfrac{t}{\phi(t)}\right)^{n-1}&=\dfrac{n-1}{n-e_0}[t^{n-1}]\left(\sum_{k\geq 1}x_kt^{k}\right)^{n-e_0}\\ \nonumber &=\dfrac{n-1}{n-e_0}[t^{n-1}] \sum_{e_1+e_2+\cdots =n-e_0}\dfrac{(n-e_0)!}{e_1!e_2!\cdots}x_{1}^{e_1}x_{2}^{e_2}\cdots t^{e_1+2e_2+\cdots}\\ &=\dfrac{n-1}{n-e_0}\sum_{\substack{e_1+e_2+\cdots= n-e_0 \\ e_1+2e_2+\cdots =n-1}}\dfrac{(n-e_0)!}{e_1!e_2!\cdots}x_{1}^{e_1}x_{2}^{e_2}\cdots. \end{align} Similarly, \begin{align}\label{lnc3} [u^{d_0-1}]\left(\dfrac{u}{\psi(u)}\right)^{n-1} &=\dfrac{n-1}{n-d_0}\sum_{\substack{d_1+d_2+\cdots= n-d_0 \\ d_1+2d_2+\cdots =n-1}}\dfrac{(n-d_0)!}{d_1!d_2!\cdots}y_{1}^{d_1}y_{2}^{d_2}\cdots. \end{align} Plugging Equations \eqref{lnc2} and \eqref{lnc3} into \eqref{lnc1}, we end up with \begin{align*} [z^{n}x_0^{e_0}x_1^{e_1}x_2^{e_2}&\cdots y_0^{d_0}y_1^{d_1}y_2^{d_2}\cdots]T\\ &=(n-1){n-1\choose n-e_0-d_0}\dfrac{(n-e_0-1)!}{e_1!e_2!\cdots}\dfrac{(n-d_0-1)!}{d_1!d_2!\cdots}. \end{align*} This completes the proof. \qed \section{Consequences of the main theorem}\label{sec:cor} A number of corollaries follow immediately from our main result upon specialisation. The first and most obvious specialisation of this kind is to consider only the outdegree sequence (or only the indegree sequence), which is done in the following corollary. \begin{corollary}\label{indeg100} The number of lnc-trees of order $n$ whose outdegree sequence (indegree sequence) is $ \lambda= 0^{e_0}1^{e_{1}}2^{e_{2}}\cdots $ is equal to \begin{align}\label{ncEq2} \dfrac{(2n-2)!}{(n+e_0-1)!e_1!e_2!\cdots}. \end{align} \end{corollary} \begin{proof} We first sum over all possibilities for $d_1,d_2,\ldots$: since \begin{align*} \sum_{\substack{d_1,d_2,\ldots \geq 0 \\ d_1 + 2d_2 + 3d_3 + \cdots = n-1 \\ d_1+ d_2 + d_3 + \cdots = k}} \frac{1}{d_1! d_2! \cdots} &= [x^{n-1} y^k] \prod_{j \geq 1} \Bigl( \sum_{m \geq 0} \frac{x^{jm} y^m}{m!} \Bigr) = [x^{n-1} y^k] \prod_{j \geq 1} \exp(x^j y) \\ &= [x^{n-1} y^k] \exp \Bigl( \frac{xy}{1-x} \Bigr) = \frac{1}{k!} \binom{n-2}{k-1}, \end{align*} we find that the total number of lnc-trees with outdegree sequence $\lambda$ and $d_0$ sources is \begin{multline*} \frac{(n-1)(n-d_0-1)!(n-e_0-1)!}{e_1!e_2! \cdots} \binom{n-1}{e_0+d_0-1} \cdot \frac{1}{(n-d_0)!} \binom{n-2}{n-d_0-1} \\ = \frac{(n-e_0-1)!}{e_1!e_2! \cdots} \binom{n-1}{e_0+d_0-1} \binom{n-1}{n-d_0}, \end{multline*} and~\eqref{ncEq2} follows by summing over all $d_0$ from the Vandermonde identity. \end{proof} \begin{corollary}\label{fixed_indeg} The average number of vertices with outdegree (indegree) $a$ in lnc-trees of order $n$ is $$\begin{cases} \frac{(2n-1)\binom{3n-a-4}{2n-3}}{\binom{3n-3}{2n-2}} & a > 0, \\ \frac{n+1}{3} & a = 0. \end{cases}$$ \end{corollary} \begin{remark} Asymptotically, the average number of vertices with outdegree (indegree) $a$ is $4n/3^{a+1}$ for $a > 0$ (for example, roughly $4/9$ of the vertices have outdegree $1$). \end{remark} \begin{proof} Starting from the previous corollary, we first sum over all possibilities for $e_1,e_2,\ldots$: \begin{align*} \sum_{\substack{e_1,e_2,\ldots \geq 0 \\ e_1 + 2e_2 + 3e_3 + \cdots = n-1 \\ e_1+ e_2 + e_3 + \cdots = k}} \frac{e_a}{e_1! e_2! \cdots} &= [x^{n-1} y^k] \Bigl( \sum_{m \geq 0} \frac{m x^{am} y^m}{m!} \Bigr) \prod_{\substack{j \geq 1 \\ j \neq a}} \Bigl( \sum_{m \geq 0} \frac{x^{jm} y^m}{m!} \Bigr) \\ &= [x^{n-1} y^k] x^ay \exp \Bigl( \frac{xy}{1-x} \Bigr) = \frac{1}{(k-1)!} \binom{n-a-2}{k-2}, \end{align*} which leaves us with $$\sum_{e_0 = 1}^{n-1} \frac{(2n-2)!}{(n+e_0-1)!} \cdot \frac{1}{(n-e_0-1)!} \binom{n-a-2}{n-e_0-2} = \binom{3n-a-4}{2n-3}$$ for the total number of vertices whose indegree is $a$ if $a > 0$. The statement follows by dividing by the total number of noncrossing trees of order $n$. The formula for $a = 0$ follows either directly in the same way or by subtracting the average number of vertices whose indegree is greater than $0$: $$n - \frac{(2n-1)}{\binom{3n-3}{2n-2}} \sum_{a = 1}^{n-1} \binom{3n-a-4}{2n-3} = \frac{n+1}{3}.$$ \end{proof} We see that vertices of indegree or outdegree $0$ (i.e., \emph{sources} and \emph{sinks}) play a special role. In the following, we present several results on the enumeration of lnc-trees with respect to the number of sources and sinks. \begin{corollary}\label{source_sink} The number of lnc-trees of order $n$ with $k$ sources and $\ell$ sinks is equal to \begin{align}\label{nc-trees1} \dfrac{1}{n-1}{n-1\choose k-1}{n-1\choose \ell-1}{n-1\choose k+\ell-1}. \end{align} \end{corollary} \begin{proof} The result follows by summing \eqref{ncEq1} over all possibilities of $e_1,e_2,\ldots$ and $d_1,d_2,\ldots$ as in the proof of Corollary~\ref{indeg100}. A bijective proof of this corollary is given in Section~\ref{four}. \end{proof} \begin{corollary} There are \begin{align*} \dfrac{1}{n-1}{n-1\choose k-1}{2n-2\choose n-k-1} \end{align*}lnc-trees of order $n$ with $k$ sources. \end{corollary} \begin{proof} This formula follows immediately by summing over all $\ell$ in Equation \eqref{nc-trees1}. \end{proof} \begin{corollary} The number of lnc-trees of order $n$ with a total of $r$ sources and sinks is given by \begin{align*} \dfrac{1}{n-1}{n-1\choose r-1}{2n-2\choose r-2}. \end{align*} \end{corollary} \begin{proof} We set $\ell=r-k$ in Equation \eqref{nc-trees1} and sum over all $k$. \end{proof} \begin{remark} Trees with the property that every vertex is either a source or a sink (equivalently, every vertex is either only adjacent to vertices whose label is higher or only to vertices whose label is lower) are called \emph{alternating trees}. The special case $r=n$ in the previous corollary shows that the number of noncrossing alternating trees of order $n$ is the Catalan number $\frac{1}{n-1}{2n-2\choose n-2}$; this was first proven by Gelfand, Graev and Postnikov in \cite{Gelfand1997combinatorics}, where those trees are called \emph{standard trees}. \end{remark} From the explicit formula~\eqref{nc-trees1}, we also obtain further information on the distribution of the number of sources and sinks in random lnc-trees. Specifically, we have the following theorem: \begin{theorem} The mean and variance of the number of sources and the number of sinks are equal to $(n+1)/3$ and $(4n^2-10n+4)/(27n-36)$ respectively. The covariance of the two is equal to $(-2n^2+5n-2)/(27n-36)$. Asymptotically, the two numbers follow a two-dimensional Gaussian distribution. \end{theorem} \begin{proof} We know from Theorem~\ref{source_sink} that the probability for an lnc-tree to have exactly $k$ sources and $\ell$ sinks is \begin{equation}\label{eq:prob_k_l} \frac{{n-1\choose k-1}{n-1\choose \ell-1}{n-1\choose k+\ell-1}}{\binom{3n-3}{n-2}}. \end{equation} The explicit formula for the mean (which has already been derived in Corollary~\ref{fixed_indeg} as well) follows by multiplying by $k$ and then summing over all $k$ and $\ell$; the other moments are obtained in the same way. For the asymptotic distribution, set $k = n/3 + x\sqrt{n}$ and $\ell = n/3 + y\sqrt{n}$ and apply Stirling's formula to obtain $$\frac{{n-1\choose k-1}{n-1\choose \ell-1}{n-1\choose k+\ell-1}}{\binom{3n-3}{n-2}} \sim \frac{9\sqrt{3}}{4\pi n} e^{-9(x^2+xy+y^2)/2},$$ which shows that the limiting distribution is a two-dimensional normal distribution. \end{proof} Finally, if we multiply~\eqref{eq:prob_k_l} by $\ell$ and sum over all possible $\ell$, we obtain the total and thus also the average number of sinks in trees with $k$ sources. The variance can be obtained in the same way, and we end up with the following corollary: \begin{corollary} The mean number of sinks in lnc-trees on $n$ labelled vertices with $k$ sources is $(n-k+1)/2$, and the variance is given by $(n^2-k^2-2n+1)/(8n-12)$. \end{corollary} \begin{remark} The statement of this corollary remains true if we prescribe the entire indegree sequence in addition to the number of sources, cf.~Remark~\ref{rem:independence}. \end{remark} \section{A bijection with ternary trees}\label{four} The total number of $n$-vertex noncrossing trees given in \eqref{lnc} is also the number of ternary trees with $n-1$ vertices, and bijections between the two were established by different authors. The aim of this section is to present a refinement of this correspondence. Let $T$ be a ternary tree which consists of a root $e$ and $3$ disjoint ternary subtrees, $T_3,T_2,T_1$ in this order. See Figure \ref{i-edge}. \begin{figure}[H] \begin{center} \begin{tikzpicture}[scale=0.6,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.4] (1)at (0,3) [label=above:\small $e$] {}; \node[fill,circle,scale=0.4] (5) at (2.6,1.5) [label=below:\small ] {}; \node[fill,circle,scale=0.4] (11) at (-2.6,1.5) [label=below:\small ] {}; \node[fill,circle,scale=0.4] (12) at (0.0,1.5) [label=below:\small ] {}; \node (4) at (-2.7,1) [label=below:\small $T_3$] {}; \node (6) at (0.0,1) [label=below:\small $T_2$] {}; \node (7) at (3,1) [label=below:\small $T_1$] {}; \path (11) edge[-] (1) (5) edge[-] (1) (12)edge[-] (1) ; \draw (-2.6,1.5)--(-4,-0.5)--(-2,-0.5)--(-2.6,1.5); \draw (0,1.5)--(-1.0,-0.5)--(1.1,-0.5)--(0,1.5); \draw (2.6,1.5)--(2,-0.5)--(4,-0.5)--(2.6,1.5); \end{tikzpicture} \end{center} \caption{Rooted ternary tree showing left-, middle- and right-edges.} \label{i-edge} \end{figure} \noindent We shall call the edges from the root to $T_1, T_2$ and $T_3$ right-edge, middle-edge and left-edge respectively. Cigler \cite[Theorem 1]{Cigler1987remarks} showed that the number of ternary trees on $n-1$ vertices having precisely $\ell-1$, $k-1$, and $n-k-\ell$ right-edges, middle-edges and left-edges respectively is given by $$\dfrac{1}{n-1}{n-1\choose k-1}{n-1\choose \ell-1}{n-1\choose k+\ell-1},$$ which also counts noncrossing trees with $n$ vertices, $k$ sources and $\ell$ sinks by Corollary~\ref{source_sink}. In the following, we construct an explicit bijection between the two that is a modification of the bijection between ternary trees and noncrossing trees obtained independently by Simion and Postnikov as mentioned by Stanley in \cite[Solution 5.46]{Stanley1999enumerative}. Other bijective proofs can be found in the literature, see for example papers of Dulucq and Penaud \cite{Dulucq1993cordes}, and Panholzer and Prodinger \cite{Panholzer2002bijections}. \begin{theorem}\label{nc-trees10} There is a bijection between the set of ternary trees on $n-1$ vertices such that there are $k-1$ and $\ell-1$ middle-edges and right-edges respectively, and the set of lnc-trees on $n$ vertices with $k$ sources and $\ell$ sinks. \end{theorem} \begin{proof} Given an lnc-tree $T$ on $n$ vertices having $k$ sources and $\ell$ sinks, we obtain the corresponding ternary tree $\beta(T)$ on $n-1$ vertices (the $n-1$ edges of $T$ become the vertices of $\beta(T)$) with $k-1$ middle-edges and $\ell-1$ right-edges by the following steps: \begin{itemize} \item[I.] The lnc-tree consisting only of a single vertex is associated with the empty ternary tree. \item[II.] If $T$ has at least two vertices, let $s$ be the vertex with the smallest label in $T$ ($1$ initially), and let $j$ be the vertex with the greatest label adjacent to $s$. We denote the edge $sj$ by $e$. Three subtrees of $T$ are defined as follows: \item[III.] $T_1$ is the connected component containing $s$ in the graph $T-e$ obtained by removing the edge $e$; \item[IV.]$T_2$ is the connected component containing vertex $j$ in the graph obtained from $T$ by removing the edge $e$ and vertices with labels greater than $j$; \item[V.]$T_3$ is the tree induced by the vertices with labels greater or equal to $j$. \item[VI.] Take $e$ as the root of $\beta(T)$ and recursively define $\beta(T_1)$, $\beta(T_2)$ and $\beta(T_3)$ (from right to left) to be the three branches, with the respective roots connected to $e$. Label left-edges, middle-edges and right-edges as $l$, $m$ and $r$ respectively in the ternary tree rooted at $e$. \end{itemize} See Figure \ref{fig_nc-tree} for an example. The process is easily reversible. We can match each edge label $r$ with the vertex in the corresponding subtree $T_1$ whose label is greatest, which is necessarily a sink. Likewise, we can match each edge label $m$ with the vertex in the corresponding subtree $T_2$ whose label is smallest (which is necessarily a source), and match each edge label $l$ with the vertex in the corresponding subtree $T_3$ whose label is smallest (which is neither a source nor a sink). In this way, we obtain a bijective correspondence between edges of $\beta(T)$ and all vertices in $T$ except for $1$ and $n$, in such a way that $r$-edges correspond to sinks, $m$-edges to sources and $l$-edges to all other vertices. In Figure~\ref{fig_nc-tree}, we have indicated the labels of the vertices associated with the edges of $\beta(T)$. Thus, the resulting ternary tree $\beta(T)$ has $k-1$ middle-edges (vertex 1, which is a source, does not correspond to any edge in the ternary tree since it always occurs in the subtree $T_1$) and $\ell-1$ right-edges (vertex $n$, which is a sink, does not correspond to any edge in the ternary tree since it always occurs in the subtree $T_3$), which is what we wanted to achieve. \begin{figure}[htp!] \begin{center} \begin{tikzpicture}[scale=1.6,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.2] (1) at (0,3) [label=above:\small $1$] {1}; \node[fill,circle,scale=0.2] (2) at (3,0) [label=right:\small $4$] {2}; \node[fill,circle,scale=0.2] (3) at (-3,0) [label=left:\small $10$] {3}; \node[fill,circle,scale=0.2] (4) at (0,-3) [label=below:\small $7$] {4}; \node[fill,circle,scale=0.2] (5) at (2.6,1.5) [label=right:\small $3$] {5}; \node[fill,circle,scale=0.2] (6) at (1.6,2.5) [label=above:\small $2$] {5}; \node[fill,circle,scale=0.2] (7) at (2.6,-1.5) [label=right:\small $5$] {5}; \node[fill,circle,scale=0.2] (8) at (1.6,-2.5) [label=below:\small $6$] {5}; \node[fill,circle,scale=0.2] (9) at (-2.6,-1.5) [label=left:\small $9$] {5}; \node[fill,circle,scale=0.2] (10) at (-1.6,-2.5) [label=below:\small $8$] {5}; \node[fill,circle,scale=0.2](11) at (-2.6,1.5) [label=left:\small $11$] {5}; \node[fill,circle,scale=0.2] (12) at (-1.6,2.5) [label=above:\small $12$] {5}; \node[fill,circle,scale=0.2] (13) at (-1.3,2.26) [label=right:\color{blue}e] {5}; \node[fill,circle,scale=0.2] (14) at (0.87,0) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (15) at (0.8,-2.75) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (16) at (1.5,1.5) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (17) at (2.8,-0.75) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (18) at (1.4,2.2) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (19) at (2.1,2.0) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (20) at (-2.1,2.0) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (21) at (-2.1,-0.5) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (22) at (-2.1,-2.0) [label=below:\small ] {5}; \node[fill,circle,scale=0.2] (23) at (-2.8,0.8) [label=below:\small ] {5}; \draw (0,0) circle (3cm); \path (1) edge[->] (8) (1) edge[->] (2) (8) edge[->] (4) (1) edge[->] (5) (6) edge[->] (5) (2) edge[->] (7) (10) edge[->] (11) (11) edge[->] (12) (1) edge[->] (11) (3) edge[->] (11) (10) edge[->] (9) (13) edge[dashed] (14) (14) edge[dashed] (15) (16) edge[dashed] (14) (16) edge[dashed] (17) (16) edge[dashed] (18) (18) edge[dashed] (19) (13) edge[dashed] (21) (22) edge[dashed] (21) (23) edge[dashed] (21) (13) edge[dashed] (20) (13) edge[dashed] node [right] {\color{red}\small $r (7)$} (14) (14) edge[dashed] node [left] {\color{red} \small $l (6)$} (15) (16) edge[dashed] node [below right] {\color{red}\small $r (5)$} (14) (16) edge[dashed] node [right] {\color{red}\small $l (4)$} (17) (16) edge[dashed] node [left] {\color{red}\small $r (3)$} (18) (18) edge[dashed] node [above left] {\color{red}\small $m (2)$} (19) (13) edge[dashed] node [right] {\color{red}\small $m (8)$} (21) (22) edge[dashed] node [left] {\color{red}\small $r (9)$} (21) (23) edge[dashed] node [above] {\color{red} \small $m (10)$} (21) (13) edge[dashed] node [below] {\color{red} \small $l (11)$} (20) ; \end{tikzpicture} \end{center} \caption{Diagram showing the bijection in the proof of Theorem~\ref{nc-trees10}.} \label{fig_nc-tree} \end{figure} \end{proof} \section{In- and outdegree of a single vertex}\label{sec:single} Let us finally consider the distribution of the in- and outdegree of a fixed vertex $i$. By symmetry, it is sufficient to consider one of the two, so we define the number $N(n,i,d)$ to be the number of lnc-trees on $n$ vertices for which vertex $i$ has outdegree $d$. In \cite[Theorem 2.3]{Noy1998enumeration}, Noy showed that the number of noncrossing trees of order $n$ such that a fixed vertex has degree $d$ is given by \begin{align}\label{lnc-deg} U(n,d) = \dfrac{2d}{3n-d-3}{3n-d-3\choose n-d-1}. \end{align} \begin{theorem} The number $N(n,i,d)$ of lnc-trees of order $n$ for which vertex $i$ has outdegree $d\geq 1$ is \begin{align}\label{lnc-outdeg} N(n,i,d)=U(n,d)-\sum_{j=2}^{i}U(n-j+1,d-1)U(j,1), \end{align} where $U(n,d)$ is given by \eqref{lnc-deg}. \end{theorem} \begin{proof} To prove the theorem it suffices to show that for $i\geq 2,$ $N(n,i,d)$ satisfies the recurrence \begin{align}\label{eq:rec} N(n,i,d)=N(n,i-1,d)-U(n-i+1,d-1)U(i,1), \end{align} and that $N(n,1,d)$ is indeed given by Equation \eqref{lnc-deg}, i.e.~$N(n,1,d) = U(n,d)$. The latter is clear since the outdegree of vertex 1 is also always its degree, and we prove recurrence~\eqref{eq:rec} by means of a bijective argument. Consider an lnc-tree $T$ in which vertex $i-1$ has outdegree $d$. We relabel the vertices such that vertex $n$ is given label $1$, and for $j < n$, vertex $j$ is given label $j+1$ (this amounts to a rotation of labels). \begin{figure}[H] \begin{center} \begin{minipage}[l]{120pt} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i-1 $] {4}; \node[fill,circle,scale=0.2] (5) at (-1,-2.85) [label=below left:\small $i $] {5}; \node (10) at (-0.2,1,1) [] {}; \node (11) at (-2.0,0.6) [] {}; \node (13) at (1.2,1,1) [] {}; \node (14) at (2,0.6) [] {}; \node (12) at (0.7,-4.8) [] {\small outdegree $d$}; \draw (-0.2,1)--(0.1,1)--(0,-3.0)--cycle; \draw (0.7,1)--(0.4,1)--(0,-3.0)--cycle; \draw (-2.8,0.6)--(-2.3,0.6)--(0,-3.0)--cycle; \draw (2.8,0.6)--(2.3,0.6)--(0,-3.0)--cycle; \path (10) edge[dotted] (11); \path (13) edge[dotted] (14); \draw (0,0) circle (3cm); \end{tikzpicture} \end{minipage} \begin{minipage}[c]{60pt} $\longrightarrow$ \end{minipage} \begin{minipage}[r]{120pt} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i $] {4}; \node[fill,circle,scale=0.2] (5) at (1,-2.85) [label=below right:\small $i-1 $] {5}; \node (10) at (-0.2,1,1) [] {}; \node (11) at (-2.0,0.6) [] {}; \node (13) at (1.2,1,1) [] {}; \node (14) at (2,0.6) [] {}; \node (12) at (0.7,-4.8) [] {\small outdegree $d$}; \draw (-0.2,1)--(0.1,1)--(0,-3.0)--cycle; \draw (0.7,1)--(0.4,1)--(0,-3.0)--cycle; \draw (-2.8,0.6)--(-2.3,0.6)--(0,-3.0)--cycle; \draw (2.8,0.6)--(2.3,0.6)--(0,-3.0)--cycle; \path (10) edge[dotted] (11); \path (13) edge[dotted] (14); \draw (0,0) circle (3cm); \end{tikzpicture} \end{minipage} \end{center} \end{figure} In the resulting tree $T'$, the outdegree of vertex $i$ is $d$ again, except in the case where there is an edge from $i-1$ to $n$ in $T$; this edge becomes an edge from $i$ to $1$ in $T'$, with the direction reversed, so that the outdegree of $i$ is $d-1$. \begin{figure}[H] \begin{center} \begin{minipage}[l]{120pt} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \tikzset{edge/.style = {->,> = latex'}} \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i-1 $] {4}; \node[fill,circle,scale=0.2] (5) at (-1,-2.85) [label=below left:\small $i $] {5}; \node[fill,circle,scale=0.2] (2) at (1,2.85) [label=above:\small $n $] {2}; \node[fill,circle,scale=0.2] (3) at (2,2.25) [label=right:\small $1 $] {3}; \node (10) at (-0.2,1,1) [] {}; \node (11) at (-2.0,0.6) [] {}; \node (13) at (1.5,1,1) [] {}; \node (14) at (2,0.6) [] {}; \draw (-0.2,1)--(0.1,1)--(0,-3.0)--cycle; \draw (-2.8,0.6)--(-2.3,0.6)--(0,-3.0)--cycle; \draw (2.8,0.6)--(2.3,0.6)--(0,-3.0)--cycle; \path (10) edge[dotted] (11); \path (13) edge[dotted] (14); \draw[edge] (4) to (2); \draw (0,0) circle (3cm); \end{tikzpicture} \end{minipage} \begin{minipage}[c]{60pt} $\longrightarrow$ \end{minipage} \begin{minipage}[r]{120pt} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \tikzset{edge/.style = {->,> = latex'}} \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i $] {4}; \node[fill,circle,scale=0.2] (5) at (1,-2.85) [label=below right:\small $i-1 $] {5}; \node[fill,circle,scale=0.2] (2) at (1,2.85) [label=above:\small $1 $] {2}; \node[fill,circle,scale=0.2] (3) at (0,3) [label=above:\small $n $] {3}; \node (10) at (-0.2,1,1) [] {}; \node (11) at (-2.0,0.6) [] {}; \node (13) at (1.5,1,1) [] {}; \node (14) at (2,0.6) [] {}; \draw (-0.2,1)--(0.1,1)--(0,-3.0)--cycle; \draw (-2.8,0.6)--(-2.3,0.6)--(0,-3.0)--cycle; \draw (2.8,0.6)--(2.3,0.6)--(0,-3.0)--cycle; \path (10) edge[dotted] (11); \path (13) edge[dotted] (14); \draw[edge] (2) to (4); \draw (0,0) circle (3cm); \end{tikzpicture} \end{minipage} \end{center} \end{figure} In this case, we perform one more step. Let $j$ be the smallest label greater than $i$ such that there is an edge between $1$ and $j$ in $T'$. We remove this edge and replace it by an edge between $i$ and $j$, thereby effectively moving a branch from $1$ to $i$ and increasing the outdegree of $i$ to $d$. The resulting tree is called $T''$. \begin{figure}[H] \begin{center} \begin{minipage}[l]{120pt} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \tikzset{edge/.style = {->,> = latex'}} \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i $] {4}; \node[fill,circle,scale=0.2] (5) at (1,-2.85) [label=below right:\small $i-1 $] {5}; \node[fill,circle,scale=0.2] (2) at (1,2.85) [label=above:\small $1 $] {2}; \node[fill,circle,scale=0.2] (3) at (0,3) [label=above:\small $n $] {3}; \node (10) at (-0.4,1) [] {}; \node (11) at (-0.4,-2) [] {}; \node (13) at (-0.1,0) [label=left:\small move] {}; \draw (-1.8,-1.3)--(-1.3,-1.3)--(0,-3.0)--cycle; \draw (-2,-1.8)--(-2.3,-1.8)--(0,-3.0)--cycle; \draw (2,-1.8)--(2.3,-1.8)--(0,-3.0)--cycle; \draw[color=blue] (-0.8,1.3)--(0,1.3)--(1,2.85)--cycle; \draw (-1,1.8)--(-2,1.8)--(1,2.85)--cycle; \draw[edge] (2) to (4); \draw[edge, color=red] (10) to (11); \draw (0,0) circle (3cm); \end{tikzpicture} \end{minipage} \begin{minipage}[c]{60pt} $\longrightarrow$ \end{minipage} \begin{minipage}[r]{120pt} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \tikzset{edge/.style = {->,> = latex'}} \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i $] {4}; \node[fill,circle,scale=0.2] (5) at (1,-2.85) [label=below right:\small $i-1 $] {5}; \node[fill,circle,scale=0.2] (2) at (1,2.85) [label=above:\small $1 $] {2}; \node[fill,circle,scale=0.2] (3) at (0,3) [label=above:\small $n $] {3}; \draw (-1.8,-1.3)--(-1.3,-1.3)--(0,-3.0)--cycle; \draw (-2,-1.8)--(-2.3,-1.8)--(0,-3.0)--cycle; \draw (2,-1.8)--(2.3,-1.8)--(0,-3.0)--cycle; \draw[color=blue] (-0.8,-0.8)--(0,-0.8)--(0,-3.0)--cycle; \draw (-1,1.8)--(-2,1.8)--(1,2.85)--cycle; \draw[edge] (2) to (4); \draw (0,0) circle (3cm); \end{tikzpicture} \end{minipage} \end{center} \end{figure} The map that sends $T$ to $T'$ in the first case and to $T''$ in the second case thus maps lnc-trees for which the outdegree of vertex $i-1$ is $d$ to lnc-trees for which the outdegree of vertex $i$ is $d$. It can easily be reversed: given a tree in which vertex $i$ has degree $d$, move the branch with $i$'s highest-label neighbour from $i$ to $1$ if there is an edge between $1$ and $i$ (otherwise, do not move anything) and rotate the labels. In the resulting lnc-tree, vertex $i-1$ has outdegree $d$. This is almost a bijection, but there is one exceptional case that is not covered, namely the situation that there is an edge between $i-1$ and $n$ in $T$ (thus an edge between $i$ and $1$ in $T'$), and vertex $1$ does not have any neighbours in $T'$ whose label is greater than $i$. To complete the proof, it remains to show that there are exactly $U(n-i+1,d-1)U(i,1)$ trees of this kind. \begin{figure}[H] \begin{center} \begin{tikzpicture}[scale=0.5,>=stealth',shorten >=0pt,auto,node distance=3cm, thick] \tikzset{edge/.style = {->,> = latex'}} \node[fill,circle,scale=0.2] (4) at (0,-3.0) [label=below:\small $i $] {4}; \node[fill,circle,scale=0.2] (2) at (1,2.85) [label=above:\small $1 $] {2}; \draw (-1.8,-1.3)--(-1.3,-1.3)--(0,-3.0)--cycle; \draw (-2,-1.8)--(-2.3,-1.8)--(0,-3.0)--cycle; \draw (-0.8,-0.8)--(0,-0.8)--(0,-3.0)--cycle; \draw (1.8,-1.3)--(1.3,-1.3)--(0,-3.0)--cycle; \draw (2,-1.8)--(2.3,-1.8)--(0,-3.0)--cycle; \draw (1.8,1.3)--(1,1.3)--(1,2.85)--cycle; \draw (2.6,1.3)--(2,1.3)--(1,2.85)--cycle; \draw[edge] (2) to (4); \draw (0,0) circle (3cm); \end{tikzpicture} \end{center} \caption{Exceptional lnc-trees.}\label{fig:exceptional} \end{figure} Consider an exceptional lnc-tree, as illustrated in Figure~\ref{fig:exceptional}. It can be decomposed into two parts: one part is the lnc-tree induced by the vertices $i,i+1,\ldots,n$, which can be any lnc-tree on those $n-i+1$ vertices such that vertex $i$ has degree $d-1$. There are thus $U(n-i+1,d-1)$ possibilities. The rest is an arbitrary lnc-tree with $i$ vertices such that vertices $1$ and $i$ are connected by an edge. The number of such trees is equal to the number of trees for which vertex $1$ has degree $1$, since in either case we have a unique decomposition into two rooted subtrees: the subtrees obtained when the edge between $1$ and $i$ is removed in the first case, and the subtrees on either side of the edge going out from $1$ in the other case. See also \cite[Corollary 2.4]{Noy1998enumeration}. Thus the total number of exceptional trees is indeed given by $$U(n-i+1,d-1)U(i,1),$$ which completes the proof. \end{proof} \begin{remark} In the special case $d=1$, we obtain a surprising corollary: every vertex of an lnc-tree of order $n$, except for vertex $n$, has equal probability of having outdegree $1$, which is also the probability of having total degree $1$. This is because $U(n-j+1,0) = 0$ unless $j = n$, so that~\eqref{lnc-outdeg} gives us $$N(n,1,1) = N(n,2,1) = \cdots = N(n,n-1,1) = U(n,1).$$ \end{remark} \section*{Acknowledgments} The first author was supported by the German Academic Exchange Service (DAAD), in association with the African Institute for Mathematical Sciences (AIMS). Code No.: A/12/92062. The second author was supported by the National Research Foundation of South Africa under grant number 96236. \begin{thebibliography}{10} \bibitem{Cigler1987remarks} J.~Cigler. \newblock Some remarks on {C}atalan families. \newblock {\em European J. Combin.}, 8(3):261--267, 1987. \bibitem{Cotterill2011geometry} E.~Cotterill. \newblock Geometry of curves with exceptional secant planes: linear series along the general curve. \newblock {\em Math. Z.}, 267(3-4):549--582, 2011. \bibitem{Deutsch2002statistics} E.~Deutsch and M.~Noy. \newblock Statistics on non-crossing trees. \newblock {\em Discrete Math.}, 254(1-3):75--87, 2002. \bibitem{Du2010counting} R.~R.~X. Du and J.~Yin. \newblock Counting labelled trees with given indegree sequence. \newblock {\em J. Combin. Theory Ser. A}, 117(3):345--353, 2010. \bibitem{Dulucq1993cordes} S.~Dulucq and J.-G. Penaud. \newblock Cordes, arbres et permutations. \newblock {\em Discrete Math.}, 117(1-3):89--105, 1993. \bibitem{Flajolet1999analytic} P.~Flajolet and M.~Noy. \newblock Analytic combinatorics of non-crossing configurations. \newblock {\em Discrete Math.}, 204(1-3):203--229, 1999. \bibitem{Gelfand1997combinatorics} I.~M. Gelfand, M.~I. Graev, and A.~Postnikov. \newblock Combinatorics of hypergeometric functions associated with positive roots. \newblock In {\em The {A}rnold-{G}elfand mathematical seminars}, pages 205--221. Birkh\"auser Boston, Boston, MA, 1997. \bibitem{Hough2003descents} D.~S. Hough. \newblock Descents in noncrossing trees. \newblock {\em Electron. J. Combin.}, 10:Note 13, 5 pp., 2003. \bibitem{Noy1998enumeration} M.~Noy. \newblock Enumeration of noncrossing trees on a circle. \newblock In {\em Proceedings of the 7th {C}onference on {F}ormal {P}ower {S}eries and {A}lgebraic {C}ombinatorics ({N}oisy-le-{G}rand, 1995)}, volume 180, pages 301--313, 1998. \bibitem{Okoth2015counting} I.~O. Okoth and S.~Wagner. \newblock Counting labelled trees by sources, sinks and indegree sequences. \newblock Preprint, 2015. \bibitem{Pang2013refinement} S.~X.~M. Pang and L.~Lv. \newblock A refinement of leaves on noncrossing trees. \newblock {\em Graphs Combin.}, 29(1):131--143, 2013. \bibitem{Panholzer2003height} A.~Panholzer. \newblock The height distribution of nodes in non-crossing trees. \newblock {\em Ars Combin.}, 69:19--32, 2003. \bibitem{Panholzer2003non-crossing} A.~Panholzer. \newblock Non-crossing trees revisited: cutting down and spanning subtrees. \newblock In {\em Discrete random walks ({P}aris, 2003)}, Discrete Math. Theor. Comput. Sci. Proc., AC, pages 265--276. 2003. \bibitem{Panholzer2002bijections} A.~Panholzer and H.~Prodinger. \newblock Bijections for ternary trees and non-crossing trees. \newblock {\em Discrete Math.}, 250(1-3):181--195, 2002. \bibitem{Shin2011bijective} H.~Shin and J.~Zeng. \newblock A bijective enumeration of labeled trees with given indegree sequence. \newblock {\em J. Combin. Theory Ser. A}, 118(1):115--128, 2011. \bibitem{Stanley1999enumerative} R.~P. Stanley. \newblock {\em Enumerative combinatorics. {V}ol. 2}, volume~62 of {\em Cambridge Studies in Advanced Mathematics}. \newblock Cambridge University Press, Cambridge, 1999. \bibitem{Wagner2011labeled} S.~Wagner. \newblock Labeled trees, functions, and an algebraic identity. \newblock {\em Electron. J. Combin.}, 18(1):Paper 188, 5 pp., 2011. \end{thebibliography} \end{document}