\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

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

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

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

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{amsthm}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{latexsym}
\usepackage{graphics}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Sequences That Satisfy $a(n{-}a(n))=0$}

\vskip 1cm
\large
Nate Kube\footnote{Research supported in part by a NSERC PGS-M scholarship.}
\ and \
Frank Ruskey\footnote{Research supported in part by NSERC.} \\
Department of Computer Science \\
University of Victoria \\
Victoria, British Columbia V8W 3P6 \\
CANADA \\
\href{nkube@cs.uvic.ca}{\tt nkube@cs.uvic.ca} \\
\begin{center}
\epsfxsize=1.75in
\leavevmode\epsffile{rusk.eps}
\end{center}
\end{center}


\vskip .2 in
\begin{abstract}
We explore the properties of some sequences for which
$a(n-a(n))=0$. Under the natural restriction that $a(n) < n$ the
number of such sequences is a Bell number. Adding other natural
restrictions yields sequences counted by the Catalan numbers, the
Narayana numbers, the triangle of triangular binomial
coefficients, and the Schr\"{o}der numbers.
\end{abstract}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\theoremstyle{plain}
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\def\I#1{{[\![#1]\!]}}            % Iversonian

%\begin{document}

\section{Introduction, set partitions}

We consider here sequences $a(1),a(2),\ldots,a(n)$ with the property
that $a(j-a(j)) = 0$ for all $j = 1,2,\ldots,n$. Naturally, we must
have $1 \le j-a(j) \le n$ for $j = 1,2,\ldots,n$.  Let
$\mathbf{F}(n)$ be the set of all such sequences, and let
$\mathbf{F}(n,m)$ be the subset of those for which $m$ of the $a(j)$
are zero.\footnote{Throughout the paper we will use a bold-case
letter, like $\mathbf{X}$ to denote a set of sequences, $\mathbf{X}(n)$
to denote the sequences in $\mathbf{X}$ of length $n$, and
$\mathbf{X}(n,m)$ to denote the sequences in $\mathbf{X}(n)$ that
contain exactly $m$ zeroes.}
\begin{theorem}
For all $1 \le m \le n$,
\[
|\mathbf{F}(n,m)| = {n \choose m} m^{n-m}.
\]
\label{thm:F}
\end{theorem}
\begin{proof}
There are ${n \choose m}$ ways to choose the $m$ indices $J =
  \{j_1,j_2,\ldots,j_m\}$ for which $a(j) = 0$.
Each of the $n-m$
  other elements $t$ can take on any value from the $m$-set
  $\{ t - j : j \in J \}$. For such a value of $t$,
  we have $a(t-a(t)) = a( t - (t - j)) = a(j) = 0$.
\end{proof}

The numbers occurring in Theorem \ref{thm:F} are not in the OEIS \cite{OEIS}
but summing on $m$ yields A000248, the number of labelled forests
in which every tree is a star (isomorphic to $K_{1s}$ for some
$s$).  To get a correspondence with our sequences, let the parent
of node $j$ be node $j-a(j)$, with roots regarded as self-parents.

Comtet \cite{Comtet} calls these numbers the ``idempotent numbers"
  (see pp. 91,135).
The number of idempotent functions on an $n$-set that have $m$
  fixed-points is ${n \choose m} m^{n-m}$.

If we take the subset of $\mathbf{F}(n)$ that is closed under the
taking of prefixes (or, equivalently, that the $a(j)$ only take on
non-negative values), then we get the additional constraint that
$a(j) < j$ for $j = 1,2,\ldots,n$. (Of course, the set of
sequences that only satisfy the condition $a(j) < j$ has
cardinality $n!$, but our condition is stronger.) Let
$\mathbf{A}(n)$ denote the set of all such sequences and let
$\mathbf{A}(n,m)$ denote the subset of $\mathbf{A}(n)$ consisting
of sequences with exactly $m$ zeroes. Below we list the elements
of $\mathbf{A}(n)$ for $n = 1,2,3,4$.

\begin{eqnarray*}
\mathbf{A}(1) & = & \{ 0 \} \\
\mathbf{A}(2) & = & \{ 00, 01 \} \\
\mathbf{A}(3) & = & \{ 000, 001, 002, 010, 012 \} \\
\mathbf{A}(4) & = & \{ 0000, 0001, 0002, 0003, 0010, 0012, 0013, 0020, \\
     &   &    0022, 0023, 0100, 0101, 0103, 0120, 0123 \}
\end{eqnarray*}

Note that $011$ is missing from $\mathbf{A}(3)$ since then
$a(3-a(3)) = a(3-1) = a(2) = 1 \neq 0$.
% It is easy enough to write
% an efficient program to list the elements of $\mathbf{A}(n)$ and
% we find that there is an exact match with the Bell numbers
% A000110.
Using the notation of Comtet \cite{Comtet} and Knuth
\cite{Knuth7215}, we denote the $n$-th Bell number, A000110, by $\varpi_n$ and
Stirling numbers of the second kind, A008277, by ${n \brace m}$.

\begin{theorem} For all $0 < m \le n$,
\[
|\mathbf{A}(n)| = \varpi_n \ \ \mbox{ and } \ \ |\mathbf{A}(n,m)| = {n \brace m}.
\]
\end{theorem}
\begin{proof}
Let $j_1,j_2,\cdots,j_m$ be the positions for which
  $a(j) = 0$.
Now define the $i$-th block of a partition to be
the set
\[
B_i = \{ k : k-a(k) = j_i \}.
\]
Note that $j_i$ is the smallest element of $B_i$.
It should be clear that this specifies a one-to-one
correspondence.
\end{proof}

\textbf{Example:} The sequence that corresponds to the partition
$\{1,3,4\},\{2,5,8\},\{6,7\}$ is \\$(0,0,2,3,3,0,1,6)$.

There is a natural pictorial representation of the sequences in $\mathbf{A}(n)$
  as what we call a \emph{linear difference diagram},
  as shown in Figure \ref{fig1}(i) for
  the sequence $(0,0,0,3,2,4,0,1,2,7)$.
For each value $x \in \{1,2,\ldots,n\}$,
  we draw an arc from $x$ to $x-a(x)$,
  except if $a(x) = 0$.
Our condition $a(n-a(n))=0$ then translates into the property
  that each connected component of the underlying graph is a star.

\begin{figure}
  %\center
  \includegraphics{fig1.eps}
  \caption{Linear difference diagram representation of an element from:
  (i) $\mathbf{A}(n)$, (ii) $\mathbf{B}(n)$,
    (iii) $\mathbf{C}(n)$, and (iv) $\mathbf{D}(n)$.}\label{fig1}
\end{figure}

Define the set $\mathbf{B}(n)$ to be the subset of $\mathbf{A}(n)$
that satisfy the constraint that if $a(j) \neq 0$, then $a(j-1) <
a(j)$.  We have that $\mathbf{B}(n) = \mathbf{A}(n)$ for $n =
1,2,3$ and $\mathbf{B}(4) = \mathbf{A}(4) \setminus \{0022\}$. Let
$\mathbf{B}(n,m)$ denote the subset of $\mathbf{B}(n)$ consisting
of sequences with exactly $m$ zeroes.  The numbers
$|\mathbf{B}(n,m)|$ appear in OEIS \cite{OEIS} as sequence A098568 but no
combinatorial interpretation is assigned to them.  Summing on $m$
gives the sequence A098569.

In terms of set partitions, the set $\mathbf{B}$ corresponds to
those in which every element $j$ such that $j$ is not smallest in
its block is in a block whose smallest element is no greater than
the smallest element of the block containing $j-1$.

\textbf{Example} The sequence $(0,0,2,3,0,0,2,6,0,1)$, depicted in
Figure \ref{fig1}(ii), is in $\mathbf{B}(n)$.

\begin{theorem}
For all $1 \le m \le n$,
\begin{equation}
|\mathbf{B}(n,m)| = { n-1+{m \choose 2} \choose n-m }.
% { n-m-1+{m+1 \choose 2} \choose n-m }.
\label{eq:seqB}
\end{equation}
\end{theorem}

\begin{proof}
Denote $B(n,m) = |\mathbf{B}(n,m)|$. Classify the sequences in
$\mathbf{B}(n,m)$ according to the index $k$ of the rightmost
zero.  The sequences that occur in the first $k-1$ positions are
exactly those in $\mathbf{B}(k-1,m-1)$. The values that can go
into positions $k+1$ to $n$ must be increasing and can be thought
of as a selection with repetition of size $n-k-1$ from the set of
positions of the 0's, call them $1 = j_1 <j_2 < \cdots < j_m = k$.
Arrange the selection as a nonincreasing sequence $l_{k+1} \ge
l_{k+2} \ge \cdots \ge l_{n}$. Now, if $l_s = j_t$, then set $a(s)
= s - j_t$.  Note that $a(s-a(s)) = a(j_t) = 0$.  Furthermore,
$a(s) < a(s+1)$ since $a(s) = s - j_t < s+1-j_{t'} = a(s+1)$ where
$t' \ge t$. This classification implies that the following
recurrence relation holds, with the initial condition that $B(n,1)
= 1$.
\[
B(n,m) = \sum_{k=m}^{n} B(k-1,m-1) {n-k+m-1 \choose n-k}
\]
We will now show that the expression in (\ref{eq:seqB}) satisfies
this recurrence relation.
The following identity is well-known (see Gould \cite{Gould}, equation
(3.2)).
\begin{equation}
{x+y+t+1 \choose t} = \sum_{j=0}^t {j+x \choose j}{t-j+y \choose t-j}
\label{eq:gould}
\end{equation}
We wish to show that
\[
{ n-m-1+{m+1 \choose 2} \choose n-m } =
\sum_{k=m}^{n} {k-m-1+{m \choose 2} \choose k-m} {n-k+m-1 \choose n-k}.
\]
But this is the same as (\ref{eq:gould}) with
  $j = k-m$, $t = n-m$, $x = {m \choose 2}-1$, and $y = m-1$.
\end{proof}

\section{Catalan and Schr\"oder correspondences}

Note that the linear difference diagram of Figures 1 (i) and 1 (ii)
  have crossing arcs. How many
such sequences have no crossing arcs?

Define the set $\mathbf{C}(n)$ to be the set of sequences
$a(1),a(2),\ldots,a(n)$ for which (a) $0\leq a(j) < j$ and (b)
there is no subsequence such that $i - a(i) < j - a(j) \leq i <
j$.  Note that $\mathbf{C}(n) = \mathbf{B}(n)$ for $n =
1,2,3,4$ and $\mathbf{C}(5) = \mathbf{B}(5) \setminus \{00203\}$,
since $3-a(3) < 5-a(5) \le 3 < 5$. Let $\mathbf{C}(n,m)$ denote
the subset of $\mathbf{C}(n)$ consisting of sequences with exactly
$m$ zeroes. The numbers $|\mathbf{C}(n,m)|$ appear in OEIS \cite{OEIS} as
sequence A001263, the Catalan triangle. Summing on $m$ gives the
Catalan numbers A000108.

\begin{lemma}
For all $n \ge 1$, $\mathbf{C}(n) \subseteq \mathbf{A}(n)$.
\end{lemma}
\begin{proof}
Suppose that there is some value $j$ for which $a(j-a(j)) > 0$, and
let $i = j-a(j)$.  We will show that
\[
i - a(i) < j - a(j) = i < j,
\]
which will prove the lemma.
First note that $a(j) > 0$ since otherwise $a(j-a(j)) = a(j) = 0$.
Thus $i < j$.  Finally,
$i - a(i) = j - a(j) - a(j-a(j)) < j - a(j)$ by our assumption that
$a(j-a(j)) > 0$.
\end{proof}

\begin{lemma}
For all $n \ge 1$, $\mathbf{C}(n) \subseteq \mathbf{B}(n)$
\end{lemma}
\begin{proof}
If there is some sequence $a(1),a(2),\ldots,a(n)$ that is not in
$\mathbf{B}(n)$, then there is some value of $j$ such that
$a(j-1) \ge a(j)$ and $a(j) > 0$.  Setting $i = j-1$ we
would then have $i - a(i) < j - a(j) \le i < j$ and so
the sequence is not in $\mathbf{C}(n)$ either.
\end{proof}


A Dyck path on $2n$ steps is a lattice path in the coordinate
plane $(x,y)$ from $(0,0)$ to $(2n,0)$ with steps $(1,1)$
(\textit{Up}) and $(1,-1)$ (\textit{Down}), never falling below
the $x$-axis.
Figure \ref{fig2} shows a typical Dyck path of length 24.

The numbers shown below for $|\mathbf{C}(n,m)|$ are called the
Narayana numbers \cite{Stanley2}. They count the number of Dyck
paths on $2n$ steps with $m$ peaks.

Let $C_n$ denote the $n$-th Catalan number, $C_n =
\frac{1}{n+1}{2n \choose n}$.  The correspondence used in the
proof below is mentioned in Stanley \cite{StanleyCatalan},
problem 6.19($\mbox{f}^4$).

\begin{theorem}
\[
|\mathbf{C}(n)| = C_n \mbox{ and }
|\mathbf{C}(n,m)| = \frac{1}{m}{n-1 \choose m-1}{n \choose m-1}.
\]
\end{theorem}
\begin{proof}
Considering \textit{Up} steps as left parentheses and
\textit{Down} steps as right parentheses, a Dyck path of length
$2n$ corresponds to a well-formed parentheses string of equal
length. Furthermore, a peak corresponds to a \texttt{()} pair.

Let $\mathbf{S}_{2n}$ denote the set of well-formed parenthesis
strings of length $2n$. Define the function $f$ from
$\mathbf{S}_{2n}$ to $\mathbf{C}(n)$ as
$f(s)=(a(1),a(2),\ldots,a(n))$ where $a(j)$ is the number of right
parentheses that are properly enclosed by the $j$-th parentheses
pair where the parentheses pairs are numbered by the order in
which their right parentheses occur. The left parenthesis that
matches the $j$-th right parenthesis is referred to as
\emph{$j$'s match}. For example, consider $s=$
\texttt{((())(()))(((()))()()())}. Subscripting the right
parentheses and overlining matching parentheses pairs we obtain
\[
\overline{\texttt{(}\overline{\texttt{(}\overline{\texttt{()}}_1\texttt{)}}_2%
\overline{\texttt{(}\overline{\texttt{()}}_3\texttt{)}}_4\texttt{)}}_5%
\overline{\texttt{(}\overline{\texttt{(}\overline{\texttt{(}\overline{\texttt{()}}_6\texttt{)}}_7%
\texttt{)}}_8\overline{\texttt{()}}_9\overline{\texttt{()}}_{10}\overline{\texttt{()}}_{11}\texttt{)}}_{12}
\]
and thus $f(s)=(0,1,0,1,4,0,1,2,0,0,0,6)$ (represented as a linear
difference diagram in Figure \ref{fig1}(iii)).

We now need to explain why $f(\mathbf{S}_{2n})\subseteq
\mathbf{C}(n)$. Let $s\in\mathbf{S}_{2n}$ and consider $f(s)=
(a(1),a(2),\ldots,$ $a(n))$. By definition $a(i)<i$. Furthermore
the sequence satisfies the non-crossing property. If it did not,
for some $i < j$ we would have that both $j - a(j) \le i$ and $i -
a(i) < j - a(j)$. Notice that $j-a(j)$ is the position of the
leftmost right parenthesis to the right of $j$'s match. Now,
$j-a(j)\le i<j$ implies that the $i$-th right parenthesis must lie
between $j$ and its match.  As well, $i-a(i)<j-a(j)$ implies that
the leftmost right parenthesis to the right of $i$'s match is left
of the leftmost right parenthesis to the right of $j$'s match.
This implies that $i$'s match is left of $j$'s match which
contradicts the fact that $s$ is well-formed. Hence $f(s)\in
\mathbf{C}(n)$ thus $f(\mathbf{S}_{2n})\subseteq \mathbf{C}(n)$.

We now show that $f$ is indeed a bijection. Let $b=
(b(1),b(2),\ldots,b(n))\in \mathbf{C}(n)$. We show by induction
that it is possible to construct exactly one $s\in
\mathbf{S}_{2n}$ such that $f(s)=(a(1),a(2),\ldots,a(n))=b$. Let
$k=1$ and $s$ be the well-formed parenthesis string \texttt{()}.
Then $f(s)=(a(1))=(0)=b(1)$ and $s$ is the only such string.
Assume $f(s)=(a(1),a(2),\ldots,a(n))$ $=$
$(b(1),b(2),\ldots,b(n))$ for some $n\ge 1$ where $s$ is the only
such string. Consider $b(n+1)$. If $b(n+1)=0$ then appending
\texttt{()} to $s$, in which there is only one way, results in
$f(s)=(a(1),a(2),\ldots,a(n),a(n+1))=(b(1),b(2),\ldots,b(n),b(n+1))$
and $s$ is the only such string. Similarly, if $b(n+1)=n$, then
enclosing $s$ within a right and a left parenthesis produces the
desired result.

Suppose that $0<b(n+1)<n$. Consider the substring $s'$ consisting
of all elements of $s$ to the right of the $\{n+1 - b(n+1) -
1\}$-th right parenthesis. If $s'$ is not well-formed then there
exists a right parenthesis $i$ with $n+1-b(n+1)\leq i<n+1$ whose
match is to the left of the $\{n+1 - b(n+1) - 1\}$-th right
parenthesis. This implies that $i-b(i)\leq n+1 - b(n+1) - 1$.
However then, $i-b(i)<n+1-b(n+1)\leq i < n+1$ which contradicts
the fact that $b$ is in $\mathbf{C}(n)$. Therefore $s'$ is
well-formed and simply enclosing it in a left and right
parentheses pair within $s$ produces the desired result.

Furthermore, note that a zero in an element of $\mathbf{C}(n)$
corresponds to a \texttt{()} in an element of $\mathbf{S}_{2n}$
which corresponds to a peak in a Dyck path of length $2n$. Thus
$|\mathbf{C}(n,m)|$ is the number of Dyck paths of length $2n$ with
$m$ peaks.
\end{proof}

\begin{figure}
  \center
  \includegraphics{fig2.eps}
  \caption{The sequence $(0,1,0,1,4,0,1,2,0,0,0,6)$ represented as:
  (i) a Dyck path of length 24, (ii) a Schr\"{o}der path of length 11.}\label{fig2}
\end{figure}

The reader may wonder what happens if we were allowed to have
$i-a(i) < j-a(j) = i < j$ but not $i-a(i) < j-a(j) < i < j$. Call
the resulting set $\mathbf{D}(n)$.  Such sequences need no longer
satisfy $a(j-a(j)) = 0$ so strictly speaking are outside the scope
of this paper, but the question is interesting nonetheless.  They
are counted by Schr\"{o}der numbers.

Let $D_n$ denote, A006318, the $n$-th Schr\"{o}der number,
  $D_n= \langle z^n
  \rangle (1-z-\sqrt{1-6z+z^2})/(2z)$ (see Stanley \cite{Stanley2}, pg. 178).

\textbf{Example} The sequence $(0,1,1,3,1,2,3,1,2,3)$, depicted as
a linear difference diagram in Figure \ref{fig1}(iv), is in
$\mathbf{D}(n)$ but not $\mathbf{C}(n)$.

A Schr\"{o}der path is a lattice path in the coordinate plane
$(x,y)$ from $(0,0)$ to $(n,0)$ with steps $(1,1)$ (\textit{Up}),
$(1,-1)$ (\textit{Down}) and $(1,0)$ (\textit{Straight}) never
falling below the x-axis. The length of a Schr\"{o}der path is the
number of \textit{Up} and \textit{Straight} steps in the path.
Figure \ref{fig2}shows a typical Schr\"{o}der path of length 11.

The numbers ${2n-m-1 \choose m-1}C_{n-m}$ count the number
of Schr\"{o}der paths from $(0,0)$ to $(n-1,n-1)$ containing $m-1$
\textit{Straight} steps (A060693).

\begin{theorem}
\[
|\mathbf{D}(n)| = D_{n-1} \mbox{ and } |\mathbf{D}(n,m)| = {2n-m-1
\choose m-1}C_{n-m}
\]
\end{theorem}
\begin{proof}

Let $\mathbf{P}_{n}$ denote the set of Schr\"{o}der paths of
length $n$. Define the function $g$ from $\mathbf{P}_{n-1}$ to
$\mathbf{D}(n)$ as $g(p)=(0, a(1),a(2),\ldots,a(n-1))$ where
$a(j)$ is 0 if the $j$-th counted step is \textit{Straight} or is
the number of counted steps (starting with itself) between it and
its corresponding \textit{Down} step. For example, let $p$ be the
Schr\"{o}der path shown in Figure \ref{fig2}. Then $g(p)=(0,
a(1),a(2),\ldots,a(11))=(0,1,0,1,4,0,1,2,0,0,0,6)$. Notice that
$a(i)=0$ exactly when the $i$-th counted step in $p$ is
\textit{Straight}.

We now need to explain why $g(\mathbf{P}_{n-1})\subseteq
\mathbf{D}(n)$. Let $p\in\mathbf{P}_{n-1}$. Consider $g(p)=(0,
a(1),a(2),$ $\ldots,a(n-1))$ $=$ $(b(1),b(2),\ldots,b(n))$. Since
$p$ is a Schr\"{o}der path $a(i)\leq i$. Since $b(i+i)=a(i)$ we
have that $b(i+1)<i+1$. Now, suppose that there exists an $1<i <
j\leq n$ such that $i-b(i) < j-b(j) < i < j$. Then there exists
some $1\leq x < y <n$ such that $x-a(x)<y-a(y)<x<y$. Since both
$a(y)$ and $a(x)$ must be non-zero to satisfy this inequality, we
have that they both count the number of countable steps (beginning
with themselves) between them and their respective matches. Now,
$x$ lies between $y$ and its match. Furthermore, $y-a(y)$ is the
position of the first countable step to the left of $y$'s match.
Since $x-a(x)<y-a(y)$, the first countable step to the left of
$x$'s match is to the left of the first countable step to the left
of $y$'s match which implies that $x$'s match is to the left of
$y$'s match. This means that between $y$ and its match there is
one more \textit{Up} step then \textit{Down} step thus $y$ and its
match are not on the same level contradicting the fact that this
is indeed $y$'s match. Hence $g(p)\in \mathbf{D}(n)$ thus
$g(\mathbf{P}_{n-1})\subseteq \mathbf{D}(n)$.

We now show that $g$ is a bijection. Let $b=
(b(1),b(2),\ldots,b(n))\in \mathbf{D}(n)$. We show by induction
that it is possible to construct exactly one $p\in
\mathbf{P}_{n-1}$ such that $g(p)=(0, a(1),a(2),\ldots,a(n-1))=b$.
Let $k=2$. If $b(2)=a(1)=0$ let $p'$ be the Schr\"{o}der path of
length $1$ consisting of 1 \textit{Straight} step. Then
$g(p')=(0,0)=(b(1),b(2))$ and there was only one such $p'$.
Otherwise let $p'$ be the Schr\"{o}der path of length 1 consisting
of one \textit{Up} step and its match. Then
$g(p')=(0,1)=(b(1),b(2))$ and there was only one such $p'$.

Assume $g(p')=(0,a(1),a(2),\ldots,a(j-1))$ $=$
$(b(1),b(2),\ldots,b(j))$ for some $j\ge 1$ and $p'$ is the only
such path. Consider $b(j+1)$. If $b(j+1)=0$ then appending a
\textit{Straight} step to $p'$, in which there is only one way,
results in
$g(p')=(0,a(1),a(2),\ldots,a(j))=(b(1),b(2),\ldots,b(j),b(j+1))$
and $p'$ is the only such string. Similarly, if $b(j+1)=j$
appending an \textit{Up} step to the end $p'$ and placing its
match at the front produces the desired result.

Suppose that $0<b(j+1)<j$. Consider the path $p''$ consisting of
all elements of $p'$ to the right of the $j - a(j)$-th countable
step. If $p''$ is not a Schr\"{o}der path then there exists some
\textit{Up} step at position $j-a(j)<i<j$ whose match is to the
left of the $j-a(j)$-th countable step. However, this implies that
the first countable step to the left of $i$'s match is to the left
of the first countable step to the left of $j$'s match. This
implies that $i-a(i)<j-a(j)<i<j$ and hence
$i+1-b(i+1)<j+1-b(j+1)<i+1<j+1$ contradicting the fact that $b$ is
in $\mathbf{D}(n)$. Therefore $p''$ is a Schr\"{o}der path. Now,
within $p'$, simply appending an \textit{Up} step to the end of
$p''$ and placing its match at the front of $p''$ produces the
desired result.

Furthermore, since a zero in an element of $\mathbf{D}(n)$ in any
position other than the first corresponds to a \textit{Straight}
step in a Schr\"{o}der path of length $n-1$, $|\mathbf{D}(n,m)|=$
the number of Schr\"{o}der paths of length $n-1$ with $m-1$ zeros.
\end{proof}




\begin{thebibliography}{99}

\bibitem{Comtet} Louis Comtet,
\emph{Advanced Combinatorics},
D. Reidel Publishing Company, 1974.

\bibitem{Gould} H.W. Gould,
\emph{Combinatorial Identities},
Morgantown Printing and Binding, revised edition, 1972.

\bibitem{Knuth7215} Donald E. Knuth,
\emph{The Art of Computer Programming, Volume 4,
Fascicle 3, Generating All Combinations and
Partitions},
Addison-Wesley, 2005.

\bibitem{Stanley2} Richard P. Stanley,
\emph{Enumerative Combinatorics, Volume 2},
Cambridge University Press, 1999.

\bibitem{StanleyCatalan} Richard P. Stanley,
\emph{Catalan Addendum}, version of 17
February 2005, available online at
\href{http://www-math.mit.edu/~rstan/ec/catadd.pdf}{\tt 
 http://www-math.mit.edu/\~{}rstan/ec/catadd.pdf}.

\bibitem{OEIS}
Neil J. Sloane,
\href{http://www.research.att.com/~njas/sequences/}{The Online Encyclopedia of Integer Sequences (OEIS)},
March 2005.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 68R15.

\noindent \emph{Keywords: } 
Bell number, Catalan number, Schr\"oder number, bijection.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000110},
\seqnum{A000248},
\seqnum{A001263},
\seqnum{A006318},
\seqnum{A008277},
\seqnum{A060693},
\seqnum{A098568}, and
\seqnum{A098569}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  March 28 2005;
revised version received October 24 2005.  
Published in {\it Journal of Integer Sequences}, October 24 2005.

\bigskip
\hrule
\bigskip

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


\end{document}