\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 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)