\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}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\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}}}
\DeclareMathOperator\sgn{sgn}
\usepackage{graphicx,color}
\graphicspath{{Figures/}}
\gdef\SetFigFont#1#2#3#4#5{}
\newcount\magproz
\newcount\vorne
\newcount\hinten
\newcount\zwischen
\magproz=100
\def\path{Figures}
\def\calc_figscale#1{
\magproz=#1
\vorne=\magproz
\divide\vorne by 100
\hinten=\magproz
\zwischen=\vorne
\multiply\zwischen by 100
\advance\hinten by -\zwischen
\def\figscale{\the\vorne.\the\hinten}
}
\def\PsFigCap#1#2#3{
\calc_figscale{#1}
\begin{figure}[htb]
\centerline{\input{\path/#2.pstex_t}}
\caption{#3\label{fig:#2}}
\end{figure}
}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Lattice Path Enumeration and \\
\vskip .12in
Toeplitz Matrices
}
\vskip 1cm
\large
Stefan Felsner and Daniel Heldt \\
Institut f\"ur Mathematik \\
Technische Universit\"at Berlin \\
Stra\ss e des 17. Juni 136 \\
D-10623 Berlin \\
Germany \\
\href{mailto:felsner@math.tu-berlin.de}{\tt felsner@math.tu-berlin.de} \\
\href{mailto:dheldt@math.tu-berlin.de}{\tt dheldt@math.tu-berlin.de}
\end{center}
\vskip .2 in
\def\lf{\hfill\\}
\def\diag{\hbox{\rm\sf diag}}
\def\Toeplitz{\hbox{\rm\sf toep}}
\begin{abstract}
This paper is about counting lattice paths. Examples are the paths
counted by Catalan, Motzkin or Schr\"oder numbers. We identify
lattice paths with walks on some path-like graph. The entries of
the $n$th power of the adjacency matrix are the number of paths of
length $n$ with prescribed start and end position. The adjacency
matrices turn out to be Toeplitz matrices. Explicit expressions for
eigenvalues and eigenvectors of these matrices are known. This
yields expressions for the numbers of paths in the form of
trigonometric sums. We give many examples of known sequences that
have such expressions.
We also deal with cases where no explicit expressions for
eigenvalues and eigenvectors of the relevant matrices are known. In
some of these cases it is possible to use the characteristic
polynomial to get linear recurrence relations for the numbers in
question.
\end{abstract}
\section{Introduction}
Let $P_{n}(\alpha)$ be the path of $n+1$ vertices with a loop of
weight~$\alpha$ at each vertex and path-edges of weight~$1$, see
Figure~\ref{fig:lattice_paths-path}. We label the vertices from one
end to the other, starting with vertex $0$ and ending with vertex $n$.
A walk in a graph is a list $x_0,e_1,x_1,\ldots,e_m,x_m$ of vertices
$x_i$ and edges $e_j$, such that edge~$e_i$ has endpoints $x_{i-1}$
and $x_i$. A walk is oriented; it starts with $x_0$ and ends with $x_m$.
We say that the walk is from $x_0$ to $x_m$. The length of a path
is the number of edges traversed, and it is $m$ in the example. For a
walk in an edge-weighted graph we define its weight as the product of
the weights of its edges. Example: $ 1 \rightarrow 2 \rightarrow 3
\rightarrow 3 \rightarrow 2 $ is a walk from $1$ to $2$ in
$P_{5}(\alpha)$. Its length is $4$ and its weight is $\alpha$.
\PsFigCap{85}{lattice_paths-path}{The path $P_{n}(\alpha)$
with $n+1$ vertices and loops of weight $\alpha$.}
Counting walks on $P_{n}(\alpha)$ enables us to count Motzkin paths in a
strip: Motzkin paths of length~$n$ are lattice paths with steps of three types
$(x,y) \to (x+1,y+1)$, $(x,y) \to (x+1,y)$, and $(x,y) \to
(x+1,y-1)$ that start in $(0,0)$ end in $(n,0)$ and stay above the $x$-axis, i.e,
$y \geq 0$. A Motzkin path is in the strip $[0,k]$ iff its
$y$-coordinate never exceeds $k$.
\PsFigCap{45}{lattice_paths-motzkin_paths}{The 9 Motzkin paths
of length 4; the first eight are in the strip $[0,1]$.}
Other types of lattice walks in a strip (for example Dyck paths or
Schr\"oder paths) can also be interpreted as walks on paths, see
Section~\ref{sec:bijections}. We use the weighted adjacency matrix of
$P_{n}(\alpha)$ as a tool to enumerate classes of such lattice
paths. In principle, this is nothing but a variant of the traditional
transfer-matrix method. Results similar to ours but tailored towards
an audience of physicists and with a focus on random walks have been
obtained by by Cicuta et al.~\cite{CCM}.
The enumeration of classes of lattice paths is a classical topic
originating from Bertrand's ballot problem. They are investigated in
probability theory in the context of the gambler's ruin problem
\cite[Chapter XIV]{Feller}, but also in their own right. The monograph
by Mohanty~\cite{Mohanty} gives a valuable overview. An
survey on more recent aspects of lattice path enumeration was given
by Humphrey~\cite{Humphreys}.
\section{The counting approach\label{sec:computations}}
Let us start with two simple facts about the enumeration of walks in graphs.
\begin{fact}~\label{fact:adjacency_matrix}
Let $G$ be a graph with weights on the edges and let $A$ be its
weighted adjacency matrix. The sum of the weights of walks of
length $m$ from vertex $i$ to vertex $j$ is
$$ e_i^T\cdot A^m \cdot e_j.$$
\end{fact}
From now on we focus on the graph $P_n=P_n(1)$ and its weighted version
$P_n(\alpha)$ respectively. With $A_{(n,\alpha)}$ we denote the
weighted adjacency matrix of $P_n(\alpha)$; clearly $A_{(n,\alpha)}\in
\mathbb{R}^{(n+1) \times (n+1)}$.
\begin{definition}
$$
Z^{n}_{i,j}(m,\ell) := \#( \text{walks from } i \text{ to } j \text{
of length } m, \text{ using }\ell\text{ loops in } P_{n}).
$$
\end{definition}
The following is obtained from Fact~\ref{fact:adjacency_matrix}
and simple combinatorial reasoning.
\begin{fact}\label{fact:Zij}
\begin{align}
& \notag \\[-11mm]
Z^{n}_{i,j}(m,\ell) &= \binom{m}{\ell} \cdot Z^{n}_{i,j}(m-\ell,0) \\
\sum_{\ell=0}^{m} Z^{n}_{i,j}(m,\ell)\;\alpha^\ell &=
e_i^T\cdot A^m_{(n,\alpha)} \cdot e_j
\end{align}
\end{fact}
From these fact we can deduce explicit expressions for
$Z^{n}_{i,j}(m,\ell)$ as trigonometric sums.
\begin{theorem}\label{thm:keyZ}
\begin{align}
& \notag \\[-8mm]
Z^{n}_{i,j}(m-\ell,0) &=
\frac{2}{n+2} \sum_{k = 1}^{n+1} \left( 2 \cos \left(
\frac{k\cdot \pi}{n+2}\right) \right)^{m-\ell} \sin\left( i
\frac{k\cdot\pi}{n+2}\right) \sin\left(j
\frac{k\cdot\pi}{n+2} \right)\label{for:3}
\\
e_i^T\cdot A^m_{(n,\alpha)} \cdot e_j &=
\frac{2}{n+2} \sum_{k = 1}^{n+1}\left( \alpha + 2\cos \left(
\frac{k\cdot \pi}{n+2}\right) \right)^m \sin\left( i
\frac{k\cdot\pi}{n+2}\right) \sin\left( j
\frac{k\cdot\pi}{n+2} \right)\label{for:4}
\end{align}
\end{theorem}
To prove the two formulas given in the theorem we
begin with simple linear algebra. The first proposition is well known:
\begin{proposition}\label{prop:ONBPower}
Let $A \in \mathbb{R}^{(n+1) \times (n+1)}$ be a matrix and assume
that $A$ admits an orthonormal basis $(v_1, \dots, v_{n+1})$ of
eigenvectors. Also let $\lambda_i\in \mathbb{C}$ be the eigenvalue
corresponding to $v_i =(v_{1,i},\ldots,v_{n+1,i})$. Then
$$ e_i^T\cdot A^m \cdot e_j = \sum_{k=1}^{n+1} \lambda_k^m v_{i,k} v_{j,k}.$$
\end{proposition}
\begin{proof}
Consider the matrix $S = [v_1, \dots, v_{n+1}]$, i.e., $S\cdot e_i =
v_i$ for all $i$. From orthogonality we obtain $S^T = S^{-1}$. This
implies $ e_i = S^T\cdot v_i $ and $S^T \cdot A \cdot S =
\text{diag}(\lambda_1,\ldots,\lambda_{n+1})=: D$. Now $A^m= (S\cdot
D\cdot S^{-1})^m = S\cdot D^m\cdot S^{-1} = S\cdot D^m\cdot S^T$ and
hence, $e_i^T\cdot A^m \cdot e_j = e_i^T S\cdot D^m\cdot S^T e_j =
(S^Te_i)^T\cdot D^m\cdot (S^Te_j) =
(v_{i,1},\ldots,v_{i,n+1})^T\cdot D^m\cdot
(v_{j,1},\ldots,v_{j,n+1}) = \sum_{k=1}^{n+1} \lambda_k^m v_{i,k}
v_{j,k}$.
\end{proof}
Since $A_{(n,\alpha)}$ is a real symmetric matrix
it has a real orthonormal basis
$(v_1, \dots, v_{n+1}) \in \mathbb{R}^{n+1}$ of eigenvectors.
The next lemma relates eigenvalues and eigenvectors of
$A_{(n,\alpha)}$ and of $A_{(n,0)}$.
\begin{lemma}\label{lem:alphadoesntmatter}
Let $\lambda_1, \dots, \lambda_{n+1}$ be the eigenvalues of
$A_{(n,0)}$ and $(v_1 \dots, v_{n+1})$ a corresponding orthonormal
basis of eigenvectors. Then all eigenvalues of $A_{(n,\alpha)}$ are
of the form $\lambda_i + \alpha$ and $(v_1, \dots, v_{n+1})$ is an
orthonormal basis of eigenvectors of $A_{(n,\alpha)}$.
\end{lemma}
\begin{proof} Let $v$ be an eigenvector of $A_{(n,0)}$ with respect to
$\lambda$, then $A_{(n,\alpha)}\cdot v = (A_{(n,0)} + \alpha \cdot
{I}_n) \cdot v = A_{(n,0)}\cdot v + \alpha \cdot v =
(\lambda+\alpha) \cdot v$. Hence, $v$ is an eigenvector of
$A_{(n,\alpha)}$ w.r.t.\ the eigenvalue $\lambda + \alpha$.
\end{proof}
Our next aim is to determine the orthonormal basis of eigenvectors of
$A_{(n,0)}$. The structure of this matrix is captured by the next
definition.
\begin{definition}(\label{def:Toeplitz}Toeplitz matrix)\\[2mm]
A matrix $A= (a_{ij}) \in \mathbb{R}^{(n+1) \times (n+1)}$ is called a
\emph{Toeplitz matrix} if there exist
$$c_{-n}, c_{-(n-1)}, \dots,
c_0, \dots c_{n} \in \mathbb{R}$$ such that
$$
a_{ij} = c_{i-j} \text{ for all } i,j=1,2,\dots,n+1
$$
i.e., $A$ is constant on all diagonals. We will denote $A$ as
$\Toeplitz(c_{-n},\dots,c_{n})$ to have a short notation for
$A$. If $c_{-k} = c_k$ the matrix
$A$ is a \emph{symmetric Toeplitz matrix}.
\end{definition}
\begin{fact}
$A_{(n,\alpha)} =
\Toeplitz(0,\dots 0, 1, \alpha, 1, 0, \dots 0)$ is the adjacency matrix of $P_n(\alpha)$.
\end{fact}
\begin{proposition}\label{prop:ONB}
The eigenvalues $\lambda_k$ and (right) eigenvectors $v_k$ of
$A_{(n,0)}$ are
$$ \lambda_k :=2 \cdot \cos\left( \frac{k\cdot \pi}{n+2}\right)
$$
and
$$
v_k := \left( \sin\left(1 \cdot \frac{k \cdot \pi}{n+2} \right),
\sin\left(2 \cdot \frac{k \cdot \pi}{n+2} \right), \dots,
\sin\left((n+1) \cdot \frac{k \cdot \pi}{n+2} \right) \right)
$$
for $k=1,\ldots,n+1$. Moreover, $\|v_k\|_2^2 = \frac{n+2}{2}$ for all
$k$.
\end{proposition}
\begin{proof}
Since $A_{(n,0)}$ is a tridiagonal Toeplitz matrix with diagonals
$1,0$, and $1$, the eigenvectors and eigenvalues are known, see
e.g.~\cite{TOEPLITZ}. Replacing $(a,b,c)$ in the given formula on
page 35 of that book by $(1,0,1)$ yields the result.
\end{proof}
Now it is easy to complete the proof of
formulas (3) and (4):
\begin{proof}(Theorem~\ref{thm:keyZ})
For (3) first replace $Z^{n}_{i,j}(0,m-\ell)$ by $e_i^T\cdot
A^{m-\ell}_{(n,0)} \cdot e_j$, a consequence of (2). The proof of the
formulas now follows from a combination of
Proposition~\ref{prop:ONBPower}, Lemma~\ref{lem:alphadoesntmatter}
and Proposition~\ref{prop:ONB}.
\end{proof}
The eigenvalues in Proposition~\ref{prop:ONB} are closely related to
the roots of Chebyshev polynomials of the second kind. Connections
between these polynomials and the counting of Motzkin paths have
surfaced before. The work of Chow and West~\cite{ChowWest} contains
relations between the Chebyshev polynomials, their roots, and
123-avoiding permutations, which are closely linked to Motzkin
paths. Starting out from continued fractions expressions {\em \`a la
Flajolet}, Elizalde and Mansour~\cite{em-rmp-05} have uncovered more
explicit connections.
\medskip
Besides the exact enumeration in terms of trigonometric sums, the
numbers $Z_{i,j}^n(m, \ell)$ can also be related to linear recurrences
and generating functions. An approach to obtaining the generating
function can be found in~\cite[Chapter 4, Theorem 4.2.7]{Stanley}. A
linear recurrence can be derived from the characteristic polynomial of
the weighted adjacency matrix or any other polynomial, which has the
weighted adjacency matrix as a root:
\begin{fact}\label{fact:CharPoly}
Let $A\in\mathbb{R}^{(n+1) \times (n+1)}$ be a matrix and
$\chi_A(x)$ be the characteristic polynomial of $A$. The
Cayley-Hamilton Theorem states that
$\chi_{A}(A)=0$.
The polynomial $\chi_{A_{(n,\alpha)}}(x) = x^{n+1} + \sum_{k=0}^{n} a_k x^k$
leads to the linear recurrence:
$$
(A_{(n,\alpha)})^{n+1} = -\sum_{k=0}^n a_k (A_{(n,\alpha)})^k.
$$
\end{fact}
With Fact~\ref{fact:Zij}(2) we obtain
$$
Z_{i,j}^n(m, \ell) = - \sum_{k=0}^{n} a_k Z_{i,j}^{n}(m
-n +j, \ell).
$$
The characteristic polynomial of
$A_{(n,\alpha)}$ is known to be determined by the
$n+1$-th Chebyshev polynomial of second kind $U_{n+1}(x)$ as
$$
\chi_{A_{(n,\alpha)}}(x) = U_{n+1}(\tfrac{x-\alpha}{2}).
$$
From this the explicit expressions for the coefficients $a_k$ can be
obtained. This then leads to an explicit linear recurrence for
$Z_{i,j}^n(m, \ell)$.
\section{\label{sec:bijections}Interesting special cases}
In this section we show that the numbers $Z_{i,j}^n(m, \ell)$ are
quite universal. Special combinations of their parameters lead to
a multitude of well known and not so well known sequences.
In many cases we refer to a sequence by using its number from the
{\em The On-Line Encyclopedia of Integer Sequences}
(OEIS).
\begin{example}(Binomial Coefficients)\vbox{}\vskip-7mm\vbox{}
$$Z_{k,n-k}^{n}(n,0) = \binom{n}{k}$$
\end{example}
\begin{proof}
The start and end for the walks on $P_n$ are such that any sequence
of $k$ steps down and $n-k$ steps up stays on $P_n$.
\end{proof}
The choice of the parameters is not unique. Indeed for all $k'\geq k$
and $n'\geq k'+n-k$ we have
$$ Z_{k',k'+n-2k}^{n'}(n,0) =Z_{k,n-k}^{n-k}(n,0) = \binom{n}{k}.$$
\begin{example}(Bounded Binomial Coefficients)\lf
Let $C(n,k,b)$ be the number of $\{0,1\}$-strings of length $n$ with
$k$ times $1$ such that for each initial segment of the string the
number of $0$'s and the number of $1$'s differ at most by $b$. It
is easy to verify that
$$
C(n,k,b) = Z_{b,2k+b-n}^{2b}(n,0).
$$
For $b= 1$, we have
$Z_{1,1}^{2}(2n,0) = 2^n = Z_{1,2}^{2}(2n+1,0)$ and for $b=2$ we have
$Z_{2,2}^{4}(2n,0) = 2 \cdot 3^n$.
Since the sequence $a_n := Z_{3,3}^{6}(2n,0)$
fulfills the recursion $ a_n = 4 a_{n-1} - 2 a_{n-2}$ and has the same
initial values it is \seqnum{A006012}.
The sequence $b_n = Z_{4,4}^{8}(2n,0)$ seems to be \seqnum{A147748}.
\end{example}
\begin{example}(Catalan numbers)\vbox{}\vskip-7mm\vbox{}
$$ Z_{0,0}^{n}(2n,0) = \frac{1}{n+1} \binom{2n}{n} = C_n$$
\end{example}
\begin{proof}
Catalan numbers count Dyck paths from $(0,0)$ to $(0,2n)$, i.e.,
lattice paths with steps $i \rightarrow i+1$ and $i \rightarrow i-1$
from $(0,0)$ to $(0,2n)$, which stay above the $x$-axis. Dyck paths
correspond to walks on $P_{n}$ without loops, starting at vertex $0$
and returning to $0$ after $2n$ steps.
\end{proof}
Again, this can be generalized to all $n'\geq n$ since $
Z_{0,0}^{n'}(2n,0)=Z_{0,0}^{n}(2n,0)$. Also Dyck paths can be
restricted in height.
\begin{example}(Bounded Catalan numbers)\lf
Bounded Catalan numbers in our sense count the number of Dyck paths,
which do not exceed a given level $k$. When $k=2$ we obtain
$ Z_{1,1}^2(2(m-1),0)= Z_{0,0}^2(2m,0) = 2^{m-1}$. For bigger $k$
some of the sequences are also well known, as the corresponding entries
from the OEIS show:
\begin{center}
\begin{tabular}{
l@{ $\rightarrow$ }l|l@{ $\rightarrow$ }l|l@{ $\rightarrow$ }l}
$Z_{0,0}^3(2m,0)$ & \seqnum{A001519} &
$Z_{0,0}^5(2m,0)$ & \seqnum{A080937} &
$Z_{0,0}^{m-2}(2m,0)$ & not listed\\
$Z_{0,0}^4(2m,0)$ & \seqnum{A124302} &
$Z_{0,0}^6(2m,0)$ & \seqnum{A024175} &
$Z_{0,0}^{m-1}(2m,0)$ & not listed
\end{tabular}
\end{center}
\end{example}
Bounded Dyck paths have also been counted by Owczarek and
Prellberg~\cite{Owczarek2012}. They derive a closed formula for a
$q$-analog, where $q$ is taking the area under the path
into account.
\begin{example}(Fibonacci Numbers)\vbox{}\vskip-7mm\vbox{}
$$ Z_{0,\gcd(m,2)}^{2}(m,0) = F_m
$$
\end{example}
\begin{proof}
$F_n =$ number of Catalan paths from $(0,0)$ to $(n, \gcd(n,2))$
that stay between the lines $y = 0$ and $y = 3$. In the On-Line
Encyclopedia of Integer Sequences this is attributed to Kimberling.
\end{proof}
\begin{example}(Motzkin numbers)\vbox{}\vskip-7mm\vbox{}
$$\sum_{\ell=1}^n Z_{0,0}^{\lfloor n/2\rfloor}(n,\ell)
= M_n$$
\end{example}
\begin{proof}
Motzkin numbers count Motzkin paths, i.e., lattice paths from $(0,0)$
to $(0,n)$, using only steps up-left, horizontal or down-left, see
Figure~\ref{fig:lattice_paths-motzkin_paths}. These paths can be counted as walks
with loops on $P_n(1)$.
\end{proof}
The refined counting for Motzkin numbers allows us to control
the maximal height of the corresponding path as well as the number of
horizontal steps allowed (or at least used).
\begin{example}(Bounded Motzkin numbers)\lf
Bounded Motzkin numbers are defined similarly to bounded Catalan
numbers but on the basis of Motzkin paths instead of Dyck paths.
\medskip
\begin{tabular}{
c@{ $\rightarrow$ }c|c@{ $\rightarrow$ }c|c@{ $\rightarrow$ }c}
$\sum_{\ell} Z_{0,0}^1(m, \ell)$ & $2^{m-1}$ &
$\sum_{\ell} Z_{0,0}^5(m, \ell)$ & \seqnum{A094287} & \vdots & \vdots \\
$\sum_{\ell} Z_{0,0}^2(m, \ell)$ & \seqnum{A024537} &
$\sum_{\ell} Z_{0,0}^6(m, \ell)$ & \seqnum{A094288} &
$\sum_{\ell} Z_{0,0}^{\lfloor{\tfrac{m}{2}}\rfloor -1}(m, \ell)$ & n.l.\\
$\sum_{\ell} Z_{0,0}^3(m, \ell)$ &\seqnum{A005207} &
$\sum_{\ell} Z_{0,0}^7(m, \ell)$ & not listed &
$\sum_{\ell} Z_{0,0}^{\lfloor{\tfrac{m}{2}}\rfloor -2}(m, \ell)$ & n.l.\\
$\sum_{\ell} Z_{0,0}^4(m, \ell)$ & \seqnum{A094286} &
\vdots & \vdots & &
\end{tabular}
\end{example}
\begin{example}(Delannoy numbers)\vbox{}\vskip-5mm\vbox{}
$$ \sum_{\ell=0}^{a} Z_{a,b-a}^{b+a}(a+b-\ell,\ell) =
\sum_{\ell=0}^a \binom{a}{\ell}\binom{b+\ell}{b} =D(a,b)$$
\end{example}
\begin{proof}
Delannoy numbers describe the number of lattice paths from $(0,0)$
to $(a,b)$ which use steps up, right and
diagonal (i.e., steps with the effect of up+right). We do a
refined counting (by counting the paths with a fixed number of
diagonal steps and therefore a fixed number of total steps). The
Delannoy paths from $(0,0)$ to $(a,b)$ with $\ell \leq a $ diagonal
steps have length $a+b - \ell$, they use $b-\ell$ up-steps and $a-\ell$
right-steps. Modeling right-steps as decreasing-steps in the path,
diagonals as loops and up-steps as increasing-steps, we see
that the number of these paths is
$Z_{a,b-a}^{b+a}(a+b-\ell,\ell)$.
\end{proof}
\begin{example}
(Schr\"oder numbers)
$$ \sum_{\ell=0}^{n} Z_{0,0}^{n}(2n-2\ell,\ell)= S(n)$$
\end{example}
\begin{proof}
Schr\"oder numbers count lattice paths from $(0,0)$ to $(n,n)$ with
steps up, right and diagonal, which do not exceed the
diagonal. Again, a counting, refined by fixing the number of diagonal
steps (to fix the number of steps in the path) yields the result. All we have to change
is the start and endpoint of our walks to ensure, that the
path does not exceed the diagonal.
\end{proof}
\begin{example}(Pell numbers)\lf
Another example are Pell numbers (\seqnum{A000129}),
which can be computed using
$b_n = \sum_{\ell=0}^n Z_{0,2}^{2}(n,\ell)$, since the $b_n$ then satisfy
the recursion $b_n = 2b_{n-1} + b_{n-2}$.
\end{example}
\section{\label{sec:refined}Refined Counting}
In this section we derive linear recursions for a refined version of the
ballot problem. A \emph{turn} is a change of direction from up to down or vice
versa (the up step and the down step need not be consecutive, they may
enclose some loops, respectively horizontal steps). Figure
\ref{fig:lattice_paths-directed_example} shows an example.
\PsFigCap{85}{lattice_paths-directed_example}{A lattice walk of
length 12 with 4 turns (red double-arrows) and 2 straight steps
(green) in $\vec{P}_3(\alpha)$ from $u_0$ to $u_2$.}
Refined counting is going to keep track of the number of
\emph{turns} of the paths. As in
Section~\ref{sec:computations} we identify lattice walks
with walks on some graph. The relevant graph $\vec{P}^+_n(\alpha)$
is obtained from the graph $\vec{P}_n(\alpha)$ shown
in Figure~\ref{fig:lattice_paths-directed_path} by adding the vertices
$u_0$ and $d_n$ with their loops and the edges $u_0\to u_1$ and $d_n
\to d_{n-1}$.
\PsFigCap{80}{lattice_paths-directed_path}{The directed path
$\vec{P}_{n}(\alpha)$ with $2n$ vertices and
loops of weight $\alpha$ and turning-edges of weight $\beta$}
The graph $\vec{P}_{n}(\alpha)$ consists of two directed paths of length $n-1$ with loops
which are connected by bidirectional edges in such a way, that the
$i$-th vertex of the first path is linked to the $(n-i)$-th vertex of
the second one. The weight of the loops is $\alpha$. The weight of the
bidirectional edges is~$\beta$ and the weight of the directed edges on
the two paths is $1$. Note that the vertices $u_0$ and $d_n$ are omitted, they have no
incoming edges and do not play a role in the counting of
lattice walks unless one of them represents the starting vertex.
Now, let
\begin{eqnarray*}
\vec{Z}_{v,w}^n(m,\ell, t) &:=&
\#( \text{ walks on } \vec{P}_n(\alpha) \text{ from } v \text{ to } w
\text{ of length } m \\
&& \text{ \hskip 3cm with } \ell \text{ loops and } t \text{ turns} ),\\
\vec{Z}_{v,w}^n(m) &:=& \sum_{\ell, t} \vec{Z}_{v,w}^n(m,\ell, t) \alpha^\ell \beta^t.
\end{eqnarray*}
Krattenthaler counted some instances of these lattice paths. See
\cite{Krattenthaler}, especially Theorem~3.4.4 for details. However, his
work does not cover straight steps (or loops in our language).
\begin{theorem}(Characteristic polynomial of $\vec{P}_n(\alpha)$
\label{thm:lattice_paths-char_polynomial})\\
Let $\chi_{\vec{P}_n(\alpha)}(x)$ be the characteristic polynomial
of the adjacency matrix of the graph $\vec{P}_n(\alpha)$. Then:
$$ \sum_{n=0}^\infty \chi_{\vec{P}_n(\alpha)}(x) \lambda^n =
\frac{(\alpha-x)^2(\lambda-1)-\beta^2 }
{1+(\beta^2-1+ (\alpha-x)^2(\lambda-1))\lambda }
$$
and
$$ \vec{Z}_{v,w}^n(m) = \frac{-1}{c^n_{2n}}\cdot \sum_{k=1}^{2n} c^n_{2n-k} \cdot \vec{Z}_{v,w}^n(m-k),$$
where
$$
c^n_{k} = (-1)^k
\sum_{j=0}^{n} \sum_{l=0}^{n-j} \sum_{i=0}^{j}
\binom{n - l - j -1}{j-1}\binom{ l +j }{j}\binom{ j }{i} \binom{2i }{k}
(- \beta^2)^{l+j-i}\alpha^{2i-k}
$$
are the coefficients of the characteristic polynomials
$\chi_{\vec{P}_n(\alpha)}(x)$ of the graphs $\vec{P}_n(\alpha)$.
\end{theorem}
To prove this theorem, we use a well known connection between cycle
covers and determinants of the adjacency matrix of the covered
(di-)graphs.
\begin{definition}
Let $\vec{G}$ be a directed graph with weighted edges. A
\emph{cycle cover} $C$ of $\vec{G}$ consists of $|V(\vec{G})|$
edges, such that every vertex has one incoming and one outgoing
edge. In other words it is a set of simply directed cycles which
contains every vertex exactly once.
Further, the weight $\omega(C)$ of the cycle cover $C$ is the
product of all edge-weights of $C$ multiplied with $(-1)^{\# \text{
even cycles}}$. Finally $\mathcal{C}(\vec{G})$ is the set of all
cycle covers of $\vec{G}$.
\end{definition}
\begin{lemma}(\label{lem:CycleCover}Cycle covers and determinants)\lf
Let $\vec{G}$ be a digraph with edge weights and adjacency matrix $A
= (a_{ij})$. We have
$$
\det(A) = \sum_{\sigma \in S_n} \left(\sgn(\sigma) \cdot \prod_{i=1}^n
a_{i,\sigma(i)}\right) = \sum_{C \in \mathcal{C}(\vec{G})} \omega(C)
= \omega(\mathcal{C}(\vec{G})).
$$
\end{lemma}
\begin{proof}
A permutation $\sigma \in S_n$ can be seen as a subset of $n$
directed edges $C = \{ (i, \sigma(i)) \mid i=1\dots,n\}$, which form
a cycle cover. This cycle cover has weight $ \sgn(\sigma) \cdot
\prod_{i=1}^n a_{i,\sigma(i)}$. If one of the edges is not present
in $\vec{G}$, the weight is $0$, since the corresponding entry of
$A$ is $0$. The sign of $\sigma$ is the product of the signs of
individual cycles. Even cycles contribute a factor of $-1$, odd
cycles a factor $+1$.
\end{proof}
\begin{proposition}\label{prop:lattice_paths-Kasteleyn}
(Theorem 4.7.2 of \cite{Stanley}
or Proposition V.9 of \cite{citeulike:2587917})\\
Let $A$ be the adjacency matrix of a graph $G$. Further, let
$N_{i,j}(k)$ be the number of walks from $i$ to $j$ of length $k$ and
$w_{ij} = \sum_{k=0}^\infty N_{i,j}(k) \cdot t^k$. Then $W=(w_{ij}) =
(\mathcal{I} - t \cdot A)^{-1}$, where $\mathcal{I}$ is the identity
matrix of the right size.
\end{proposition}
With this we are ready for the proof of the theorem:
\begin{proof}(Theorem~\ref{thm:lattice_paths-char_polynomial}) To find
the generating function for the characteristic polynomials
$\chi_{\vec{P}_n(\alpha)}$ of the adjacency matrix of the graph
$\vec{P_n}(\alpha)$, we count weighted cycle covers of the graph
$\vec{P}_n(\alpha-x)$. According to Lemma~\ref{lem:CycleCover} the
sum of their weights is the polynomial we are looking for. Now, we
partition the set of all cycle covers, according to the edges they
use, to cover the vertices $d_{n-1}$ and $u_n$. Let $A_n$ be the
set of all cycle covers of $\vec{P}_n(\alpha-x)$, such that the
vertices $u_n$ and $d_{n-1}$ are both covered by loops and let $B_n$
be the set of all remaining cycle covers. Cycle covers in $B_n$
contain the edge $(u_n, d_{n-1})$, since apart from the loop this is
the only outgoing edge of $u_n$. Further, let $a_n := \omega(A_n) =
\sum_{C \in A_n} \omega(C) $ and $b_n := \omega(B_n)$. This implies
$\omega(\mathcal{C}(\vec{P}_n(\alpha-x))) = \sum_{C \in
\mathcal{C}(\vec{P}_n(\alpha-x))} \omega(C) = a_n + b_n$. Now,
every cycle cover of $\vec{P}_{n-1}(\alpha)$ can be extended with
two loops of weight $(\alpha-x)^2$ or a two-cycle of weight
$-\beta^2$. Further for every cycle cover in $B_{n-1}$, we can
replace the edge $u_{n-1},d_{n-2}$ by the path
$u_{n-1},u_n,d_{n-1},d_{n-2}$. This leads to a cycle cover in $B_n$
with the same weight. Conversely, from a cycle cover in $A_n$ we can
delete the two loops at $u_n$ and $d_{n-1}$ to obtain a cover of
$\vec{P}_{n-1}$. In a cycle cover in $B_n$ the two vertices $u_n$
and $d_{n-1}$ are either covered by a two cycle which can be deleted
or they belong to a longer cycle from which they can be
removed. This implies the linear recursions $ a_{n+1} = (\alpha
-x)^2 (a_{n} + b_{n})$ and $b_{n+1} = -\beta^2 a_n + (-\beta^2+ 1)
b_n$. The initial conditions are $a_0 = (\alpha-x)^2$ and $b_0 =
-\beta^2 $. With $A =\left(\begin{array}{cc} (\alpha-x)^2
&(\alpha-x)^2\\ -\beta^2 & -\beta^2 + 1 \end{array} \right)$, we
obtain:
\begin{eqnarray*}
\chi_{\vec{P}_n(\alpha)}(x)
&=&
\omega(\mathcal{C}(\vec{P}_n(\alpha-x))) = a_n + b_n = (1, 1) \cdot
\begin{pmatrix}a_{n} \\ b_{n} \end{pmatrix}\\
&=&
(1,1) \cdot A \cdot \begin{pmatrix}a_{n-1} \\ b_{n-1} \end{pmatrix} =(1,1) \cdot
A^{n} \cdot \begin{pmatrix}a_{0} \\ b_{0} \end{pmatrix}.
\end{eqnarray*}
Hence,\vskip-6mm
$$
\sum_{n=1}^\infty \chi_{\vec{P}_n(\alpha)}(x) \lambda^n =
\sum_{n=1}^\infty \left( (1,1)\cdot A^{n}\cdot \begin{pmatrix}a_{0} \\
b_{0}\end{pmatrix} \right) \cdot \lambda^n$$ and
Proposition~\ref{prop:lattice_paths-Kasteleyn} can be applied.
For this we need the inverse of $(\mathcal{I}_2 - \lambda A)$
which is
$$
\frac{1}{1+(\beta^2 -1)\lambda + (\alpha-x)^2(\lambda^2-\lambda)}
\left(
\begin{array}{cc}
1-(-\beta^2+1)\lambda & (\alpha- x)^2 \lambda \\
-\beta^2 \lambda & 1- (\alpha-x)^2 \lambda
\end{array}
\right).
$$
Hence, the generating function for the characteristic polynomials
of $\vec{P}_n(\alpha)$ is
\begin{eqnarray*}
\sum_{n=0}^\infty \chi_{\vec{P}_n(\alpha)}(x) \cdot \lambda^n &=&
(1,1) \cdot (\mathcal{I}_2 - \lambda A)^{-1}
\cdot \begin{pmatrix}(\alpha-x)^2\\ -\beta^2\end{pmatrix}\\
&=& \frac{(\alpha-x)^2(\lambda-1)-\beta^2 }
{1+(\beta^2-1+ (\alpha-x)^2(\lambda-1))\lambda }.
\end{eqnarray*}
This proves the first part of the theorem.
To deduce the theorem's second claim, one could establish an explicit
representation of the characteristic polynomial
$\chi_{\vec{P}_n(\alpha)}(x)$ via a partial fraction decomposition of
the generating function above. However, there is a more direct and elegant
approach using Lemma~\ref{lem:CycleCover}: A cycle cover of
$\vec{P}_n(\alpha -x)$ decomposes the upper path of $\vec{P}_n(\alpha
-x)$ into segments of consecutive vertices, each segment belonging to
one cycle. Conversely every such decomposition induces some cycle
covers, each segment has to be closed to a cycle. For sections, which
have length $\geq 1$, the cycle is unique, while for singleton
vertices, there is either a loop on both sides or a two cycle.
There are $\binom{n-1 }{p-1}$ decompositions of the upper part of
$\vec{P}_n$ into $p$ parts. They induce different numbers of cycle
decompositions of weights. We count these decompositions with respect
to~$l$, the number of sections of length 1, and $j$, the number of
sections of length $\geq 2$. There are $\binom{n-l-j-1}{j-1}$
decompositions of $n-l$ elements into $j$ sections of length $\geq 2$.
For given $(l,j)$ we therefore have $\binom{n-l-j-1}{j-1}\binom{l+j}{j}$
decompositions. For each of them, the sum of the weights of the
corresponding cycle covers is $(-\beta^2)^l((\alpha-x)^2 - \beta^2)^j$.
This yields
$$
\chi_{\vec{P}_n(\alpha)}(x) =
\sum_{j=0}^{n} \sum_{l=0}^{n-j} \binom{n - l - j -1 }{j-1}
\binom{ l +j }{j} (-\beta^2)^l((\alpha-x)^2 - \beta^2)^j
$$
and with simple algebra this equals
\vskip-6mm
$$
\sum_{k=0}^{2n} x^k \overbrace{\left(\kern-3pt (-1)^k
\sum_{j=0}^{n} \sum_{l=0}^{n-j} \sum_{i=0}^{j}
\binom{n - l - j -1}{j-1}\binom{l +j}{j}\binom{j}{i} \binom{2i}{k}
(- \beta^2)^{l+j-i}\alpha^{2i-k}\right)}^{=c^n_{k}}.
$$
Now, Fact~\ref{fact:CharPoly} yields the second claim of our theorem
since $\vec{Z}_{v,w}^n(m)$ is the entry of the $m$-th power of
the adjacency matrix of $\vec{P}_n(\alpha)$, associated to $v$ and $w$.
\end{proof}
\section{Further Results}
\subsection{Tri-diagonal Toeplitz matrices \label{ssec:BandToeplitz}}
In the literature you commonly find variants of the formulas in
Theorem~\ref{thm:keyZ} with an additional parameter. This parameter
represents different weights for the step $i\rightarrow i+1$ and
the step $i \rightarrow i-1$. These different weights still yield a
tridiagonal Toeplitz matrix. The spectrum and an orthonormal basis of
eigenvectors are known for tridiagonal Toeplitz matrices,
see~\cite{TOEPLITZ}. Therfore, our theorem can easily be adapted to
cover the more general case.
\subsection{The symmetric case}
For the case of symmetric lattice walks, i.e., walks on graphs, having
an adjacency matrix, which is a symmetric Toeplitz matrix, we can apply
Theorem~\ref{thm:keyZ} for the enumeration of the walks.
Let $A\in\mathbb{R}^{(n+1) \times (n+1)}$ be a symmetric Toeplitz
matrix and let $c_0, c_1, \dots c_{n} \in \mathbb{R}$ be its first
row; $A$ is completely determined by these values. The powers
$A^k_{(n,0)}$, $k=0,\ldots,n$ of the adjacency matrix of~$P_n(0)$
form a basis for symmetric Toeplitz matrices, in fact if $a^k_0,
a^k_1, \dots a^k_{n}$ is the first row of~$A^k_{(n,0)}$, then
$a^k_k = 1$ and $a^k_j = 0$ for all $j> k$.
Hence we can write
$$ A = \sum_{k=0}^{n} \tilde{c_k} \cdot A_{(n,0)}^k
$$
and the coefficients $\tilde{c_k}$ can be recursively computed
as $\tilde{c_n} = c_n$ and $\tilde{c_k} = c_k - \sum_{j=k+1}^{n}
\tilde{c_j} a_{k}^j$.
Therefore, the orthonormal basis of eigenvectors of $A_{(n,0)}$ is
an orthonormal basis of eigenvectors of $A$. Furthermore the eigenvalues of $A$ are
$$ \hat{\lambda_i} := \sum_{k=0}^{n-1}\tilde{c_k} \lambda_i^k,$$
where $\lambda_i$ are the eigenvalues of $A_{(n,0)}$. Since we have
an orthonormal basis of eigenvectors and the corresponding
eigenvalues, we can write down formulas for $A$ that correspond to
the formulas (3) and (4) for $A_{(n,0)}$.
\subsection{Lattice walks with arbitrary positive steps \label{ssec:PosSteps}}
\def\mrarrow#1{\stackrel{#1}{\rightarrow}}
For some cases of asymmetric lattice walks, we find linear
recursions. If we only allow steps $i \rightarrow i +j$ with $j \in
\{ -1, 0, 1, \dots, k \}$ with weights $c_j \in \mathbb{R}$, then the
adjacency matrices are of the form $\Toeplitz(0, \dots, 0, c_{-1},
c_0, \dots, c_k, 0 , \dots, 0)$. For these, we can give linear
recursions for the characteristic polynomials. With
Fact~\ref{fact:CharPoly} we obtain linear recursions for the number of
corresponding lattice paths if we get a handle on the characteristic
polynomial $\chi_n(x)$ of the $n\times n$ matrix $\Toeplitz(0, \dots,
0, c_{-1}, c_0, \dots, c_k, 0 , \dots, 0)$.
A recursion for the characteristic polynomial can be obtained
via Lemma~\ref{lem:CycleCover}. In a cycle decomposition the last
vertex $v_n$ belongs to a cycle
$v_n\mrarrow{-1}v_{n-1}\mrarrow{-1}\ldots\mrarrow{-1}v_{n-j},\mrarrow{j}v_n$
for some $j$. This yields the recursion
$$ \chi_{n+1}(x) = (c_0 -x) \chi_n(x) + \sum_{j=1}^k c_{-1}^j c_j \chi_{n-j}(x).$$
For small $k$ we can solve the linear recursion above
and get an explicit representation of the characteristic polynomial.
This yields an explicit linear recursion for the numbers of lattice walks.
\subsection{\label{ssec:circulant} Cylindrical lattice walks}
As a last instance we now consider walks, which allow arbitrary step length
(and arbitrary weights) on a cycle. Taking an edge for each allowed
step we obtain a circulant graph. The ``time expansion'' yields a
cylinder as analog to the lattice strips.
\PsFigCap{75}{lattice_paths-circulant_walks}{A circulant graph with
8 vertices and steps $+1$ (black) and $-2$ (blue).}
The adjacency matrices of circulant graphs are
\emph{circulant matrices}. For this class of matrices eigenvalues and
eigenvectors are known. According to Gray~\cite{Gray2005} they are as follows:
\begin{theorem}(\label{thm:lattice_paths-circulant_matrices}
Eigenvalues and -vectors of circulants, Theorem 3.1 of \cite{Gray2005})\lf
Let $C \in \mathbb{R}^{n\times n}$ a circulant matrix with first row
$(c_0, c_1, \dots, c_{n-1})\in \mathbb{R}^n$. Then the
eigenvalues $\psi_m$ and corresponding eigenvectors $y_m$ of $C$ for
$m=0,1,\dots,n-1$
are as follows:
$$\psi_m =: \sum_{k=0}^{n-1} c_k e^{\tfrac{-2\pi i m k}{n}}, \quad
y_m =: \tfrac{1}{\sqrt{n}} (1, e^{\tfrac{-2 \pi i m}{n}},
e^{\tfrac{-2 \pi i m 2 }{n}},\dots, e^{\tfrac{-2 \pi i m(n-1)}{n}}).
$$
\end{theorem}
Note, that the eigenvectors of circulant matrices do \emph{not} depend
on the matrix, but only on the dimension $n$. Therefore, they are
the same for all circulant matrices of the same size (which implies
these matrices commute). Now, we can count walks on circulant graphs with
the techniques from Section~\ref{sec:computations}.
This leads to explicit formulas as well as to linear recursions.
\section{\label{sec:future}Conclusion and future work}
Trigonometric sums of the form given in Theorem~\ref{thm:keyZ}
can be handled quite well by computer algebra systems, e.g. {\tt Maple}.
Our impression is that indeed the formulas lead to the most
effective way of evaluating the number of paths of a certain type in not
too narrow and rather long strips. For narrow strips a generating function approach
may be practical and superior. For short strips it can be reasonable to explicitly
use the recursion (dynamic programming).
In the examples section (Section~\ref{sec:bijections}) we have listed some cases
of integer sequences that could be obtained by
counting (weighted) walks in $P_n(\alpha)$.
The basic approach, however, is not limited to this case.
The crucial requirement is that we are able find an
explicit expression for the entries of powers of the
adjacency matrix. Cases where this is possible
include situations where Toeplitz matrices are substituted
for the entries of a Toeplitz matrix. Investigating this and
related cases should allow to count families of
{\it lattice surfaces}, e.g., fillings of the cells of an
$n\times m$ grid with numbers between~$0$ and~$h$
such that the numbers of adjacent cells differ by
at most one.
Some problems remain. For example in Section~\ref{sec:refined}, we
found a linear recursion, but the explicit generating
functions remain unknown. In
Section~\ref{ssec:BandToeplitz} we quote results for band matrices
with (at most) five nonzero diagonals. Improvements in this work can
be directly translated back into lattice path enumeration.
Section~\ref{ssec:PosSteps} contains linear recursions for linear
recursions, can this be simplified?
Another direction might be to try to solve special families of
instances that are not covered by our work. For example walks with steps
$i\rightarrow i+k$ for $k \in\{-3, -1, 0, +1, +5\}$. Banderier and
Nicodeme~\cite{banderier:hal-00542185} considered some related
instances. They were able to enumerate the corresponding number of lattice
walks.
In general the inverses of Toeplitz matrices are interesting. If they
are given we can apply Proposition~\ref{prop:lattice_paths-Kasteleyn},
similar to what we did in the proof of
Theorem~\ref{thm:lattice_paths-char_polynomial}. There is a lot of
work in this direction, see~\cite{Dow} and references therein.
\section{\label{sec:acknowledgements}Acknowledgments}
A preliminary version of this work was presented at the 7th
International Conference on Lattice Path Combinatorics and
Applications in Siena. There we got interesting feedback, hints to
relevant literature, remarks and further ideas, which partly were
included here. In particular, we thank Cyril Banderier, Christian
Krattenthaler, and Helmut Prodinger for helpful remarks.
\begin{thebibliography}{10}
\bibitem{banderier:hal-00542185}
Cyril Banderier and Pierre Nicodeme,
Bounded discrete walks, In {\em {Proc. AofA' 10}},
{\em Discrete Math. Theor. Comput. Sci.}, 2010,
pp.~35--48.
\bibitem{TOEPLITZ}
Albrecht B\"ottcher and Sergei~M. Grudsky, {\em {Spectral Properties of
Banded {T}oeplitz Matrices}}, SIAM, 2005.
\bibitem{ChowWest}
Timothy Chow and Julian West, Forbidden subsequences and {C}hebyshev
polynomials, {\em Discrete Math.} {\bf 204} (1999), 119--128.
\bibitem{CCM}
Giovanni~M. Cicuta, Marco Contedini, and Luca~G. Molinari, {Enumeration
of simple random walks and tridiagonal matrices}, {\em J. Phys. A} {\bf
35} (2002), 1125--1146.
\bibitem{Dow}
Murray Dow, {Explicit inverses of {T}oeplitz and associated
matrices}, {\em ANZIAM J.} {\bf 44} (2003), 185--215.
\bibitem{em-rmp-05}
Sergi Elizalde and Toufik Mansour, Restricted {M}otzkin permutations,
{M}otzkin paths, continued fractions, and {C}hebyshev polynomials, {\em
Discrete Math.} {\bf 305} (2005), 170--189.
\bibitem{Feller}
William Feller, {\em {An Introduction to Probability Theory and its
Applications, Vol.~1}}, John Wiley \& Sons, 1968.
\bibitem{citeulike:2587917}
Philippe Flajolet and Robert Sedgewick, {\em {Analytic Combinatorics}},
Cambridge Univ. Press, 2009.
\bibitem{Gray2005}
Robert~M. Gray, Toeplitz and circulant matrices: A review, {\em Commun.
Inf. Theory} {\bf 2} (2005), 155--239.
\bibitem{Humphreys}
Katherine Humphreys, A history and a survey of lattice path
enumeration, {\em J. Statist. Plann. Inference}
{\bf 140} (2010), 2237--2254.
\bibitem{Krattenthaler}
Christian Krattenthaler, The enumeration of lattice paths with respect
to their number of turns.
\newblock In {\em Advances in Combinatorial Methods
and Applications to
Probability and Statistics}, Stat. Ind. Technol.,
Birkh\"auser, 1997, pp.~29--58.
\bibitem{Mohanty}
Gopal Mohanty, {\em {Lattice Path Counting and Applications}},
Academic Press, 1979.
\bibitem{Owczarek2012}
Aleks Owczarek and Thomas Prellberg, Enumeration of area-weighted
{D}yck paths with restricted height, {\em Australas. J. Combin.} {\bf
54} (2012), 13--18.
\bibitem{Stanley}
Richard~P. Stanley, {\em Enumerative {C}ombinatorics}, Vol. 1,
Cambridge Univ. Press, 1997.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A05, 15A09, 15B05.
\noindent \emph{Keywords: } Catalan number, Motzkin number,
transfer matrix, trigonometric sum.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A000129},
\seqnum{A001519},
\seqnum{A005207},
\seqnum{A006012},
\seqnum{A024175},
\seqnum{A024537},
\seqnum{A080937},
\seqnum{A094286},
\seqnum{A094287},
\seqnum{A094288},
\seqnum{A124302}, and
\seqnum{A147748}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 6 2014;
revised versions received December 3 2014; December 23 2014.
Published in {\it Journal of Integer Sequences}, December 26 2014.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}