




\documentclass[12pt]{amsart}


\usepackage{array}



\setlength{\textheight}{8.0in}
\setlength{\textwidth}{6.0in}
\setlength{\oddsidemargin}{0.4in}
\setlength{\evensidemargin}{0.4in}
\theoremstyle{plain}
\newtheorem{Thm}{Theorem}
\newtheorem{Cor}{Corollary}

\theoremstyle{remark}

%\renewcommand{\baselinestretch}{1.5}
\newcommand{\cal}{\mathcal}

\begin{document}
\title [Directed column-convex polyominoes and ordered trees]   
{A bijection between \\
directed column-convex polyominoes and \\ordered trees of height
at most three}
\author{Emeric Deutsch}
\address{Department of Mathematics, Polytechnic University, Brooklyn, NY
11201}
\email{deutsch@duke.poly.edu}
\author{Helmut Prodinger}
\address{The John Knopfmacher Centre for Applicable Analysis and Number
Theory, School of Mathematics, University of the Witwatersrand, P.\;O.
Wits, 2050 Johannesburg, South Africa}   
\email{helmut@maths.wits.ac.za}
\keywords{Directed column-convex polyominoes; Ordered trees.}
\subjclass{05A15}
\begin{abstract}
A bijection is given between the set of directed column-convex polyominoes   
of area \( n \) and the set of ordered trees of height at most
three and having \(n \) edges.
Additional bijections with less well known combinatorial objects
are sketched.
\end{abstract}   
\maketitle

% xxxxxx

{\bf 1. Introduction.} By a {\em directed polyomino} we mean a polyomino
that can be built by
starting with a single cell and adding new cells on the right or on the
top of an existing cell. By a {\em directed column-convex polyomino}
(DCCP) we
mean a directed polyomino in which every column is formed by contiguous
cells. The {\em area} of a polyomino is defined to be the number of its
cells. It is known \cite{barc1} that the number of directed column-convex
polyomino of area \(n \) is the Fibonacci number \(F_{2n-1}\) with
\(F_0=0,
F_1=1\) (it is sequence A001519 in Sloane's On-Line Encyclopedia of
Integer Sequences).   
Introducing also the empty polyomino of area zero, with count 1,
it follows that the generating function for the number of directed
column-convex polyominoes according to area is \(\frac{1-2z}{1-3z+z^2}\).
We give a simple derivation of this in the Appendix.

By the {\em size} of a tree we mean the number of its edges and by {\em height} we mean the number of edges on a maximal path starting at the root (some authors replace ``edges" by ``nodes" in these definitions, resulting in a difference of one unit). The {\em level} of a   
node in a tree is the number of edges on the unique path from the root to that node.
It is easy to show, using for example the so-called symbolic method \cite{flased, sedfla},   
that the generating function for ordered trees of height at most three, with respect to   
number of edges, is again \(\frac{1-2z}{1-3z+z^2}\) (see also \cite{brui, prod}).
For the sake of completeness, we derive this in the Appendix.

Consequently, the number of directed column-convex polyominoes of area \(n
\) is equal to the number of ordered trees of height at most three and
having \(n \) edges. We present a bijection between these two sets of
combinatorial objects.

\medskip

{\bf 2. The Bijection.} For convenience, we define a {\em bouquet} of
size
\(k\)
(\(k=1,2,\dots\)) to be an ordered tree whose root has a unique child from
which \(k-1\) edges are emanating. In other words, a bouquet is a tree of
height at most 2 and root of degree 1.

Let \(\pi\) be a directed column-convex polyomino of area \(n\) (\(n \geq
1\)). Suppose that \(\pi\) has width \(w\) and assume that the
\(i\)th
column extends from level \(a_i\) to level \(b_i\)   
($i=1,2,\dots, w$; $a_1=0$).   
To the directed column-convex polyomino \(\pi\) we associate an
ordered tree \(\tau\) defined in the following manner:

(i) the root of \(\tau\) has degree \(b_w\) (i.\;e.   
the altitude of the top of the last column of \(\pi\));

(ii) labeling the children of the root from left to right by \(0, 1, 2,
\dots, b_w-1\), on the nodes labeled \(a_2,a_3,\dots, a_w\) we hang
bouquets of sizes \(b_1-a_2,b_2-a_3,\dots,b_{w-1}-a_w\), respectively. Note
that the numbers \(a_2, a_3, \dots, a_w\) need not be distinct and,
consequently, several bouquets may be dangling from the same node.

We show that the tree \(\tau \) has \(n \) edges. By definition, the
number of edges at level 1 is \(b_w\) and the number of nodes at level 2
and 3 is the number of edges in all the bouquets, i.\;e.
\(\sum_{i=1}^{w-1}(b_i-a_{i+1})\). Thus, the total number of
edges of
\(\tau \) is equal to \(\sum_{i=1}^w(b_i-a_i)\), i.\;e. the area \(n\) of
\(\pi\).   

It is easy to see what is the inverse mapping. We shall indicate it on   
the considered example.

\smallskip

{\em Example.} Consider the directed column-convex polyomino \(\pi\) of
Fig. 1. We have \(w=8\) and the values of \(a_i,b_i,b_{i-1}-a_i\) are
given in Table 1.


\begin{figure}[h]    
%\hskip5.6cm
\hspace*{-5.6cm}
%\input{deu1.pic}
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(200.00,72.00)
\put(150.00,12.00){\line(1,0){10.00}}
\put(160.00,12.00){\line(0,1){10.00}}
\put(160.00,22.00){\line(0,1){10.00}}
\put(160.00,32.00){\line(1,0){30.00}}
\put(190.00,32.00){\line(0,1){10.00}}
\put(190.00,42.00){\line(1,0){10.00}}
\put(200.00,42.00){\line(0,1){10.00}}
\put(200.00,52.00){\line(-1,0){10.00}}
\put(190.00,52.00){\line(0,1){10.00}}
\put(190.00,62.00){\line(-1,0){20.00}}
\put(170.00,62.00){\line(0,-1){20.00}}
\put(170.00,42.00){\line(-1,0){10.00}}
\put(160.00,42.00){\line(0,1){30.00}}
\put(160.00,72.00){\line(-1,0){10.00}}
\put(150.00,72.00){\line(0,-1){10.00}}
\put(150.00,62.00){\line(-1,0){10.00}}
\put(140.00,62.00){\line(0,-1){30.00}}
\put(140.00,32.00){\line(-1,0){10.00}}
\put(130.00,32.00){\line(0,-1){10.00}}
\put(130.00,22.00){\line(-1,0){10.00}}
\put(120.00,22.00){\line(0,-1){20.00}}
\put(120.00,12.00){\line(1,0){30.00}}
\put(150.00,12.00){\line(0,1){50.00}}
\put(150.00,62.00){\line(1,0){10.00}}
\put(130.00,22.00){\line(1,0){10.00}}
\put(140.00,22.00){\line(0,1){10.00}}
\put(140.00,32.00){\line(1,0){20.00}}
\put(160.00,32.00){\line(0,1){10.00}}
\put(130.00,2.00){\line(0,1){20.00}}
\put(140.00,2.00){\line(0,1){20.00}}
\put(140.00,22.00){\line(1,0){20.00}}
\put(140.00,42.00){\line(1,0){20.00}}
\put(140.00,52.00){\line(1,0){20.00}}
\put(170.00,32.00){\line(0,1){10.00}}
\put(170.00,42.00){\line(1,0){20.00}}
\put(190.00,42.00){\line(0,1){10.00}}
\put(190.00,52.00){\line(-1,0){10.00}}
\put(180.00,52.00){\line(0,-1){20.00}}
\put(170.00,52.00){\line(1,0){10.00}}
\put(180.00,52.00){\line(0,1){10.00}}
\put(120.00,2.00){\line(1,0){20.00}}
\put(140.00,2.00){\line(1,0){10.00}}
\put(150.00,2.00){\line(0,1){10.00}}
\put(150.00,12.00){\line(-1,0){10.00}}
\put(140.00,2.00){\line(0,1){10.00}}
\end{picture}   
\caption{A  directed column-convex polyomino of area $25$}
\end{figure}

\begin{table}[h]
\begin{center}
\begin{tabular}{ c | c c c c c c c c c c }
        \( i \) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8   \\
        \hline
        \(a_i\) & 0 & 0 & 0 & 1 & 3 & 3 & 3 & 4 \\
        \(b_i\) & 2 & 3 & 6 & 7 & 4 & 6 & 6 & 5 \\
        \(b_{i-1}-a_i\) &  & 2 & 3 & 5 & 4 & 1 & 3 & 2 \\
\end{tabular}
\end{center}
\caption{} \label{Ta:1}
\end{table}
                                     
The tree \(\tau\) corresponding to \(\pi\) has root of degree \(b_8=5\),
the children of the root are labeled from left to right   
by $0, 1, 2, 3, 4$ and on the nodes with labels   
$0, 0, 1, 3, 3, 3, 4$ we hang
bouquets of
sizes, $2, 3, 5, 4, 1, 3, 2$, respectively (see Fig. 2). Conversely, assume
that the tree in Fig. 2 is given. Since bouqets of sizes   
$2, 3, 5, 4, 1, 3, 2$ are hanging from the nodes   
$0, 0, 1, 3, 3, 3, 4$ of level 1, it follows
that
the bottoms of the columns are at levels   
$0, 0, 0, 1, 3, 3, 3, 4$, while
the tops are at levels $2+0, 3+0, 5+1, 4+3, 1+3, 3+3, 2+4, 5$   
(the last being the degree of the root).


\begin{figure}[h]    
%\hskip4.2cm
\hspace*{-4.2cm}
%\input{deu5.pic}   
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(222.00,35.00)
\put(98.00,24.00){\circle*{2.00}}
\put(131.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(184.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(177.00,14.00){\line(2,3){6.67}}
\put(183.67,24.00){\line(0,-1){10.00}}
\put(191.00,14.33){\line(-3,4){7.25}}
\put(184.00,14.00){\circle*{2.00}}
\put(131.00,24.00){\circle*{2.00}}
\put(131.00,14.00){\circle*{2.00}}
\put(131.00,14.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,14.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,14.00){\circle*{2.00}}
\put(221.00,4.00){\circle*{2.00}}
\put(221.00,4.00){\line(0,1){20.00}}
\put(98.00,24.00){\circle*{2.00}}
\put(105.00,14.00){\circle*{2.00}}
\put(99.00,4.00){\circle*{2.00}}
\put(110.00,4.00){\circle*{2.00}}
\put(91.00,14.00){\circle*{2.00}}
\put(91.00,4.00){\circle*{2.00}}
\put(91.00,14.00){\line(2,3){6.67}}
\put(105.00,14.33){\line(-3,4){7.25}}
\put(91.00,4.00){\circle*{2.00}}
\put(91.00,4.33){\line(0,1){9.67}}
\put(98.00,24.00){\circle*{2.00}}
\put(98.00,24.00){\circle*{2.00}}
\put(131.00,24.00){\circle*{2.00}}
\put(131.00,24.00){\circle*{2.00}}
\put(131.00,24.00){\circle*{2.00}}
\put(131.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(184.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(221.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,24.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(158.00,34.00){\circle*{2.00}}
\put(97.67,24.33){\line(6,1){60.33}}
\put(158.00,34.39){\line(-5,-2){26.67}}
\put(158.00,24.00){\line(0,1){10.33}}
\put(158.00,34.33){\line(6,-1){63.00}}
\put(184.00,24.33){\line(-5,2){26.00}}
\put(99.00,4.00){\line(3,5){5.80}}
\put(104.80,13.67){\line(3,-5){5.80}}
\put(127.00,4.00){\circle*{2.00}}
\put(120.00,4.00){\circle*{2.00}}
\put(135.00,4.00){\circle*{2.00}}
\put(142.00,4.00){\circle*{2.00}}
\put(120.00,4.00){\line(1,1){10.67}}
\put(130.67,14.67){\line(-1,-3){3.56}}
\put(135.00,4.00){\line(-2,5){3.87}}
\put(131.13,13.67){\line(6,-5){11.20}}
\put(131.00,14.00){\line(0,1){10.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,4.00){\circle*{2.00}}
\put(174.00,4.00){\circle*{2.00}}
\put(177.67,14.00){\line(0,-1){10.00}}
\put(178.00,4.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(178.00,14.00){\circle*{2.00}}
\put(182.00,4.00){\circle*{2.00}}
\put(174.00,4.00){\line(2,5){4.00}}
\put(178.00,14.00){\line(2,-5){4.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(187.00,4.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(191.00,14.00){\circle*{2.00}}
\put(195.00,4.00){\circle*{2.00}}
\put(187.00,4.00){\line(2,5){4.00}}
\put(191.00,14.00){\line(2,-5){4.00}}
\end{picture}
\caption{An ordered tree with $25$ edges and height 3}
\end{figure}

\medskip

{\bf 3. Bijections with other combinatorial objects.}
 In this section we
sketch bijections between DCCPs, ordered
trees of height at most three, and three other combinatorial objects. Some
of these bijections reproduce those in \cite{prod} but this time we word
them differently (for example, without {\em words}).   

By a {\em nondecreasing Dyck path\/} we mean a Dyck path for which the
sequence of the altitudes of the valleys is nondecreasing. They have been
introduced and investigated in \cite{barc2}. There is a simple bijection
between DCCPs of area \(n\) and nondecreasing Dyck paths of length \(2n\).   
We explain it on an example. The columns of the DCCP of Fig.~1, traversed
from left to right, start at
the altitudes $0, 0, 0, 1, 3, 3, 3, 4$   
and end at the altitudes $2, 3, 6, 7, 4, 6, 6, 5$.
We associate to it a nondecreasing Dyck path for which the altitudes of
the valleys, including the origin, are   
$0, 0, 0, 1, 3, 3, 3, 4$ and the altitudes
of the peaks are $2, 3, 6, 7, 4, 6, 6, 5$.   
We obtain the nondecreasing Dyck path of
Fig.~3. The fact that the polyomino is directed ensures that the first of
these sequences is nondecreasing. The inverse mapping is obvious.   

\begin{figure}[h]    
%\hskip1.2cm
\hspace*{-1.8cm}
%\input{deu9.pic}   
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(282.00,36.00)
%\emline(32.00,1.00)(242.00,1.00)
\put(32.00,1.00){\line(1,0){210.00}}
%\end
%\emline(32.00,6.00)(242.00,6.00)
\put(32.00,6.00){\line(1,0){210.00}}
%\end
%\emline(32.00,11.00)(242.00,11.00)
\put(32.00,11.00){\line(1,0){210.00}}
%\end
%\emline(32.00,16.00)(242.00,16.00)
\put(32.00,16.00){\line(1,0){210.00}}
%\end
%\emline(32.00,21.00)(242.00,21.00)
\put(32.00,21.00){\line(1,0){210.00}}
%\end
%\emline(32.00,26.00)(242.00,26.00)
\put(32.00,26.00){\line(1,0){210.00}}
%\end
%\emline(32.00,31.00)(242.00,31.00)
\put(32.00,31.00){\line(1,0){210.00}}
%\end
%\emline(32.00,36.00)(242.00,36.00)
\put(32.00,36.00){\line(1,0){210.00}}
%\end
%\emline(32.00,1.00)(32.00,36.00)
\put(32.00,1.00){\line(0,1){35.00}}
%\end
%\emline(37.00,1.00)(37.00,36.00)
\put(37.00,1.00){\line(0,1){35.00}}
%\end
%\emline(42.00,1.00)(42.00,36.00)
\put(42.00,1.00){\line(0,1){35.00}}
%\end
%\emline(47.00,1.00)(47.00,36.00)
\put(47.00,1.00){\line(0,1){35.00}}
%\end
%\emline(52.00,1.00)(52.00,36.00)
\put(52.00,1.00){\line(0,1){35.00}}
%\end
%\emline(57.00,1.00)(57.00,36.00)
\put(57.00,1.00){\line(0,1){35.00}}
%\end
%\emline(62.00,1.00)(62.00,36.00)
\put(62.00,1.00){\line(0,1){35.00}}
%\end
%\emline(67.00,1.00)(67.00,36.00)
\put(67.00,1.00){\line(0,1){35.00}}
%\end
%\emline(72.00,1.00)(72.00,36.00)
\put(72.00,1.00){\line(0,1){35.00}}
%\end
%\emline(77.00,1.00)(77.00,36.00)
\put(77.00,1.00){\line(0,1){35.00}}
%\end
%\emline(82.00,1.00)(82.00,36.00)
\put(82.00,1.00){\line(0,1){35.00}}
%\end
%\emline(87.00,1.00)(87.00,36.00)
\put(87.00,1.00){\line(0,1){35.00}}
%\end
%\emline(92.00,1.00)(92.00,36.00)
\put(92.00,1.00){\line(0,1){35.00}}
%\end
%\emline(97.00,1.00)(97.00,36.00)
\put(97.00,1.00){\line(0,1){35.00}}
%\end
%\emline(102.00,1.00)(102.00,36.00)
\put(102.00,1.00){\line(0,1){35.00}}
%\end
%\emline(107.00,1.00)(107.00,36.00)
\put(107.00,1.00){\line(0,1){35.00}}
%\end
%\emline(112.00,1.00)(112.00,36.00)
\put(112.00,1.00){\line(0,1){35.00}}
%\end
%\emline(117.00,1.00)(117.00,36.00)
\put(117.00,1.00){\line(0,1){35.00}}
%\end
%\emline(122.00,1.00)(122.00,36.00)
\put(122.00,1.00){\line(0,1){35.00}}
%\end
%\emline(127.00,1.00)(127.00,36.00)
\put(127.00,1.00){\line(0,1){35.00}}
%\end
%\emline(132.00,1.00)(132.00,36.00)
\put(132.00,1.00){\line(0,1){35.00}}
%\end
%\emline(137.00,1.00)(137.00,36.00)
\put(137.00,1.00){\line(0,1){35.00}}
%\end
%\emline(142.00,1.00)(142.00,36.00)
\put(142.00,1.00){\line(0,1){35.00}}
%\end
%\emline(147.00,1.00)(147.00,36.00)
\put(147.00,1.00){\line(0,1){35.00}}
%\end
%\emline(152.00,1.00)(152.00,36.00)
\put(152.00,1.00){\line(0,1){35.00}}
%\end
%\emline(157.00,1.00)(157.00,36.00)
\put(157.00,1.00){\line(0,1){35.00}}
%\end
%\emline(162.00,1.00)(162.00,36.00)
\put(162.00,1.00){\line(0,1){35.00}}
%\end
%\emline(167.00,1.00)(167.00,36.00)
\put(167.00,1.00){\line(0,1){35.00}}
%\end
%\emline(172.00,1.00)(172.00,36.00)
\put(172.00,1.00){\line(0,1){35.00}}
%\end
%\emline(177.00,1.00)(177.00,36.00)
\put(177.00,1.00){\line(0,1){35.00}}
%\end
%\emline(182.00,1.00)(182.00,36.00)
\put(182.00,1.00){\line(0,1){35.00}}
%\end
%\emline(187.00,1.00)(187.00,36.00)
\put(187.00,1.00){\line(0,1){35.00}}
%\end
%\emline(192.00,1.00)(192.00,36.00)
\put(192.00,1.00){\line(0,1){35.00}}
%\end
%\emline(197.00,1.00)(197.00,36.00)
\put(197.00,1.00){\line(0,1){35.00}}
%\end
%\emline(202.00,1.00)(202.00,36.00)
\put(202.00,1.00){\line(0,1){35.00}}
%\end
%\emline(207.00,1.00)(207.00,36.00)
\put(207.00,1.00){\line(0,1){35.00}}
%\end
%\emline(212.00,1.00)(212.00,36.00)
\put(212.00,1.00){\line(0,1){35.00}}
%\end
%\emline(217.00,1.00)(217.00,36.00)
\put(217.00,1.00){\line(0,1){35.00}}
%\end
%\emline(222.00,1.00)(222.00,36.00)
\put(222.00,1.00){\line(0,1){35.00}}
%\end
%\emline(227.00,1.00)(227.00,36.00)
\put(227.00,1.00){\line(0,1){35.00}}
%\end
%\emline(232.00,1.00)(232.00,36.00)
\put(232.00,1.00){\line(0,1){35.00}}
%\end
%\emline(237.00,1.00)(237.00,36.00)
\put(237.00,1.00){\line(0,1){35.00}}
%\end
%\emline(242.00,1.00)(242.00,36.00)
\put(242.00,1.00){\line(0,1){35.00}}
%\end
%\emline(247.00,1.00)(247.00,36.00)
\put(247.00,1.00){\line(0,1){35.00}}
%\end
%\emline(252.00,1.00)(252.00,36.00)
\put(252.00,1.00){\line(0,1){35.00}}
%\end
%\emline(257.00,1.00)(257.00,36.00)
\put(257.00,1.00){\line(0,1){35.00}}
%\end
%\emline(262.00,1.00)(262.00,36.00)
\put(262.00,1.00){\line(0,1){35.00}}
%\end
%\emline(267.00,1.00)(267.00,36.00)
\put(267.00,1.00){\line(0,1){35.00}}
%\end
%\emline(272.00,1.00)(272.00,36.00)
\put(272.00,1.00){\line(0,1){35.00}}
%\end
%\emline(277.00,1.00)(277.00,36.00)
\put(277.00,1.00){\line(0,1){35.00}}
%\end
%\emline(282.00,1.00)(282.00,36.00)
\put(282.00,1.00){\line(0,1){35.00}}
%\end
%\emline(32.00,1.00)(42.00,11.00)
\multiput(32.00,1.00)(0.12,0.12){84}{\line(0,1){0.12}}
%\end
%\emline(42.00,11.00)(52.00,1.00)
\multiput(42.00,11.00)(0.12,-0.12){84}{\line(0,-1){0.12}}
%\end
%\emline(52.00,1.00)(52.00,1.00)
\put(52.00,1.00){\line(0,1){0.00}}
%\end
%\emline(52.00,1.00)(67.00,16.00)
\multiput(52.00,1.00)(0.12,0.12){126}{\line(0,1){0.12}}
%\end
%\emline(67.00,16.00)(82.00,1.00)
\multiput(67.00,16.00)(0.12,-0.12){126}{\line(0,-1){0.12}}
%\end
%\emline(207.00,6.00)(207.00,6.00)
\put(207.00,6.00){\line(0,1){0.00}}
%\end
%\emline(82.00,1.00)(112.00,31.00)
\multiput(82.00,1.00)(0.12,0.12){250}{\line(0,1){0.12}}
%\end
%\emline(112.00,31.00)(137.00,6.00)
\multiput(112.00,31.00)(0.12,-0.12){209}{\line(0,-1){0.12}}
%\end
%\emline(137.00,6.00)(167.00,36.00)
\multiput(137.00,6.00)(0.12,0.12){250}{\line(0,1){0.12}}
%\end
%\emline(167.00,36.00)(187.00,16.00)
\multiput(167.00,36.00)(0.12,-0.12){167}{\line(0,-1){0.12}}
%\end
%\emline(187.00,16.00)(192.00,21.00)
\multiput(187.00,16.00)(0.12,0.12){42}{\line(0,1){0.12}}
%\end
%\emline(192.00,21.00)(197.00,16.00)
\multiput(192.00,21.00)(0.12,-0.12){42}{\line(0,-1){0.12}}
%\end
%\emline(197.00,16.00)(212.00,31.00)
\multiput(197.00,16.00)(0.12,0.12){126}{\line(0,1){0.12}}
%\end
%\emline(212.00,31.00)(227.00,16.00)
\multiput(212.00,31.00)(0.12,-0.12){126}{\line(0,-1){0.12}}
%\end
%\emline(227.00,16.00)(242.00,31.00)
\multiput(227.00,16.00)(0.12,0.12){126}{\line(0,1){0.12}}
%\end
%\emline(242.00,31.00)(252.00,21.00)
\multiput(242.00,31.00)(0.12,-0.12){84}{\line(0,-1){0.12}}
%\end
%\emline(252.00,21.00)(257.00,26.00)
\multiput(252.00,21.00)(0.12,0.12){42}{\line(0,1){0.12}}
%\end
%\emline(257.00,26.00)(282.00,1.00)
\multiput(257.00,26.00)(0.12,-0.12){209}{\line(0,-1){0.12}}
%\end
%\emline(242.00,1.00)(282.00,1.00)
\put(242.00,1.00){\line(1,0){40.00}}
%\end
%\emline(242.00,6.00)(282.00,6.00)
\put(242.00,6.00){\line(1,0){40.00}}
%\end
%\emline(242.00,11.00)(282.00,11.00)
\put(242.00,11.00){\line(1,0){40.00}}
%\end
%\emline(242.00,16.00)(282.00,16.00)
\put(242.00,16.00){\line(1,0){40.00}}
%\end
%\emline(242.00,21.00)(282.00,21.00)
\put(242.00,21.00){\line(1,0){40.00}}
%\end
%\emline(242.00,26.00)(282.00,26.00)
\put(242.00,26.00){\line(1,0){40.00}}
%\end
%\emline(242.00,31.00)(282.00,31.00)
\put(242.00,31.00){\line(1,0){40.00}}
%\end
%\emline(242.00,36.00)(282.00,36.00)
\put(242.00,36.00){\line(1,0){40.00}}
%\end
\end{picture}
\caption{A nondecreasing Dyck path of length 50}
\end{figure}

There is a well-known bijection between Dyck paths and ordered trees
(traverse the tree in preorder, the root being at the top; to each edge
passed on the way down there correspond a NE step and to each edge passed
on the way up  there corresponds a SE step). The nondecreasing restriction
on the Dyck path implies that the ordered tree can have branch nodes only
on its righmost path. We call such trees {\em Elena trees}, or simply {\em
Elenas} (see \cite{prod}). For example, to the nondecreasing Dyck path of
Fig.~3 there corresponds the Elena of Fig.~4. For the purpose of further
identification, we have marked the edges along the rightmost path by
\(a,b,c,d,e\).   

\begin{figure}[h]    
%\input{deut2.pic}
%\hskip5.3cm   
\hspace*{-5.5cm}
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(197.00,75.00)
\put(121.00,74.00){\circle*{2.00}}
\put(136.00,64.00){\circle*{2.00}}
\put(151.00,54.00){\circle*{2.00}}
\put(166.00,44.00){\circle*{2.00}}
\put(166.00,44.00){\circle*{2.00}}
\put(181.00,34.00){\circle*{2.00}}
\put(196.00,24.00){\circle*{2.00}}
\put(181.00,24.00){\circle*{2.00}}
\put(181.00,14.00){\circle*{2.00}}
\put(181.00,14.00){\line(0,1){20.00}}
\put(173.00,34.00){\circle*{2.00}}
\put(173.00,24.00){\circle*{2.00}}
\put(173.00,14.00){\circle*{2.00}}
\put(173.00,14.00){\line(0,1){20.00}}
\put(166.00,34.00){\circle*{2.00}}
\put(159.00,34.00){\circle*{2.00}}
\put(159.00,24.00){\circle*{2.00}}
\put(159.00,14.00){\circle*{2.00}}
\put(159.00,14.00){\line(0,1){20.00}}
\put(159.00,34.00){\line(2,3){6.67}}
\put(165.67,44.00){\line(0,-1){10.00}}
\put(173.00,34.33){\line(-3,4){7.25}}
\put(159.00,24.00){\circle*{2.00}}
\put(159.00,14.00){\circle*{2.00}}
\put(159.00,4.00){\circle*{2.00}}
\put(159.00,4.00){\line(0,1){20.00}}
\put(166.00,34.00){\circle*{2.00}}
\put(136.00,64.00){\circle*{2.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(136.00,44.00){\circle*{2.00}}
\put(136.00,44.00){\line(0,1){20.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(136.00,44.00){\circle*{2.00}}
\put(136.00,34.00){\circle*{2.00}}
\put(136.00,34.00){\line(0,1){20.00}}
\put(136.00,34.00){\circle*{2.00}}
\put(136.00,24.00){\circle*{2.00}}
\put(136.00,34.00){\circle*{2.00}}
\put(136.00,24.00){\circle*{2.00}}
\put(136.00,14.00){\circle*{2.00}}
\put(136.00,14.00){\line(0,1){20.00}}
\put(121.00,74.00){\circle*{2.00}}
\put(128.00,64.00){\circle*{2.00}}
\put(128.00,54.00){\circle*{2.00}}
\put(128.00,44.00){\circle*{2.00}}
\put(128.00,44.00){\line(0,1){20.00}}
\put(114.00,64.00){\circle*{2.00}}
\put(114.00,54.00){\circle*{2.00}}
\put(114.00,64.00){\line(2,3){6.67}}
\put(128.00,64.33){\line(-3,4){7.25}}
\put(114.00,54.00){\circle*{2.00}}
\put(114.00,54.33){\line(0,1){9.67}}
\put(196.00,24.00){\line(-3,2){75.33}}
\put(131.00,71.67){\makebox(0,0)[cc]{$a$}}
\put(146.33,62.00){\makebox(0,0)[cc]{$b$}}
\put(161.00,51.33){\makebox(0,0)[cc]{$c$}}
\put(176.67,42.33){\makebox(0,0)[cc]{$d$}}
\put(191.33,32.67){\makebox(0,0)[cc]{$e$}}
\end{picture}
\caption{An Elena with 25 edges}
\end{figure}   




We can view the Elena of Fig. 4 as a concatenation of the trees in Fig. 5.
We consider these trees rooted at the top. Concatenating them by
identifying their roots, we obtain the tree of Fig. 6. This is a tree   
with no branch nodes at height greater than one.

\begin{figure}[ht]    
%\hskip 4.4cm
\hspace*{-4.8cm}
%\input{deu3.pic}   
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(221.00,65.00)
\put(109.00,54.00){\circle*{2.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(198.00,44.00){\circle*{2.00}}
\put(198.00,34.00){\circle*{2.00}}
\put(198.00,24.00){\circle*{2.00}}
\put(198.00,24.00){\line(0,1){20.00}}
\put(191.00,44.00){\circle*{2.00}}
\put(185.00,44.00){\circle*{2.00}}
\put(185.00,34.00){\circle*{2.00}}
\put(185.00,24.00){\circle*{2.00}}
\put(185.00,24.00){\line(0,1){20.00}}
\put(184.00,44.00){\line(2,3){6.67}}
\put(190.67,54.00){\line(0,-1){10.00}}
\put(198.00,44.33){\line(-3,4){7.25}}
\put(185.00,34.00){\circle*{2.00}}
\put(185.00,24.00){\circle*{2.00}}
\put(185.00,14.00){\circle*{2.00}}
\put(185.00,14.00){\line(0,1){20.00}}
\put(191.00,44.00){\circle*{2.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(136.00,44.00){\circle*{2.00}}
\put(217.00,64.00){\circle*{2.00}}
\put(136.00,34.00){\line(0,1){20.00}}
\put(136.00,44.00){\circle*{2.00}}
\put(217.00,64.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(136.00,24.00){\line(0,1){20.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(217.00,44.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(217.00,44.00){\circle*{2.00}}
\put(217.00,34.00){\circle*{2.00}}
\put(217.00,34.00){\line(0,1){20.00}}
\put(109.00,54.00){\circle*{2.00}}
\put(116.00,44.00){\circle*{2.00}}
\put(116.00,34.00){\circle*{2.00}}
\put(116.00,24.00){\circle*{2.00}}
\put(116.00,24.00){\line(0,1){20.00}}
\put(102.00,44.00){\circle*{2.00}}
\put(102.00,34.00){\circle*{2.00}}
\put(102.00,44.00){\line(2,3){6.67}}
\put(116.00,44.33){\line(-3,4){7.25}}
\put(102.00,34.00){\circle*{2.00}}
\put(102.00,34.33){\line(0,1){9.67}}
\put(113.00,58.67){\makebox(0,0)[cc]{$a$}}
\put(109.00,64.00){\circle*{2.00}}
\put(109.00,64.00){\circle*{2.00}}
\put(109.00,54.00){\circle*{2.00}}
\put(108.67,64.00){\line(0,-1){10.00}}
\put(109.00,54.00){\circle*{2.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(140.00,58.67){\makebox(0,0)[cc]{$b$}}
\put(136.00,64.00){\circle*{2.00}}
\put(136.00,64.00){\circle*{2.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(135.67,64.00){\line(0,-1){10.00}}
\put(136.00,54.00){\circle*{2.00}}
\put(165.00,54.00){\circle*{2.00}}
\put(165.00,54.00){\circle*{2.00}}
\put(165.00,54.00){\circle*{2.00}}
\put(165.00,54.00){\circle*{2.00}}
\put(169.00,58.67){\makebox(0,0)[cc]{$c$}}
\put(165.00,64.00){\circle*{2.00}}
\put(165.00,64.00){\circle*{2.00}}
\put(165.00,54.00){\circle*{2.00}}
\put(165.00,64.00){\line(0,-1){10.00}}
\put(165.00,54.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(195.00,58.67){\makebox(0,0)[cc]{$d$}}
\put(191.00,64.00){\circle*{2.00}}
\put(191.00,64.00){\circle*{2.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(191.00,64.00){\line(0,-1){10.00}}
\put(191.00,54.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(221.00,58.67){\makebox(0,0)[cc]{$e$}}
\put(217.00,64.00){\circle*{2.00}}
\put(217.00,64.00){\circle*{2.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(217.00,64.00){\line(0,-1){10.00}}
\put(217.00,54.00){\circle*{2.00}}
\put(136.00,34.00){\circle*{2.00}}
\put(136.00,24.00){\circle*{2.00}}
\put(136.00,14.00){\circle*{2.00}}
\put(136.00,14.00){\line(0,1){20.00}}
\put(136.00,24.00){\circle*{2.00}}
\put(136.00,14.00){\circle*{2.00}}
\put(136.00,4.00){\circle*{2.00}}
\put(136.00,4.00){\line(0,1){20.00}}
\end{picture}
\caption{The constituents of the Elena of Fig. 4}
\end{figure}   

\begin{figure}[ht]    
%\hskip 5.8cm
 \hspace*{-6.0cm}
%\input{deu4.pic}   
\unitlength 0.50mm
\linethickness{0.4pt}
\begin{picture}(190.00,68.00)
\put(130.00,57.00){\circle*{2.00}}
\put(148.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(179.00,47.00){\circle*{2.00}}
\put(179.00,37.00){\circle*{2.00}}
\put(179.00,27.00){\circle*{2.00}}
\put(179.00,27.00){\line(0,1){20.00}}
\put(172.00,47.00){\circle*{2.00}}
\put(166.00,47.00){\circle*{2.00}}
\put(166.00,37.00){\circle*{2.00}}
\put(166.00,27.00){\circle*{2.00}}
\put(166.00,27.00){\line(0,1){20.00}}
\put(165.00,47.00){\line(2,3){6.67}}
\put(171.67,57.00){\line(0,-1){10.00}}
\put(179.00,47.33){\line(-3,4){7.25}}
\put(166.00,37.00){\circle*{2.00}}
\put(166.00,27.00){\circle*{2.00}}
\put(166.00,17.00){\circle*{2.00}}
\put(166.00,17.00){\line(0,1){20.00}}
\put(172.00,47.00){\circle*{2.00}}
\put(148.00,57.00){\circle*{2.00}}
\put(148.00,47.00){\circle*{2.00}}
\put(148.00,37.00){\line(0,1){20.00}}
\put(148.00,47.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(148.00,27.00){\line(0,1){20.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,47.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,47.00){\circle*{2.00}}
\put(189.00,37.00){\circle*{2.00}}
\put(189.00,37.00){\line(0,1){20.00}}
\put(130.00,57.00){\circle*{2.00}}
\put(137.00,47.00){\circle*{2.00}}
\put(137.00,37.00){\circle*{2.00}}
\put(137.00,27.00){\circle*{2.00}}
\put(137.00,27.00){\line(0,1){20.00}}
\put(123.00,47.00){\circle*{2.00}}
\put(123.00,37.00){\circle*{2.00}}
\put(123.00,47.00){\line(2,3){6.67}}
\put(137.00,47.33){\line(-3,4){7.25}}
\put(123.00,37.00){\circle*{2.00}}
\put(123.00,37.33){\line(0,1){9.67}}
\put(130.00,57.00){\circle*{2.00}}
\put(130.00,57.00){\circle*{2.00}}
\put(148.00,57.00){\circle*{2.00}}
\put(148.00,57.00){\circle*{2.00}}
\put(148.00,57.00){\circle*{2.00}}
\put(148.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(172.00,57.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(189.00,57.00){\circle*{2.00}}
\put(148.00,37.00){\circle*{2.00}}
\put(148.00,27.00){\circle*{2.00}}
\put(148.00,17.00){\circle*{2.00}}
\put(148.00,17.00){\line(0,1){20.00}}
\put(148.00,27.00){\circle*{2.00}}
\put(148.00,17.00){\circle*{2.00}}
\put(148.00,7.00){\circle*{2.00}}
\put(148.00,7.00){\line(0,1){20.00}}
\put(160.00,67.00){\circle*{2.00}}
\put(160.00,67.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,57.00){\circle*{2.00}}
\put(160.00,67.00){\circle*{2.00}}
\put(160.00,67.00){\circle*{2.00}}
\put(160.00,67.00){\circle*{2.00}}
\put(160.00,67.00){\circle*{2.00}}
\put(160.00,57.00){\line(0,1){10.00}}
\put(130.00,57.00){\line(3,1){30.00}}
\put(160.00,67.00){\line(0,0){0.00}}
\put(160.00,67.00){\line(-5,-4){12.00}}
\put(172.00,57.33){\line(-5,4){11.67}}
\put(160.33,66.67){\line(3,-1){28.67}}
\end{picture}
\caption{The constituents glued together at the root}
\end{figure}




Finally, if in the tree of Fig. 6 we replace all the paths that start
at level 2 by a bouquet of the same size, then we obtain the tree of Fig.
2. This is a tree of height at most three.   

\medskip


{\bf 4. Bijection correspondences.}

In this section we give correspondences under the mentioned bijections between various statistics on DCCPs, nondecreasing Dyck paths, Elena trees, and ordered trees of height   
at most three. They follow more or less immediately from the definitions of the bijections.   
First we introduce some additional terminology.   

In a Dyck path by a {\em return} we mean a SE step hitting the \(x\)-axis; by an {\em ascent}   
we mean a maximal string of NE steps. A {\em pyramid} in a Dyck path is a succession of NE   
steps followed immediately by the same number of SE steps. An {\em exterior pair} in a Dyck   
path is a pair consisting of a NE step and its matching SE step (i.e. connectable to the NE   
step by a horizontal line lying strictly under the path) which do not belong to any pyramid.   
The statistic ``number of exterior pairs" and the closely related statistic ``pyramid weight" have been investigated in \cite{densio}. It is easy to see that in a nondecreasing Dyck path   
the number of exterior pairs is equal to the altitude of the last valley.   

In an ordered tree by a {\em branch node} we mean a node of outdegree at least 2. By a {\em branch} we mean a minimal succession of edges joining either the root with a branch node, or   
two branch nodes, or a branch node with a leaf.   

In an ordered tree of height at most three we label the children of the root from left to   
right by 0,1,2,\ldots (these labels will be used below).   

In order to have a simpler formulation of the bijection correspondences, we assume that the considered DCCP does not consist of a single column. To a single-column DCCP of height \(n\) there correspond a nondecreasing Dyck path that is a pyramid of height \(n\), an Elena tree   
that is a path of length \(n\), and a tree of height 1 with \(n\) edges.


\begin{scriptsize}
\begin{table}[h]
\begin{center}
\setlength{\extrarowheight}{1pt}
\begin{tabular}{ |l | l| l| l |}
\hline
        DCCPs & Nondecreasing   
Dyck paths & Elena trees & Trees of height $\leq 3$    \\
        \hline\hline

area &semilength  &size&size\\   
\hline
number of columns   &number of peaks & number of leaves   &
$1+$ number of nodes at level 2\\   
\hline
number of cells    &number of returns   &root degree   &
total degree of the \\   
 in bottom row   & &  &
leftmost child of the root\\   
\hline
number of cells      &altitude of 1st peak &
level of leftmost leaf  & 
label of the leftmost child of
\\   
in 1st column&&&  the root on which a bouquet 
\\ &&&  
hangs $+$ size of this bouquet
\\   
\hline
number of cells   &length of rightmost ascent     & 
length of last branch    &$1+$ number of final \\
in last column&&&leaves at level $1$\\
\hline
level of the bottom     &
altitude of last valley &level of last branchpoint    
&label of the last nonleaf \\   
of the last column&(=number of exterior pairs)&&
child of the root\\
\hline

level of the top      &altitude of the last peak &
level of rightmost leaf&root degree
  \\   
of the last column&&&\\

\hline
\end{tabular}



 



\end{center}
\caption{How 7 parameters translate under the bijections discussed in 
the paper. ``Last'' in the columns related to trees is with respect to
preorder traversal.
The numerical values for our running example are
25, 8, 3, 2, 1, 4, 5, respectively.} \label{Ta:2}
\end{table}

\end{scriptsize}

%\medskip


{\bf 5. Appendix.}   
Making use of the symbolic method \cite{sedfla, flased}, we derive   
(a) the generating function of the DCCPs and (b) the generating functions
of ordered trees of height at most three.   

(a) Every DCCP is either (i) the empty DCCP or (ii) its bottom
row consists of a single cell (in which case, above it, left justified, we
have a possibly empty DCCP), or (iii) to the right of its first column we
have a nonempty DCCP.   
(see Fig. 7).
Denoting the generation function by
\(G(z)\), this
leads at once to the equation
\begin{equation}
G = 1 + zG + \frac{z}{1-z}(G - 1),
\end{equation}
the factor \(\frac{z}{1-z}\) being the generating function of the
sequence of possible first columns in the case
(iii). The solution of (1) is \(\frac{1-2z}{1-3z+z^2}\).   

\begin{figure}[ht]    
%\input{deu11.pic}   
\hspace*{-3.3cm}
\unitlength 0.40mm
\linethickness{0.4pt}
\begin{picture}(317.79,56.58)
\put(81.67,7.00){\makebox(0,0)[cc]{$\mathcal{D}\ \ =$}}
%\emline(131.33,2.67)(141.33,2.67)
\put(131.33,2.67){\line(1,0){10.00}}
%\end
%\emline(141.33,2.67)(141.33,13.00)
\put(141.33,2.67){\line(0,1){10.33}}
%\end
%\emline(141.33,13.00)(131.33,13.00)
\put(141.33,13.00){\line(-1,0){10.00}}
%\end
%\emline(131.33,13.00)(131.33,2.67)
\put(131.33,13.00){\line(0,-1){10.33}}
%\end
\put(107.00,7.33){\makebox(0,0)[cc]{$\bullet$}}
\put(119.67,7.33){\makebox(0,0)[cc]{$+$}}
%\emline(131.33,50.67)(131.33,16.67)
\put(131.33,50.67){\line(0,-1){34.00}}
%\end
%\emline(131.33,16.67)(163.00,16.67)
\put(131.33,16.67){\line(1,0){31.67}}
%\end
\bezier{132}(131.33,50.33)(152.00,51.33)(156.67,40.33)
\bezier{100}(156.33,40.67)(158.67,37.33)(162.67,16.67)
\put(145.33,32.33){\makebox(0,0)[cc]{$\mathcal{D}$}}
\put(168.67,7.67){\makebox(0,0)[cc]{$+$}}
\put(200.82,47.48){\line(0,-1){44.85}}
\put(200.82,2.64){\line(1,0){116.97}}
\bezier{680}(200.82,46.88)(315.97,56.58)(317.79,2.64)
\put(247.48,20.82){\makebox(0,0)[cc]{$\mathcal{D}\setminus\{\bullet\}$}}
\put(184.67,23.00){\line(0,-1){20.33}}
\put(184.67,2.67){\line(1,0){10.33}}
\put(195.00,2.67){\line(0,1){20.00}}
\put(184.67,35.00){\line(0,1){17.67}}
\put(184.67,52.67){\line(1,0){10.33}}
\put(195.00,35.00){\line(0,1){17.67}}
\put(184.67,31.33){\makebox(0,0)[cc]{$\vdots$}}
\put(195.00,31.33){\makebox(0,0)[cc]{$\vdots$}}
\end{picture}
\caption{The symbolic equation for $\mathcal{D}=$DCCP}
\end{figure}


(b) The trees of height at most 1 have generating function
\(\frac{1}{1-z}\).
Consequently, trees of height at most 2 and having root of degree
1 have generating
function \(\frac{z}{1-z}\). Taking finite sequences of the latter and
joining them at their roots we obtain all the trees of height at most 2
and the generating function is \(\frac{1}{1-\frac{z}{1-z}} =
\frac{1-z}{1-2z}\). Consequently, trees of height at most 3 and having   
root of degree 1 have
generating function \(\frac{z(1-z)}{1-2z}\) and, taking again finite
sequences of the latter and joining them at their roots, we obtain all the
trees of height at most three and the generating function is
\[
	\frac{1}{1-\dfrac{z(1-z)}{1-2z}} = \frac{1-2z}{1-3z+z^2}.
\]

%{\em Remark.} This note originates from a relatively recent paper by E.
%Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani on {\em nondecreasing
%Dyck paths} \cite{barc2}. These are Dyck paths for which the sequence of
%the altitudes of the valleys is nondecreasing. The authors of the present
%note have found independently a simple bijection between nondecreasing
%Dyck paths and directed column-convex polyominoes (unpublished),
%respectively a bijection between nondecreasing Dyck paths and ordered
%trees of height at most three \cite{prod}.   


%yyyyyy

\begin{thebibliography}{60}

\bibitem{barc1}
E. Barcucci, R. Pinzani, and R. Sprugnoli, Directed column-convex
polyominoes by recurrence relations, in: M.-C.~Gaudel and   
J.-P.~Jouannaud
(eds.), TAPSOFT '93: Theory and Practice of Software Development,
Proceedings of the 4th International Joint Conference CAAP/FASE, Orsay,
France, April 1993, Lecture Notes in Computer Science, No. 668, Springer,
Berlin (1993), pp. 282-298.

\bibitem{barc2}
E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, Nondecreasing Dyck
paths and \(q\)-Fibonacci numbers,  Discrete Math., 170, 211-217, 1997.   

\bibitem{brui}
N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of
planted trees, in: Graph Theory and Computing (edited by R. C. Read),
Academic Press, New York (1972), pp. 15-22. Reprinted in:
Selected papers on analysis of algorithms. CSLI Publications, Stanford, CA, 2000. xvi+621 pp. 



\bibitem{densio}
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 155-176, 1995.   

\bibitem{flased}   
P. Flajolet and R. Sedgewick, Analytic Combinatorics. Book in
preparation, 1998. (Individual chapters are available as INRIA
Research Reports 1888, 2026, 2376, 2956, 3162.)

\bibitem{prod}
H. Prodinger, Words, Dyck paths, trees, and bijections.
In: Words, semigroups, and transductions, 369--379, World Sci. Publishing, River Edge, NJ, 2001.


\bibitem{sedfla}
R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms,   
Addison-Wesley, Reading, 1996.

\bibitem{sloplo}
N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences,   
Academic Press, San Diego, 1995.   

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


%zzzzzz
\end{thebibliography}    



          
\end{document}



