\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amsmath,amsthm,amssymb,tikz,enumerate}
\usetikzlibrary{decorations.pathreplacing}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{epsf}

\usepackage[colorlinks=true,linkcolor=webgreen,filecolor=webbrown,citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
%\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}

\begin{center}
\vskip 1cm{\LARGE\bf The Boundary of Ordered Trees}
\vskip 1cm
\large
Dennis E. Davenport and Louis W. Shapiro\\ 
Mathematics Department\\
Howard University, Washington, DC\\
\href{mailto:dennis.davenport@howard.edu}{\tt dennis.davenport@howard.edu} \\
\href{mailto:lshapiro@howard.edu}{\tt lshapiro@howard.edu}\\
\ \\
Lara K. Pudwell\\
Department of Mathematics and Statistics\\ 
Valparaiso University, Valparaiso, IN\\
\href{mailto:lara.pudwell@valpo.edu}{\tt lara.pudwell@valpo.edu}\\
\ \\
Leon C. Woodson\\
Department of Mathematics\\ 
Morgan State University, Baltimore, MD\\
\href{mailto:leon.woodson@morgan.edu}{\tt leon.woodson@morgan.edu}
\end{center}

\vskip .2 in

\begin{abstract}
In this paper we compute the distribution of several statistics on the set of rooted ordered trees.  In particular, we determine the number of boundary edges, the number of singleton boundary edges, and the analogous values when edges may take on one of $k$ colors.
\end{abstract}


\section{Introduction}

In this paper we consider properties of trees.  A \emph{rooted ordered tree} is defined recursively as having a root and an ordered set of subtrees.  A tree with $n$ edges necessarily has $n+1$ vertices, so we may count trees according to either edges or vertices and obtain the same results.  Rooted ordered trees appear naturally as data structures in computer science, but they may also appear as models for real-world objects such as river networks or family trees.

In our investigation several sequences were found which were already in the Online Encyclopedia of Integer Sequences (OEIS) \cite{SLOE}; the A-numbers in this paper are from this source.

Much enumerative work has already been done with ordered trees.  The number of ordered trees with $n$ edges is $C_n=\frac{1}{n+1} \binom{2n}{n}$, the $n^{th}$ Catalan number. Recall that the generating function for the Catalan numbers is $C(z)=\sum_{n=0}^{\infty }{C_{n}z^{n}}$. It is well known that $C(z)=1+zC^2(z)=\frac{1}{1-zC(z)}$ and that $$C(z)=\frac{1-\sqrt{1-4z}}{2z}= 1+1z+2z^2+5z^3+14z^4+42z^5+132z^6+\cdots \text{(\seqnum{A000108}).}$$ We will denote $C(z)$ by $C$ when this causes no confusion.  A companion generating function is $B(z)=B=\sum_{n=0}^{\infty } \binom{2n}{n} z^{n}=1+2zBC=\frac{1}{1-2zC}=\frac{C}{1-zC^{2}}$. Here, $$B(z)=\frac{1}{\sqrt{1-4z}}=1+2z+6z^2+20z^3+70z^4+252z^5+924z^6+\cdots \text{(\seqnum{A000984}).}$$  It turns out that $B$ is the generating function for ordered trees with one marked vertex. This is immediate since a tree with $n$ edges has $n+1$ vertices and $\sum_{n=0}^{\infty }(n+1)C_{n}z^n=\sum_{n=0}^{\infty }(n+1)\frac{1}{n+1} \binom{2n}{n}z^{n}=\sum_{n=0}^{\infty } \binom{2n}{n} z^{n}=B$.  A related result is that the number of trees with a marked leaf (outdegree 0) has the generating function $\frac{B}{C}=\frac{B+1}{2}$.  A second companion generating function is the one for the Fine numbers, defined by $F(z)=F=\frac{C}{1+zC}=\frac{1}{1-z^{2}C^{2}}=1+1z^2+2z^3+6z^4+18z^5+57z^6+\cdots$ (\seqnum{A000957}) or equivalently $C=\frac{F}{1-zF}$. These three sequences are known to count a number of different combinatorial objects.  For example, the Catalan numbers have over 200 different combinatorial interpretations \cite{Stanley}.  The Fine numbers also count many things, including ordered trees with even root degree and Dyck paths with no hills \cite{DS01}.  These three sequences appear in relation to one another in several contexts \cite{DS01a, GKP, JZ03, S14}, and they appear in results throughout this paper as we consider specific characteristics of trees.

In particular, we are concerned with the boundaries of trees.  The \emph{right boundary} of an ordered tree is the rightmost path that emanates from the root and terminates at the rightmost leaf. The \emph{left boundary} is defined similarly. The \emph{boundary} of an ordered tree is the union of the left and right boundaries.  We measure the length of a boundary in terms of its number of distinct edges.  To illustrate the boundary, consider the ordered tree in Figure \ref{onetree}. The vertices are labeled to make the description easier. The path $a$, $b$, $e$, $h$ (the leftmost path emanating from the root, $a$, and terminating at the leftmost leaf, $h$) is the left boundary and the path $a$, $d$, $g$ is the right boundary. Together they make up the boundary of the tree. The left boundary has length 3, the right boundary has length 2, and the total boundary has length 5.

\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}[
  level distance=10mm,
  every node/.style={circle,inner sep=2pt,fill=black},
  level 1/.style={sibling distance=10mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=10mm}
]
\node[label=below:a] {} [grow=up]
  child {node[label=right:d] {}
	  child {node[label=right:g] {}}
    child {node[label=right:f] {}}
  }
	child {node[label=right:c] {}}
  child {node[label=right:b] {}
	  child {node[label=right:e] {}
	  	  child {node[label=right:i] {}}
        child {node[label=right:h] {}}
	  }
  };
\end{tikzpicture}
\end{center}
\caption{An ordered tree with 8 edges}
\label{onetree}
\end{figure}

In applications, the tree boundary may contain important information about the rest of a system.  If the ordered tree represents a family tree, the left boundary carries information about the chain of oldest descendants. If the ordered tree represents a physical river system, the boundary may be the most useful region to take measures preventing pollution from outside sources.  It is also natural to color boundary edges.  For example, if the ordered tree represents a river network a boundary edge might be clean, polluted, or very polluted. If we are looking at supply lines, we might consider an edge as safe or vulnerable. 

Another interesting subcase is to restrict such considerations to edges without siblings, i.e. edges above a vertex of updegree 1. We call such edges \emph{singletons} or \emph{single edges}. In Figure \ref{onetree}, edge $(b,e)$ is the only single edge. All trunks are composed of single edges. In Figure \ref{smalltrees}, tree (i) has three single edges, tree (ii) one, tree (iii) none, and trees (iv) and (v) one.  In applications, single edges may carry extra importance for the system.  For example, a single supply line or river branch may require extra fortification.  We also consider the case where only singleton edges on the boundary may be $k$-colored.



\begin{figure}[hbt]
\begin{center}
\begin{tabular}{ccccc}
\begin{tikzpicture}[
  level distance=10mm,
  every node/.style={circle,inner sep=2pt,fill=black},
  level 1/.style={sibling distance=10mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=10mm}
]
\node {} [grow=up]
  child {node {}
	  child {node {}
	      child {node {}}
	  }
  };
\end{tikzpicture}
&
\begin{tikzpicture}[
  level distance=10mm,
  every node/.style={circle,inner sep=2pt,fill=black},
  level 1/.style={sibling distance=10mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=10mm}
]
\node {} [grow=up]
  child {node {}
	  child {node {}}
	  child {node {}}
  };
\end{tikzpicture}
&
\begin{tikzpicture}[
  level distance=10mm,
  every node/.style={circle,inner sep=2pt,fill=black},
  level 1/.style={sibling distance=10mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=10mm}
]
\node {} [grow=up]
  child {node {}}
	  child {node {}}
	  child {node {}};
\end{tikzpicture}
&
\begin{tikzpicture}[
  level distance=10mm,
  every node/.style={circle,inner sep=2pt,fill=black},
  level 1/.style={sibling distance=10mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=10mm}
]
\node {} [grow=up]
  child {node {}}
	  child {node {}
	  	  child {node {}}
	  };
\end{tikzpicture}
&
\begin{tikzpicture}[
  level distance=10mm,
  every node/.style={circle,inner sep=2pt,fill=black},
  level 1/.style={sibling distance=10mm},
  level 2/.style={sibling distance=10mm},
  level 3/.style={sibling distance=10mm}
]
\node {} [grow=up]
  child {node {}
 	  child {node {}}
  }
	  child {node {}};
\end{tikzpicture}
\\
(i)&(ii)&(iii)&(iv)&(v)\\
\end{tabular}
\end{center}
\caption{The 5 trees with 3 edges}
\label{smalltrees}
\end{figure}


The \emph{trunk} of a tree is a path from the root to the first vertex with updegree greater than 1 or to a leaf. For example, if we consider the 5 trees with 3 edges given in Figure \ref{smalltrees}, the first two trees have trunks, while the others do not. Of course a trunk would be included in the boundary. A canopy is the portion of the tree that is above the trunk. In Figure \ref{smalltrees}, tree (i) has no canopy, tree (ii) has both a trunk and a canopy, while trees (iii), (iv), and (v) are canopies with no trunk. We call a tree with no trunk a bush.

In Section \ref{S:left} we focus on the left boundary.  We compute the total number of left boundary edges in the set of $n$-edge rooted ordered trees as well as the number of singleton edges on left boundaries.  In Section \ref{S:total}, we generalize our results to the total number of edges on the (right and left) boundary.  In Section \ref{S:special} we specialize our results to when the number of available colors is either $k=1$ or $k=2$.  Our computations enable us to determine the average values of such statistics in an arbitrarily chosen tree with $n$ edges.  Finally, in Section \ref{S:Bij} we present bijections between trees and enriched Dyck paths that give alternate explanations for some of the results of Section \ref{S:left}.




\section{Left Boundary Edges}\label{S:left}

We start by examining the left boundary edges. Two questions occur naturally. If we allow $k$ colors for all left boundary edges how many trees do we have?  Also how many edges are on the left boundary of all such trees with $n$ edges?  The answers to these questions will allow us to determine the average length of the left boundary and the average number of left boundary singleton edges among all $n$-edge trees with $k$-colored left boundaries.


\begin{theorem}\label{lefttree}
Let $T_{k}$ be the generating function counting all ordered trees with each left boundary edge one of $k$ colors. Then $T_{k}=1+kzT_{k}C=\frac{1}{1-kzC}$
\end{theorem}


\begin{proof}
In Figure \ref{left}, either we have the trivial tree, or there is a leftmost edge connected to the root. $C$ represents an arbitrary subtree emanating from the root.  Converting the picture to generating functions gives the proof.
\end{proof}

\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (-3,0) circle [radius=0.1];
\draw (0,0) node {$\bigcup$};
\draw[fill] (3,0) circle [radius=0.1];
\draw (3,1) -- (3,0) -- (4,0);
\draw (4,0) arc (-90:180:1);
\draw (4,1) node {$C$};
\draw (3,0) -- (2,2) node [below left, pos=0.7] {$kz$};
\draw (2.707,2.707) arc (-45:225:1);
\draw (2.707,2.707) -- ++(225:1) -- +(135:1);
\draw (2,3.293) node {$T_k$};
\end{tikzpicture}
\end{center}
\caption{Marking trees with a $k$-colored left boundary}
\label{left}
\end{figure}


If $k=0$, then $T_{0}=1$, counting the trivial tree.  If $k=1$, then we are just counting ordered trees and indeed $T_{1}=\frac{1}{1-zC}=C$. If $k=2$, then $T_{2}=\frac{1}{1-2zC}=B$. 

Now that we have counted trees with $k$-colored left boundary edges, we count the number of edges on the left boundary.  

\begin{theorem}\label{leftsingle}
If $\mathcal{E}_{k}$ is the generating function for the number of boundary edges on the left boundary, then $\mathcal{E}_{k}=kzCT_{k}^{2}$.
\end{theorem}



We present two approaches to compute $\mathcal{E}_k$.

\begin{proof}[Proof 1]
The first proof is to mark one of the left boundary edges with $kz$ and use Figure \ref{left2} to determine the generating function. 
\end{proof}


\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (0,-0.4) circle [radius=0.1];
\draw (-0.707,1.293) arc (135:405:1);
\draw (-0.707,1.293) -- ++(45:1) -- +(315:1);
\draw (0,0.707) node {$T_k$};
\draw (0,3) -- (0,2) -- (1,2);
\draw (1,2) arc (-90:180:1);
\draw (1,3) node {$C$};
\draw (0,2) -- (-1,4) node [below left, pos=0.7] {$kz$};
\draw (-0.293,4.707) arc (-45:225:1);
\draw (-0.293,4.707) -- ++(225:1) -- +(135:1);
\draw (-1,5.293) node {$T_k$};
\end{tikzpicture}
\end{center}
\caption{Marking left boundary edges}
\label{left2}
\end{figure}


\begin{proof}[Proof 2]

A second proof is to mark each edge on the left boundary with a $ku$. Then let $E(z,u)=E=\sum_{t} u^{m_t}z^{n_t}$, where the sum is taken over all rooted trees $t$, $m_t$ is the number of edges on the left boundary of $t$, and $n_t$ is the the number of edges of $t$. We get $E=1+kzuEC=\frac{1}{1-kzuC}$.
Note that $E(z,1)=T_k$.

If there are $m$ edges on the left boundary, we want a contribution of $m$ so we differentiate with respect to $u$ to get

$$E_u=\frac{\partial E}{\partial u}=\frac{kzC}{(1-kzuC)^{2}}=kzCE^2$$


Note that $\mathcal{E}_{k}=E_{u}|_{u=1}$. This gives a second proof of the result.

\end{proof}


By choosing particular values for $k$, we obtain the following corollaries.

\begin{corollary}\label{C:left}
The generating function for the number of left boundary edges for uncolored ordered trees is $zC^{3}=z+3z^{2}+9z^{3}+28z^{4}+90z^5+297x^6+\cdots =\sum_{n\geq 1}\frac{3}{2n+1} \binom{2n+1}{n-1}z^n=\sum_{n\geq 1}\frac{3n}{n+2}C_{n}z^n$ (\seqnum{A000245}) and the average length of the left boundary is $\frac{3n}{n+2}$, which approaches \textnormal{3} as $n$ goes to $\infty$.
\end{corollary}

\begin{proof}
Let $k=1$.
\end{proof}

\begin{corollary}
The generating function for the number of left boundary edges of ordered trees with bicolored edges on the left boundary is $2zB^{2}C=B(2zBC)=B(B-1)=B^{2}-B=\sum_{n\geq 1}(4^{n}-\binom{2n}{n})z^{n}=2z+10z^{2}+44z^{3}+186z^4+772z^5+3172z^6+\cdots$ (\seqnum{A068551}). Thus the average length of the left boundary is $\frac{4^{n}- \binom{2n}{n}}{\binom{2n}{n}}\sim  \sqrt{\pi} n - 1 \sim \sqrt{\pi} n$.
\end{corollary}

\begin{proof}
Let $k=2$ and observe that $\binom{2n}{n}$$ \sim \frac{4^n}{\sqrt{\pi}n}$.
\end{proof}


Next, we modify our work to count trees where the only edges that are $k$-colored are singleton edges on the left boundary.   

\begin{theorem}
Let $\widetilde{T}_{k}$ be the generating function for the number of trees where the only edges that are $k$-colored are singleton edges on the left boundary. Then,

$$\widetilde{T}_{k}=1 + kz\widetilde{T}_{k}+z\widetilde{T}_{k}(C-1)=\frac{1}{1-kz-z(C-1)}=\frac{1}{1-kz-z^{2}C^{2}}.$$
\end{theorem}


\begin{proof}
There are three possible cases, the trivial tree, a tree with a trunk, or a bush.  We mark each singleton edge with a $kz$.

Using Figure \ref{ksingle} we get $\widetilde{T}_{k}=1 + kz\widetilde{T}_{k}+z\widetilde{T}_{k}(C-1)=\frac{1}{1-kz-z(C-1)}=\frac{1}{1-kz-z^{2}C^{2}}$. As before, 1 is for the trivial tree, while $C-1$ gives us a nontrivial subtree on the right so the leftmost edge at the root is not a singleton. 
\end{proof}


\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (-7,0) circle [radius=0.1];
\draw (-5,0) node {$\bigcup$};
\draw[fill] (-3,0) circle [radius=0.1];
\draw (-3,0) -- (-3,2) node [left, pos=0.7] {$kz$};
\draw (-2.293,2.707) arc (-45:225:1);
\draw (-2.293,2.707) -- ++(225:1) -- +(135:1);
\draw (-3,3.293) node {$\widetilde{T}_k$};
\draw (0,0) node {$\bigcup$};
\draw[fill] (3,0) circle [radius=0.1];
\draw (3,1) -- (3,0) -- (4,0);
\draw (4,0) arc (-90:180:1);
\draw (4,1) node {$C-1$};
\draw (3,0) -- (2,2) node [below left, pos=0.7] {$z$};
\draw (2.707,2.707) arc (-45:225:1);
\draw (2.707,2.707) -- ++(225:1) -- +(135:1);
\draw (2,3.293) node {$\widetilde{T}_k$};
\end{tikzpicture}
\end{center}
\caption{Marking k-colored singleton boundary edges}
\label{ksingle}
\end{figure}


Here the case when $k=0$ is nontrivial. $\widetilde{T}_0$ counts trees where there are no singleton edges on the left boundary.  The generating function is $\widetilde{T}_{0}=\frac{1}{1-z^{2}C^{2}}=F=1+z^{2}+2z^{3}+6z^{4}+18z^{5}+57z^{6}+ \cdots$ and we have the Fine numbers. This occurrence of the Fine numbers appears to be new to the literature.


For other values of $k$, we obtain other nice generating functions.

When $k=1$, 
$$\widetilde{T}_{1}=\frac{1}{1-z-z^{2}C^{2}}=C,$$ which counts ordered trees, as expected.  

When $k=2$, $$\widetilde{T}_{2}=\frac{1}{1-2z-z^{2}C^{2}}=C^{2} = zC,$$ which is the sequence of Catalan numbers with shifted indexing. 

 When $k=3$, $$\widetilde{T}_{3}=BC = \sum_{n \geq 0} \binom{2n+1}{n+1}z^n = 1+3z+10z^2+35z^3+126z^4+462z^5+1716z^6+\cdots \text{ (\seqnum{A001700})},$$ which is known the enumerate a variety of combinatorial objects ranging from ordered trees to lattice paths \cite{FPR00, Wolf}.

We give bijective explanations of these three results in Section \ref{S:Bij}.

Finally, we count the total number of singleton left boundary edges in $n$-edge trees counted by $\widetilde{T}_k$.  If we also mark each singleton edge with a $u$, we get $$\widetilde{E}(z,u)=\frac{1}{1-uz-z^{2}C^{2}}=1+uz+(u^{2}+1)z^{2}+(u^{3}+2u+2)z^{3}+(u^{4}+3u^{2}+4u+6)z^{4}+\cdots.$$  Arranging these coefficients in matrix form gives
$$\left[ 
\begin{array}{cccccc}
1 &  &  &  & & \\ 
0 & 1 &  &  & &\\ 
1 & 0 & 1 & &  &\\ 
2 & 2 & 0 & 1 & & \\ 
6 & 4 & 3 & 0 & 1 &\\ 
18& 13& 6 & 4& 0&1 \\
& & \hdots & & \\
\end{array}
\right].$$

The generating function for the $k^{th}$ column ($k=0, 1, 2, \dots$) is $z^{k}F^{k+1}$, counting the number of trees with $k$ singleton edges on the left branch. The row sums are the Catalan numbers since every tree has some number of left edge singletons. We could multiply the matrix by the column vector $[1,1,1,\dots]^{T}$ to obtain the row sums. Also the total number of left boundary singletons is $C_n$, for $n\geq 1$ (i.e multiply by $[0, 1, 2, 3,\dots]^{T}$).  In Riordan group terminology $$(F,zF)*\frac{z}{(1-z)^{2}}=\frac{FzF}{(1-zF)^{2}}=zC^2 = C-1.$$ If all ordered trees with $n$ edges are equally likely, then there is one left boundary singleton per tree on average.

As before we can compute $\widetilde{\mathcal{E}}_k=kz\widetilde{T}_{k}^{2}$ by marking a singleton edge on the left boundary and then looking at Figure \ref{old6}. 

\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (0,-0.4) circle [radius=0.1];
\draw (-0.707,1.293) arc (135:405:1);
\draw (-0.707,1.293) -- ++(45:1) -- +(315:1);
\draw (0,0.707) node {$\widetilde{T}_k$};
\draw (0,2) -- (-1,4) node [below left, pos=0.7] {$kz$};
\draw (-0.293,4.707) arc (-45:225:1);
\draw (-0.293,4.707) -- ++(225:1) -- +(135:1);
\draw (-1,5.293) node {$\widetilde{T}_k$};
\end{tikzpicture}
\end{center}
\caption{Marking a singleton left boundary edge}
\label{old6}
\end{figure}

For a second approach we mark each singleton boundary edge by $kuz$, then differentiate with respect to $u$ to find the number of singleton left boundary edges. Note that
$$\widetilde{E}_{u}=\frac{\partial \widetilde{E}}{\partial u}= -(1-kuz-z(C-1))^{-2}(-kz), \text{ and } \widetilde{E}_{u}|_{u=1}=kz\widetilde{T}_{k}^2.$$

For a third approach we note, briefly, that the corresponding Riordan group array would be 
\begin{eqnarray*}
\left[ 
\begin{array}{cccccc}
1 &  &  &  & & \\ 
0 & k &  &  & &\\ 
1 & 0 & k^{2} & &  &\\ 
2 & 2k & 0 & k^{3} & & \\ 
6 & 4k & 3k^{2} & 0 & k^{4} &\\ 
18& 13k& 6k^{2} & 4k^{3}& 0&k^{5} \\
& & \hdots & & \\
\end{array}%
\right]=(F,zkF)
\end{eqnarray*}

If $k=3$ we have $(F,3zF)*\frac{1}{1-z}=\frac{F}{1-3zF}=BC$.

Thus, we have three different explanations of the following result:

\begin{theorem}\label{leftsingleedge}
Let $\widetilde{\mathcal{E}_{k}}$ be the generating function for the number of singleton edges on the left boundary tree with $k$-colored singleton edges on the left boundary. Then $\widetilde{\mathcal{E}_{k}}=kz\widetilde{T}_{k}^2$.
\end{theorem}

\section{Total Number of Boundary Edges} \label{S:total}

We now generalize from left boundaries to total boundaries of trees.  Consider the set of ordered trees where the boundary edges can be one of $k$ colors. We denote the generating function for the number of such trees according to number of edges as $H_k$. The companion generating function where only the singleton boundary edges are colored will be denoted $\widetilde{H}_k$. 

Using Figure \ref{old7} we get the following defining equation for $H_k$. 
$$H_{k}=1+kzH_{k}+k^{2}z^{2}T^{2}_{k}C=\frac{1}{1-kz}(1+k^{2}z^{2}T^{2}_{k}C).$$

\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (-6,0) circle [radius=0.1];
\draw (-5,0) node {$\bigcup$};
\draw[fill] (-3,0) circle [radius=0.1];
\draw (-3,0) -- (-3,2) node [left, pos=0.7] {$kz$};
\draw (-2.293,2.707) arc (-45:225:1);
\draw (-2.293,2.707) -- ++(225:1) -- +(135:1);
\draw (-3,3.293) node {$H_k$};
\draw (0,0) node {$\bigcup$};
\draw[fill] (3,0) circle [radius=0.1];
\draw (3.707,0.707) arc (-45:225:1);
\draw (3.707,0.707) -- ++(225:1) -- +(135:1);
\draw (3,1.293) node {$C$};
\draw (3,0) -- (1,2) node [below left, pos=0.7] {$kz$};
\draw (1,3) -- (1,2) -- (0,2);
\draw (1,3) arc (0:270:1);
\draw (0,3) node {$T_k$};
\draw (3,0) -- (5,2) node [below right, pos=0.7] {$kz$};
\draw (5,3) -- (5,2) -- (6,2);
\draw (6,2) arc (-90:180:1);
\draw (6,3) node {$T_k$};
\end{tikzpicture}
\end{center}
\caption{Marking left and right boundary edges}
\label{old7}
\end{figure}

Using similar methods to find $\widetilde{H}_{k}$ we get,
$$\widetilde{H}_{k}=1+kz\widetilde{H}_{k}+z^{2}\widetilde{T}^{2}_{k}C=\frac{1}{1-kz}(1+z^{2}\widetilde{T}^{2}_{k}C).$$

The factor $\frac{1}{1-kz}$ is the generating function for the stem. On top of the stem is either the trivial tree or a branch point.  Note that $H_{1}=\widetilde{H}_{1}=C$, as expected.

We now find a generating function counting the boundary edges. To do so, we can add the left boundary edges to the dual right boundary edges. Since the stem would be counted twice, we subtract the stem edges. We denote the generating function that counts $k$ colored boundary edges by $M_k$ and the generating function counting $k$ colored singleton boundary edges by $\widetilde{M}_{k}$. Using Theorem \ref{leftsingleedge}, we get the following.

\begin{equation}
M_{k}=2kzCT^{2}_{k}-\frac{kz}{(1-kz)^{2}}\left(1+(kz)^{2}T^{2}_{k}C\right)
\label{Meq}
\end{equation}

To find $\widetilde{M}_{k}$ it is simpler to first find the stem contribution, $\widetilde{S}_{k}$, and the canopy contribution, $\widetilde{V}_{k}$, and use the fact that $\widetilde{M}_{k}=\widetilde{S}_{k}+\widetilde{V}_{k}$.

Now 
$$\widetilde{S}_{k}=\frac{kz}{(1-kz)^2}\left(1+2z^{2}\widetilde{E}_{k}C\widetilde{T}^{2}_{k}\right) \hspace{0.2in} \text{ and } \hspace{0.2in} \widetilde{V}_{k}=\frac{1}{1-kz}\left(2z^{2}\widetilde{E}_{k}C\widetilde{T}^{2}_{k}\right).$$

Hence
\begin{align*}
\widetilde{M}_{k}&=\widetilde{S}_{k}+\widetilde{V}_{k}\\
&=\frac{kz}{(1-kz)^2}\left(1+2z^{2}\widetilde{E}_{k}C\widetilde{T}^{2}_{k}\right)+\frac{1}{1-kz}\left(2z^{2}\widetilde{E}_{k}C\widetilde{T}^{2}_{k}\right).
\end{align*}


Going back to Figure \ref{smalltrees}, we note that only one edge is not a boundary edge. So, an obvious question is, what proportion of edges are on the boundary in larger trees?  We first consider the case when $k=1$. Lemma \ref{M1} can be proved using the Equation \ref{Meq} and the fact that $T_{1}=C$.

\begin{lemma}\label{M1}
$M_{1}=\frac{zC}{1-z}+\frac{2z^2C^4}{1-z}$
\end{lemma}

For some of our asymptotic estimates we use the following result of Bender.

\begin{lemma}[Bender's Lemma \cite{Bender, M92}]
Let $A(z)$ and $B(z)$ be generating functions with radii $\alpha$ and $\beta$ respectively, with $\alpha > \beta$. Let $C(z)=A(z)B(z)$ and suppose further $\frac{b_{n-1}}{b_n}$ approaches $\beta$ as $n\to \infty$. If $A(\beta)\ne 0$, then $c_n\sim A(\beta)b_n$.
\end{lemma}

\begin{theorem}
When $k$=1, let $R_n$ be the proportion of boundary edges among all edges for trees with $n$ edges. Then 
$$R_n\sim \frac{17}{3n}.$$
\end{theorem}

\begin{proof}
The total number of edges in the set of all trees with $n$ edges is $nC_n$.
Using Lemma \ref{M1}, the total number of boundary edges is 

$$[z^n]\left(\frac{zC}{1-z}+\frac{2z^2C^4}{1-z}\right).$$

Using Bender's Lemma, we obtain

$$[z^n]\left(\frac{zC}{1-z}+\frac{2z^2C^4}{1-z}\right)\sim \frac{\frac{1}{4}C_n}{1-\frac{1}{4}}+\frac{2\cdot\left(\frac{1}{4}\right)^2}{1-\frac{1}{4}}[z^n]C^4=\frac{1}{3}C_n+\frac{1}{6}[z^n]C^4.$$

Now 
\begin{align*}
[z^n]C^4&=&\frac{4}{2n+4}\binom{2n+4}{n}
&=&\frac{2}{n+2}\frac{(2n+4)(2n+3)(2n+2)(2n+1)(2n)!}{(n+4)(n+3)(n+2)(n+1)!n!}\sim 32C_n
\end{align*}

Thus we get 
$$[z^n]\left(\frac{zC}{1-z}+\frac{2z^2C^4}{1-z}\right)\sim \left[\frac{1}{3}+\frac{32}{6}\right]C_{n}=\frac{17}{3}C_n$$

Hence $R_n\sim \frac{17}{3n}.$
\end{proof}

For numerical reassurance we compare the two ratios, boundary edges to all edges, and $\frac{17}{3n}$ when $n=100$. The ratio of these two ratios is approximately 0.97805.

We can also count boundary edges exactly. The average length of the left (resp. right) boundary is 3, as shown in Corollary \ref{C:left}.  Similarly, to count edges in the stem, consider the trees in Figure \ref{heuristic}.  Then we obtain
$$\left(C-zC\right)\left(0+z+2z^2+3z^3+\cdots\right) = C(1-z)\dfrac{z}{(1-z)^2} = \dfrac{zC}{1-C}$$
as the generating function counting the total number of stem edges in the set of ordered trees with $n$ edges.  A quick computation shows that 
$$[z^n] \dfrac{zC}{1-C} = \sum_{i=0}^{n-1} C_i \text{ (\seqnum{A014137})},$$ 
and therefore the average number of stem edges as $n$ approaches infinity is $$\lim_{n \to \infty} \dfrac{\sum_{i=0}^{n-1} C_i}{C_n} = \dfrac{1}{3}.$$

\begin{figure}[!hbt]
\begin{center}
\begin{tabular}{cccc}
\begin{tikzpicture}
\draw[fill] (0,4.5) circle [radius=0.1];
\draw (0,5.5) circle [x radius=1.5, y radius = 1];
\draw (0,5.5) node {$C-zC$};
\end{tikzpicture}
&\begin{tikzpicture}
\draw[fill] (0,3.5) circle [radius=0.1];
\draw[fill] (0,4.5) circle [radius=0.1];
\draw (0,3.5)--(0,4.5) node [left, pos=0.5] {$z$};
\draw (0,5.5) circle [x radius=1.5, y radius = 1];
\draw (0,5.5) node {$C-zC$};
\end{tikzpicture}
&\begin{tikzpicture}
\draw[fill] (0,2.5) circle [radius=0.1];
\draw[fill] (0,3.5) circle [radius=0.1];
\draw[fill] (0,4.5) circle [radius=0.1];
\draw (0,2.5)--(0,3.5) node [left, pos=0.5] {$z$};
\draw (0,3.5)--(0,4.5) node [left, pos=0.5] {$z$};
\draw (0,5.5) circle [x radius=1.5, y radius = 1];
\draw (0,5.5) node {$C-zC$};
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt] (1,4.5) -- (1,2.5);
\draw (1.75,3.5) node {$2z^2$};
\end{tikzpicture}
&\begin{tikzpicture}
\draw[fill] (0,1.5) circle [radius=0.1];
\draw[fill] (0,2.5) circle [radius=0.1];
\draw[fill] (0,3.5) circle [radius=0.1];
\draw[fill] (0,4.5) circle [radius=0.1];
\draw (0,1.5)--(0,2.5) node [left, pos=0.5] {$z$};
\draw (0,2.5)--(0,3.5) node [left, pos=0.5] {$z$};
\draw (0,3.5)--(0,4.5) node [left, pos=0.5] {$z$};
\draw (0,5.5) circle [x radius=1.5, y radius = 1];
\draw (0,5.5) node {$C-zC$};
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt] (1,4.5) -- (1,1.5);
\draw (1.75,3) node {$3z^3$};
\end{tikzpicture}
\end{tabular}
\end{center}
\caption{Counting stem edges}
\label{heuristic}
\end{figure}




Putting these two enumerations together, the average size of the boundary approaches $3+3-\frac{1}{3}=\frac{17}{3}$ as $n$ grows arbitrarily large.  

\section{Special Cases}\label{S:special}

In this section we look at the special cases when $k=1$ and $k=2$ and we find the proportion of singleton boundary edges in these cases. 

\begin{theorem} \label{singleedge}
Let $\widetilde{M}_1$ be the generating function for the number of singleton boundary edges in all $n$-edge trees.  Then,
\begin{enumerate}[(a)]
\item $\widetilde{M}_{1}=\frac{zC}{1-z}+\frac{2z^3C^4}{1-z}=z+2z^2+6z^3+19z^4+61z^5+199z^6+661z^7+ 2234z^8+ \cdots $(\seqnum{A228180}).
\item Let $n$ be a positive integer, then the proportion of single edges that are on the boundary among all single edges is asymptotic to $\frac{5}{3n}$.
\end{enumerate}
\end{theorem}

\begin{proof}
For (a), we consider the number of single boundary edges on a bush. The generating function for a single edge is simply $z$. The generating function counting boundary edges of a bush is $2z^2C^4$. Hence, the number of single edges on the boundary of a bush has generating function $2z^3C^4$. If the tree has only a trunk, then the generating function is $\frac{z}{(1-z)^2}$. Hence 
\begin{align*}
\widetilde{M}_{1}&=\frac{1}{1-z}\left(2z^3C^4\right)+\frac{z}{(1-z)^2}\left(1+z^2C^3\right)\\
&=\frac{2z^3C^4}{1-z}+\frac{zC}{1-z}.
\end{align*}

For (b), there is a simple bijection for counting single edges. Any single edge can be contracted to a vertex and conversely any marked vertex can be replaced by a single edge. Thus the generating function counting all single edges is $zB=\sum_{n=0}^{\infty}\binom{2n-2}{n-1}z^n$. The proportion $\frac{[z^n]\widetilde{M}_{1}}{[z^n]zB}$, by (a) and Bender's Lemma, is asymptotic to $\frac{5}{3n}$. For related results see $\cite{Cheon-Lou}$.\\
\end{proof}

The proof of the following theorem is an application of Bender's Lemma and is similar to the proof of Theorem \ref{singleedge}, hence it is omitted.

\begin{theorem}
The proportion of single boundary edges among all boundary edges in an $n$-edge tree approaches 5/17 as $n$ goes to $\infty$.
\end{theorem}

We now consider trees whose boundary edges are bicolored, i.e. $k=2$. Recall that $T_{2}=B=\sum_{n=0}^{\infty}\binom{2n}{n}z^n = \frac{1}{\sqrt{1-4z}}=1+2zCB=\frac{1}{1-2zC}$. 

This is the generating function for the central binomial coefficients. Thus we have the easily proven, yet possibly novel, result that the number of ordered trees with bicolored boundary edges allowed on the left branch is $\binom{2n}{n}$ for such trees with $n$ edges.

Consider next trees where the boundary edges are bicolored and the root degree is at least two. In other words, bushes. 

\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (3,0) circle [radius=0.1];
\draw (3.707,0.707) arc (-45:225:1);
\draw (3.707,0.707) -- ++(225:1) -- +(135:1);
\draw (3,1.293) node {$C$};
\draw (3,0) -- (1,2) node [below left, pos=0.7] {$2z$};
\draw (1.707,2.707) arc (-45:225:1);
\draw (1.707,2.707) -- ++(225:1) -- +(135:1);
\draw (1,3.293) node {$T_2$};
\draw (3,0) -- (5,2) node [below right, pos=0.7] {$2z$};
\draw (5.707,2.707) arc (-45:225:1);
\draw (5.707,2.707) -- ++(225:1) -- +(135:1);
\draw (5,3.293) node {$T_2$};
\end{tikzpicture}
\end{center}
\caption{Marking edges in bushes}
\label{bush}
\end{figure}

Using Figure \ref{bush}, the generating function for the number of bushes with bicolored boundary edges is $(2z)^2T_{2}^{2}C=4z^2B^2C=4z^{2}+20z^{3}+88z^{4}+372z^{5}+1544z^{6}+6344z^{7}+25904z^{8}+\cdots$.

In the case that the root degree is one we have a stem, a maximal chain of vertices, each of updegree 1, starting at the root. For this case the generating function is just $\frac{1}{1-2z}=\sum_{n=0}^{\infty}{2^nz^n}$. Using the generating functions counting boundary edges on bushes and stems we get the following theorem.
\begin{theorem} Let $H_2$ be the generating function for the number of trees where the boundary edges are bicolored.  Then,
\begin{align*}
H_{2}&=\frac{1}{1-2z}(1+4z^2B^2C)\\
&=\frac{1}{1-2z}(1-2zB+2zB^2)\\
&=1+2z+8z^2+36z^3+160z^4+692z^5+\cdots \text{(\seqnum{A228197})}.
\end{align*}
\end{theorem}

Finally, consider the case where only boundary singleton edges can be bicolored. The computations in this case are slightly subtler but follow the same pattern. This situation is illustrated in Figure \ref{boundarysingle}.  We have $$\widetilde{T}_{2}=1+2z\widetilde{T}_{2}+z\widetilde{T}_{2}(C-1)=\frac{1}{1-2z-z(C-1)}=\frac{1}{1-z-zC}=C^2.$$

\begin{figure}[hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (-3,0) circle [radius=0.1];
\draw (-3,0) -- (-3,2) node [left, pos=0.7] {$2z$};
\draw (-2.293,2.707) arc (-45:225:1);
\draw (-2.293,2.707) -- ++(225:1) -- +(135:1);
\draw (-3,3.293) node {$\widetilde{T}_2$};
\draw (0,0) node {$\bigcup$};
\draw[fill] (3,0) circle [radius=0.1];
\draw (3,1) -- (3,0) -- (4,0);
\draw (4,0) arc (-90:180:1);
\draw (4,1) node {$C-1$};
\draw (3,0) -- (2,2) node [below left, pos=0.7] {$z$};
\draw (2.707,2.707) arc (-45:225:1);
\draw (2.707,2.707) -- ++(225:1) -- +(135:1);
\draw (2,3.293) node {$\widetilde{T}_2$};
\end{tikzpicture}
\end{center}
\caption{Marking singleton boundary edges}
\label{boundarysingle}
\end{figure}


Thus using the same techniques as before, the bushes have generating function
$$z^2(\widetilde{T}_{2})^2C=z^2C^5=z^2+5z^3+20z^4+75z^5+275z^6+1001z^7+\cdots \text{ (\seqnum{A000344})}.$$

The generating function for the stem is again $\frac{1}{1-2z}$. Using these generating functions we get the following theorem.
\begin{theorem} Let $\widetilde{H}_2$ be the generating function for the number of trees where the singleton boundary edges are bicolored.  Then,
$$\widetilde{H}_{2}=\frac{1}{1-2z}(1+z^2C^5)=1+2z+5z^2+15z^3+50z^4+165z^5+\cdots \text{(\seqnum{A228343})}.$$
\end{theorem}


There is much more that could be done along these lines. We could look at other related classes of trees where the updegree of each vertex is 0, 1, or 2 (Motzkin trees) or updegree must be even (even trees). We could change from left boundary to leftmost principal branch.  However, we conclude this section with a curiosity, answering a question that may not have been bothering you.  Where does the generating function $C^7$ occur in a ``natural'' setting?
If we consider bushes (root degree $\geq 2$) with bicolored singleton edges on the boundary, then the generating function counting the number of singleton boundary edges is $4z^{3}C^7$.
The factor $z^{2}C$ sets up the base of a bush. To count the number of left boundary edges, we have $$\widetilde{\mathcal{E}_{k}}=2z\widetilde{T}_{k}^{2}=2zC^4$$ and $$\widetilde{T}_{k}=C^2$$ possible trees on the right branch. This gives us $$z^{2}C(2zC^{4})C^2$$ edges on the left side. And doubling this gives us $$4z^{3}C^{7}=4z^{3}+28z^{4}+140z^{5}+616z^{6}+\cdots =4z^{3}\sum_{n=0}^{\infty}\frac{7}{2n+7}\binom{2n+7}{n}z^n.$$


\section{Bijections}\label{S:Bij}

In this final section, we provide bijections to illustrate some of our previous results, namely that $\widetilde{T}_{1}=C, \widetilde{T}_{2}=C^2$, and $\widetilde{T}_{3}=BC$.  Recall from Section \ref{S:left} that $\widetilde{T}_k$ is the generating function for the number of trees where the only edges that are $k$-colored are singleton edges on the left boundary.

The first bijection relates the edges of the left boundary to subtrees connected to the root, as shown in Figure \ref{rootbranch}.  Here, for each edge $E$ in the left boundary, let $E^*$ be the subtree whose root is the lower vertex of $E$ but not including edge $E$.  If the original tree has $\ell$ edges in the left boundary, we obtain a new tree with $\ell$ edges emanating from the root.  Each of these edges $E$ is the stem for a subtree corresponding to $E^*$.  Thus, $\widetilde{T}_1 = C$.

\begin{figure}[!hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (0,0) circle [radius=0.1];
\draw[fill] (1,1) circle [radius=0.1];
\draw[fill] (-1,1) circle [radius=0.1];
\draw[fill] (-2,2) circle [radius=0.1];
\draw[fill] (1,2) circle [radius=0.1];
\draw[fill] (1.5,2) circle [radius=0.1];
\draw[fill] (2,2) circle [radius=0.1];
\draw[fill] (-3,3) circle [radius=0.1];
\draw[fill] (-2,3) circle [radius=0.1];
\draw[fill] (-1.5,3) circle [radius=0.1];
\draw[fill] (1,3) circle [radius=0.1];
\draw[fill] (-2.25,4) circle [radius=0.1];
\draw[fill] (-1.75,4) circle [radius=0.1];
\draw (0,0)--(1,1)--(1,2)--(1,3);
\draw (1.5,2)--(1,1)--(2,2);
\draw (0,0)--(-1,1) node [below left, pos=0.5] {$\alpha$};
\draw (-1,1)--(-2,2) node [below left, pos=0.5] {$\beta$};
\draw (-2,2)--(-3,3) node [below left, pos=0.5] {$\gamma$};
\draw (-2.25,4)--(-2,3)--(-1.75,4);
\draw (-2,3)--(-2,2)--(-1.5,3);
\draw[dashed] (0.25,2.25) -- (0,0) -- (2.25,0.25);
\draw[dashed] (2.25,0.25) arc (-90:180:2);
\draw (2.5,3) node {$\alpha^*$};
\draw[dashed] (-0.5,2) -- (-1,1) -- (0,1.5);
\draw[dashed] (0,1.5) arc (0:90:0.5);
\draw (-0.5,1.5) node {$\beta^*$};
\draw[dashed] (-0.701,2.75) arc (-60:210:1.5);
\draw[dashed] (-0.701,2.75) -- ++(210:1.5) -- +(120:1.5);
\draw (-1,4) node {$\gamma^*$};
\end{tikzpicture}

\vspace{0.1in}

\begin{tikzpicture}
\draw[fill] (0,-1) circle [radius=0.1];
\draw[fill] (-2,1) circle [radius=0.1];
\draw[fill] (0,1) circle [radius=0.1];
\draw[fill] (2,1) circle [radius=0.1];
\draw (0,-1)--(2,1) node [right, pos=0.5] {$\alpha$};
\draw (0,-1)--(0,1) node [right, pos=0.5] {$\beta$};
\draw (0,-1)--(-2,1) node [right, pos=0.5] {$\gamma$};
\draw[dashed] (0.65,1.375) arc (-60:210:0.75);
\draw[dashed] (0.65,1.375) -- ++(210:0.75) -- +(120:0.75);
\draw (0.3,2) node {$\beta^* = \emptyset$};
\draw[fill] (3,4) circle [radius=0.1];
\draw[fill] (3,3) circle [radius=0.1];
\draw[fill] (3.5,3) circle [radius=0.1];
\draw[fill] (4,3) circle [radius=0.1];
\draw[fill] (3,2) circle [radius=0.1];
\draw (2,1)--(3,2)--(3,3)--(3,4);
\draw (3.5,3)--(3,2)--(4,3);
\draw[dashed] (2.25,3.25) -- (2,1) -- (4.25,1.25);
\draw[dashed] (4.25,1.25) arc (-90:180:2);
\draw (4.5,4) node {$\alpha^*$};
\draw[fill] (-2,2) circle [radius=0.1];
\draw[fill] (-1.5,2) circle [radius=0.1];
\draw[fill] (-2.25,3) circle [radius=0.1];
\draw[fill] (-1.75,3) circle [radius=0.1];
\draw (-2.25,3)--(-2,2)--(-1.75,3);
\draw (-2,2)--(-2,1)--(-1.5,2);
\draw[dashed] (-0.939,2.061) arc (-45:225:1.5);
\draw[dashed] (-0.939,2.061) -- ++(225:1.5) -- +(135:1.5);
\draw (-2,4) node {$\gamma^*$};
\end{tikzpicture}
\end{center}
\caption{A bijection between left boundary edges and edges containing the root}
\label{rootbranch}
\end{figure}

The second bijection is well-known, called such things as ``the worm climbing the tree'', ``the glove bijection'', or ``preorder transversal'' \cite{Stanley}.  As in the first bijection, edges on the left boundary are converted the edges emanating from the root, but then we take the transformation one step further, as shown in Figure \ref{rootpath}.  Now, edges emanating from the root are mapped to steps touching the $x$-axis in a Dyck path.  Singletons edges on the left boundary in Figure \ref{rootbranch} correspond to UD subpaths starting and ending on the $x$-axis in Figure \ref{rootpath}.  We call such UD subpaths \emph{hills}.

\begin{figure}[!hbt]
\begin{center}
\begin{tikzpicture}
\draw[fill] (0,-1) circle [radius=0.1];
\draw[fill] (-2,1) circle [radius=0.1];
\draw[fill] (0,1) circle [radius=0.1];
\draw[fill] (2,1) circle [radius=0.1];
\draw (0,-1)--(2,1) node [right, pos=0.5] {$\alpha$};
\draw (0,-1)--(0,1) node [right, pos=0.5] {$\beta$};
\draw (0,-1)--(-2,1) node [right, pos=0.5] {$\gamma$};
\draw[dashed] (0.65,1.375) arc (-60:210:0.75);
\draw[dashed] (0.65,1.375) -- ++(210:0.75) -- +(120:0.75);
\draw (0.3,2) node {$\beta^* = \emptyset$};
\draw[fill] (3,4) circle [radius=0.1];
\draw[fill] (3,3) circle [radius=0.1];
\draw[fill] (3.5,3) circle [radius=0.1];
\draw[fill] (4,3) circle [radius=0.1];
\draw[fill] (3,2) circle [radius=0.1];
\draw (2,1)--(3,2)--(3,3)--(3,4);
\draw (3.5,3)--(3,2)--(4,3);
\draw[dashed] (2.25,3.25) -- (2,1) -- (4.25,1.25);
\draw[dashed] (4.25,1.25) arc (-90:180:2);
\draw (4.5,4) node {$\alpha^*$};
\draw[fill] (-2,2) circle [radius=0.1];
\draw[fill] (-1.5,2) circle [radius=0.1];
\draw[fill] (-2.25,3) circle [radius=0.1];
\draw[fill] (-1.75,3) circle [radius=0.1];
\draw (-2.25,3)--(-2,2)--(-1.75,3);
\draw (-2,2)--(-2,1)--(-1.5,2);
\draw[dashed] (-0.939,2.061) arc (-45:225:1.5);
\draw[dashed] (-0.939,2.061) -- ++(225:1.5) -- +(135:1.5);
\draw (-2,4) node {$\gamma^*$};
\end{tikzpicture}

\vspace{0.1in}

\begin{tikzpicture}
\draw (0,0)--(12.5,0) node [right] {$y=0$};
\draw (0,0)--(0.5,0.5)--(1,1)--(1.5,1.5)--(2,1)--(2.5,1.5)--(3,1)--(3.5,0.5)--(4,1)--(4.5,0.5)--(5,0)--(5.5,0.5)--(6,0)--(6.5,0.5)--(7,1)--(7.5,1.5)--(8,2)--(8.5,1.5)--(9,1)--(9.5,1.5)--(10,1)--(10.5,1.5)--(11,1)--(11.5,0.5)--(12,0);
\draw[fill] (0,0) circle [radius=0.1];
\draw[fill] (0.5,0.5) circle [radius=0.1];
\draw[fill] (1,1) circle [radius=0.1];
\draw[fill] (1.5,1.5) circle [radius=0.1];
\draw[fill] (2,1) circle [radius=0.1];
\draw[fill] (2.5,1.5) circle [radius=0.1];
\draw[fill] (3,1) circle [radius=0.1];
\draw[fill] (3.5,0.5) circle [radius=0.1];
\draw[fill] (4,1) circle [radius=0.1];
\draw[fill] (4.5,0.5) circle [radius=0.1];
\draw[fill] (5,0) circle [radius=0.1];
\draw[fill] (5.5,0.5) circle [radius=0.1];
\draw[fill] (6,0) circle [radius=0.1];
\draw[fill] (6.5,0.5) circle [radius=0.1];
\draw[fill] (7,1) circle [radius=0.1];
\draw[fill] (7.5,1.5) circle [radius=0.1];
\draw[fill] (8,2) circle [radius=0.1];
\draw[fill] (8.5,1.5) circle [radius=0.1];
\draw[fill] (9,1) circle [radius=0.1];
\draw[fill] (9.5,1.5) circle [radius=0.1];
\draw[fill] (10,1) circle [radius=0.1];
\draw[fill] (10.5,1.5) circle [radius=0.1];
\draw[fill] (11,1) circle [radius=0.1];
\draw[fill] (11.5,0.5) circle [radius=0.1];
\draw[fill] (12,0) circle [radius=0.1];
\draw[thick, <->] (0.25,-0.5) -- (4.75,-0.5) node [below, pos=0.5] {$\gamma$};
\draw[thick, <->] (5.25,-0.5) -- (5.75,-0.5) node [below, pos=0.5] {$\beta$};
\draw[thick, <->] (6.25,-0.5) -- (11.75,-0.5) node [below, pos=0.5] {$\alpha$};
\draw[dashed] (0.25,0.5)--(4.75,0.5)--(4.75,2.5)--(0.25,2.5)--(0.25,0.5);
\draw (2.5,2) node {$\gamma^*$};
\draw[dashed] (6.25,0.5)--(11.75,0.5)--(11.75,3)--(6.25,3)--(6.25,0.5);
\draw (9,2.5) node {$\alpha^*$};
\end{tikzpicture}
\end{center}
\caption{The worm climbing the tree}
\label{rootpath}
\end{figure}

Now, towards understanding $\widetilde{T}_2$, suppose that singletons on the left boundary of a tree are bicolored.  This is equivalent to having bicolored UD hills in our Dyck paths. Suppose each such UD hill is either green or red, and replace the red hills with DU, as in Figure \ref{stubstohills}.  We now have an ``enriched'' Dyck path that has the freedom to go as low as the line $y = -1$.  The number of such ``enriched'' Dyck paths has the generating function $C^2$. 

\begin{figure}[!htb]
\begin{center}
\begin{tikzpicture}
\draw (0,0)--(8.5,0) node [right] {$y=0$};
\draw (0,0)--(0.5,0.5)--(1,1)--(1.5,0.5)--(2,1)--(2.5,0.5)--(3,0)--(3.5,0.5)--(4,0);
\draw (5,0)--(5.5,0.5)--(6,1)--(6.5,0.5)--(7,0);
\draw[red,very thick,dashed] (4,0)--(4.5,0.5)--(5,0);
\draw[red,very thick,dashed] (7,0)--(7.5,0.5)--(8,0);
\draw[fill] (0,0) circle [radius=0.1];
\draw[fill] (0.5,0.5) circle [radius=0.1];
\draw[fill] (1,1) circle [radius=0.1];
\draw[fill] (1.5,0.5) circle [radius=0.1];
\draw[fill] (2,1) circle [radius=0.1];
\draw[fill] (2.5,0.5) circle [radius=0.1];
\draw[fill] (3,0) circle [radius=0.1];
\draw[fill] (3.5,0.5) circle [radius=0.1];
\draw[fill] (4,0) circle [radius=0.1];
\draw[fill] (4.5,0.5) circle [radius=0.1];
\draw[fill] (5,0) circle [radius=0.1];
\draw[fill] (5.5,0.5) circle [radius=0.1];
\draw[fill] (6,1) circle [radius=0.1];
\draw[fill] (6.5,0.5) circle [radius=0.1];
\draw[fill] (7,0) circle [radius=0.1];
\draw[fill] (7.5,0.5) circle [radius=0.1];
\draw[fill] (8,0) circle [radius=0.1];
\end{tikzpicture}

\vspace{0.1in}

\begin{tikzpicture}
\draw (0,0)--(8.5,0) node [right] {$y=0$};
\draw (0,-0.5)--(8.5,-0.5) node [right] {$y=-1$};
\draw (0,0)--(0.5,0.5)--(1,1)--(1.5,0.5)--(2,1)--(2.5,0.5)--(3,0)--(3.5,0.5)--(4,0);
\draw (5,0)--(5.5,0.5)--(6,1)--(6.5,0.5)--(7,0);
\draw[red,very thick,dashed] (4,0)--(4.5,-0.5)--(5,0);
\draw[red,very thick,dashed] (7,0)--(7.5,-0.5)--(8,0);
\draw[fill] (0,0) circle [radius=0.1];
\draw[fill] (0.5,0.5) circle [radius=0.1];
\draw[fill] (1,1) circle [radius=0.1];
\draw[fill] (1.5,0.5) circle [radius=0.1];
\draw[fill] (2,1) circle [radius=0.1];
\draw[fill] (2.5,0.5) circle [radius=0.1];
\draw[fill] (3,0) circle [radius=0.1];
\draw[fill] (3.5,0.5) circle [radius=0.1];
\draw[fill] (4,0) circle [radius=0.1];
\draw[fill] (4.5,-0.5) circle [radius=0.1];
\draw[fill] (5,0) circle [radius=0.1];
\draw[fill] (5.5,0.5) circle [radius=0.1];
\draw[fill] (6,1) circle [radius=0.1];
\draw[fill] (6.5,0.5) circle [radius=0.1];
\draw[fill] (7,0) circle [radius=0.1];
\draw[fill] (7.5,-0.5) circle [radius=0.1];
\draw[fill] (8,0) circle [radius=0.1];
\end{tikzpicture}
\end{center}
\caption{A bijection from bicolored left singletons to enriched Dyck paths}
\label{stubstohills}
\end{figure}

Finally, keeping this framework, we tricolor singleton boundary edges so that the hills can now be green, red, or purple. Each time a purple hill is encountered we change UD to UU. If there are $\ell$ purple hills, the final height of the path will be $2\ell$. In Figure \ref{tricolor}, the purple hills are denoted by the double red lines.

\begin{figure}[!hbt]
\begin{center}
\begin{tikzpicture}
\draw (0,0)--(10.5,0) node [right] {$y=0$};
\draw (0,0)--(0.5,0.5)--(1,0);
\draw (3,0)--(3.5,0.5)--(4,1)--(4.5,0.5)--(5,0);
\draw (6,0)--(6.5,0.5)--(7,1)--(7.5,0.5)--(8,1)--(8.5,0.5)--(9,0)--(9.5,0.5)--(10,0);
\draw[red,very thick,dashed] (1,0)--(1.5,0.5)--(2,0);
\draw[purple, thick, double] (2,0)--(2.5,0.5)--(3,0);
\draw[purple, thick, double] (5,0)--(5.5,0.5)--(6,0);
\draw[fill] (0,0) circle [radius=0.1];
\draw[fill] (0.5,0.5) circle [radius=0.1];
\draw[fill] (1,0) circle [radius=0.1];
\draw[fill] (1.5,0.5) circle [radius=0.1];
\draw[fill] (2,0) circle [radius=0.1];
\draw[fill] (2.5,0.5) circle [radius=0.1];
\draw[fill] (3,0) circle [radius=0.1];
\draw[fill] (3.5,0.5) circle [radius=0.1];
\draw[fill] (4,1) circle [radius=0.1];
\draw[fill] (4.5,0.5) circle [radius=0.1];
\draw[fill] (5,0) circle [radius=0.1];
\draw[fill] (5.5,0.5) circle [radius=0.1];
\draw[fill] (6,0) circle [radius=0.1];
\draw[fill] (6.5,0.5) circle [radius=0.1];
\draw[fill] (7,1) circle [radius=0.1];
\draw[fill] (7.5,0.5) circle [radius=0.1];
\draw[fill] (8,1) circle [radius=0.1];
\draw[fill] (8.5,0.5) circle [radius=0.1];
\draw[fill] (9,0) circle [radius=0.1];
\draw[fill] (9.5,0.5) circle [radius=0.1];
\draw[fill] (10,0) circle [radius=0.1];
\end{tikzpicture}

\vspace{0.1in}

\begin{tikzpicture}
\draw (0,0)--(10.5,0) node [right] {$y=0$};
\draw (0,-0.5)--(10.5,-0.5) node [right] {$y=-1$};
\draw (0,2)--(10.5,2) node [right] {$y=4$};
\draw (0,0)--(0.5,0.5)--(1,0);
\draw (3,1)--(3.5,1.5)--(4,2)--(4.5,1.5)--(5,1);
\draw (6,2)--(6.5,2.5)--(7,3)--(7.5,2.5)--(8,3)--(8.5,2.5)--(9,2)--(9.5,2.5)--(10,2);
\draw[red,very thick,dashed] (1,0)--(1.5,-0.5)--(2,0);
\draw[purple, thick, double] (2,0)--(2.5,0.5)--(3,1);
\draw[purple, thick, double] (5,1)--(5.5,1.5)--(6,2);
\draw[fill] (0,0) circle [radius=0.1];
\draw[fill] (0.5,0.5) circle [radius=0.1];
\draw[fill] (1,0) circle [radius=0.1];
\draw[fill] (1.5,-0.5) circle [radius=0.1];
\draw[fill] (2,0) circle [radius=0.1];
\draw[fill] (2.5,0.5) circle [radius=0.1];
\draw[fill] (3,1) circle [radius=0.1];
\draw[fill] (3.5,1.5) circle [radius=0.1];
\draw[fill] (4,2) circle [radius=0.1];
\draw[fill] (4.5,1.5) circle [radius=0.1];
\draw[fill] (5,1) circle [radius=0.1];
\draw[fill] (5.5,1.5) circle [radius=0.1];
\draw[fill] (6,2) circle [radius=0.1];
\draw[fill] (6.5,2.5) circle [radius=0.1];
\draw[fill] (7,3) circle [radius=0.1];
\draw[fill] (7.5,2.5) circle [radius=0.1];
\draw[fill] (8,3) circle [radius=0.1];
\draw[fill] (8.5,2.5) circle [radius=0.1];
\draw[fill] (9,2) circle [radius=0.1];
\draw[fill] (9.5,2.5) circle [radius=0.1];
\draw[fill] (10,2) circle [radius=0.1];
\end{tikzpicture}
\end{center}
\caption{A bijection from tricolored left singletons to paths}
\label{tricolor}
\end{figure}

Suppose now we have ordered trees where the singleton edges can be either green, red, or purple. Using the first two bijections, these trees correspond to Dyck paths with tricolored hills. We traverse the path from left to right.  When we encounter a green hill we do nothing. When we encounter a red hill, we change the steps UD to DU. This gives us enriched Dyck paths as in Figure \ref{stubstohills}. When we encounter a purple hill, we change UD to UU. Each purple hill now gives a path that ends 2 units higher. If  there are $\ell$ purple hills, the path ends at the point $\left( 2n,2\ell\right)$ and the number of such paths is $\frac{2\ell+2}{n+\ell+2}\binom{2n+1}{n-\ell}=\binom{2n+1}{n-\ell}-\binom{2n+1}{n-\ell-1}$.  Here, the last equality is found by using the reflection principle of ``good paths come from all paths minus bad paths''. Now summing over $\ell$ gives the telescoping sum $\sum_{\ell=0}^{n}\binom{2n+1}{n-\ell}-\binom{2n+1}{n-\ell-1}=\binom{2n+1}{n}$ and $\sum_{n\geq 0}\binom{2n+1}{n}z^{n}=BC$.  Thus, $\widetilde{T}_3=BC$.

An alternate proof using the Riordan group (see \cite{SGWW}) we have 
$$
\left(C^{2},zC^{2}\right) = 
\left[ 
\begin{array}{ccccc}
1 & 0 & 0 & 0 & \cdots  \\ 
2 & 1 & 0 & 0 &  \\ 
5 & 4 & 1 & 0 &  \\ 
14 & 14 & 6 & 1 &  \\ 
&  & \cdots  &  & 1
\end{array}
\right].$$
So by the Fundamental Theorem of Riordan Arrays, we have 
$$\left(C^{2},zC^{2}\right)\ast \frac{1}{1-z}=\frac{C^2}{1-zC^2}=C\left(\frac{C}{1-zC^2}\right)=BC.$$

\section{Acknowledgement}\label{S:Ack}

The authors would like to thank an anonymous referee for suggestions that improved the presentation of this paper.

\begin{thebibliography}{9}
\bibitem{Bender}E. Bender, Asymptotic methods in enumeration, \emph{SIAM Rev.} \textbf{16} (1974), 485--515; errata, ibid., \textbf{18} (1976), 292.
\bibitem{Cheon-Lou}G. Cheon and L. Shapiro, The uplift principle for ordered trees, \emph{Appl. Math. Lett.} \textbf{25} (2012), 1010--1015.
\bibitem{DS01a} E. Deutsch and L. Shapiro, Seventeen Catalan identities, \emph{Bull. Inst. Combin. Appl.} \textbf{31} (2001), 31--38.
\bibitem{DS01} E. Deutsch and L. Shapiro, A survey of the Fine numbers, \emph{Discrete Math.} \textbf{241} (2001), 241--265.
\bibitem{FPR00} A. Frosini, R. Pinzani and S. Rinaldi, About half the middle binomial coefficient, \emph{Pure Math. Appl.} \textbf{11} (2000), 497--508.
\bibitem{GKP}R. Graham, D. Knuth, and O. Patashnik, \emph{Concrete Mathematics, 2nd ed.}, Addison-Wesley, 1994.
\bibitem{JZ03} M. Jani and M. Zeleke, $k$-Trees and Catalan identities, \emph{Congr. Numer} \textbf{165} (2003), 39--49.
\bibitem{Wolf}W. Lang, On Polynomials Related to powers of the generating function of Catalan's numbers, \emph{Fibonacci Quart.} \textbf{38} (2000), 408--419.
\bibitem{M92} H. Mahmoud, \emph{Evolution of Random Search Trees}, Wiley, 1992.
\bibitem{SGWW} L. Shapiro, S. Getu,  W.J. Woan, and L. Woodson, The Riordan group, \emph{Discrete Appl. Math.} \textbf{34} (1991), 229--239.
\bibitem{S14} L. Shapiro, 42 Catalan identities and why you should care, \emph{Bull. Inst. Combin. Appl.} \textbf{71} (2014), 94--102.
\bibitem{Stanley} R. Stanley, \emph{Catalan Numbers}, Cambridge University Press, 2015.
\bibitem{SLOE} The On-Line Encyclopedia of Integer Sequences, published electronically at \href{http://oeis.org}{http://oeis.org}, 2015.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05C30; Secondary 05C05.

\noindent \emph{Keywords: } 
ordered tree, boundary, colored edges, singleton edges

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000245},
\seqnum{A000344},
\seqnum{A000957},
\seqnum{A000984},
\seqnum{A001700},\\ 
\seqnum{A068551},
\seqnum{A014137},  
\seqnum{A228180},
\seqnum{A228197}, and
\seqnum{A228343}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 24 2014;
revised version received May XX 2015.
Published in {\it Journal of Integer Sequences}, May XX 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
