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