\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{mathrsfs}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts,amsmath,amsthm}
\usepackage{latexsym,amsmath,amssymb,amsfonts,epsfig,graphicx,cite,psfrag}
\usepackage{eepic,color,colordvi,amscd,amsthm}
\usepackage{pstcol,pstricks,color}
\usepackage{epsfig}
\parskip=4pt
%--------------------------------------------------------------------

%--------------------------------------------------------------------
\newtheorem{theorem}{Theorem}[section]
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{question}[theorem]{Question}
\newtheorem{ex}[theorem]{Example}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{continuation}[theorem]{Continuation of Example}
\newtheorem{alg}{Algorithm}[section]
\def\theequation{\thesection.\arabic{equation}}
\makeatletter \@addtoreset{equation}{section}
\newcommand{\pf}{\proof}
\makeatother
%--------------------------------------------------------------------


\title{A decomposition algorithm for noncrossing trees}
\author{
{Lun Lv}\\
  {\small School of Sciences}\\
  {\small Hebei University of Science and Technology}\\
    {\small Shijiazhuang 050018, P.R. China }\\
     {\vspace{0.5cm}}
  {\small \texttt{klunlv@gmail.com}}\\
  { Sabrina X.M. Pang\footnote{Corresponding author}}\\
  {\small College of Mathematics and Statistics}\\
  {\small Hebei University of Economics and Business}\\
    {\small Shijiazhuang 050061, P.R. China}\\
     {\small \texttt {stpangxingmei@heuet.edu.cn}}}
\date{\dateline{May 7, 2013}{Dec 7, 2013}{}\\
\small Mathematics Subject Classifications: 05A05, 05A19}
%--------------------------------------------------------------------



\begin{document}

\maketitle



\begin{abstract}
Based on the classic bijective algorithm for trees due to Chen, we
present a decomposition algorithm for noncrossing trees. This leads
to a combinatorial interpretation of a formula on noncrossing trees
of size $n$ with $k$ descents. We also derive the formula for
noncrossing trees of size $n$ with $k$ descents and $i$ leaves,
which is a refinement of the formula given by Flajolet and Noy. As
an application of our algorithm, we answer a question proposed by
Hough, which asks for a bijection between two classes of noncrossing
trees with a given number of descents.

\bigskip\noindent \textbf{Keywords:} noncrossing tree, descent, bijection
\end{abstract}





\section{Introduction}
A \textit{noncrossing tree} (NC-tree for short) is a tree drawn on
$n$ points numbered in counterclockwise order on a circle in such a
way that its edges are rectilinear and do not cross. We always
consider the points labeled counterclockwise from $1$ to $n$ and the
root labeled $1$. The \textit{size} of a NC-tree is defined as the
number of edges. It is well known that the number of NC-trees of
size $n$ equals $\frac{1}{2n+1}{3n\choose n}$, the generalized
Catalan number. Noncrossing configurations have been extensively
studied, see, for example, \cite{MN, DN, DH, PP, FN, CY,
Sun-Wang-2008,Asin-Mans08,Klu12,Guo11}.

\begin{figure}[h,t]
\begin{center}\vspace{60pt}
\begin{pspicture}(3,0)(0,0)
\psset{unit=.15cm} \pscircle[linewidth=.01pt](0,0){8}
\pscircle*(0,8){.2} \pscircle*(-4,6.93){.2}\pscircle*(-6.93,4){.2}
\pscircle*(-8,0){.2} \pscircle*(-6.93,-4){.2}
\pscircle*(-4,-6.93){.2} \pscircle(0,-8){.2}
\pscircle(4,-6.93){.2}\pscircle*(6.93,-4){.2}
\pscircle*(8,0){.2}\pscircle*(6.93,4){.2} \pscircle(4,6.93){.2}
\psline[linewidth=.5pt](0,8)(-8,0)
\psline[linewidth=.5pt](-8,0)(-4,6.93)
\psline[linewidth=.5pt](-8,0)(-6.93,4)
\psline[linewidth=.5pt](-8,0)(-4,-6.93)
\psline[linewidth=.5pt](-4,-6.93)(-6.93,-4)
\psline[linewidth=.5pt](-4,-6.93)(0,-8)
\psline[linewidth=.5pt](0,8)(4,-6.93)
\psline[linewidth=.5pt](0,8)(6.93,-4)
\psline[linewidth=.5pt](6.93,-4)(6.93,4)
\psline[linewidth=.5pt](6.93,-4)(4,6.93)
\psline[linewidth=.5pt](6.93,4)(8,0)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rput(0,10){\footnotesize$1$}\rput(-5.2,8){\footnotesize$2$}
\rput(-8.3,4.5){\footnotesize$3$}\rput(-9.6,0){\footnotesize$4$}
\rput(-8.2,-4.5){\footnotesize$5$}\rput(-4.8,-8.4){\footnotesize$6$}
\rput(0,-9.7){\footnotesize$7$}\rput(4.9,-8.2){\footnotesize$8$}
\rput(8.5,-4.5){\footnotesize$9$}\rput(9.8,0){\footnotesize$10$}
\rput(9,4.5){\footnotesize$11$}\rput(5.6,8){\footnotesize$12$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\psset{unit=.2cm} \psline[linewidth=.5pt](25,7)(20,3)
\psline[linewidth=.5pt](25,7)(25,3)
\psline[linewidth=.5pt](25,7)(30,3)
\psline[linewidth=.5pt](20,3)(17,-1)
\psline[linewidth=.5pt](20,3)(20,-1)
\psline[linewidth=.5pt](20,3)(23,-1)
\psline[linewidth=.5pt](23,-1)(21,-5)
\psline[linewidth=.5pt](23,-1)(25,-5)
\psline[linewidth=.5pt](30,3)(27,-1)
\psline[linewidth=.5pt](30,3)(33,-1)
\psline[linewidth=.5pt](27,-1)(27,-5)
\pscircle*(25,7){.2}\pscircle*(20,3){.2}
\pscircle*(25,3){.2}\pscircle*(30,3){.2}
\pscircle*(17,-1){.2}\pscircle*(20,-1){.2}
\pscircle*(23,-1){.2}\pscircle*(21,-5){.2}
\pscircle*(25,-5){.2}\pscircle*(27,-1){.2}
\pscircle*(33,-1){.2}\pscircle*(27,-5){.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(21,5){\footnotesize$r$}\put(24,4){\footnotesize$r$}
\put(28.5,5){\footnotesize$r$}\put(17.5,.5){\footnotesize$l$}
\put(19.3,.3){\footnotesize$l$}\put(22,.7){\footnotesize$r$}
\put(21,-3.5){\footnotesize$l$}\put(24.5,-3.5){\footnotesize$r$}
\put(27.5,1){\footnotesize$r$}\put(32,1){\footnotesize$r$}
\put(27.7,-3.5){\footnotesize$l$}
\end{pspicture}
\vspace{35pt} \caption{The $(l;r)$-representation of a
NC-tree.}\label{f1} \vspace{-5pt}
\end{center}
\end{figure}

In a NC-tree $T$, a vertex $v$ is \textit{planted} at $u$ if $(u,v)$
is an edge and $u$ lies on the unique path from the root to $v$.
Moreover, $(u,v)$ is a \textit{descent} if $u>v$. Denote $N_{n,k}$
the number of NC-trees of size $n$ with $k$ descents. Using
generating function, Hough \cite{DH} pointed out the following
formula
\begin{theorem}[Theorem 2.2, \cite{DH}]\label{theorem2}
\begin{eqnarray}\label{eqn4}
N_{n,k}=\frac{1}{n}{n-1+k\choose n-1}{2n-k\choose n+1}.
\end{eqnarray}
\end{theorem}
Hough \cite{DH} also observed that $N_{2k+1,k-1}=N_{2k+1,k}$, and
proposed the following question.
\begin{question}[Question 4.2, \cite{DH}]\label{question1}
Find a bijection on NC-trees with $2k+1$ edges between those with
$k-1$ descents and those with $k$ descents.
\end{question}

In this paper, we give a combinatorial interpretation of formula
\eqref{eqn4} by introducing a decomposition algorithm for NC-trees.
Moreover, we derive a refined formula on NC-trees of size $n$ with
respect to the number of descents and the number of leaves. Notice
that this formula is also a refinement of a result given by Flajolet
and Noy \cite{FN}. The second result of this paper is to provide a
bijective proof for Question \ref{question1}.


\begin{figure}[h,t]
\begin{center}\vspace{70pt}
\begin{pspicture}(13,0)(0,0)
\psset{unit=.25cm} \psline[linewidth=.5pt](25,7)(20,3)
\psline[linewidth=.5pt](25,7)(25,3)
\psline[linewidth=.5pt](25,7)(30,3)
\psline[linewidth=.5pt](20,3)(17,-1)
\psline[linewidth=.5pt](20,3)(20,-1)
\psline[linewidth=.5pt](20,3)(23,-1)
\psline[linewidth=.5pt](23,-1)(21,-5)
\psline[linewidth=.5pt](23,-1)(25,-5)
\psline[linewidth=.5pt](30,3)(27,-1)
\psline[linewidth=.5pt](30,3)(33,-1)
\psline[linewidth=.5pt](27,-1)(27,-5)
\pscircle*(25,7){.2}\pscircle*(20,3){.2}
\pscircle*(25,3){.2}\pscircle*(30,3){.2}
\pscircle*(17,-1){.2}\pscircle*(20,-1){.2}
\pscircle*(23,-1){.2}\pscircle*(21,-5){.2}
\pscircle*(25,-5){.2}\pscircle*(27,-1){.2}
\pscircle*(33,-1){.2}\pscircle*(27,-5){.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(21,5){\footnotesize$r$}\put(24,4){\footnotesize$r$}
\put(28.5,5){\footnotesize$r$}\put(17.5,.5){\footnotesize$l$}
\put(19.3,.3){\footnotesize$l$}\put(22,.7){\footnotesize$r$}
\put(21,-3.5){\footnotesize$l$}\put(24.5,-3.5){\footnotesize$r$}
\put(27.5,1){\footnotesize$r$}\put(32,1){\footnotesize$r$}
\put(27.7,-3.5){\footnotesize$l$}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(25,7.5){\footnotesize$8$}\put(19,3){\footnotesize$3$}
\put(25.5,2.8){\footnotesize$2$}\put(30.5,3){\footnotesize$10$}
\put(16.3,-2.8){\footnotesize$11$}\put(19.5,-2.8){\footnotesize$7$}
\put(23.5,-1){\footnotesize$1$}\put(20.7,-6.8){\footnotesize$5$}
\put(24.7,-6.8){\footnotesize$9$}\put(28,-1.5){\footnotesize$12$}
\put(32.7,-2.8){\footnotesize$4$}\put(26.7,-6.8){\footnotesize$6$}
\end{pspicture}\vspace{55pt}
\caption{A labeled NC-tree.}\label{f2} \vspace{-5pt}
\end{center}
\end{figure}

Our combinatorial interpretation of formula \eqref{eqn4} relies on
the $(l;r)$-representation of NC-trees introduced by Panholzer and
Prodinger \cite{PP}. Represent a NC-tree $T$ by a plane tree with
each edge labeled by $l$ or $r$ using the following rules: Label an
edge by $l$ if it is a descent; Otherwise, label it by $r$. See
Figure \ref{f1} for the $(l;r)$-representation of a NC-tree.
Briefly, we call an edge labeled by $l$ or $r$ an $l$-edge or an
$r$-edge respectively. It is obvious that a plane tree obtained in
this way has two properties: (i) the edges adjacent to the root are
always $r$-edges; (ii) for any internal vertex $v$, the vertices
planted at $v$ with $l$-edges are always to the left of the vertices
planted at $v$ with $r$-edges. In addition, these two properties
provide a necessary and sufficient condition for a plane tree to
become a NC-tree. Note that each $l$-edge in such a plane tree
corresponds to a descent. To construct the decomposition algorithm,
we still need the notion of labeled NC-trees. A \textit{labeled
NC-tree} of size $n$ is referred to the $(l;r)$-representation of a
NC-tree of size $n$ with the label set $[n+1]:=\{1,2,\ldots,n+1\}$.
See Figure \ref{f2} for a labeled NC-tree. Clearly, the number of
labeled NC-trees of size $n$ equals $(n+1)!$ times the number of
NC-trees of size $n$.


\section{A decomposition algorithm for labeled
NC-trees}\label{section2}

The purpose of this section is to give a decomposition algorithm for
labeled NC-trees that leads to a combinatorial interpretation of
formula \eqref{eqn4}. Our algorithm is a generalization of the
bijective algorithm for plane trees in \cite{Chen99}. It should be
pointed out that Chen \cite{Chen99} established a more general
bijection for trees.

A \textit{planted tree} is a rooted tree with root degree one, and a
\textit{planted edge} is the edge adjacent to the root. Define a
planted tree \textit{$r$-unique} if the planted edge is an $r$-edge
and all the other edges are $l$-edges.

We begin to deal with a labeled NC-tree $T$ of size $n$ with $k$
$l$-edges. Remind that the label set of $T$ is $[n+1]$. The first
procedure of our algorithm is to decompose $T$ into a forest $F$ on
$[2n-k]$, where $F$ is composed of $n-k$ $r$-unique planted trees.

\noindent{\bf Decomposition algorithm:}
\begin{itemize}
\item[Step 1.] Find an $r$-unique planted subtree of $T$ with planted edge $(u,v)$
such that $v$ is the rightmost child of $u$ and the original label
$i$ of $u$ is the smallest. Then we may obtain an $r$-unique planted
subtree with planted edge $(u,v)$.
\item[Step 2.]Remove the $r$-unique planted
subtree and relabel the vertex $u$ by $n+2$ in $T$. However, the
original label $i$ will be reused for later comparisons of vertices.
\item[Step 3.]Repeat the above steps for the remaining tree
and subsequently supply $n+3,n+4,\ldots,2n-k$ to relabel the
encountered vertex $u$.
\end{itemize}
\begin{figure}[h,t]
\begin{center}\vspace{60pt}%\hspace{-20pt}
\begin{pspicture}(100,0)(4,0)
\psset{unit=.3cm} \psline[linewidth=.5pt](25,7)(20,3)
\psline[linewidth=.5pt](25,7)(25,3)
\psline[linewidth=.5pt](25,7)(30,3)
\psline[linewidth=.5pt](20,3)(17,-1)
\psline[linewidth=.5pt](20,3)(20,-1)
\psline[linewidth=.5pt](20,3)(23,-1)
\psline[linewidth=.5pt](20,-1)(18,-5)
\psline[linewidth=.5pt](20,-1)(22,-5)
\psline[linewidth=.5pt](30,3)(27,-1)
\psline[linewidth=.5pt](30,3)(33,-1)
\psline[linewidth=.5pt](27,-1)(27,-5)
\pscircle*(25,7){.2}\pscircle*(20,3){.2}
\pscircle*(25,3){.2}\pscircle*(30,3){.2}
\pscircle*(17,-1){.2}\pscircle*(20,-1){.2}
\pscircle*(23,-1){.2}\pscircle*(18,-5){.2}
\pscircle*(22,-5){.2}\pscircle*(27,-1){.2}
\pscircle*(33,-1){.2}\pscircle*(27,-5){.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(21.8,5){\footnotesize$r$}\put(24.4,5){\footnotesize$r$}
\put(28,5){\footnotesize$r$}\put(17.5,.5){\footnotesize$l$}
\put(19.5,.5){\footnotesize$l$}\put(22.2,.5){\footnotesize$l$}
\put(18.5,-3){\footnotesize$l$}\put(21.2,-3){\footnotesize$r$}
\put(27.5,.5){\footnotesize$r$}\put(30.8,.5){\footnotesize$r$}
\put(26.3,-3){\footnotesize$l$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(24.8,7.4){\footnotesize$5$}\put(19,3){\footnotesize$7$}
\put(25.5,3){\footnotesize$1$}\put(30.5,3){\footnotesize$12$}
\put(16.7,-2.2){\footnotesize$6$}\put(20.4,-1.8){\footnotesize$8$}
\put(23.5,-1){\footnotesize$11$}\put(17.7,-6.2){\footnotesize$4$}
\put(21.7,-6.2){\footnotesize$3$}\put(26.2,-1){\footnotesize$9$}
\put(33.5,-1){\footnotesize$10$}\put(26.7,-6.2){\footnotesize$2$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(36,-1){$\Longleftrightarrow$}\put(36.4,0){(a)}
\end{pspicture}
\begin{pspicture}(100,0)(-8,1)
\psset{unit=.35cm} \psline[linewidth=.5pt](0,4)(0,1)
\pscircle*(0,4){.2}\pscircle*(0,1){.2} \put(0.4,2){\footnotesize$r$}
\put(-.5,4.5){\footnotesize$8$}\put(-.4,-.5){\footnotesize$3$}
\psline[linewidth=.5pt](2.5,4)(2.5,1)
\pscircle*(2.5,4){.2}\pscircle*(2.5,1){.2}
\put(2.9,2){\footnotesize$r$}
\put(2,4.5){\footnotesize$12$}\put(2,-.5){\footnotesize$10$}
\psline[linewidth=.5pt](6,6)(6,3) \psline[linewidth=.5pt](6,3)(6,0)
\pscircle*(6,6){.2}\pscircle*(6,3){.2}\pscircle*(6,0){.2}
\put(6.4,4){\footnotesize$r$}\put(6.4,1){\footnotesize$l$}
\put(6,6.5){\footnotesize$14^*$}\put(6.5,2.7){\footnotesize$9$}
\put(6.5,-.7){\footnotesize$2$}
\psline[linewidth=.5pt](9.5,4)(9.5,1)
\pscircle*(9.5,4){.2}\pscircle*(9.5,1){.2}
\put(9.9,2){\footnotesize$r$}
\put(9.2,4.5){\footnotesize$5$}\put(9,-.5){\footnotesize$15^*$}
\psline[linewidth=.5pt](12,4)(12,1)
\pscircle*(12,4){.2}\pscircle*(12,1){.2}
\put(12.4,2){\footnotesize$r$}
\put(11.7,4.5){\footnotesize$16^*$}\put(11.9,-.5){\footnotesize$1$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\psline[linewidth=.5pt](18,7)(18,4)
\psline[linewidth=.5pt](18,4)(16,2)
\psline[linewidth=.5pt](18,4)(18,2)
\psline[linewidth=.5pt](18,4)(20,2)
\psline[linewidth=.5pt](18,2)(18,-1)
\pscircle*(18,7){.2}\pscircle*(18,4){.2}\pscircle*(16,2){.2}
\pscircle*(18,2){.2}\pscircle*(20,2){.2}\pscircle*(18,-1){.2}
\put(18.4,7){\footnotesize$17^*$}\put(18.3,4){\footnotesize$7$}\put(15.7,1){\footnotesize$6$}
\put(18.2,1.3){\footnotesize$13^*$}\put(20.4,2){\footnotesize$11$}\put(18.4,-1){\footnotesize$4$}
\put(18.4,5){\footnotesize$r$}\put(16.2,2.6){\footnotesize$l$}\put(17.6,2.6){\footnotesize$l$}
\put(19.7,2.6){\footnotesize$l$}\put(18.4,.3){\footnotesize$l$}
\put(12,-3.5){$\Updownarrow$}\put(13,-3.5){(b)}
\end{pspicture}\vspace{-23pt}
\begin{pspicture}(15,5.25)(-6,0)
\psset{unit=.35cm} \psline[linewidth=.5pt](0,6)(0,1)
\pscircle*(0,6){.2}\pscircle*(0,1){.2} \put(0.4,3){\footnotesize$r$}
\put(-.5,6.5){\footnotesize$8$}\put(-.4,-.5){\footnotesize$3$}
\psline[linewidth=.5pt](2.5,6)(2.5,1)
\pscircle*(2.5,6){.2}\pscircle*(2.5,1){.2}
\put(2.9,3){\footnotesize$r$}
\put(2,6.5){\footnotesize$12$}\put(2,-.5){\footnotesize$10$}
\psline[linewidth=.5pt](5,6)(5,1)
\pscircle*(5,6){.2}\pscircle*(5,1){.2} \put(5.4,3){\footnotesize$r$}
\put(4.7,6.5){\footnotesize$5$}\put(4.5,-.5){\footnotesize$15^*$}
\psline[linewidth=.5pt](7.5,6)(7.5,1)
\pscircle*(7.5,6){.2}\pscircle*(7.5,1){.2}
\put(7.9,3){\footnotesize$r$}
\put(7,6.5){\footnotesize$16^*$}\put(7.2,-.5){\footnotesize$1$}
\psline[linewidth=.5pt](10,6)(10,1)
\pscircle*(10,6){.2}\pscircle*(10,1){.2}
\put(10.4,3){\footnotesize$r$}
\put(10,6.5){\footnotesize$14^*$}\put(9.5,-.5){\footnotesize$19^{\#}$}
\psline[linewidth=.5pt](12.5,6)(12.5,1)
\pscircle*(12.5,6){.2}\pscircle*(12.5,1){.2}
\put(12.9,3){\footnotesize$r$}
\put(12,6.5){\footnotesize$17^*$}\put(12.2,-.5){\footnotesize$22^{\#}$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\psline[linewidth=.5pt](15,6)(15,1)
\pscircle*(15,6){.2}\pscircle*(15,1){.2}
\put(15.4,3){\footnotesize$l$}
\put(14.7,6.5){\footnotesize$7$}\put(14.7,-.5){\footnotesize$11$}
\psline[linewidth=.5pt](17.5,6)(17.5,1)
\pscircle*(17.5,6){.2}\pscircle*(17.5,1){.2}
\put(17.9,3){\footnotesize$l$}
\put(17.2,6.5){\footnotesize$9$}\put(17.2,-.5){\footnotesize$2$}
\psline[linewidth=.5pt](20,6)(20,1)
\pscircle*(20,6){.2}\pscircle*(20,1){.2}
\put(20.4,3){\footnotesize$l$}
\put(19.7,6.5){\footnotesize$13^*$}\put(19.7,-.5){\footnotesize$4$}
\psline[linewidth=.5pt](22.5,6)(22.5,1)
\pscircle*(22.5,6){.2}\pscircle*(22.5,1){.2}
\put(22.9,3){\footnotesize$l$}
\put(22.2,6.5){\footnotesize$18^{\#}$}\put(22.2,-.5){\footnotesize$20^{\#}$}
\psline[linewidth=.5pt](25,6)(25,1)
\pscircle*(25,6){.2}\pscircle*(25,1){.2}
\put(25.4,3){\footnotesize$l$}
\put(24.7,6.5){\footnotesize$21^{\#}$}\put(24.7,-.5){\footnotesize$6$}
\end{pspicture}
 \vspace{0pt} \caption{The decomposition algorithm of
a labeled NC-tree.}\label{figure2}
\end{center}
\end{figure}
Figure \ref{figure2} (a) is an illustration of the first procedure
of the decomposition algorithm. The second procedure of our
algorithm is to decompose $F$ into a set $M$ of $n$ matches on
$[2n]$, where a match is a rooted tree with two vertices.

\begin{itemize}
\item[Step 4.] Find an $l$-edge $(u,v)$ such that $v$ is the rightmost child of $u$,
$v$ is a leaf and the label $i$ of $u$ is the smallest. Then we
obtain a match with root $u$.
\item[Step 5.] Remove the match and relabel the vertex $u$ by
$2n-k+1$ in $F$. However, the label $i$ is still used for later
comparisons of vertices.
\item[Step 6.] Repeat Step 4 and Step 5 for the remaining forest and  subsequently supply $2n-k+2,2n-k+3,\ldots,2n$ to relabel the
encountered vertex $u$.
\end{itemize}
See Figure \ref{figure2} (b) for an example of the second procedure.
It is clear that for $k=0$, the decomposition algorithm for a
labeled NC-tree with $k$ descents reduces to the algorithm for a
plane tree introduced by Chen \cite{Chen99}.

We call a match labeled by $r$ or $l$ an \textit{$r$-match} or
\textit{$l$-match} respectively. For $k\geq1$, the resulting $n$
matches on $[2n]$ have the following properties:
\begin{itemize}
\item[(A1)] There are $k$ $l$-matches and $n-k$ $r$-matches;
\item[(A2)] The labels for the roots of $r$-matches are
in the set $[2n-k]$;
\item[(A3)] The label $2n$ is a leaf of an
$r$-match.
\end{itemize}
Let $\mathcal{M}_{n,k}:=\{M| M\ \mbox{is a set of}\ n\ \mbox{matches
on}\  [2n]\ \mbox{satisfying conditions (A1)-(A3)}\}.$ Now we are
ready to establish the inverse of the decomposition algorithm.
Specifically, for $M\in\mathcal{M}_{n,k}$, we need to merge $M$ into
a labeled NC-tree.

First, rewrite the label set $[2n]$ of $M$ by the marked set
$\{1,2,\ldots,n+1,(n+2)^*,\ldots,(2n-k)^*,(2n-k+1)^{\#},\ldots,(2n)^{\#}\}$.
A vertex labeled by a mark $*$ or a mark $\#$ is called a $*$-marked
or a $\#$-marked vertex respectively.

\noindent{\bf Merging algorithm:}
\begin{itemize}
\item[Step 1.] Find the tree $T$ without $r$-edge and $\#$-marked vertex, such that the root $i$ of $T$ is the smallest.
\item[Step 2.] Find the tree $T^{\#}$ with the smallest
$\#$-marked vertex. Let $j^{\#}$ be this marked vertex.
\item[Step 3.] If $j^{\#}$ is the root of $T^{\#}$, then merge $T$ with $T^{\#}$ by identifying $i$ and $j^{\#}$,
put the subtrees of $T$ to the right of $T^{\#}$, and keep $i$ as
the label of the combined vertex. This operation is called a
\textit{horizontal merge}. If $j^{\#}$ appears as a leaf of
$T^{\#}$, then replace $j^{\#}$ by $T$ in $T^{\#}$. This operation
is called a \textit{vertical merge}. See Figure \ref{figure3}.
\item[Step 4.] Repeat the above steps until no $\#$-marked vertex left.
\item[Step 5.] Find the tree $T$ without $*$-marked vertex and the root $i$ of $T$ is the smallest.
\item[Step 6.] Find the tree $T^{*}$ with the smallest
$*$-marked vertex $j^{*}$. If $j^{*}$ is the root of $T^{*}$, then
merge $T$ with $T^{*}$ by applying the horizontal merge. If $j^{*}$
appears as a leaf of $T^{*}$, then merge $T$ with $T^{*}$ by
applying the vertical merge.
\item[Step 7.] Repeat Step 5 and Step 6 until we get a labeled
NC-tree.
\end{itemize}

\begin{figure}[h,t]
\begin{center}\vspace{60pt}%\hspace{-20pt}
\begin{pspicture}(80,0)(3,0)
\psset{unit=.23cm} \psline[linewidth=.5pt](25,7)(25,1)
\pscircle*(25,7){.2}\pscircle*(25,1){.2}\put(25.4,7.5){$j^{\#}$}
\put(25,-1.5){$T^{\#}$}\put(27,4){$+$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\psline[linewidth=.5pt](30,1)(30,4.5)
\psline[linewidth=.5pt](30,4.5)(30,8) \pscircle*(30,1){.2}
\pscircle*(30,4.5){.2}\pscircle*(30,8){.2}\put(30.4,8.5){$i$}
\psline[linewidth=.5pt](30,8)(33,5)
\psline[linewidth=.5pt](33,5)(33,1)\pscircle*(33,5){.2}
\pscircle*(33,1){.2}\put(31,-1.5){$T$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(35.8,4){$\Rightarrow$}\pscircle*(39,5){.2}\psline[linewidth=.5pt](42,8)(39,5)
\psline[linewidth=.5pt](42,1)(42,4.5)
\psline[linewidth=.5pt](42,4.5)(42,8) \pscircle*(42,1){.2}
\pscircle*(42,4.5){.2}\pscircle*(42,8){.2}\put(42.4,8.5){$i$}
\psline[linewidth=.5pt](42,8)(45,5)
\psline[linewidth=.5pt](45,5)(45,1)\pscircle*(45,5){.2}
\pscircle*(45,1){.2}
%%%%%%%%%%%%%%%%%%%%
\psline[linewidth=.5pt](55,7)(55,1)
\pscircle*(55,7){.2}\pscircle*(55,1){.2}\put(55.4,.5){$j^{\#}$}
\put(55,-1.5){$T^{\#}$}\put(57,4){$+$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \psline[linewidth=.5pt](62,7)(60,2)
\psline[linewidth=.5pt](62,7)(64,2) \pscircle*(62,7){.2}
\pscircle*(60,2){.2}\pscircle*(64,2){.2}\put(62.4,7.5){$i$}
\put(61.6,-1){$T$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(65.8,4){$\Rightarrow$} \psline[linewidth=.5pt](70,7)(70,3.5)
\psline[linewidth=.5pt](70,3.5)(68,.5)
\psline[linewidth=.5pt](70,3.5)(72,.5)\pscircle*(70,7){.2}
\pscircle*(70,3.5){.2}\pscircle*(68,.5){.2}\pscircle*(72,.5){.2}
\put(70.5,3.5){$i$}
\end{pspicture}
\vspace{-5pt} \caption{A horizontal merge and a vertical
merge.}\label{figure3}
\end{center}
\end{figure}


Relying on the above algorithms, we arrive at the following result.
\begin{theorem}\label{theorem1}
The decomposition algorithm and the merging algorithm are inverse to
each other. Consequently, for $k\geq1$, there is a bijection between
the set of labeled NC-trees of size $n$ with $k$ descents and the
set $\mathcal{M}_{n,k}$.
\end{theorem}

The proof of Theorem \ref{theorem1} is elementary but tedious, and
we present it in Appendix A.

\begin{proof}[Combinatorial proof of Theorem {\rm\ref{theorem2}}]

A NC-tree of size $n$ with $0$ descent reduces to a plane tree with
$n$ edges. It is well known that the set of plane trees of $n$ edges
is counted by the $n$-th Catalan number, see, for example,
\cite{Stan99}. Hence, the formula (\ref{eqn4}) is clear. We only
need to confirm \eqref{eqn4} for $k\geq1$. Keep in mind that the
number of labeled NC-trees of size $n$ with $k$ descents equals
$(n+1)!$ times the number of NC-trees of size $n$ with $k$ descents.
By Theorem \ref{theorem1}, it is equivalent to prove the following
expression
\begin{eqnarray}\label{eqn3}
|\mathcal{M}_{n,k}|=(n+1)!N_{n,k}=\frac{(n+1)!}{n}{n-1+k\choose
n-1}{2n-k\choose n+1}.
\end{eqnarray}
Note that the set of matches in $\mathcal{M}_{n,k}$ satisfies
conditions (A1)--(A3). Formula (\ref{eqn3}) holds since (i) there
are ${2n-k\choose n-k}$ ways to choose $n-k$ labels from $[2n-k]$
for the roots of $r$-matches, (ii) there are ${n-k\choose 1}$ ways
to choose a label to match $2n$ for an $r$-match, (iii) there are
${n+k-1\choose k}$ ways to choose $k$ labels from the remaining
label set for the roots of $l$-matches, and (iv) there are $(n-1)!$
ways to arrange the remaining labels for the leaves of the matches.
This gives the number
\[{2n-k\choose n-k}{n-k\choose 1}{n+k-1\choose k}(n-1)!,\]
which equals the right hand side of (\ref{eqn3}).
\end{proof}

Observe that in the  merging algorithm, a leaf with an unmarked
label in $M$ is still a leaf in the corresponding labeled NC-tree.
We may derive a refined formula on NC-trees with respect to the
number of descents and the number of leaves.

\begin{theorem}
For $k\geq1$, the number of NC-trees of size $n$ with $k$ descents
and $i$ leaves is equal to
\begin{eqnarray}\label{eqn5}
\frac{1}{n}\sum_{t=0}^{n-k}{n\choose t-1}{n-k\choose t}{n+1-t\choose
i}{k+t-2\choose n-1-i}.
\end{eqnarray}
\end{theorem}

\begin{proof}[Proof.] The proof is similar as Theorem \ref{theorem2}, and we give a sketch. Note that a labeled NC-tree of size
$n$ with $k$ descents and $i$ leaves corresponds to a set of $n$
matches $M\in\mathcal{M}_{n,k}$ with $i$ unmarked leaves. Consider
the set of $M$ in $\mathcal{M}_{n,k}$ with exactly $i$ unmarked
leaves and $t$ $r$-matches with unmarked roots, which is counted by
\begin{eqnarray*}
{n+1\choose t}{n-k-1\choose n-k-t}{n-k\choose 1}{n+1-t\choose
i}{k+t-2\choose n-1-i}(n-1)!.
\end{eqnarray*}
By summing over $t$, we derive that the number of labeled NC-trees
of size $n$ with $k$ descents and $i$ leaves is
\begin{eqnarray*}
&&\sum_{t=0}^{n-k}{n+1\choose t}{n-k-1\choose
n-k-t}{n-k\choose 1}{n+1-t\choose i}{k+t-2\choose n-1-i}(n-1)!\\
&&=\frac{(n+1)!}{n}\sum_{t=0}^{n-k}{n\choose t-1}{n-k\choose
t}{n+1-t\choose i}{k+t-2\choose n-1-i}.
\end{eqnarray*}
This implies expression \eqref{eqn5}.
\end{proof}

We remark that for $k=0$, the number of NC-trees of size $n$ with
$k$ descents and $i$ leaves is given by the Narayana number, see
\cite{Deut-1999}. The formula \eqref{eqn5} is also a refinement of a
formula obtained by Flajolet and Noy \cite[Theorem 1]{FN}.

By arranging the matches in $M\in \mathcal{M}_{n,k}$ in terms of the
increasing order of their leaves, we obtain a sequence on the roots
of these $n$ matches. Assume that the label for the root of an
$r$-match is colored white, while the label for the root of an
$l$-match is colored black and written in boldface. Therefore, $M$
can be represented by a bicolored sequence consisting of $n$
distinct integers such that
\begin{itemize}
\item[(B1)] there are $n-k$ white elements that belong to the
set $[2n-k]$,
\item[(B2)] there are $k$ black elements that belong to the set
$[2n-1]$,
\item[(B3)] the last element is white.
\end{itemize}
For example, the corresponding bicolored sequence for the labeled
NC-tree in Figure \ref{figure2} is
$(16,\textbf{9},8,\mathbf{13},\mathbf{21},12,\mathbf{7},5,14,\mathbf{18},17).$

Denote $\mathcal{P}_{n,k}$ the set of bicolored sequences satisfying
conditions (B1)--(B3). It is straightforward to obtain the following
correspondence between labeled NC-trees and the bicolored sequences.

\begin{theorem}\label{theorem3}
For $k\geq1$, there is a bijection between labeled NC-tree of size
$n$ with $k$ descents and the set $\mathcal{P}_{n,k}$.
\end{theorem}





\section{A bijective proof of Question \ref{question1}}

In this section we present a bijective proof of Question
\ref{question1}. To describe our bijection, we first notice that it
is equivalent to construct  a bijection between the set of labeled
NC-trees of size $2k+1$ with $k$ $l$-edges and the set of labeled
NC-trees of size $2k+1$ with $k-1$ $l$-edges. Using Theorem
\ref{theorem3}, it remains to give a one-to-one correspondence
between $\mathcal{P}_{2k+1,k}$ and $\mathcal{P}_{2k+1,k-1}$.

%Recall that a bicolored permutation $\pi$ in $\mathcal{P}_{2k+1,k}$
%satisfies (1) it has $k+1$ white elements, which are in the set
%$\{1,2,\ldots,3k+2\}$, (2) it has $k$ black elements, which are in
%the set $\{1,2,\ldots,4k+1\}$, (3) the last element is a white
%element. A bicolored permutation $\sigma$ in
%$\mathcal{P}_{2k+1,k-1}$ satisfies (1) it has $k+2$ white elements,
%which are in the set $\{1,2,\ldots,3k+3\}$, (2) it has $k-1$ black
%elements, which are in the set $\{1,2,\ldots,4k+1\}$, (3) the last
%element is a white element.

Let $\mathcal{A}_{2k+1,k}$ denote the set of bicolored sequences
$\pi$ in $\mathcal{P}_{2k+1,k}$ such that a white element $i$ is
underlined and a black element $j$ is double underlined. For
example,
$$(16,\textbf{9},8,\underline{\underline{\mathbf{13}}},\mathbf{21},12,\mathbf{7},\underline{5},14,\mathbf{18},17)$$
belongs to $\mathcal{A}_{11,5}$. By definition, we have
\begin{eqnarray}
|\mathcal{A}_{2k+1,k}|=(k+1)k|\mathcal{P}_{2k+1,k}|.
\end{eqnarray}
Let $\mathcal{B}_{2k+1,k-1}$ be the set of bicolored sequences
$\sigma$ in $\mathcal{P}_{2k+1,k-1}$ such that (i) a white element
$i$ is underlined, (ii) a white element $j$ different from $i$ is
double underlined, (iii) neither $i$ nor $j$ is the last white
element in $\sigma$. For example,
$$(16,\textbf{9},8,\underline{13},\mathbf{21},\underline{\underline{12}},\mathbf{7},5,14,\mathbf{18},17)$$
belongs to $\mathcal{B}_{11,4}$. It follows that
\begin{eqnarray}
|\mathcal{B}_{2k+1,k-1}|=(k+1)k|\mathcal{P}_{2k+1,k-1}|.
\end{eqnarray}

We proceed to construct a bijection
$\Phi:\mathcal{A}_{2k+1,k}\rightarrow\mathcal{B}_{2k+1,k-1}$, which
relies on the partition of $\mathcal{A}_{2k+1,k}$ and
$\mathcal{B}_{2k+1,k-1}$. Without loss of generality, we may assume
that the elements in an integer set are  arranged in the increasing
order. As mentioned above, the underlined and double underlined
elements are always denoted by $i$ and $j$ respectively. Now we need
to consider five cases.

\noindent \textit{Case 1.} $\phi_1:S_1\rightarrow T_1$, where
\begin{itemize}
\item $S_1$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that $i$ is not the last white element
and $j<3k+3$,

\item $T_1$ is the set
of bicolored sequences $\sigma$ in $\mathcal{B}_{2k+1,k-1}$ such
that $3k+3$ is not a white element in $\sigma$.
\end{itemize}

For $\pi\in S_1$, $\phi_1(\pi)$ can be generated from $\pi$ by
changing the black element $j$ to a white element $j$. For example,
$\pi=(16,\textbf{9},8,\underline{\underline{\mathbf{13}}},\mathbf{21},\underline{12},\mathbf{7},5,14,\mathbf{18},17)$
in $\mathcal{A}_{11,5}$ belongs to $S_1$. Then $\phi_1(\pi)=
(16,\textbf{9},8,\underline{\underline{13}},\mathbf{21},\underline{12},\mathbf{7},5,14,\mathbf{18},17).$


\noindent \textit{Case 2.} $\phi_2:S_2\rightarrow T_2$, where
\begin{itemize}
\item $S_2$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that $i$ is not the last white element
and $j=3k+3$,

\item $T_2$ is the set of bicolored sequences $\sigma$ in
$\mathcal{B}_{2k+1,k-1}$ such that $3k+3$ is a white element but not
the last in $\sigma$ and $j=3k+3$.
\end{itemize}

For $\pi\in S_2$, $\phi_2(\pi)$ can be generated from $\pi$ by
changing the black element $3k+3$ to a white element $3k+3$. For
example,
$\pi=(16,\textbf{9},\underline{8},\mathbf{13},\mathbf{21},12,\mathbf{7},5,14,\underline{\underline{\mathbf{18}}},17)$
in $\mathcal{A}_{11,5}$ belongs to $S_2$. Then $\phi_2(\pi)=(
16,\textbf{9},\underline{8},\mathbf{13},\mathbf{21},12,\mathbf{7},5,14,\underline{\underline{18}},17).$


\noindent \textit{Case 3.} $\phi_3:S_3\rightarrow T_3$, where
\begin{itemize}
\item $S_3$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that $3k+3$ is an element in $\pi$ and
$i$ is the last white element,

\item $T_3$ is the set of bicolored sequences $\sigma$ in
$\mathcal{B}_{2k+1,k-1}$ such that $3k+3$ is the last white element
in $\sigma$.
\end{itemize}

For $\pi\in S_3$, assume that $j$ is the $m$-th black element in
$\pi$. This implies that $1\leq m\leq k$. Then $\phi_3(\pi)$ can be
generated from $\pi$ by the following procedures:
\begin{itemize}
\item[] Step 1. Remove the double underline from $j$ to the $m$-th white
element;

\item[]Step 2. Change the black element $3k+3$ to a white element $3k+3$;

\item[]Step 3. Exchange the positions of $3k+3$ and $i$, where $i$ is still
underlined.
\end{itemize}
For example,
$\pi=(16,\textbf{9},8,\mathbf{13},12,\mathbf{18},\underline{\underline{\mathbf{7}}},5,14,\mathbf{21},\underline{17})$
in $\mathcal{A}_{11,5}$ belongs to $S_3$. Then
$\phi_3(\pi)=(16,\textbf{9},8,\mathbf{13},12,\underline{17},\mathbf{7},\underline{\underline{5}},14,\mathbf{21},18)$.


\noindent \textit{Case 4.} $\phi_4:S_4\rightarrow T_4$, where
\begin{itemize}
\item $S_4$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that
\begin{itemize}
\item $3k+3$ is not an element in $\pi$,
\item $i$ is the last white element,
\item $j$ is the $m$-th element in the set $([4k+1]-E(\pi)-\{3k+3\})\cup
\{j\}$ with $1\leq m\leq k$, where ${E(\pi)}$ is the set of elements
in $\pi$,
\end{itemize}

\item $T_4$ is the set of bicolored sequences $\sigma$ in
$\mathcal{B}_{2k+1,k-1}$ such that $3k+3$ is a white element but not
the last in $\sigma$ and $i=3k+3$.
\end{itemize}

For $\pi\in S_4$, $\phi_4(\pi)$ can be generated from $\pi$ by the
following procedures:
\begin{itemize}
\item[]Step 1. Remove the double underline from $j$ to the $m$-th white
element;

\item[]Step 2. Replace the black element $j$ by a white element $3k+3$;

\item[]Step 3. Remove the underline from $i$ to $3k+3$.
\end{itemize}
For example,
$\pi=(16,\textbf{9},8,\mathbf{13},12,\mathbf{19},\underline{\underline{\mathbf{3}}},2,14,\mathbf{21},\underline{17})$
is in $\mathcal{A}_{11,5}$. By definition, $k=5$ and
$([4k+1]-E(\pi)-\{3k+3\})\cup \{j\}=\{1,3,4,5,6,7,10,11,15,20\}$. It
follows that $m=2$ and $1\leq m\leq k$. One can verify that $\pi$
belongs to $S_4$. Then
$\phi_4(\pi)=(16,\textbf{9},\underline{\underline{8}},\mathbf{13},12,\mathbf{19},\underline{18},2,14,\mathbf{21},17).$

\noindent \textit{Case 5.} $\phi_5:S_5\cup S_6\cup S_7\rightarrow
T_5$, where

\begin{itemize}
\item $S_5$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that $3k+3$ is an element in $\pi$, $i$
is not the last white element and $j>3k+3$,

\item $S_6$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that  $3k+3$ is not an element in $\pi$,
$i$ is not the last white element and $j>3k+3$,

\item $S_7$ is the set of bicolored sequences $\pi$ in
$\mathcal{A}_{2k+1,k}$ such that
\begin{itemize}
\item $3k+3$ is not an element in $\pi$,

\item $i$ is the last white element,

\item  $j$ is the $m$-th element in the set
$([4k+1]-E(\pi)-\{3k+3\})\cup \{j\}$ with $k+1\leq m\leq 2k$,
\end{itemize}

\item $T_5$ is the set of bicolored sequences $\sigma$ in
$\mathcal{B}_{2k+1,k-1}$ such that $3k+3$ is a white element but not
the last in $\sigma$, $i<3k+3$ and $j<3k+3$.
\end{itemize}

For $\pi\in S_5\cup S_6\cup S_7$, we have the following three cases.
\begin{itemize}

\item[1.] If $\pi\in S_5$, assume that
$j$ is $m$-th element in $\pi$ greater than $3k+3$. Then
$\phi_5(\pi)$ can be generated from $\pi$ by the following
procedures:
\begin{itemize}
\item[Step 1.] Change the black element $3k+3$ to a white element $3k+3$;
\item[Step 2.] Remove the double underline from $j$ to the $m$-th white
element, except for $i$ and $3k+3$.
\end{itemize}
 For example,
$\pi=(16,\textbf{9},8,\mathbf{13},\underline{\underline{\mathbf{21}}},12,\mathbf{7},\underline{5},14,\mathbf{18},17)$
in $\mathcal{A}_{11,5}$ belongs to $S_5$. One sees that $m=1$. Then
$\phi_5(\pi)=(\underline{\underline{16}},\textbf{9},8,\mathbf{13},\mathbf{21},12,\mathbf{7},\underline{5},14,18,17).$


\item[2.] If $\pi\in S_6$, let $B$ denote the set of elements in $\pi$,
except for $j$, greater than $3k+3$. Assume that $j$ is the $m$-th
element in the set $\{3k+4,3k+5,\ldots,4k+1\}-B$. Then $\phi_5(\pi)$
can be generated from $\pi$ by the following procedures:
\begin{itemize}
\item[Step 1.] Replace the black element $j$ by a white element
$3k+3$;

\item[Step 2.] Remove the double underline to the $(m+|B|)$-th white
element, except for $i$ and $3k+3$.
\end{itemize}
For example,
$\pi=(16,\textbf{9},\underline{8},\mathbf{13},\underline{\underline{\mathbf{20}}},12,\mathbf{7},5,14,\mathbf{21},17)$
in $\mathcal{A}_{11,5}$ belongs to $S_6$. By definition, $B=\{21\}$,
$\{3k+4,3k+5,\ldots,4k+1\}-B=\{19,20\}$, $m=2$ and $|B|=1$. Hence,
$\phi_5(\pi)=(16,\textbf{9},\underline{8},\mathbf{13},18,12,\mathbf{7},\underline{\underline{5}},14,\mathbf{21},17).$


\item[3.] If $\pi\in S_7$, $\phi_5(\pi)$ is generated from $\pi$ by the
following procedures:

\begin{itemize}
\item[Step 1.] Remove the underline from $i$ to the $(m-k)$-th white
element;

\item[Step 2.] Replace the black element $j$ by a white element
$3k+3$;

\item[Step 3.] Remove the double underline to the $(k-1)$-th white element,
except for the underlined white element and $3k+3$.
\end{itemize}
For example,
$\pi=(16,\textbf{9},8,\mathbf{13},12,\mathbf{19},\underline{\underline{\mathbf{15}}},5,14,\mathbf{21},\underline{17})$
is in $\mathcal{A}_{11,5}$. By definition, $k=5$,
$([4k+1]-E(\pi)-\{3k+3\})\cup \{j\}=\{1,2,3,4,6,7,10,11,15,20\}$ and
thus $m=9$, which implies that $k+1\leq m\leq 2k$. It follows that
$\pi$ belongs to $S_7$. Therefore
$\phi_5(\pi)=(16,\textbf{9},8,\mathbf{13},12,\mathbf{19},18,\underline{5},\underline{\underline{14}},\mathbf{21},17).$
\end{itemize}

It is easy to see that (i) $S_i\cap S_j=\varnothing$ holds for
$1\leq i\neq j\leq 7$, (ii) $T_i\cap T_j=\varnothing$ holds for
$1\leq i\neq j\leq 5$, (iii)
$\mathcal{A}_{2k+1,k}=\bigcup_{i=1}^{7}S_i$, and (iv)
$\mathcal{B}_{2k+1,k-1}=\bigcup_{i=1}^{5}T_i$. Furthermore, it can
be checked that each map $\phi_i$ is bijective. Given
$\pi\in\mathcal{A}_{2k+1,k}$, it is natural to construct the
bijection $\Phi$ as follows
\begin{eqnarray*}
\Phi(\pi)=\left\{\begin{array}{cc}
           \phi_1(\pi),& if\ \pi\in S_1,  \\
           \phi_2(\pi),& if\ \pi\in S_2,  \\
           \phi_3(\pi),& if\ \pi\in S_3,  \\
           \phi_4(\pi),& if\ \pi\in S_4,  \\
           \phi_5(\pi),& if\ \pi\in S_5\cup S_6\cup S_7.
         \end{array}\right.
\end{eqnarray*}
This finishes the proof of Question \ref{question1}.

\vskip 3mm \noindent {\bf Acknowledgments.}

We would like to thank the referees for helpful suggestions to
improve the presentation. This work was supported by the National
Natural Science Foundation of China (Projects 11001073 and
11101116), the Natural Science Foundation of Hebei Province
(Projects A2012207001 and A2014208152), the One-Hundred Outstanding
Innovative Talents Scheme of Hebei Province Education Department(No.
BR2-231) and the Top Young-aged Talents Program of Hebei Province.

\appendix

\section*{Appendix A: The proof of Theorem \ref{theorem1}}

We shall follow the notation introduced in Section \ref{section2}.
To prove Theorem \ref{theorem1}, it is sufficient to show the
following two lemmas.

\begin{lemma}\label{lemma1}
Step 1 -- Step 4 in the merging algorithm and Step 4 -- Step 6 in
the decomposition algorithm are inverse to each other.
\end{lemma}

\begin{lemma}\label{lemma2}
Step 5 -- Step 7 in the merging algorithm and Step 1 -- Step 3 in
the decomposition algorithm are inverse to each other.
\end{lemma}

\begin{proof}[The proof of Lemma {\rm\ref{lemma1}}]
First, it is necessary to verify the feasibility of the algorithms.
Obviously, Step 4 -- Step 6 in the decomposition algorithm are
always feasible. It remains to confirm the feasibility of Step 1 --
Step 4 in the merging algorithm.


For $M\in\mathcal{M}_{n,k}$, note that $M$ contains $k$ trees
without an $r$-edge and $k$ $\#$-marked vertices. The merging
algorithm consists of $k$ merging operations successively by merging
the $k$ $\#$-marked vertices in their increasing order.


In order to show the validity of Step 1, we observe that each
merging operation decreases the number of trees without an $r$-edge
by 1 and the number of $\#$-marked vertices by 1. Then before the
$i$th ($1\leq i\leq k$) merging operation, the number of trees
without an $r$-edge and the number of $\#$-marked vertices are both
$k-i+1$. It follows that there will be at least one tree without an
$r$-edge and $\#$-marked vertices since $(2n)^{\#}$ belongs to an
$r$-match.


For the validity of Step 3, we need to show that all the $\#$-marked
vertices must appear either as a root or as a leaf. This is obtained
by observing that in our merging algorithm, the only trees with more
than one $\#$-marked vertex must be the match in $M$ with two
$\#$-marked vertices.


To complete the proof of Lemma \ref{lemma1}, it suffices to show
that
\begin{itemize}
\item[Claim 1.] if $M$ is a set of matches obtained from a
forest $F$ by applying Step 4 -- Step 6 of the decomposition
algorithm, then we can recover $F$ from $M$ by applying Step 1 --
Step 4 of the merging algorithm;
\item[Claim 2.] if $F$ is a forest obtained from a set of
matches $M$ by applying Step 1 -- Step 4 of the merging algorithm,
then we can recover $M$ from $F$ by applying Step 4 -- Step 6 of the
decomposition algorithm.
\end{itemize}
We only prove Claim 1 for brevity and similarity. Set $F\,'$ the
corresponding forest by applying Step 1 -- Step 4 of the merging
algorithm to $M$. Note that any $\#$-marked label in an $r$-match of
$M$ appears as a leaf. It follows that each $r$-match with
$\#$-marked label will be merged by adopting a vertical merge in the
merging algorithm, and the resulting tree is an $r$-unique planted
tree without $\#$-marked label. This implies that $F\,'$ is composed
of $r$-unique planted trees. To verify Claim 1, it suffices to show
that $F\,'=F$. Remind that the number of $l$-edges in $F$ is $k$ and
the number of trees in $F$ is $n-k$. We proceed by induction on the
number $k$.

If $k=1$, denote $F$ by $\{T_1,T_2,\ldots,T_{n-1}\}$, where $T_1$
contains the unique $l$-edge. It implies that $T_1$ is composed of
two edges. More precisely, an $l$-edge is attached under an $r$-edge
in $T_1$. In addition, any of $T_2,\ldots,T_{n-1}$ is an $r$-match.
By applying Step 4 -- Step 6 of the decomposition algorithm to $F$,
we get $M=\{T_{11},T_{12},T_2,\ldots,T_{n-1}\}$, where $T_{11}$ and
$T_{12}$ are the $l$-match and the $r$-match respectively decomposed
from $T_1$. Conversely, it is easy to see that $(2n)^{\#}$ is the
unique $\#$-marked label in $M$ and $(2n)^{\#}$ appears as the leaf
of $T_{12}$. Thus, by applying Step 1 -- Step 4 of the merging
algorithm, $T_{11}$ will be merged with $T_{12}$ by a vertical
merge. Clearly, this operation recovers $F$, that is, $F\,'=F$.

Assume that the result holds with $k$ replaced by $k-1$. Then if
there are $k$ $l$-edges in $F$, let $(i,j)$ be the first edge
decomposed from $F$ at the first running of Step 4 -- Step 6 in the
decomposition algorithm. Notice that $(i,j)$ is an $l$-edge, $j$ is
the rightmost child of $i$ and $j$ is a leaf. Let $F_1$ be the
forest obtained from $F$ by deleting the edge $(i,j)$ and the vertex
$j$. Besides, denote $M_1$ the corresponding set of matches by
applying Step 4 -- Step 6 of the decomposition algorithm to $F_1$.
One sees that there are $k-1$ $l$-edges in $F_1$. By the induction
hypothesis, we can recover $F_1$ from $M_1$ by applying Step 1 --
Step 4 of the merging algorithm.

In light of the decomposition algorithm, it is straightforward to
derive the following relations between $M$ and $M_1$.
\begin{itemize}
\item[(1)] $(i,j)$ is an $l$-match in $M$ but not in $M_1$;
\item[(2)] The set of other matches in $M$ is the same as $M_1$
if we replace the label $(2n-k+1)^{\#}$ in $M$ by $i$, and replace
the $\#$-marked labels in $M_1$ in increasing order by
$(2n-k+2)^{\#}$, $(2n-k+3)^{\#}$, $\ldots$, $(2n)^{\#}$
respectively.
\end{itemize}
Observe that $(i,j)$ is still the first edge encountered whenever
applying the merging algorithm to $M$ (This is implied by the fact
that all the $l$-matches without $\#$-marked vertex are obtained
from those leaves that are the rightmost child. Among such matches,
$(i,j)$ has the smallest root label). Furthermore, the first merge
step for $M$ is the merging of the match $(i,j)$ and the match with
the label $(2n-k+1)^{\#}$. Then clearly, the following merge steps
are the same as those for $M_1$. Moreover, at any step, $j$ is
always the rightmost child of $i$. It follows that the forest
$F\,'$, corresponding to $M$ by Step 1 -- Step 4 of the merging
algorithm, can be obtained from $F_1$ by attaching a rightmost child
$j$ to $i$. This gives $F\,'=F$.
\end{proof}

\begin{proof}[The proof of Lemma {\rm\ref{lemma2}}]
The feasibility of Step 1 -- Step 3 in the decomposition algorithm
is obvious. It is routine to check the feasibility of Step 5 -- Step
7 in the merging algorithm.

Before the first running of Step 5 -- Step 7 in the merging
algorithm, there are $n-k$ trees and $n-k-1$ $*$-marked vertices in
these trees. Thus there must be a tree without $*$-marked vertex.
After each merge, both the number of trees and the number of
$*$-marked vertices decrease by $1$. It means that we can always
find a tree without $*$-marked vertex at any step. Therefore, Step 5
-- Step 7 in the merging algorithm are feasible.

To complete the proof of Lemma \ref{lemma2}, it remains to show that
\begin{itemize}
\item[Claim 3.] if $F$ is a forest obtained from a
tree $T$ by applying Step 1 -- Step 3 of the decomposition
algorithm, then we can recover $T$ from $F$ by applying Step 5 --
Step 7 of the merging algorithm;
\item[Claim 4.] if $T$ is a tree obtained from a forest $F$ by
applying Step 5 -- Step 7 of the merging algorithm, then we can
recover $F$ from $T$ by applying Step 1 -- Step 3 of the
decomposition algorithm.
\end{itemize}
The proofs  of Claim 3 and Claim 4 are similar to that of Claim 1,
and we only present a sketch for the proof of Claim 3. Set $T\,'$
the corresponding tree by applying Step 5 -- Step 7 of the merging
algorithm to $F$. Since each tree in $F$ is an $r$-unique planted
tree, we eventually get a NC-tree $T\,'$ by adopting merging
algorithm. Now, it suffices to show $T\,'=T$. We proceed by
induction on the number of $r$-edges in $T$.

If there is only one $r$-edge in $T$, $T$ must be an $r$-unique
planted tree. In terms of the decomposition algorithm, $F$ contains
a unique tree $T$. Hence, we can recover $T$ from $F$ trivially.

For a general labeled NC-tree $T$, let $\widehat{T}$ be the first
$r$-unique planted subtree of $T$ encountered at the first running
of Step 1 -- Step 3 in the decomposition algorithm. Moreover, let
$(i,j)$ be the planted edge of $\widehat{T}$. Notice that $(i,j)$ is
an $r$-edge and $j$ is the rightmost child of $i$. Let $T_1$ be the
tree obtained from $T$ by deleting $\widehat{T}$ but keeping the
vertex $i$. It is clear that the number of $r$-edges in $T_1$
decreases by $1$. Denote $F_1$ the corresponding forest by applying
Step 1 -- Step 3 of the decomposition algorithm to $T_1$. By the
induction hypothesis, we can recover $T_1$ from $F_1$ by applying
Step 5 -- Step 7 of the merging algorithm.

One can check that the relations between $F$ and $F_1$ are
\begin{itemize}
\item[(1)] $\widehat{T}$ is an $r$-unique planted tree in $F$ but not in $F_1$;
\item[(2)] the set of other trees in $F$ is the same as $F_1$
if we replace the labels $(n+2)^{*}$ in $F$ by $i$, and replace the
$*$-marked labels in $F_1$ in increasing order by $(n+3)^{*}$,
$(n+4)^{*}$, $\ldots$, $(2n-k)^{*}$ respectively.
\end{itemize}
In addition, $\widehat{T}$ is still the first tree encountered
whenever applying the merging algorithm to $F$. Furthermore, the
first merge step for $F$ is the merging of $\widehat{T}$ and the
tree with the label $(n+2)^{*}$. After that, the merge steps are the
same as those for $F_1$. Finally, $T\,'$ can be obtained from $T_1$
by combining the vertex $i$ of $T_1$ and the vertex $i$ of
$\widehat{T}$ such that $j$ is the rightmost child of $i$, which
implies $T\,'=T$.
\end{proof}



\begin{thebibliography}{99}
\bibitem{Asin-Mans08}
A. Asinowski and T. Mansour, Dyck paths with coloured ascents,
\textit{European J. Combin.} 29 (2008) 1262--1279.

\bibitem{Chen99}
W.Y.C. Chen, A general bijective algorithm for trees, \textit{Proc.
Natl. Acad. Sci.} 87 (1990) 9635-9639.

\bibitem{CY}
W.Y.C. Chen and S.H.F. Yan, Noncrossing trees and noncrossing
graphs, \textit{Electron. J. Combin.} 13 (2006) \#N12.

\bibitem{Deut-1999}
E. Deutsch, Dyck path enumeration, \textit{Discrete Math.} 204
(1999) 167-202.

\bibitem{DN}
E. Deutsch and M. Noy, Statistics on non-crossing trees,
\textit{Discrete Math.} 254 (2002) 75-87.


\bibitem{FN}
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing
configurations, \textit{Discrete Math.} 204 (1999) 203-229.

\bibitem{Guo11}
A. Guo, Cyclic sieving phenomenon in non-crossing connected graphs,
\textit{Electron. J. Combin.} 18(1) (2011) \#P9.

\bibitem{DH}
D.S. Hough, Descents in noncrossing trees, \textit{Electron. J.
Combin.} 10 (2003) \#N13.

\bibitem{Klu12}
S. Kluge, The cyclic sieving phenomenon for non-crossing forests,
\textit{Electron. J. Combin.} 19(3) (2012) \#P1.

\bibitem{MN}
M. Noy, Enumeration of noncrossing trees on a circle,
\textit{Discrete Math.} 180 (1998) 301-313.

\bibitem{PP}
A. Panholzer and H. Prodinger, Bijections for ternary trees and
noncrossing trees, \textit{Discrete Math.} 250 (2002) 181-195.

\bibitem{Stan99}
R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge
University Press, Cambridge, New York, 1999.

\bibitem{Sun-Wang-2008}
Y. Sun and Z. Wang, Consecutive pattern avoidances in non-crossing
trees, \textit{Graphs Combin.} 26 (2010) 815--832.


\end{thebibliography}
\end{document}