\documentclass[12pt,reqno,a4paper]{amsart}

\advance\voffset    by -1  cm
\advance\hoffset    by -1.5cm
\advance\textwidth  by  3  cm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Diverse Kleinigkeiten, Abkuerzungen etc.:                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\bit{\begin{itemize}}
\def\eit{\end{itemize}}

% Speziell fuer cylindric walkers:
\def\wexp{{\mathcal W}}
\def\lgt{Lindstr\"om--Gessel--Viennot}
\def\polylog#1#2{\operatorname{Li}_{#1}\of{#2}}

% Weiter im Text:

\def\pas#1{\left(#1\right)}
\def\var#1{\operatorname{var}\left(#1\right)}
\def\cov#1{\operatorname{cov}\left(#1\right)}
\def\image{\operatorname{im}\!}
\def\var#1{\operatorname{var}\left(#1\right)}

\def\E#1{{\mathbb E}\left(#1\right)}
\def\bit{\begin{itemize}}
\def\eit{\end{itemize}}

\def\modulo#1{\;\pas{#1}}
\def\modeq#1#2#3{#1\equiv #2\;\pas{#3}}

\def\C{{\mathbb C}}
\def\N{{\mathbb N}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\Z{{\mathbb Z}}

\def\i{{\mathbf i}}
\def\d{{\mathrm d}}
\def\e{{\mathbf e}}

\newcommand{\SG}{{\mathcal S}}
\newcommand{\defeq}{:=}                 % define equal...
\newcommand{\fpath}{{\mathbf P}}       % family of lattice paths
\newcommand{\GF}[1]{\mathbf{GF}\of{#1}}
\newcommand{\sgn}{\operatorname{sgn}}                   % Signum
\newcommand{\id}{{\mathrm{id}}}             % Identity permutation

\newcommand{\thmref}[1]{Theorem~\ref{#1}}
\newcommand{\secref}[1]{Section~\ref{#1}}
\newcommand{\lemref}[1]{Lemma~\ref{#1}}
\newcommand{\figref}[1]{Figure~\ref{#1}}
\newcommand{\tabref}[1]{Table~\ref{#1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                    Diverse Klammerungen:                                 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\seqof}[1]{\left\langle#1\right\rangle}
\newcommand{\setof}[1]{\left\{#1\right\}}
\newcommand{\of}[1]{\left(#1\right)}
\newcommand{\parof}[1]{\left(#1\right)}
\newcommand{\numof}[1]{\left|#1\right|}
\newcommand{\detof}[2]{\left|{#2}\right|_{#1\times #1}}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\firstcolumn}[1]{%\underbrace{#1%}_{\text{first column}}
\quad \vdots\quad }
\newcommand{\firstrow}[1]{%\underbrace{#1%}_{\text{first row}}
\quad \vdots\quad }
\newcommand{\brkof}[1]{\left[#1\right]}
\newcommand{\intof}[1]{\lfloor #1\rfloor}
\newcommand{\absof}[1]{\left|#1\right|}
\newcommand{\sgnof}[1]{\operatorname{sgn}\of{#1}}

\newcommand{\edge}[2]{\left[#1\rightarrow #2\right]}
\newcommand{\pathof}[2]{\left[\left[#1\rightarrow #2\right]\right]}
\newcommand{\setpathof}[2]{{\mathcal P}\of{#1,#2}}
\newcommand{\hatsetpathof}[2]{\hat{{\mathcal P}}\of{#1,#2}}
\newcommand{\setnipathof}[2]{{\mathcal P^+}\of{#1,#2}}

\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{obs}[thm]{Observation}
\newtheorem{rem}[thm]{Remark}
\newtheorem{con}[thm]{Conjecture}

\usepackage{epsfig} 

\begin{document}

\bibliographystyle{plain}

\title{Nonintersecting lattice paths
on the cylinder}

\begin{abstract}
We show how a formula concerning ``vicious walkers'' (which basically are
nonintersecting lattice paths) on the cylinder
given by P.J.~Forrester can be proved and generalized
by using the \lgt\ method, after having things set up in the
right way. We apply the corresponding results to the
(thermodynamic limit of the) free energy of the ``lock step
model of vicious walkers'', thus completing (and in one instance correcting) the work of Forrester.
Moreover, we also show how a related formula given
by I.~Gessel and C.~Krattenthaler can be obtained from the same
``point of view''.
\end{abstract}

\author{Markus Fulmek}
\address{Institut f\"ur Mathematik, Universit\"at Wien\\
Nordbergstra\ss e 15, A--1090 Wien, Austria}
\email{{\tt Markus.Fulmek@Univie.Ac.At}\newline\leavevmode\indent
{\it WWW}: {\tt http://www.mat.univie.ac.at/\~{}mfulmek}
}

\date{}
\thanks{Research partially supported by European Commission's
	IHRP Programme,
	grant HPRN--CT--2001--00272, ``Algebraic Combinatorics in
	Europe''.}
% Research partially supported by the European Commission's IHRP
% Programme, grant HPRN-CT-2001-00272, ``Algebraic Combinatorics
% in Europe"
\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 52 \rms (2004), Article~B52b\hfill}
\def\thepage{}
%
%

\section{Introduction}
\label{intro}

In this paper, we consider interesting formulas concerning
nonintersecting lattice paths on the cylinder, and show how the
well--known \lgt\ method provides a common and
quite simple framework for proving them.

We also consider
the asymptotic behaviour of these formulas (i.e., we determine
the thermodynamic limit of the free energy of the ``lock
step model of vicious walkers'') and correct a small
error in the respective formula
\cite[(2.33)]{forrester:vicious-walkers} given by Forrester.

\subsection{Forrester's formula}
In his paper \cite{forrester:vicious-walkers}, Forrester considered
the generating function of certain ``vicious walkers''
\cite[Theorem 2.1]{forrester:vicious-walkers}. The model of
vicious walkers was originally introduced by Fisher \cite{fisher:walks}.
% by a certain physical model, but omitting this background,
% we may simply view
In combinatorial terms, Forrester's formula % given in
simply gives the enumeration of nonintersecting
lattice paths on a cylindric lattice, expressed as a determinant of certain sums,
% of generating functions of lattice paths,
but only for the case of an {\em odd\/} number of nonintersecting lattice paths.
Forrester proved this formula using a recurrence relation.

\subsection{Simple framework for Forrester's formula: \lgt}
In our paper, we shall show how the \lgt\ 
framework \cite{lindstroem,gessel-viennot:det} for
directed graphs
% the lattice $\Z\times\Z$
can be effortlessly adapted to the cylindric lattice $\Z\times\Z_M$.
% , just by choosing ``the right point of view''.
From this point of view, Forrester's formula literally is ``easily seen''.

Moreover, it is almost immediate
that in this
% the appropriate \lgt--
setting the appropriate generalization of Forrester's formula also holds for
an {\em even\/} number of ``vicious walkers''. However, in its ``raw''
form, the respective formula
% corresponding generating function
% however, 
% i.e., nonintersecting lattice paths,
contains summands with negative sign, and hence
is not very useful for enumeration purposes. We overcome this
disadvantage by
appropriately modifying the weights in the respective generating function
(see Theorem~\ref{thm:main2}). 

As applications, we give enumeration formulas for the case of $r$ {\em equidistant\/}
vicious walkers.
While for an odd number $r$, this formula
is already contained in \cite[(2.28)]{forrester:vicious-walkers}, the formula
for even $r$ seems to be new. Thus we are able to complete
Forrester's work; in particular, we can now also determine
the 
asymptotics for even $r$.
Finally, we indicate another proof (basically amounting to coefficient
extraction in Forrester's formula) of a formula given by
Gessel and Krattenthaler \cite{gessel-kratt:cylindric-partitions}.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MARKUS FULMEK}{\SMALL NONINTERSECTING LATTICE PATHS
ON THE CYLINDER}
%
%

\subsection{Organization of this paper} 
This paper is organized as follows:

\bit
\item In Section~\ref{basic}, we present the basic definitions and recall
the \lgt\ method.
\item In Section~\ref{results}, we explain how the \lgt\ me\-thod applies to a cylindric lattice.
\item In Section~\ref{applics}, we derive explicit
	enumeration formulas for equidistant vicious walkers.
	(These are related to a formula obtained by Grabiner
	\cite[(33)]{grabiner:random-walks2003}: Our
	formulas \eqref{eq:eqd-odd} and \eqref{eq:eqd-even} could
	be obtained by an appropriate summation of Grabiner�s
	formula). Moreover, we give the corresponding
	asymptotic formulas for the number of paths tending to
	infinity (and correct a small error in the asymptotic formula
	\cite[(2.33)]{forrester:vicious-walkers} given by Forrester).
	Finally, we indicate
	how Forrester's formula and our generalization is related
	to the
	main theorem of Gessel and Krattenthaler
	\cite[Proposition 1, Equation (3.5)]{gessel-kratt:cylindric-partitions}.
% \item In Section~\ref{open}, we state some open problems.
\eit

\section{Basic Definitions and Presentation of known Formulas}
\label{basic}
The main purpose of this paper is to present how the right point of
view almost immediately gives insight in Forrester's formula as well as in
Gessel and Krattenthaler's formula. So we make an effort to give
a careful explanation of this point of view.
% Thus, we review the well--known concept of nonintersecting
% lattice paths and the \lgt\ determinant.
\subsection{Nonintersecting paths and generating functions in the
lattice $\Z\times\Z$}

Consider the lattice $\Z\times\Z$, i.e., the directed graphs with
vertex set $\Z\times\Z$ and arcs from $\pas{m,n}$ to $\pas{m-1,n+1}$
(a ``step to the left'') and from $\pas{m,n}$ to $\pas{m+1,n+1}$
(a ``step to the right'') for all $\pas{m,n}\in\Z\times\Z$ (see
\figref{fig:zz-lat}). To all steps to the right, assign weight $1$, and
to all steps to the left, assign weight $x$, i.e., for the edge
$$e=\edge{\pas{m_0,n}}{\pas{m_1,n+1}}$$
we have
\begin{equation}
\label{eq:weightsteps}
w\of{e} =
\begin{cases}
1 & \text{if } m_1 = m_0 + 1, \\
x & \text{if } m_1 = m_0 - 1.
\end{cases}
\end{equation}

\begin{figure}
\caption{Illustration of lattice paths in $\Z\times\Z$. The picture shows
three lattice paths $p_1$, $p_2$ and $p_3$; from $\pas{3,-2}$ to $\pas{6,11}$,
from $\pas{6,-2}$ to $\pas{11,11}$, and from $\pas{9,-2}$ to $\pas{10,11}$,
respectively. Note that $p_1$ intersects $p_3$ in point $\pas{7,4}$, but
$p_2$ does neither intersect $p_1$ nor $p_3$, since the ``geometric
crossings'' do not correspond to common lattice points.}
\label{fig:zz-lat}
\centerline{\epsfxsize12cm\epsffile{zzlattice.eps}}
\end{figure}

A path $p$ of length $N$ is simply a sequence of $N$ adjacent edges
$\pas{e_1,\dots,e_N}$; i.e., for the sequence $\pas{v_i}_{i=0}^N$ of
vertices in the path, we have
$$
e_i = \edge{v_{i-1}}{v_i}
$$
for $i = 1,\dots N$.
The vertices $v_0$ and $v_N$ are called the starting point
and the end point of $p$, respectively.
% ; we denote this by $p=\pathof{v_0}{v_N}$.

The weight of a lattice path $p=\pas{e_1,\dots,e_N}$ of length $N$ is
simply defined to be the product of the weights of its edges, i.e.,
\begin{equation}
\label{eq:unsigned-weights}
w\of p = \prod_{i=1}^N w\of{e_i}.
\end{equation}

Two lattice paths $p_1$ and $p_2$ are called {\em intersecting\/}, if they
have a {\em vertex\/} (i.e., a {\em lattice point\/}) in common. A family of lattice paths $p_1,\dots,p_r$
(also called an $r$--tuple of lattice paths) is called {\em nonintersecting\/},
if no two of its paths are intersecting.

See \figref{fig:zz-lat} for an illustration of these simple concepts.

\begin{rem}
\label{rem:evenonly}
Note that ``intersection'' refers only to {\em common lattice
points}: E.g., the ``geometric crossings'' of path $p_1$ and $p_2$ in
\figref{fig:zz-lat} do {\em not\/} constitute intersections
in this sense.

It is clear that two paths starting in lattice points $\pas{m_1,n_1}$ and
$\pas{m_2,n_2}$, respectively, can only be intersecting if
$\pas{m_1-m_2+n_1-n_2}$ is an {\em even\/} number.

While the following considerations and formulas are valid even if this
parity condition is violated, the most interesting case occurs if we
consider the ``even--numbered'' sub--lattice
$\setof{\pas{x,y}\in\Z\times\Z:\; x+y\equiv 0\modulo{2}}$.
\end{rem}

The weight of an arbitrary (not necessarily non--intersecting) $r$--tuple
$\fpath=\pas{p_1,\dots,p_r}$ of lattice paths is simply defined
to be the product of the weights of the single paths, i.e.,
\begin{equation}
w\of{\fpath} = \prod_{i=1}^r w\of{p_i}.
\end{equation}

As usual, by the generating function of some set $A$ of weighted objects
we understand the sum of the weights of the objects, i.e.,
$$
\GF{A} = \sum_{a\in A} w\of{a}.
$$
\subsection{The \lgt\ determinant}
The enumeration of nonintersecting paths in some directed
graph with given starting and
end points is given by the \lgt\
determinant (see \cite[Lemma 1]{lindstroem} or
\cite[Corollary 2]{gessel-viennot:det}). In order to make clear how
this elegant method can be applied to the case of cylindric lattices also,
we state % and prove
this well--known result:
\begin{prop}
\label{prop:lgv-det}
Let $D=\pas{{\mathcal V},{\mathcal A}}$ a directed graph (with vertex
set ${\mathcal V}$ and arc set ${\mathcal A}$), and let $A=\pas{a_1,\dots,a_r}$ and $E=\pas{e_1,\dots,e_r}$ be
two lists of arbitrary vertices in the $D$.
% with the property
% that for $1\leq i < j \leq r$ and $1\leq k < l \leq r$, {\em any\/} path from
% $a_i$ to $e_l$ must intersect {\em any\/} path from $a_j$ to $e_k$.
Then we have:
% the
% generating function of families $\pas{p_1,\dots,p_r}$
% of {\em nonintersecting\/} lattice paths, where
% $p_i=\pathof{a_i}{e_i}$ (i.e., 
% $p_i$
% runs from $a_i$ to $e_i$,
%),
% is given by
\begin{equation}
\label{eq:lgt-gen}
\det_{1\leq i,j,\leq r}\of{\GF{\setpathof{a_i}{e_j}}} =
\sum_{\pi\in\SG_r}\sgnof\pi
	\GF{\setnipathof{A}{E_{\pi}}}.
\end{equation}
where $\setpathof{a}{e}$ denotes the set of {\em all\/} paths
starting at $a$ and ending at $e$, and $\setnipathof{A}{E_{\pi}}$
denotes the set of all $r$--tuples of {\em nonintersecting\/} paths, where path $i$ starts at $a_i$ and ends at $e_{\pi\of i}$.
\end{prop}

\begin{rem}
\label{rem:lgt}
The ``usual application'' of
% where
% of applications of
Proposition~\ref{prop:lgv-det} % is applied
contains the additional assumption, that
% Very often, it is assumed
% for the lattice points
% $A=\pas{a_1,\dots,a_r}$ and $E=\pas{e_1,\dots,e_r}$
% the following property that 
for $1\leq i < j \leq r$ and $1\leq k < l \leq r$, {\em any\/} path from
$a_i$ to $e_l$ must intersect {\em any\/} path from $a_j$ to $e_k$. In this case,
there is only one 
% permutation that can ``survive'' the cancellation in
% \eqref{eq:det-expansion}, namely the identity
% permutation, hence there is only one 
summand on the right--hand side of
\eqref{eq:lgt-gen}, namely $\GF{\setnipathof{A}{E}}$, which
corresponds to the identity permutation.
\end{rem}

\subsection{Paths and generating functions in the lattice $\Z_M\times\Z$}
For some (arbitrary, but fixed) integer $M>1$, consider the mapping
\begin{align}
\wexp &: \Z\times\Z\rightarrow\R^3, \notag\\
\wexp\of{m,n}& =\pas{\cos\frac{2\pi m}{M}, \sin\frac{2\pi m}{M}, n}.
	\label{eq:mapcylinder}
\end{align}
Note that the mapping $\wexp$ simply ``wraps'' the lattice $\Z\times\Z$
``around the cylinder''. More precisely,
% Now
view the image $\image\,\wexp$ as a ``cylindric lattice''; i.e., a lattice
with vertex set $\setof{\wexp\of{q}:q\in\Z_M\times\Z}$,
and edges leading from points
\begin{align*}
\edge{\wexp\of{m,n}}{\wexp\of{m+1,n+1}} & \text{ (a ``counter--clockwise'' step),}\\
\edge{\wexp\of{m,n}}{\wexp\of{m-1,n+1}} & \text{ (a ``clockwise'' step).}
\end{align*}
We shall call this cylindric lattice the $M$--cylinder.
(\figref{fig:cyl-lat-path} illustrates this simple concept.)

\begin{figure}
\caption{Illustration  of the $M$--cylinder for $M=12$. The picture shows a
	lattice path $p$ of length $4$ and weight $x$,
	starting in $\pas{0,0}$ and ending in $\pas{2,4}$.}
\label{fig:cyl-lat-path}
\centerline{\epsfxsize6cm\epsffile{cyl-path.eps}}
\end{figure}



% \begin{figure}
% \caption{Illustration of the $M$--cylinder for $M=12$.}
% \label{fig:cyl-lat}
% \centerline{\epsfxsize6cm\epsffile{cylinder.eps}}
% \end{figure}

Clearly, a lattice path $p$ in the $M$--cylinder can be viewed as the 
image of an ``ordinary'' lattice path in $\Z\times\Z$ under the mapping $\wexp$.
Each path $p$ in the $M$--cylinder inherits the weight from a corresponding
path in $\Z\times\Z$, i.e., if $p=\wexp\of{\hat{p}}$, we set
$w\of p \defeq w\of{\hat{p}}$. (Note that this
is well--defined.)

A lattice path may ``wind
around the cylinder several times'', in either positive or negative direction,
before reaching its end point:
The preimage
$\wexp^{-1}\of{\setpathof{a}{e}}$ of the set of
lattice paths in the $M$--cylinder,
which start at $\pas{a,0}$
and end in $\pas{e,N}$, consists of
lattice paths in $\Z\times\Z$, which start at $\pas{a+k\cdot M,0}$
and end in $\pas{e+\pas{k+o}\cdot M,N}$ for $k,o\in\Z$, i.e.,
\begin{equation*}
\wexp^{-1}\of{\setpathof{a}{e}} =
\bigcup_{o\in\Z}\pas{
	\bigcup_{k\in\Z}\hatsetpathof{a+k\cdot M}{e+\pas{k+o}\cdot M}
}.
\end{equation*}
% and some fixed $o\in\Z$.
We shall call the number $o$ the
{\em offset of the
endpoint\/} of the path $p$. (See \figref{fig:int-paths} for this
concept.)

% In an obvious
% sense, $o$ may be interpreted as
% ``winding number'' of the path $p$ around the $M$--cylinder.

% Note that a lattice path may ``wind
% around the cylinder several times'', in either positive or negative
% direction, before reaching its end point.

\begin{figure}
\caption{Illustration of intersecting lattice paths on the $M$--cylinder for $M=12$. The right picture shows representatives
of the preimages of these paths (drawn with thick lines)
in the lattice
$\Z\times\Z$ under the mapping defined in \eqref{eq:mapcylinder}.
The whole
preimage consists of an infinite family of horizontally
translated paths, indicated by % light
thin lines in the picture.}
\label{fig:int-paths}
\centerline{\epsfxsize13cm\epsffile{intersecting-paths.eps}}
\end{figure}

In the following, we shall restrict ourselves to lattice paths starting
at $\pas{a,0}$ and ending at $\pas{e,N}$, where $N$ is some (arbitrary
but fixed) integer. Note that in $\Z\times\Z$, a lattice path
starting at $\pas{a,0}$ and ending at $\pas{e,N}$ exists
if and only if
\begin{equation}
N-2k=e-a
\label{eq:condplain}
\end{equation}
for some $k\in\Z$ with $0\leq k\leq N$ (here, $k$ denotes the number of steps to the left).
For lattice paths in the $M$--cylinder, this condition is changed to
\begin{equation}
N-2k=\pas{e+o\cdot M}-a
\label{eq:condcylinder}
\end{equation}
for arbitrary $o\in\Z$ and some $k\in\Z$  with $0\leq k\leq N$
(here, $o$ denotes the {\em offset\/} of the
endpoint, and $k$ denotes the number of clockwise steps).
% \begin{equation}
% \modeq{N-e+a}{2k}{M}\text{ for some $k\in\Z$  with $0\leq2k\leq N$.}
% \label{eq:condcylinder}
% \end{equation}
 
So it is easy to see that
the generating function $q\of{M,N,a,e}$ of all lattice paths
in the $M$--cylinder, which start at $\pas{a,0}$ and end in
$\pas{e,N}$, is given by
\begin{equation}
\label{eq:gf_qx}
q\of{M,N,a,e;\;x}
=
\sum_{\shortstack{
	$\scriptstyle o\in\Z$\\
	$\scriptstyle \modeq{N-e-o\cdot M+a}{0}{2}$
	}
} \binom{N}{\frac{N-e-o\cdot M+a}{2}}x^{\frac{N-e-o\cdot M+a}{2}}.
\end{equation}
% \begin{equation}
% q\of{M,N,a,e;\;x}
% =
% \sum_{k\in I\of{M,N,a,e}}
% 	\binom{N}{k}x^k,
% \end{equation}
% where the set $I\of{M,N,a,e}$ of summation indices is given as
% \begin{equation}
% I\of{M,N,a,e}=\setof{k\in\Z:\;0\leq k\leq N/2,\;\modeq{N-e+a}{2k}{M}}.
% \label{eq:IMNae}
% \end{equation}
Forrester gave an equivalent expression (see
\cite[equation 2.11 and 2.12]{forrester:vicious-walkers}) for \eqref{eq:gf_qx}, which is more elegant insofar as it ``conceals'' the
clumsy definition of the range of  summation in \eqref{eq:gf_qx}:
% index
% set of $q\of{M,N,a,e;\;x}$:
\begin{align}
\label{eq:gf_qx-forrester}
q\of{M,N,a,e;\;x}
&=
\frac{1}{M}
\sum_{l=0}^{M-1}
	\e^{\frac{-2\pi\i\pas{e-a}l}{M}}
		\pas{x\e^{\frac{-2\pi\i l}{M}}+\e^{\frac{2\pi\i l}{M}}}^N
\\ 
& =
\sum_{k=0}^N \binom{N}{k}x^k
	\frac{1}{M}
	\sum_{l=0}^{M-1} \pas{\e^{\frac{2\pi\i}{M}\pas{N-2k-e+a}}}^l, \notag
\end{align}
where $\i$ denotes the imaginary unit.
\eqref{eq:gf_qx-forrester} is equal to \eqref{eq:gf_qx}, since
we have
\begin{equation}
\label{eq:unit-roots-powersum}
\sum_{l=0}^{M-1} \pas{\e^{\frac{2\pi\i}{M} m}}^l =
\begin{cases}
	M &\text{ if } m\equiv 0\modulo{M}, \\
	0 &\text{ else.}
\end{cases}
\end{equation}
% (We shall make use of this ``root--of--unity--trick'' several
% times in the subsequent computations.)
% Two lattice paths $p$ and $q$ in the $M$--cylinder are called {\em
% intersecting\/} if they have a lattice point in common.
% A family of lattice paths is called {\em nonintersecting\/}, if no two of its
% members are intersecting.

\section{Results and Proofs}
\label{results}

It is an obvious observation that the \lgt\ method for nonintersecting paths in a directed graph, as described in
Proposition~\ref{prop:lgv-det}, applies to the $M$--cylinder.
However, unlike the ``usual case'' outlined
in Remark~\ref{rem:lgt}, % The main difference is, that
% after cancellation of terms due to the \lgt\ involution,
there appear terms corresponding to {\em other\/} permutations
than the identity permutation; which turn out to be
{\em cyclic\/} permutations.
These permutations may
have {\em negative sign\/} if the number of paths, $r$, is even.
% So, unlike the
% ``usual'' \lgt\ framework in $\Z\times\Z$, we
% have
% But it is easy to account for these signs:
So if we are given starting points
$\pas{\pas{a_1,0},\dots\pas{a_r,0}}$ and end points $\pas{\pas{e_1,N},\dots\pas{e_r,N}}$,
% (note that we do not make any assumption
% about the original ordering of these points!),
we define the {\em signed weight\/} of a family $\fpath=\pas{P_1,\dots,P_r}$
of lattice paths, where $P_i$ starts in $\pas{a_i,0}$ and ends
in $\pas{e_{\pi\of i},N}$ for some permutation $\pi\in\SG_r$, as
\begin{equation}
w\of{\pi,\fpath} = \sgn\pi\prod_{j=1}^r w\of{P_j}.
\label{eq:signed-weights2}
\end{equation}
%(compare this definition with \eqref{eq:signed-weights}).

\subsection{A simple generalization of Forrester's formula}
Given this ``signed weight'' for families of nonintersecting lattice paths,
we may derive immediately the following generalization of Forrester's formula.
\begin{thm}
\label{thm:main}
The generating function {\em with signed weights\/} (according to
\eqref{eq:signed-weights2})
of all $r$--tuples of non--intersecting lattice
paths in the $M$--cylinder, starting at the points
$$\pas{\pas{a_1,0},\dots\pas{a_r,0}}$$
and ending in any permutation of the points
$$\pas{\pas{e_1,N},\dots\pas{e_r,N}},$$
with $0\leq a_1< a_2<\dots<a_r<M$ and $0\leq e_1<e_2 <\dots < e_r<M$,
% where for all $i$, we have $\modeq{N-e_i+a_i}{2k_i}{M}$ for some $k_i\in\Z$,
where for all $1\leq i,j\leq r$ we have $\modeq{N-e_i+a_j}{0}{2}$,
is given by
\begin{equation}
\label{eq:det-gfx}
\det\of{q\of{M,N,a_i,e_j;x}}_{i,j=1}^{r}.
\end{equation}
Moreover, we have the following expansion for the above
determinant:
\begin{equation}
\label{eq:det-gfx-expansion}
\det\of{q\of{M,N,a_i,e_j;x}}_{i,j=1}^{r}=
\sum_{i=0}^{r-1}\sgnof{\mu^i}
	\GF{\setnipathof{A}{E_{\mu^i}}},
\end{equation}
where $\mu$ denotes the permutation mapping $1$ to $2$,
$2$ to $3$, and so on; i.e., $\mu=\pas{1,2,\dots,r}$ in
cycle notation.
\end{thm}


\begin{proof}
The assertion of \eqref{eq:det-gfx} is an immediate consequence
of Proposition~\ref{prop:lgv-det}.

% Following the remarks preceding the theorem, it is clear that terms
% corresponding to intersecting $r$--tuples cancel properly due to the
% \lgt\ involution.
% \begin{rem}
% Note that nonintersecting $r$--tuples in the expansion of
% \eqref{eq:det-gfx}
% can never be affected by any cancellation, due to the
% following facts:
% So we have
% to check that cancellation %``does not go too far''.
% does not affect nonintersecting $r$--tuples. But this is guaranteed 
% by two facts:
% \begin{enumerate}
% \item If some $r$--tuple of lattice paths
% 	$\pas{p_1,\dots,p_r}$, where
% 	$p_i$ starts in $a_i$ and ends in $e_{\pi\of i}$, is
% 	nonintersecting, then
% 	$\pi$ must be a {\em cyclic\/} permutation,
% \item The absolute value of the weights (i.e., the
% 	{\em unsigned\/} weights)
% 	of $r$--tuples of
% 	nonintersecting lattice paths corresponding to
% 	{\em different\/} cyclic
% 	permutations can never be the same.
% \end{enumerate}
% Therefore, nonintersecting $r$--tuples do not cancel.

For the assertion of \eqref{eq:det-gfx-expansion},
consider the {\em preimage\/} of any nonintersecting
$r$--tuple of lattice paths with respect to $\wexp$: It appears as a periodic
configuration of {\em infinitely many\/} nonintersecting lattice paths in
$\Z\times\Z$, such that each point $\pas{a_i+s\cdot M,0}$ and each point
$\pas{e_i+s\cdot M,N}$ (for $i=1,\dots,r$ and $s\in\Z$) appears as starting
point and as end point, respectively, of some path (see \figref{fig:preimage}
for an illustration).

\begin{figure}
\caption{Illustration of the {\em preimage\/}
with respect to $\wexp$ (right picture)
of a nonintersecting
pair of lattice paths in the $6$--cylinder (left picture).}
\label{fig:preimage}
\centerline{\epsfxsize16cm\epsffile{preimage.eps}}
\end{figure}

It is obvious that
such a configuration can only correspond to some ``shift of the endpoints'' in the following sense: Consider the ``canonical'' starting points $\pas{a_i,0}$, and
label the ``canonical'' endpoints $\pas{e_i,N}$ with the numbers $1,2,\dots,r$.
Label the other possible endpoints
from left to right with the integers in a consistent way (i.e., $\pas{e_r-M,N}$ gets label
0, $\pas{e_{r-1}-M,N}$ gets label $-1$; $\pas{e_1+M,N}$ gets label
$r+1$, and so on). Then for any nonintersecting $r$--tuple of lattice paths there
is some fixed integer $p$, such that for $1\leq i\leq r$, the path starting
at $\pas{a_i,0}$ ends in the $(i+p)$--th endpoint in this labeling. This ``shift of the endpoints'' clearly
corresponds to a cyclic permutation $\mu^p$, where $\mu=\pas{1,2,\dots,r}$.
\end{proof}

% For the second assertion, note that a shift of the endpoints
% ``by one notch'' clearly amounts to a change in ``absolute''
% weight. (For
% example, for even $M$ a ``right--shift'' amounts to a change
% in weight
% of $x^{-M/2}$.)
% $$
% x^{-\pas{\pas{e_{p+1}-e_{{p}}}/2+\pas{e_{p+2}-e_{p+1}}/2+
% \dots+\pas{e_{p}+M-e_{p+r-1}}/2}} = x^{-M/2},
% $$
% with respect to the initial set of endpoints $\pas{e_{p+i},N}$
% in the above labeling.
% 
% \end{proof}
% \end{rem}
\begin{rem}
Note that under the assumptions of Theorem~\ref{thm:main}, the
case $M$ odd admits only one possible permutation of endpoints,
namely the identity permutation, since all such permutations
must be of the form $\pas{\mu^r}^{2k}=\id$, 
% because a path starting in $(a_i,0)$ {\em must\/}
% end in a
% point $(e_i+2 k M,N)$ for some $k\in \Z$,
according to condition
\eqref{eq:condcylinder}.

While the following considerations and formulas are valid also for odd $M$,
the most interesting cases occur if we assume
\bit
\item $M\equiv N \equiv 0\pas{2}$,
\item $a_i-a_j\equiv e_i-e_j\equiv 0\pas{2}
	\;\forall 1\leq i,j\leq r$.
\eit
(See also Remark~\ref{rem:evenonly}.)
\end{rem}

The determinantal expression \eqref{eq:det-gfx}
% of Theorem~\ref{thm:main}
was derived
recursively by Forrester only for odd $r$ (see \cite[Theorem 2.1, equation 2.10]{forrester:vicious-walkers}). In \thmref{thm:main}, we easily extended
it to the case of even $r$ (thus answering the respective question
posed in \cite{forrester:vicious-walkers}), just by adopting 
the right ``point of view''
(i.e., the \lgt\ framework with ``signed weights'').

\subsection{A more sophisticated generalization of Forrester's formula}
Note that for odd $r$, all the (cyclic) permutations in
\eqref{eq:det-gfx-expansion}
% the proof of
% Theorem~\ref{thm:main}
have positive sign. 
If $r$ is even, however, also negative terms appear
% ``survive'' cancellation
in the generating
function \eqref{eq:det-gfx}: This is a bit of a
nuisance, for we cannot simply set $x\equiv1$ in order
to obtain an {\em enumeration formula\/}.

An easy way out of this
difficulty is to modify the definition of the weight of a single path $p$,
so that
its ``offset of endpoint'', $o$, is taken into account via a multiplicative
factor of $y^o$, i.e.,% (by abuse of notation)
we replace definition
\eqref{eq:unsigned-weights} by
\begin{equation}
\label{eq:y-weights}
w_y\of p = y^o\prod_{i=1}^N w\of{e_i}.
\end{equation}
This amounts to the following
% in the the  {\em signed\/} weights to {\em single\/}
% lattice paths according
% to their ``offset of endpoint''. This is most easily achieved by a little
modification of \eqref{eq:gf_qx}:
\begin{equation}
\label{eq:gf_qxy}
q\of{M,N,a,e;\;x,y}
=%\\
\sum_{\shortstack{
	$\scriptstyle o\in\Z$\\
	$\scriptstyle \modeq{N-e-o\cdot M+a}{0}{2}$
	}
} \binom{N}{\frac{N-e-o\cdot M+a}{2}}y^o\cdot x^{\frac{N-e-o\cdot M+a}{2}}.
\end{equation}
%  when considering an even number of non--intersecting
% lattice paths. Note that we may rewrite the set $I\of{M,N,a,e}$ in
%  \eqref{eq:IMNae}
% equivalently as
% $$
% I\of{M,N,a,e} = \begin{cases}
% 	\frac{N-e+a}{2} + \frac{M}{2}\cdot\Z &
% 		\text{ for }\modeq{M\equiv N-e+a}{0}{2}, \\
% 	\emptyset &
% 		\text{ for }\modeq{M\not\equiv N-e+a}{1}{2}, \\
% 	\frac{N-e+a}{2} + M\cdot\Z &
% 		\text{ for }\modeq{M\not\equiv N-e+a}{0}{2}, \\
% 	\frac{N-e+a-M}{2} + M\cdot\Z &
% 		\text{ for }\modeq{M\equiv N-e+a}{1}{2};
% \end{cases}
% $$
% where notation $k+m\cdot\Z$ means $\setof{n:\;n=k+w\cdot m \text{ for }
% w\in\Z}$. This simple change to a complicated notation yields a slightly
% generalized definition of the weight of a single lattice paths, which
% also takes into account the ``winding number'': 
% $$
% w\of p = y^w \prod_{i=1}^N w\of{e_i}.
% $$
% Thus we obtain a slightly generalized generating function
% \begin{multline}
% \label{eq:gf_qxy}
% q\of{M,N,a,e;\;x,y} =\\
% \begin{cases}
% 	\sum_{k=\frac{N-e+a}{2} + r\cdot\frac{M}{2},\;r\in \Z}
% 		\binom{N}{k} x^{k}y^r &
% 		\text{ for }\modeq{M\equiv N-e+a}{0}{2}, \\
% 	0 &
% 		\text{ for }\modeq{M\not\equiv N-e+a}{1}{2}, \\
% 	\sum_{k=\frac{N-e+a}{2} + r\cdot M,\;r\in \Z}
% 		\binom{N}{k} x^{k}y^r &
% 		\text{ for }\modeq{M\not\equiv N-e+a}{0}{2}, \\
% 	\sum_{k=\frac{N-e+a-M}{2} + r\cdot M,\;r\in \Z}
% 		\binom{N}{k}x^{k}y^r &
% 		\text{ for }\modeq{M\equiv N-e+a}{1}{2}.
% \end{cases}
% \end{multline}
Now, the proof of Theorem~\ref{thm:main} (with slight and obvious
modifications) immediately yields the following Lemma:
\begin{lem}
\label{lem:main}
The generating function {\em with weights according to \eqref{eq:y-weights}\/}
of all $r$--tuples of non--intersecting lattice
paths in the $M$--cylinder, starting at the points
$$\pas{\pas{a_1,0},\dots\pas{a_r,0}}$$
and ending in some permutation of the points
$$\pas{\pas{e_1,N},\dots\pas{e_r,N}},$$
with $0\leq a_1< a_2<\dots<a_r<M$ and $0\leq e_1<e_2 <\dots < e_r<M$,
% where for all $i$, we have $\modeq{N-e_i+a_i}{2k_i}{M}$ for some $k_i\in\Z$,
where for all $1\leq i,j\leq r$ we have $\modeq{N-e_i+a_j}{0}{2}$,
is given by
\begin{equation}
\label{eq:det-gfxy}
\det\of{q\of{M,N,a_i,e_j;\;x,y}}_{i,j=1}^{r}.
\end{equation}
\end{lem}
A simple argument now leads to the desired formula without unwanted negative
signs:
\begin{thm}
\label{thm:main2}
The generating function {\em with unsigned weights\/} (i.e., according to \eqref{eq:unsigned-weights})
of all $r$--tuples of non--intersecting lattice
paths in the $M$--cylinder, starting at the points
$$\pas{\pas{a_1,0},\dots\pas{a_r,0}}$$
and ending in some permutation of the points
$$\pas{\pas{e_1,N},\dots\pas{e_r,N}},$$
with $0\leq a_1< a_2<\dots<a_r<M$ and $0\leq e_1<e_2 <\dots < e_r<M$,
% where for all $i$, we have $\modeq{N-e_i+a_i}{2k_i}{M}$ for some $k_i\in\Z$,
where for all $1\leq i,j\leq r$ we have $\modeq{N-e_i+a_j}{0}{2}$,
is given by
\begin{equation}
\label{eq:det-gfx-unsigned}
\det\of{q\of{M,N,a_i,e_j;\;x,\pas{-1}^{r-1}}}_{i,j=1}^{r}.
\end{equation}
\end{thm}
\begin{proof}
For odd $r$, we clearly have
$$
q\of{M,N,a,e;\;x,1} = q\of{M,N,a,e;\;x},
$$
whence \eqref{eq:det-gfx-unsigned} simply amounts to the assertion of
Theorem~\ref{thm:main}.

For even $r$, observe that (due to \eqref{eq:det-gfx-expansion})
the sign of the summands in
\eqref{eq:det-gfxy}
equals $\pas{-1}^{n}$, where $n$ is the number of paths with {\em odd\/}
offset of endpoint in the corresponding $r$--tuple of paths. So setting
$y=-1$ in \eqref{eq:det-gfxy} properly cancels all the negative signs.
\end{proof}

\subsection{Enumeration formulas involving trigonometric functions}
It is possible to rewrite the generating function
$q\of{M,N,a,e;x,y}$
% of Theorem~\ref{thm:main2}
in a way similar to \eqref{eq:gf_qx-forrester}.
% Since for most purposes, the only interesting case is $M$ even, we restate the
% assertions for this case only.

\begin{cor}
\label{cor:main}
For $M>0$, we have:
\begin{equation}
\label{eq:cor4}
q\of{M,N,a,e;x,y}
= %\\
\frac{y^{\frac{a-e}{M}}}{M}
\sum_{l=0}^{M-1}
	\e^{\frac{-2\pi\i\pas{e-a}l}{M}}
		\pas{
			x y^{-\frac{1}{M}}\e^{\frac{-2\pi\i l}{M}}+
			y^{\frac{1}{M}}\e^{\frac{2\pi\i l}{M}}
		}^N.
\end{equation}
Moreover, the generating function \eqref{eq:det-gfx-unsigned} of
Theorem~\ref{thm:main2} is equivalently given by
\begin{equation}
\label{eq:det-gfxr}
M^{-r}
\det\Biggl(
	\e^{\frac{\pas{r-1}\pi\i\pas{a_i-e_j}}{M}}%\\\times
	\sum_{l=0}^{M-1}
		\e^{\frac{-2\pi\i\pas{e_j-a_i}l}{M}}
			\pas{
				x\e^{\frac{-2\pi\i\pas{l+\frac{r-1}{2}}}{M}}+
				\e^{\frac{2\pi\i\pas{l+\frac{r-1}{2}}}{M}}
			}^N
\Biggr)_{i,j=1}^{r}.
\end{equation}
\end{cor}
\begin{proof}
Equation \eqref{eq:cor4} follows from the same type of computation as in
\eqref{eq:gf_qx-forrester}.
% , \eqref{eq:unit-roots-powersum}
% yields \eqref{eq:cor4}.
\begin{align*}
&\phantom{=}
\frac{y^{\frac{a-e}{M}}}{M}
\sum_{l=0}^{M-1}
	\e^{\frac{-2\pi\i\pas{e-a}l}{M}}
		\pas{
			x y^{\frac{-1}{M}}\e^{\frac{-2\pi\i l}{M}}+
			y^{\frac{1}{M}}\e^{\frac{2\pi\i l}{M}}}^N
  \\
  &=
\frac{y^{\frac{a-e}{M}}}{M}
\sum_{l=0}^{M-1}
	\e^{\frac{-2\pi\i\pas{e-a}l}{M}}
	\sum_{k=0}^N\binom{N}{k}
		x^k y^{\frac{N-2k}{M}}\e^{\frac{2\pi\i}{M}\pas{N-2k}l}
  \\
  &=
\sum_{k=0}^{N}\binom{N}{k}x^k y^{\frac{N-e+a-2k}{M}}
	\frac{1}{M}
	\sum_{l=0}^{M-1}\e^{\frac{2\pi\i}{M}\pas{N-e+a-2k}l}.
\end{align*}
Use \eqref{eq:unit-roots-powersum} to see that
\eqref{eq:cor4}
equals \eqref{eq:gf_qxy} (set 
$k=\frac{N-e+a-o\cdot M}{2}$, or, equivalently, 
$o=\frac{N-e+a-2k}{M}$).
Now set $y=\pas{-1}^{r-1}=\e^{\pas{r-1}\pi\i}$ in \eqref{eq:cor4}, and insert the result into
\eqref{eq:det-gfx-unsigned}: This immediately yields
\eqref{eq:det-gfxr}.
\end{proof}

If the starting points $a_i$ % in Corollary~\ref{cor:main}
are {\em equidistant\/},
we can simplify the corresponding expressions
even
further by a little trick, extending the computation carried
out by Forrester
\cite[equation (3.2)]{forrester:vicious-walkers} to the
case of even $r$:
\begin{cor}
\label{cor:eq-start}
Consider the case of equidistant starting points, i.e., let
$a_i=\pas{i-1}\cdot\nu$ and 
$M=r\cdot\nu$
in\eqref{eq:det-gfxy} for some fixed $\nu\in\N$. In this case,
the generating function \eqref{eq:det-gfx-unsigned} of
Theorem~\ref{thm:main2} is given by
\begin{multline}
\label{eq:eqdiststart-even}
\i^{-\frac{(r)(r-1)}{2}}\pas{\nu\sqrt{r}}^{-r}\\\times
\det\of{\sum_{a=0}^{\nu-1}
		\e^{\frac{\pi\i\pas{N-e_{j+1}\pas{2\pas{i+a r}+1}}}{r\nu}}
			\pas{
				x\e^{\frac{-2\pi\i\pas{i+a r+1}}{r\nu}}+
				\e^{\frac{2\pi\i\pas{i+a r}}{r\nu}}
			}^N}_{i,j=0}^{r-1}
\end{multline}
if $r$ is even, and by
\begin{equation}
\label{eq:eqdiststart-odd}
\i^{-\frac{(r+2)(r-1)}{2}}\pas{\nu\sqrt{r}}^{-r}
\det\of{\sum_{a=0}^{\nu-1}
		\e^{\frac{\pi\i\pas{-e_{j+1}\pas{2\pas{i+a r}}}}{r\nu}}
			\pas{
				x\e^{\frac{-2\pi\i\pas{i+a r}}{r\nu}}+
				\e^{\frac{2\pi\i\pas{i+a r}}{r\nu}}
			}^N}_{i,j=0}^{r-1}
\end{equation}
if $r$ is odd. (Note that --- as a matter of convenience ---
row and column indices range
from $0$ to $\pas{r-1}$ here.)
\end{cor}
\begin{proof}
Note that
$\brkof{
		\pas{\e^{-\frac{2\pi\i}{r}i}}^j
		r^{-1/2}
}_{i,j=0}^{r-1}$
% and
% $\brkof{
% % 	\frac{
% 		\pas{\e^{-\frac{2\pi}{r}\pas{i+1/2}}}^j
% 	}{
% 		\sqrt{r}
% 	}
% }_{i,j=0}^{r-1}$
is a unitary matrix. This fact, together with the well--known
formula for Vandermonde determinants, yields the determinant
evaluations
\begin{equation}
\label{eq:some-determinants}
\det\of{\e^{-\frac{2\pi\i}{r}i\cdot j}}_{i,j=0}^{r-1}=
	r^{\frac{r}{2}}\i^{\frac{(r+2)(r-1)}{2}},
\text{ and }
\det\of{\e^{-\frac{2\pi\i}{r}\pas{i+1/2}\cdot j}}_{i,j=0}^{r-1}=
	r^{\frac{r}{2}}\i^{\frac{(r)(r-1)}{2}}.
\end{equation}
The assertions follow by a simple computation, which we shall
show for even $r$ only (the case $r$ odd being completely analogous; see Forrester
\cite[equation (3.2)]{forrester:vicious-walkers}).
Set $y=\pas{-1}=\e^{\pi\i}$ in \eqref{eq:cor4} and insert in
\eqref{eq:det-gfx-unsigned}.
Now multiply this with the second determinant
from \eqref{eq:some-determinants};
i.e., consider the determinant of the product of the
$r\times r$--matrices
$$
\brkof{\e^{-\frac{2\pi\i}{r}\pas{k+1/2}\cdot m}}
\times
\brkof{
\frac{\e^{\pi\i\frac{N-e_{j+1}+i\nu}{r\nu}}}{r\nu}
\sum_{l=0}^{r\nu-1}
	\e^{\frac{-2\pi\i\pas{e_{j+1}-i\nu}l}{r\nu}}
		\pas{x \e^{\frac{-2\pi\i \pas{l+1}}{r\nu}}+\e^{\frac{2\pi\i l}{r\nu}}}^N
},
$$
where the row and column indices $i$ and $j$ range from
$0$ to $(r-1)$.
The $(i,j)$--entry of this matrix product is given by
\begin{align*}
a_{i,j}&=
\sum_{n=0}^{r-1}\pas{
	\e^{-\frac{2\pi\i}{r}\pas{i+1/2} n}
	\frac{\e^{\pi\i\frac{N-e_{j+1}+n\nu}{r\nu}}}{r\nu}
	\sum_{l=0}^{r\nu-1}
	\e^{\frac{-2\pi\i\pas{e_{j+1}-n\nu}l}{r\nu}}
		\pas{x \e^{\frac{-2\pi\i \pas{l+1}}{r\nu}}+
			\e^{\frac{2\pi\i l}{r\nu}}}^N
}\\
&=
\frac{1}{r\nu}
\sum_{l=0}^{r\nu-1}
	\pas{x \e^{\frac{-2\pi\i \pas{l+1}}{r\nu}}+
		\e^{\frac{2\pi\i l}{r\nu}}}^N
	\e^{\frac{\pi\i}{r\nu}
		\pas{N-e_{j+1}\pas{2l+1}}
	}
	% inner sum
	\sum_{n=0}^{r-1}
		\e^{-\frac{2\pi\i}{r}\pas{i-l} n}\\
&=
% \frac{1}{\nu}
% \sum_{a=0}^{\nu-1}
% 	\pas{x \e^{\frac{-2\pi\i \pas{i+a r+1}}{r\nu}}+
% 		\e^{\frac{2\pi\i \pas{i+a r}}{r\nu}}}^N
% 	\e^{\frac{\pi\i}{r\nu}
% 		\pas{N-e_{j+1}\pas{2\pas{i+a r}+1}}
% 	}\\
% &=
\frac{1}{\nu}
\sum_{a=0}^{\nu-1}
	\pas{x \e^{\frac{-2\pi\i \pas{i+a r+1}}{r\nu}}+
		\e^{\frac{2\pi\i \pas{i+a r}}{r\nu}}}^N
	\e^{\frac{\pi\i}{r\nu}
		\pas{N-e_{j+1}\pas{2\pas{i+a r}+1}},
	}
\end{align*}
which immediately gives \eqref{eq:eqdiststart-even}. (The proof of
\eqref{eq:eqdiststart-odd} involves multiplication with
the first determinant from \eqref{eq:some-determinants}.)
\end{proof}

\section{Applications}
\label{applics}
\subsection{An enumeration formula for a special case}
Of particular interest is the enumeration formula for the case
$M = r\nu$ with equidistant starting points and end points, $a_i=e_i=\pas{i-1}\nu$:
This simply amounts to setting $M = r\nu$, $a_i=e_i=\pas{i-1}\nu$
and $x=1$ in \eqref{eq:det-gfx-unsigned}.
Since we have the obvious relations
\begin{equation}
\label{eq:qsym}
q\of{M,N,a,e;x,y}=x^N q\of{M,N,e,a;1/x,1/y}
\end{equation}
and
\begin{equation}
\label{eq:qtrans}
q\of{r \nu,N,i \nu,j \nu;x,y} =
	y\cdot q\of{r \nu,N,i \nu,(j+r) \nu;x,y},
\end{equation}
we may concentrate on the numbers
$$
	a_d\defeq q\of{r \nu,N,0,d \nu;1,\pas{-1}^{r-1}}
	\text{ for } d=0,\dots,r-1.
$$
So for odd $r$, % by \eqref{eq:qsym} and \eqref{eq:qtrans},
we obtain a circulant matrix, the determinant of
which we can easily
evaluate by the well--known formula
(cf.~\cite[\S51, p.~131]{aitken:det}):
\begin{equation}
\label{eq:circulant}
% \det\of{q\of{M,N,a_i,e_j;\;1,\pas{-1}^{r-1}}}_{i,j=1}^{r}
% =
\det
\begin{pmatrix}
a_0     & a_1    & \dots & a_{r-2} & a_{r-1} \\
a_{r-1} & a_0    & \dots & a_{r-3} & a_{r-2} \\
\vdots  & \vdots &       & \vdots  & \vdots \\
a_1     & a_2    & \dots & a_{r-1} & a_0
\end{pmatrix}
=\prod_{m=0}^{r-1}
	\pas{\sum_{k=0}^{r-1}\pas{\e^{\frac{2m\pi\i}{r}}}^k a_k}.
\end{equation}
% which evaluates to
% \begin{equation}
% \prod_{m=0}^{r-1}\sum_{k=0}^{r-1}\e^{\frac{2\pi\i m k}{r}} a_k,
% \end{equation}
% by a well--known formula (cf.~\cite[\S51, p.~131]{aitken:det}),
% 
% Setting $y=\pas{-1}^{r-1}$ in \eqref{eq:cor4} again, we see
% that
For even $r$, however, we obtain
% But we need also the following determinant evaluation of
a ``skew--symmetric'' circulant matrix (due to 
\eqref{eq:qtrans}), the determinant of
which we can evaluate in much
the same way as \eqref{eq:circulant}. Since this evaluation
appears to be not so well--known, we state and prove it in the
following lemma:
\begin{lem}
\label{lem:skew-circulant}
For arbitrary variables $a_0\dots a_{r-1}$, we have
\begin{equation}
\label{eq:skew-circulant}
% \det\of{q\of{M,N,a_i,e_j;\;1,\pas{-1}^{r-1}}}_{i,j=1}^{r}
% =
\det
\begin{pmatrix}
a_0     & a_1    & \dots & a_{r-2} & a_{r-1} \\
-a_{r-1} & a_0    & \dots & a_{r-3} & a_{r-2} \\
\vdots  & \vdots &       & \vdots  & \vdots \\
-a_1     & -a_2    & \dots & -a_{r-1} & a_0
\end{pmatrix}
=\prod_{m=0}^{r-1}
	\pas{\sum_{k=0}^{r-1}\pas{\e^{\frac{(2 m+1)\pi\i}{r}}}^k a_k}.
\end{equation}
\end{lem}
\begin{proof}
Set $\omega_m\defeq\e^{\frac{\pas{2m+1}\pi\i}{r}}$ and consider
the $r$ vectors
$\vec\omega_m\defeq\pas{\omega_m^0,\omega_m^1,
	\dots,\omega_m^{r-1}}$ for $m=0,\dots,r-1$.
Note that
$\omega_m^r=-1$ and compute the $i$--th component
in the product $A\cdot\vec\omega_m$ (where $A$, of course,
denotes the
matrix in \eqref{eq:skew-circulant}):
\begin{align*}
\pas{A\cdot\vec\omega_m}_i &=
	-a_{r-i}\omega_m^0 -a_{r-i+1}\omega_m^1-\dots
		-a_{r-1}\omega_m^{i-1}+
	a_0\omega_m^{i}+a_1\omega_m^{i+1}+\dots
		a_{r-i-1}\omega_m^{r-1}\\
&= a_0\omega_m^{i}+a_1\omega_m^{i+1}+\dots
		a_{r-i-1}\omega_m^{r-1}+
	a_{r-i}\omega_m^r +a_{r-i+1}\omega_m^{r+1}+\dots
		+a_{r-1}\omega_m^{r+i-1}\\
&= \omega_m^{i}\cdot \pas{\sum_{k=0}^{r-1}a_k\omega_m^k}.
\end{align*}
This shows that $\vec\omega_m$ is an eigenvector of $A$
to the eigenvalue $\pas{\sum_{k=0}^{r-1}a_k\omega_m^k}$, which
proves the assertion.
\end{proof}

\begin{cor}
Denote the number
of all $r$--tuples of non--intersecting lattice
paths in the $\pas{r \nu}$--cylinder, starting at the points
$$\pas{\pas{0,0},\dots\pas{\pas{r-1}\nu,0}}$$
and ending in any permutation of the points
$$\pas{\pas{0,N},\dots\pas{\pas{r-1}\nu,N}},$$
by  $Z\of{N,r,\nu}$. Then we have the following formulas:
\begin{align}
\label{eq:eqd-odd}
Z\of{N,2r-1,\nu}&=%\\
\pas{\frac{2^{N}}{\nu}}^{\!\!2r-1}
\prod_{m=0}^{2r-2}
   \sum_{l=0}^{\nu-1}
       \cos^{N}\of{
       	2\,\pi
			\pas{
				\frac{m}{\nu\pas{2r-1}}
				+
				\frac{l}{\nu}
			}
        },\\
\label{eq:eqd-even}
Z\of{N,2r,\nu}&=%\\
\pas{\frac{2^{N}}{\nu}}^{\!\!2r}
\prod_{m=0}^{2r-1}
   \sum_{l=0}^{\nu-1}
       \cos^{N}\of{
       	2\,\pi
			\pas{
				\frac{m+1/2}{\nu\pas{2r}}
				+
				\frac{l}{\nu}
			}
        }.
\end{align}
\end{cor}

\begin{proof}
Clearly, \eqref{eq:eqd-odd} will follow by simplifying
\eqref{eq:circulant}, and \eqref{eq:eqd-even} will follow by simplifying \eqref{eq:skew-circulant}. We shall give the
corresponding computation for \eqref{eq:eqd-even} only,
the other case is completely analogous.


Straightforward insertion of
$$
	a_d\defeq q\of{r \nu,N,0,d \nu;1,\e^{\pi \i}}
$$
into
\eqref{eq:skew-circulant} gives the following expression:
\begin{equation}
\prod_{m=0}^{2r-1}
	\sum_{k=0}^{2r-1}
   		\pas{
			\pas{\e^{\frac{\pas{2m+1}\pi\i}{2r}}}^k
			\frac{\e^{\frac{\pas{N-k\nu}\pi\i}{2\nu r}}}{2\nu r}
   			\sum_{l=0}^{2\nu r-1}
				\e^{-\frac{k\nu l\pi\i}{\nu r}}
				\pas{
					\e^{-\frac{\pas{l+1}\pi\i}{\nu r}}
					+
					\e^{\frac{l\pi\i}{\nu r}}
				}^N
   		}.
\end{equation}
Now write
$$
\pas{
\e^{-\frac{\pas{l+1}\pi\i}{\nu r}}
+
\e^{\frac{l\pi\i}{\nu r}}
} =
\e^{-\frac{\pi\i}{2\nu r}}2\cos\of{\frac{\pas{l+1/2}\pi}{\nu r}},
$$
pull out appropriate factors, simplify, and interchange
summation; in order to obtain
\begin{equation*}
\pas{\frac{2^{N-1}}{\nu r}}^{2r}
\prod_{m=0}^{2r-1}
	\sum_{l=0}^{2\nu r-1}
		\cos^N\of{\frac{\pas{l+1/2}\pi}{\nu r}}
		\sum_{k=0}^{2r-1}\pas{\e^{\frac{2\pas{m-l}\pi\i}{2r}}}^k.
\end{equation*}
Observe that \eqref{eq:unit-roots-powersum} applies
to the innermost sum,
whence \eqref{eq:eqd-even} follows.  
\end{proof}

\begin{rem}
Equation \eqref{eq:eqd-odd} is basically the same as
Forrester's formula \cite[(2.28)]{forrester:vicious-walkers}.
\end{rem}

\subsection{Free energy}
In his paper, Forrester
considers the dimensionless {\em free energy per unit length\/}
on
a strip--shaped lattice of infinite width and height $N$
(see \cite[(2.30)]{forrester:vicious-walkers}):
% , a physical quantity defined as 
\begin{equation}
\label{eq:free-energy}
f_N\of\nu=-\lim_{r\to\infty}\frac{1}{\nu r}\log\of{Z\of{N,r,\nu}}.
\end{equation}
We can apply his considerations now also to the case of
even $r$. According to \eqref{eq:eqd-odd} and \eqref{eq:eqd-even},
respectively, we have
\begin{multline}
-\frac{1}{r\nu}\log\of{Z\of{N,r,\nu}} = \\
-\frac{1}{r\nu}
\Biggl(
	r\pas{N \log 2 - \log \nu}%\\
	+\sum_{m=0}^{r-1}\log\of{
		\sum_{l=0}^{\nu-1}
			\cos^N\of{2\pi\frac{l+\frac{m+\epsilon\of r}{r}}{\nu}}
	}
\Biggr),
\end{multline}
where $\epsilon\of r=1/2$ if $r$ is even, and $\epsilon\of r=0$
if $r$ is odd. In both cases, observe that we have Riemann sums,
which tend to the same integral in the limit:
\begin{equation}
\label{eq:asym-forrester}
-\frac{1}{\nu}
\Biggl(
	\pas{N \log 2 - \log \nu}%\\
	+\int_{0}^{1}\log\of{
		\sum_{k=0}^{\nu-1}
			\cos^N\of{2\pi\frac{k+t}{\nu}}}d\,t
\Biggr).
\end{equation}
(This corresponds to Forresters formula
\cite[(2.31)]{forrester:vicious-walkers}.)

Now, following Forrester
\cite[Section 2.4]{forrester:vicious-walkers}, we
consider the {\em free energy per lattice site\/} in the
two--dimensional thermodynamic limit, i.e., the quantitity
$F_\nu\defeq\lim_{N\to\infty}\frac{f_N\of\nu}{N}$.
Of course, the basic idea for evaluating this limit is
``Pull out the dominating term from the sum in
\eqref{eq:asym-forrester}''. However, we must be careful in 
determining this dominating term (there seems to be a
small flaw in
Forresters formula \cite[2.33]{forrester:vicious-walkers}
with respect to this):

For even $\nu$, the dominating term is
\bit
\item $\cos\of{\frac{2\pi t}{\nu}}$
	for $0\leq t\leq \frac12$,
\item $\cos\of{\frac{2\pi\pas{t+\nu-1}}{\nu}}=\cos\of{\frac{2\pi\pas{t-1}}{\nu}}$
	for $\frac12\leq t\leq 1$,
\eit
whence we obtain
% Note that for $\nu>4$, the
% term $\cos\of{\frac{2\pi t}{\nu}}$ is strictly positive
% for $t\in\brkof{0,1}$,
% whence we may derive in this case:
\begin{align}
F_\nu & = -\frac{\log 2}{\nu}\notag\\
&-
	%\frac{1}{\nu}
	\lim_{N\to\infty}\frac{1}{\nu N}
	\int_{0}^{\frac12}\log\of{
		\cos\of{\frac{2\pi t}{\nu}}^N\times
		\sum_{k=0}^{\nu-1}
			\pas{
				\frac{
					\cos\of{2\pi\frac{k+t}{\nu}}
				}{
					\cos\of{\frac{2\pi t}{\nu}}
				}
			}^N
	}\d\,t\notag\\
&-
	\lim_{N\to\infty}\frac{1}{\nu N}
	\int_{\frac12}^{1}\log\of{
		\cos\of{\frac{2\pi\pas{t-1}}{\nu}}^N\times
		\sum_{k=0}^{\nu-1}
			\pas{
				\frac{
					\cos\of{2\pi\frac{k+t}{\nu}}
				}{
					\cos\of{\frac{2\pi\pas{t-1}}{\nu}}
				}
			}^N
	}\d\,t\notag\\
&= -\frac{\log 2}{\nu}-
	\int_{-\frac{1}{2\nu}}^{\frac{1}{2\nu}}
		\log\of{
			\cos\of{2\pi t}
		}\d t.\label{eq:asym2-forrester-even}
\end{align}
(Forresters formula \cite[2.33]{forrester:vicious-walkers}
looks almost the same, but the range of integration is stated
as $[0,\frac1\nu]$ instead of $[-\frac1{2\nu},\frac1{2\nu}]$.) 

For odd $\nu$, the dominating term is
\bit
\item $\cos\of{\frac{2\pi t}{\nu}}$
	for $0\leq t\leq \frac14$,
\item $\cos\of{\frac{2\pi\pas{t+\frac{\nu-1}{2}}}{\nu}}=-\cos\of{\frac{2\pi\pas{t-\frac12}}{\nu}}$
	for $\frac14\leq t\leq \frac34$,
\item $\cos\of{\frac{2\pi\pas{t-1}}{\nu}}$
	for $\frac32\leq t\leq 1$,
\eit
whence by the same simple computation as above, we obtain 
\begin{equation}
\label{eq:asym2-forrester-odd}
F_\nu =-\frac{\log 2}{\nu}-
	2\int_{-\frac{1}{4\nu}}^{\frac{1}{4\nu}}
		\log\of{
			\cos\of{2\pi t}
		}\d t.
\end{equation}

\subsection{Gessel and Krattenthaler's formula}
Gessel and Krattentha\-ler \cite{gessel-kratt:cylindric-partitions}
consider nonintersecting paths in the lattice
$\Z\times\Z$, too. However, their lattice paths consist of horizontal and
vertical steps, which essentially is
equivalent to the situation of lattice paths consisting
of diagonal steps in
% the same object as
the even--numbered sublattice
%$2\Z\times2\Z$ with diagonal steps
(see Remark~\ref{rem:evenonly}).
% But this is not a big difference, since the even--numbered
% sublattice (which for most purposes is the only interesting one) of Forrester's
% lattice, shrunk by $\sqrt 2$ and rotated by $\pi/4$, is essentially the same
% object.

More precisely,
they consider lattice paths which are nonintersecting and, in addition,
are also nonintersecting with respect to ``shifted
copies'' of lattice paths; i.e., copies of the original paths which are
translated by a fixed (non--vertical and non--horizontal) shift vector
$\mathbf S$. See \figref{fig:kratt-paths} for an illustration, where
the translation $\mathbf S$ is indicated by a dotted arrow.

\begin{figure}
\caption{Illustration of nonintersecting lattice paths with nonintersecting translate. The shift vector $\mathbf S$ is
indicated by the dotted arrow. }
\label{fig:kratt-paths}
\centerline{\epsfxsize11cm\epsffile{kratt.eps}}
\end{figure}

They give a quite general formula 
\cite[Proposition 1, Equation (3.5)]{gessel-kratt:cylindric-partitions}
for the generating function of such nonintersecting families,
in the form of 
a multi--sum of certain determinants.

A special case of this formula 
\bit
\item with shift vector ${\mathbf S}=\pas{-m,m}$,
\item with a certain choice of edge--weights,
\item and with starting points and end points arranged on
	downward--sloping lines
\eit
basically appears as refinement of our formula \eqref{eq:det-gfxy}, in the sense
that now we are only interested in terms with {\em fixed\/} sum ${\sum o = c}$
of offsets of endpoints. So, this amounts to extracting the coefficient
of $y^{c}$ in the expansion of \eqref{eq:det-gfxy}.
The advantage of our formula \eqref{eq:det-gfxy} is that it consists of a
{\em single\/} determinant. Moreover, it does not appear to be
easy to obtain it
by appropriately summing up
%\cite[Proposition 1, Equation (3.5)]{gessel-kratt:cylindric-partitions}.
Gessel and Krattenthaler's formula.

In any case, the most natural way of understanding \eqref{eq:det-gfxy}
is the {\em direct\/} application of the \lgt\ method.

\subsection*{Acknowledgements}
I thank Christian Krattenthaler for many helpful hints
and discussions.

\begin{thebibliography}{1}

\bibitem{aitken:det}
A.C. Aitken.
\newblock {\em Determinants and Matrices}.
\newblock Oliver and Boyd Ltd., Edinburgh, 1956.

\bibitem{fisher:walks}
M.E. Fisher.
\newblock Walks, walls, wetting and melting.
\newblock {\em J.\ Stat.\ Phys.}, 34:667--729, 1984.

\bibitem{forrester:vicious-walkers}
P.J. Forrester.
\newblock Exact solution of the lock step model of vicious walkers.
\newblock {\em J.\ Phys.\ A: Math.\ Gen.}, 23:1259--1273, 1990.

\bibitem{gessel-kratt:cylindric-partitions}
I.~M. Gessel and C.~Krattenthaler.
\newblock Cylindric partitions.
\newblock {\em Trans.\ Amer.\ Math.\ Soc.}, 349:429--479, 1997.

\bibitem{gessel-viennot:det}
I.~M. Gessel and X.G. Viennot.
\newblock Determinants, paths, and plane partitions.
\newblock preprint, available at
  {\tt http://www.cs.brandeis.edu/\~{}ira/papers/pp.pdf}, 1989.

\bibitem{grabiner:random-walks2003}
David~J.\ Grabiner.
\newblock Random walk in an alcove of an affine {W}eyl group, and
  non--colliding random walks on an interval.
\newblock {\em J.\ Combin.\ Theory Ser.~A}, 97:285--306, 2002.

\bibitem{lindstroem}
B.~Lindstr{\"o}m.
\newblock On the vector representations of induced matroids.
\newblock {\em Bull.\ London Math.\ Soc.}, 5:85--90, 1973.

\end{thebibliography}

\end{document}
