% Sulanke's paper, Counting lattice path by Narayana polynomials
% This file need a figure called sulankefig2000.ps
\documentclass[12pt]{article}
\usepackage{float, amssymb,latexsym}
%\documentclass[12pt]{amsart}
%\usepackage{amsmath}
\newtheorem{Proposition}{Proposition}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{graphicx}
\newfloat{Figure}{p}{loa}[section]
\renewcommand{\baselinestretch}{1.1}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\PP}{{\mathbb P}}
\oddsidemargin 10pt \evensidemargin 10pt
\textheight 8.5in
\textwidth 6in
\topmargin -\headheight
\makeatletter
\renewcommand\section{\@startsection {section}{1}{\z@}%
{-3.5ex \@plus -1ex \@minus -.2ex}%
{2.3ex \@plus.2ex}%
{\normalfont\large\bfseries}}
\makeatother
%Note to editor: Please allow this section labeling font scheme.ugust
%I find the `standard'
%latex section labeling to be unattractive because of its LARGE font size.
%thanks
\begin{document}
\thispagestyle{empty}
\title{
Counting Lattice Paths by Narayana Polynomials
}
\author{Robert A. Sulanke\\
Boise State University \\
Boise, Idaho, USA\\
{\small\tt{}}
}
\date{{\small Submitted: April 15, 2000;
Accepted: August 3, 2000}}
\maketitle
\begin{abstract}
Let $d(n)$ count the lattice paths from $(0,0)$ to $(n,n)$ using
the steps (0,1), (1,0), and (1,1).
Let $e(n)$ count the lattice paths from $(0,0)$ to $(n,n)$ with
permitted steps from the step set $ \NN \times \NN - \{(0,0)\}$, where $\NN$
denotes the nonnegative integers.
We give a bijective proof of the identity $e(n) = 2^{n-1} d(n)$
for $n \ge 1$.
In giving perspective for our proof, we consider bijections between
sets of lattice paths defined on various sets of permitted steps
which yield path counts related to the Narayana polynomials.
\
%this give a blank line
\noindent Mathematical Reviews Subject Classification: 05A15
\noindent Key words: Lattice paths, Narayana numbers, Delannoy numbers.
\end{abstract}
\section{Introduction}
\pagestyle{myheadings} \markboth{\hfill{\sc the electronic
journal of combinatorics 7 (2000), \#R40}} {{\sc the electronic journal
of combinatorics 7 (2000), \#R40}\hfill}
In the plane $ \ZZ \times \ZZ$ let $D(n)$ denote the set of all
lattice paths from $(0,0)$ to $(n,n)$ using steps from the step set
$\{ (0,1), (1,0), (1,1) \}$.
The path counts $(|D(n)|)_{n \ge 0} =
(1, 3, 13, 63, 321, 1683, \ldots)$ are the well-known
central Delannoy numbers.
Let $E(n)$ denote the set of all lattice paths from $(0,0)$ to $(n,n)$ with
permitted steps from the step set
$ \NN \times \NN - \{(0,0)\}$, where $\NN$
denotes the
nonnegative integers. Figure 1a (1f, resp.) illustrates a path in
$E(8)$ ($D(8)$, resp.)
if the first step is ignored.
We will give a bijective proof for the identity
$$|E(n)| = 2^{n-1} |D(n)|$$
for $n \ge 1$, as requested in
Stanley's \cite{StanleyII} Exercise 6.16.
(A proof using generating functions appears in \cite{StanleyII}.)
To give perspective for our proof,
we will consider bijections between various sets of lattice paths
which have path counts related to Narayana polynomials.
The known results of the first two sections serve as background for the
results of the last two sections.
This paper will consider six step sets which are labeled
arbitrarily by $S_i$ for
$i = 1 \ldots 6$.
Table 1 contains a list of these step sets
and an index to the path sets considered.
Given a specific step set $S_i$, let
$A_{i}(n)$ denote the set of {\it all}\ lattice paths running
from $(0, -1)$ to $(n, n)$
that use the steps in $S_i$ and that
remain strictly above the line
$y=-1$ except initially. Let $L_{i}(n)$ denote that subset of
$A_{i}(n)$ whose member paths
remain strictly above the {\it line}\
$y=x-1$ except initially.
We complete this section by introducing the Narayana polynomials in terms
of lattice paths.
For the step set $S_1= \PP \times \PP $, with $ \PP $
denoting the positive integers, let
$A_{1}(n, k)$ ($L_{1}(n, k)$, resp.)
denote the set of paths in $A_{1}(n)$ ($L_{1}(n)$, resp.)
having $k$ steps.
For example, $A_{1}(2,1)$ contains just one path formed by the single step
$(2,3)$. Further,
$A_{1}(2,2) = \{ (1,1)(1,2),\ (1,2)(1,1) \}$, $L_{1}(2,1) = \{ (2,3) \}$,
and $L_{1}(2,2) = \{ (1,2)(1,1) \}$.
\begin{Proposition}
For $ 0 < k \le n$,
\begin{equation}
| A_{1}(n, k)| = {{n-1} \choose {k-1}} {{n}\choose {k-1}}
\label{firstequation}
\end{equation}
\begin{equation}
| L_{1}(n, k)| =
\frac{1}{k} {{n-1} \choose {k-1}}{{n}\choose {k-1}} =
\frac{1}{n} {{n} \choose {k-1}} {{n} \choose {k}}.\label{secondequation}
\end{equation}
\end{Proposition}
{\it Proof.}\ The right side of (\ref{firstequation})
simply counts the ways to assign the coordinates of the
end points of the steps constituting
a path in $A_{1}(n,k)$. E.g., consider the path $(2,1)(1,1)(1,3)
\in L_{1}(4, 3)$, expressed as a sequence of steps;
here the endpoints of the steps have coordinates
$(2,0)$, $(3,1)$, and $(4,4)$, so that $\{ 2,3\} \subset \{ 1,2,3\} $
and $\{0, 1\} \subset \{0, 1,2,3\} $.
Since exactly one of the $k$ cyclic permutations of any path in
$A_1(n,k)$ lies in $L_1(n,k)$, the middle formula of
(\ref{secondequation}) follows from
(\ref{firstequation}).
See \cite{SulKP} for details of this use of the cycle lemma.
$\square$
\
With $V$ denoting the unit vertical step $(0, 1)$ and
$H$ denoting the unit horizontal step $(1, 0)$,
let $S_2$ be the common step set $\{V, H\}$. Here, for example,
$L_2(2) = \{ VVVHH, VVHVH, \}$.
Observe that each step $(u,v) \in S_1$ determines a vertical step $(0, v)$
followed by a horizontal step $(u,0)$,
and conversely.
Hence there is an immediate matching between
$A_{1}(n,k)$
and $A_{2}(n,k)$, where $A_{2}(n,k)$
is that subset of $A_{2}(n)$ in which each path has $k$
{\it peaks} (i.e., consecutive $VH$ pairs or {\it right turns}).
Thus $| A_{1}(n)| = | A_{2}(n) |$.
Likewise, there is an immediate matching between
$L_{1}(n,k)$ and $L_{2}(n,k)$ where $L_{2}(n,k)$
is that subset of $L_{2}(n)$ in which each path has $k$
peaks; thus $| L_{1}(n)| = | L_{2}(n) |$.
The count, $ |L_{2}(n,k)| =
\frac{1}{n}{{n}\choose{k-1}}{{n}\choose{k}}$, is known as a
Narayana number, and
$$N_n(z) = \sum_ {k=1}^n\frac{1}{n}{{n}\choose{k-1}}{{n}\choose{k}}z^k$$
is known as the $n^{th}$-Narayana polynomial.
Studies of these
polynomials are given by Bonin, Shapiro, and Simion \cite{BSS}
and the author \cite{SulNar}.
The sequence
$(N_n(1))_{n \ge 0} = (1, 1, 2, 5, 14, \dots )$
is well known as the Catalan numbers, while the
sequence
$(N_n(2))_{n \ge 0}$
$ = (1, 2, 6, 22, 90,\dots)$
is known as the large Schr{\"o}der numbers.
\begin{table}[t]
\begin{center}
\begin{tabular}{l|l|l}
section & step set & path sets \\
\hline
1&
$S_1
= \PP \times \PP $ \quad &
$A_1(n)$, $A_1(n,k )$, $L_1(n)$, $L_1(n,k )$\\
& $S_2
= \{\ (0,1), (1,0) \}$ & $A_2(n)$, $A_2(n,k )$, $L_2(n)$, $L_2(n,k )$\\
\hline
2&
$S_3 = \{ (0,1), (1,0), (1,1) \}$ &
$L_2(n)$, $L_2^c(n;z)$, $L_2^{cc}(n;z)$, $L_3(n)$ \\
\hline
3 &
$S_4 = (\PP \times \{0\}) \cup (\{0\} \times \PP )$ &
$L_{4}(n) $, $L^0_{4}(n) $,
$L^*_{2}(n) $\\
\hline
4 &
$S_5 = \NN \times \NN -\{(0,0)\}$ &
$A_{5}(n)$, $A^0_{5}(n)$, $L_{5}(n)$, $L^0_{5}(n)$, $A_3^0(n)$ \\
& $S_6 = (\{0\} \times \PP ) \cup \{(1,0) \}$
&
$L_{6}(n)$, $A_{2}^{\ell}(n)$, $A_{2}^{cc}(n)$,
$A_{6}(n)$, $A^0_{6}(n)$
\end{tabular}\\
\vspace{10pt}
\end{center}
\caption{
This table gives the definitions for
six step sets together with the symbols for
various path sets, each of
which is introduced in the corresponding section.
Here $\NN $ ($\PP $,
resp.) denotes the set of nonnegative (positive, resp.) integers.}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Peaks, double ascents, and large Schr{\"o}der paths}
\label{largeschroder}
For positive integer $z$,
replicate each path in $L_{2}(n) $ by independently coloring
its peaks with colors from a set of $z$
colors where we require blue ($b$) and red ($r$)
to be present whenever $z \ge 2$.
Let $L^c_{2}(n;z) $ denote the set of all such paths with colored peaks.
For example, the six paths of $L^c_2(2;2)$
can be listed as $VVVbHH$, $VVVrHH$, $VVbHVbH$, $VVbHVrH$, $VVrHVbH$, and $VVrHVrH$.
>From the previous section we have that the restricted paths with colored
peaks are counted in terms of the Narayana polynomials as follows.
\begin{Proposition}
$$
|L^c_{2}(n;z)| = N_n(z).
\label{zlabeling}
$$
\end{Proposition}
On any path the intermediate vertex of a
consecutive $VV$ pair is called a {\it
double ascent}.
Let $ L^{cc}_{2}(n;z)$ denote the set of paths replicated from $L_{2}(n)$
by independently coloring each double ascent from the same set of $z$
colors that
were available for the peaks.
For example, the six paths of $L^{cc}_2(2;2)$
can be listed as $VbVbVHH$,
$VbVrVHH$, $VrVbVHH$, $VrVrVHH$, $VbVHVH$, and $VrVHVH$.
We define can a bijection
\begin{equation}
f: L^{cc}_{2}(n;z) \longrightarrow L^c_{2}(n;z) \label{ffmap}
\end{equation}
as follows: Let $R \in
L^{cc}_{2}(n;z)$ be determined by the coordinates of its peaks,
say,
$(x_1, y_1), \ldots, $ $ (x_k, y_k)$.
(The coordinates of a peak are the coordinates of the vertex
between the $V$ and $H$ steps.)
Then $(x'_1, y'_1), \ldots, (x'_h, y'_h), \ldots, (x'_{n+1-k}, y'_{n+1-k})$
will be the coordinates of
the peaks of the path $f(R)$ where
\begin{eqnarray*}
\{x'_1, \ldots, x'_h, \ldots, x'_{n+1-k} \} &=&
\{0, \ldots, n\} - \{y_1, \ldots, y_k\} \\
\{y'_1, \ldots, y'_h, \ldots, y'_{n+1-k}\} &=&
\{0, \ldots, n\}-\{x_1, \ldots, x_k\}
\end{eqnarray*}
with $x'_1 0$,
$|L^0_{4}(n)| = |L_{4}(n)|/2$. We find
that $(|L^0_{4}(n)|)_{n \ge 0} =$
$ (1, 1, 5, 29, 185, 1257, 8925, \ldots)$.
Deutsch's \cite{deutsch}
interest in counting $L^0_{4}(n)$ motivated this section.
{\it Proof.}
Replicate each path in $L_{2}(n) $ by independently
labeling
the intermediate vertices of its {\it noninitial}
double ascents with one of the markings `$pp$', `$pa$', `$ap$', or `$aa$'
and labeling the initial double ascent with either `$p$' or `$a$'. (The
purpose for these markings will be clear below.) With
$L^*_{2}(n) $ denoting the set of all paths
with such labels, we see
that
$| L^*_{2}(n) | = N_n(4)/2. $
Hence to obtain the proposition,
we require a bijection
$ L_{4}(n) \longrightarrow L^*_{2}(n)$.
We note that each path $ P \in L_{4}(n) $ determines
a path $Q \in L_{2}(n)$ which traces the same points in the plane.
On the path $ Q$ we label the intermediate vertex of each
double ascent and each double descent (i.e., $HH$) by a `$p$'
or an `$a$' according to the {\it presence} or {\it absence }
of an end point of a step
at the same lattice point on the path $P$. Note also that, on $Q$,
with the exception of the necessary initial double ascent,
each double ascent can be matched with the first subsequent
double descent for which the intermediate vertices lie on
the same line of slope 1. Next let the path $Q'$ be obtained from $Q$ by
relabeling each noninitial double ascent of $Q$
by one of four pairs, $pp$, $pa$, $ap$, or $aa$,
where each pair of letters designates the presence of respective singleton
labels
on a double ascent and its matching double descent.
For $Q'$ we also remove the labels from the double descents while keeping the
label for the initial double ascent.
$\square$
As an example of
$ L_{4}(4) \longrightarrow L^*_{2}(4)$,
take $P = (0,1)(0,2)(1,0)(0,1)(0,2)(3,0)(1,0) \in L_{4}(4)$. Then
initially $Q = VpVaVHVpVaVHaHaHpH$ which gets relabeled as the path
$Q' = VpVapVHVpaVaaVHHHH \in L^*_{2}(4)$.
\section{Arbitrary steps}\label{sectionarbit}
For $S_5 = \NN \times \NN -\{(0,0)\}$ where $ \NN $ denotes the non-negative integers,
let $A^0_{5}(n)$ ($L^0_{5}(n)$, resp.)
denote the set of paths in $A_{5}(n)$ ($L_{5}(n)$, resp.) that begin with a
unit vertical step.
Let $A^0_{3}(n)$ denote the subset of those paths in
$A_{3}(n)$
that begin with a unit vertical step, where $S_3 =\{ V,H,D\}$ as before.
\begin{Proposition} For $n \ge 1$,
\begin{eqnarray}
|L^0_{5}(n)| & =& 2^{n-1} |L_{3}(n)| \ \
= \ \ 2^{n-1} N_n(2) \label{fourth}
\\
|A^0_{5}(n)| &= &2^{n-1} |A^0_{3}(n)|. \label{third}
\end{eqnarray}
\end{Proposition}
We remark that without the initial vertical unit step,
$A^0_{5}(n)$ is essentially
$E(n)$ and $A^0_{3}(n)$ is essentially
$D(n)$ of Section 1.
The bijective proof of (\ref{third}) answers
Exercise 6.16 in \cite{StanleyII}.
For reference we note that
$( |L^0_5(n)|)_{n \ge 0} =$
$ ( 1, 2, 12, 88, 720, 6304, \ldots)$
and that $( |E(n)|)_{n \ge 0} =$
$ ( 1, 3, 26, 252, 2568, 26928
\ldots)$.
{\it Proof of (\ref{fourth}).}\
We will obtain (\ref{fourth}) by establishing a bijection
$$L^0_{5}(n) \longrightarrow L_{3}(n) \times 2^{[n-1]}$$
where $2^{[n-1]}$ denotes
the collection of subsets of $\{1, 2, \ldots, n-1\}$.
The intermediate
bijections composing this bijection are illustrated in Figure 1.
Written details for the figure follows this proof.
We first define a bijection
\begin{equation}
h: L^0_{5}(n) \longrightarrow L_{6}(n) \times
2^{[n-1]}
\label{hhmap}
\end{equation}
where $S_6 = (\{0\} \times \PP) \cup \{H\}$.
Let $P \in L^0_{5}(n) $ and let {\bf A}
be the set of abscissae of the initial points of the horizontal steps of $P$
excepting any step that departs from the $y$-axis; certainly,
$\mbox{\bf A} \subseteq \{1, \ldots, n-1\}$.
Let $P'$ be the path obtained from $P$
by replacing each diagonal step $(u,v)$ by the consecutive pair $(0,v) (u,0)$
and by leaving the vertical and
horizontal steps of $P$ unaltered.
Let $Q$ be obtained from $P'$ by two operations: (1)
Replace each horizontal step, say $(u,0)$,
by a string of $u$ $H$ steps. (2) Whenever $P$
departs the $y$-axis with a non-horizontal step,
join the first two steps of
$P'$ to create a new initial vertical step. Equivalently, $Q$ will
begin with a unit vertical step (ending at $(0,0)$) if, and only
if, $P$ leaves the $y$-axis by a horizontal step.
See Figures 1a, 1b, and 1c.
Define $h(P)$ to be the pair,
$h(P) = (Q, \mbox{\bf A}) \in L_{6}(n) \times 2^{[n-1]}$.
Recalling the notation of Section \ref{largeschroder},
we define a bijection
\begin{equation}
K: L_{6}(n) \longrightarrow L^{cc}_{2}(n;2) \label{Kbaby}
\end{equation}
where
$Q \in L_{5}(n) $ is matched with a path $R \in L^{cc}_{2}(n;2)$
so that the two paths trace the same points in the plane
and each intermediate vertex of a double ascent on
$Q$
becomes a red double ascent of $R$ and each lattice point
that is interior to a vertical step of $Q$ becomes a blue
double ascent of $R$.
With $id$ denoting the identity map,
$$(g \times id) \circ (f \times id) \circ (K \times id) \circ h: L^0_{5}(n)
\longrightarrow L_{3}(n) \times 2^{[n-1]}$$
is the desired bijection
yielding (\ref{fourth}).
$\square$
\
Below we spell out the example appearing in Figure 1 for
this composite bijection:
\begin{itemize}
\item[-] $P = (0,1)(0,1)(1,1)(0,2)(1,0)(2,1)(0,1)(1,1)(2,0)(1,1) \in
L^0_{5}(8) $
\item[-]
$P' = (0,1)(0,1)(0,1)(1,0)(0,2)(1,0)(0,1)(2,0)(0,1)(0,1)(1,0)(2,0)(0,1)(1,0)$
\\
with $ \mbox{\bf A} = \{1,5\} \subset \{ 1, \ldots , 7 \} $
and the knowledge that
$P$ departed the $y$-axis
by the non-horizontal step $(1,1)$
\item[-]
$Q = (0,2) (0,1) H (0,2) H (0,1) H H (0,1) (0,1) HHH (0,1) H \in L_6(8) $\\
with $ \mbox{\bf A} = \{ 1, 5 \} $
\item[-] $R = VbVrVHVbVHVHHVrVHHHVH \in L^{cc}_2(8;2)$
with $ \mbox{\bf A} = \{ 1,5 \} $
\item[-]$f(R) = VVVVbHVVrHHVbHHHVVrHH \in L^{c}_2(8;2)$
with $ \mbox{\bf A} = \{ 1,5 \} $
\item[-]$g(f(R)) = VVVDVVrHHDHHVVrHH \in L_3(8) $
with $\mbox{\bf A} = \{ 1,5 \} $
\end{itemize}
\
{\it Proof of (\ref{third}).}
We modify the bijections proving (\ref{fourth})
to prove (\ref{third}).
A {\it left turn} is the intermediate point of a consecutive $HV$ pair.
Let $A^{\ell}_{2}(n)$ ($A^{cc}_{2}(n)$, resp.)
denote the set of replicated paths formed from
$A_{2}(n)$
so each left turn (double ascent, resp.)
is independently colored blue or red.
We have a bijection
$$ F: A^{cc}_{2}(n) \longrightarrow A^{\ell}_{2}(n) $$
defined as follows: Let $R \in A^{cc}_{2}(n)$
be determined by the set (perhaps empty) of the coordinates of its left turns, namely
$\{ (x_1, y_1), \ldots, (x_k, y_k) \}$. \ \
Then $(x'_1, y'_1), \ldots, (x'_h, y'_h),$
$ \ldots,(x'_{n-k}, y'_{n-k})$ are
the left turns of the path $F(R) \in A^{cc}_{2}(n)$
where
\begin{eqnarray*}
\{x'_1, \ldots, x'_{n-k}\}&=& \{1, \ldots, n\} - \{x_1, \ldots, x_k\}\\
\{y'_1, \ldots, y'_{n-k}\} &=& \{0, \ldots, {n-1}\} - \{y_1, \ldots, y_k\}
\end{eqnarray*}
with $ x'_1