\documentclass[12pt,reqno]{amsbook}
\usepackage{amssymb}
\input sekrl.tex
\input pathlate.sty
\input priv
%\makeindex

\textwidth35pc
\textheight47pc

\begin{document}

??global: left-hand --- right-hand picture $\to$ label Figure~1.a),
b) + description: \newline
a. nonintersecting lattice path,\quad b. CSPP \dots

\chapter{Simple lattice paths in two dimensions} \label{ch1}
In this chapter we consider lattice paths in the plane
integer lattice $\Z^2$ consisting of positive unit steps. Clearly, the
number of all such paths from $(a,b)\to (c,d)$ is
\begin{equation} \label{e1.1}
\v{\L{(a,b)\to (c,d)}}=\binom {c+d-a-b}{c-a},
\end{equation}
since each path from $(a,b)$ to $(c,d)$ can be identified with a
sequence of $(c-a)$ horizontal steps and $(d-b)$ vertical steps, the
number of those sequences being given by the binomial coefficient in
\eqref{e1.1}. 

??Survey of this chapter

\section{Simple paths with boundaries of type $x=y$} \label{s1.1}
Next we want to count paths from $(a,b)$ to $(c,d)$, where $a\ge b$ and
$c\ge d$, which stay below the main diagonal $y=x$. Always, when we
say `below the line $l$' we mean that the lattice paths are allowed to
touch the line $l$. When we want to exclude touches, we shall say
`{\em strictly\/} below the line $l$'. So, what we want to know is the
number $\v{\L{(a,b)\to (c,d)\mid x\ge y}}$. This problem is most
conveniently solved by 
the so-called {\em reflection principle\/}\index{reflection principle} 
introduced
by \index{Andr\'e, D\'esir\'ee??}Andr\'e \cite{AndDAA}.

\begin{Theorem} \label{T1.1}Let $a\ge b$ and $c\ge d$. The number of
all paths from $(a,b)$ to $(c,d)$ staying below the line $y=x$ is
given by
\begin{equation} \label{e1.2}
\v{\L{(a,b)\to (c,d)\mid x\ge y}}=\binom {c+d-a-b} {c-a} -
\binom {c+d-a-b}{c-b+1}. 
\end{equation}
\end{Theorem}

\begin{proof}First we observe that the number in question is the number
of all paths from $(a,b)$ to $(c,d)$ minus the number of those paths
which cross the line $y=x$
\begin{equation} \label{e1.3}
\v{\L{(a,b)\to (c,d)\mid x\ge y}}=\v{\L{(a,b)\to (c,d)}}-
\v{\L{(a,b)\to (c,d)\mid x\not\ge y}}.
\end{equation}
By \eqref{e1.1} we already know $\v{\L{(a,b)\to (c,d)}}$. The
reflection principle shows that paths from $(a,b)$ to $(c,d)$ which
cross $y=x$ are in bijection with paths from $(b-1,a+1)$ to $(c,d)$.
This implies
$$\v{\L{(a,b)\to (c,d)\mid x\not\ge y}}=\v{\L{(b-1,a+1)\to (c,d)}}.$$
Hence, using \eqref{e1.1} again we establish
\eqref{e1.2}.

\begin{Figure} \label{F1.1}
$$
\Gitter(12,10)(-2,-1)
\Koordinatenachsen(12,10)(-2,-1)
\Pfad(1,-1),22221111212222111112\endPfad
\SPfad(-2,2),111122221211112\endSPfad
\Diagonale(-2,-2){12}
\SPfad(-2,-1),33333333333\endSPfad
\DickPunkt(1,-1)
\DickPunkt(-2,2)
\DickPunkt(7,8)
\DickPunkt(11,9)
\Label\ru{(a,b)}(1,-1)
\Label\l{(b-1,a+1)}(-4,2)
\Label\ro{(c,d)}(11,9)
\Label\ro{P}(5,3)
\Label\ro{ y=x}(2,1)
\Label\o{S}(7,8)
\Label\ro{P'}(-1,2)
\Label\u{y=x+1}(-3,0)
\hskip5cm
$$
\end{Figure}

The claimed bijection is obtained as follows. Consider a path $P$ from
$(a,b)$ to $(c,d)$ crossing the line $y=x$. See Figure~\ref{F1.1} for an
example. Then $P$ must meet the line $y=x+1$. Among all the meeting
points of $P$ and $y=x+1$ choose the right-most. Denote this point by
$S$. Now reflect the portion of $P$ from $(a,b)$ to $S$ with respect
to the line
$y=x+1$, leaving the portion from $S$ to $(c,d)$ invariant. Thus we
obtain a new path $P'$ from $(b-1,a+1)$ to $(c,d)$. To construct the
reverse mapping we only have to observe that any path from $(b-1,a+1)$
to $(c,d)$ must meet $y=x+1$ since $(b-1,a+1)$ and $(c,d)$ lie on
different sides of $y=x+1$. Again we choose the right-most meeting
point, denote it by $S$, and reflect the portion from $(b-1,a+1)$ to
$S$ with respect to the line $y=x+1$, thus obtaining a path from $(a,b)$ to $(c,d)$
that meets the line $y=x+1$, or equivalently, crosses the line $y=x$.
\end{proof}

In particular, for $a=b=0$ we obtain

\begin{Corollary} \label{T1.2}
If $c\ge d$ we have
\begin{equation} \label{e1.4}
\v{\L{(0,0)\to (c,d)\mid x\ge y}}=\frac {c+1-d} {c+d+1}\binom {c+d+1}
{d}
\end{equation}
and
\begin{equation} \label{e1.5}
\v{\L{(0,0)\to (n,n)\mid x\ge y}}= \frac {1} {n+1}\binom {2n}{n}.
\end{equation}
\qed
\end{Corollary}
The numbers $\frac {c+1-d} {c+d+1}\binom {c+d+1}{d}$ are called {\em
\index{ballot numbers}ballot numbers\/} 
since they give the answer to the classical ballot
problem\index{ballot problem} of \index{Bertrand, ?.}Bertrand 
\cite{BertAA}. The problem is stated as follows:
In an election
candidate $A$ received $c$ votes and candidate $B$ received $d$
votes;
how many ways of counting the votes are there such that at each stage
during the counting candidate $A$ has at least as many votes as
candidate $B$? Representing a vote for $A$ by a horizontal step and a
vote for $B$ by a vertical step is seen that the number  in
question is the same as the number of lattice paths from $(0,0)$ to
$(c,d)$ staying below $y=x$. This number is given in \eqref{e1.4}.
More about ballot problems appears in Section~\ref{??}.

The numbers $\frac {1} {n+1}\binom {2n}{n}$ are called {\em \index{Catalan
numbers}\index{Catalan, Eug\`ene??}Catalan
numbers\/} \cite{CataAA}. They appear at numerous places (see
\cite{??Alder (64 occurences)...}, \cite[??]{StanBI}). For example,
Catalan numbers count \index{ordered trees}ordered trees 
on $n$ vertices,
\index{parenthizations}parenthizations??
of $n$ elements of a free noncommutative group, \dots??. refer to
$q$-analogues: Hofbauer, F\"urlinger,\dots??

\medskip
Interestingly, an iterated reflection argument will give the number
of paths between two diagonal lines.

\begin{Theorem} \label{T1.3}
Let $a+t\ge b\ge a+s$ and $c+t\ge d\ge c+s$. The number of all paths
from $(a,b)$ to $(c,d)$ staying below the line $y=x+t$ and above the
line $y=x+s$ is given by
\begin{multline} \label{e1.6}
\v{\L{(a,b)\to (c,d)\mid x+t\ge y\ge x+s}}\\
=\sum _{k\in\Z} ^{}\(\binom
{c+d-a-b} {c-a-k(t-s+2)}-\binom {c+d-a-b}{c-b-k(t-s+2)+t+1}\). 
\end{multline}
\end{Theorem}

\begin{proof}The common way to obtain \eqref{e1.6} is to argue by
inclusion-exclusion (see e.g\@. \index{Mohanty, Sri Gopal}Mohanty 
\cite[pp.~6,7]{MohaAE}). 
The number of all paths from $(a,b)$ to $(c,d)$
which do not cross either of the lines $y=x+t$ and $y=x+s$ equals the
number of all paths from $(a,b)$ to $(c,d)$, minus those which cross
$y=x+t$, minus those which cross $y=x+s$, plus those which cross $y=x+t$
and then $y=x+s$, plus those which cross $y=x+s$ and then $y=x+t$, 
and so on. Then, by iterated reflection, one would show that each of these
set of paths crossing our two lines in some particular way is in
bijection with some other set of paths {\em without\/} restrictions. And
these can be easily counted. Once having guessed the result it is more
convenient to give a proof by a {\em cancelling bijection\/}. In fact, this
method works well in many situations and is therefore of particular
importance. Later on, we shall see more of these cancelling bijections.

In view of \eqref{e1.1} we may write the right-hand side of
\eqref{e1.6} as
{\refstepcounter{equation}\label{e1.7}}
\alphaeqn
\begin{align} \label{e1.7a}
&\Big\vert\bigcup _{k\in\Z} ^{}\L{(a+k(t-s+2),
b-k(t-s+2))\to  (c,d)}\Big\vert\\
\label{e1.7b}
&\hskip0cm
-\Big\vert\bigcup _{k\in\Z} ^{}\L{(b-t-1+k(t-s+2),
a+t+1-k(t-s+2))\to  (c,d)}\Big\vert.
\end{align}
\reseteqn
We shall construct a bijection between paths from the set in 
\eqref{e1.7a} that touch $y=x+t+1$ or $y=x+s-1$ and paths from
the set in \eqref{e1.7b} that also touch one of these two lines.
Suppose that this had been done. Then in \eqref{e1.7} all contributions
of paths that touch one of these two lines would cancel. But it is
easily checked that because of our assumptions $a+t\ge b\ge a+s$ and
$c+t\ge d\ge c+s$ all the paths in \eqref{e1.7a} for $k\ne 0$ and all
the paths in \eqref{e1.7b} have to touch one of these two lines. Hence,
the difference \eqref{e1.7}, and thus the right-hand side in
\eqref{e1.6}, counts what remains, i.e\@. all the paths from $(a,b)$ to
$(c,d)$ staying between the lines $y=x+t$ and $y=x+s$, which is the
left-hand side of \eqref{e1.6}.

To construct the bijection, consider a path $P$ in $\L{(a+k(t-s+2),
b-k(t-s+2))\to  (c,d)}$ that touches either $y=x+t+1$ or $y=x+s-1$.
Choose the last meeting point between $P$ and any of these two lines.
Denote this point by $S$. Now reflect the path's initial portion up to
$S$ with respect to the line that $P$ is meeting in $S$. Thus we obtain a new path
$P'$, either from $(b-k(t-s+2)-t-1,a+k(t-s+2)+t+1)$ to $(c,d)$ and
touching $y=x+t+1$, or from $(b-k(t-s+2)-s-1,a+k(t-s+2)+s+1)$ to
$(c,d)$ and touching $y=x+s-1$. In both cases $P'$ belongs to the set
in \eqref{e1.7b}. The reverse mapping clearly is defined in the same
way. 
\end{proof}

The formula in Theorem~\ref{T1.3} is very convenient for computing
the number of paths as long as the parameters are not too large.
On the other hand, it is of no use if one is interested in asymptotic
information, because the summands on the right-hand side of \eqref{e1.6}
alternate in sign so that there is considerable cancellation.
However, with the help of little integral calculus, the formula 
can be transformed into a surprising formula featuring
cosines and sines, from which asymptotic information can be easily
read off.

\begin{Theorem} \label{T1.3a}
Let $a+t\ge b\ge a+s$ and $c+t\ge d\ge c+s$. The number of all paths
from $(a,b)$ to $(c,d)$ staying below the line $y=x+t$ and above the
line $y=x+s$ is given by
\begin{multline} \label{e1.6a}
\v{\L{(a,b)\to (c,d)\mid x+t\ge y\ge x+s}}\\
=\sum _{k=1} ^{\fl{(t-s+1)/2}}\frac {4} {t-s+2}\(2\cos\frac {\pi k}
{t-s+2}\)^{c+d-a-b}\kern3cm\\
\cdot
\sin\(\frac {\pi k(a-b+t+1)} {t-s+2}\)\cdot
\sin\(\frac {\pi k(c-d+t+1)} {t-s+2}\).
\end{multline}
\end{Theorem}
\begin{proof} 
Trivially, the binomial coefficient $\binom nk$ is the
coefficient of $z^{-1}$ in the Laurent series
$$\frac {(1+z)^n} {z^{k+1}}.$$
Thus, the sum \eqref{e1.6} equals the
coefficient of $z^{-1}$ in
\begin{align} \notag
\sum _{k=0} ^{\infty}&\bigg(\frac {(1+z)^{c+d-a-b}\,z^{k(t-s+2)}} 
{z^{c-a+(c+d-a-b)(t-s+2)+1}}-
\frac {(1+z)^{c+d-a-b}\,z^{k(t-s+2)}} {z^{c-b+t+(c+d-a-b)(t-s+2)+2}}\bigg)\\
\notag
&=\frac {(1+z)^{c+d-a-b}} {z^{c-a+(c+d-a-b)(t-s+2)+1}(1-z^{t-s+2})}-
\frac {(1+z)^{c+d-a-b}} {z^{c-b+t+(c+d-a-b)(t-s+2)+2}(1-z^{t-s+2})}\\
&=\frac {(1+z)^{c+d-a-b}\(z^{(-c+d+a-b)/2}-z^{(-c+d-a+b)/2-t-1}\)} 
{z^{(c+d-a-b)/2+(c+d-a-b)(t-s+2)+1}(1-z^{t-s+2})}. \label{eq:coef}
\end{align}
(In the second line we used the formula for the geometric series. It
can be either regarded as a summation in the formal sense, or else
one must assume that $\vert z\vert<1$.)
Equivalently, 
the sum \eqref{e1.6} equals the residuum of the Laurent series
\eqref{eq:coef} at $z=0$. Now consider the contour integral of \eqref{eq:coef}
(with respect to $z$, of course)
along a circle of radius $r$ around the origin. It is a standard fact
that in the limit $r\to\infty$ this integral vanishes, because the
integrand \eqref{eq:coef} is of the order $O(1/z^2)$. Therefore, by
the theorem of residues, the
sum of the residues of \eqref{eq:coef} must be 0, or, equivalently,
the residuum at $z=0$, which we are interested in, equals the negative of
the sum of the other residues. As the other poles of \eqref{eq:coef}
are the $(t-s+2)$-th roots of unity different from 1, we obtain
\begin{multline*} 
-\sum _{k=1} ^{t-s+1}
\frac {\(1+e^{\frac {2\pi ik} {t-s+2}}\)^{c+d-a-b}
\(e^{\frac {\pi ik} {t-s+2}(-c+d+a-b)}-
e^{\frac {\pi ik} {t-s+2}(-c+d-a+b-2t-2)}\)} 
{e^{\frac {2\pi ik} {t-s+2}(\frac
{c+d-a-b} {2}+1)}\(-(t-s+2)e^{\frac {2\pi ik} {t-s+2}(t-s+1)}\)}\\
=\sum _{k=1} ^{t-s+1}\frac {1} {t-s+2}\(2\cos\frac {\pi k}
{t-s+2}\)^{c+d-a-b}
e^{\frac {\pi ik} {t-s+2}(-c+d-t-1)}\\
\cdot \(e^{\frac {\pi ik} {t-s+2}(a-b+t+1)}-
e^{-\frac {\pi ik} {t-s+2}(a-b+t+1)}\)
\end{multline*}
for the sum \eqref{e1.6}.
Now, in the last line, 
we pair the $k$-th and the $(t-s+2-k)$-th summand. Thus, upon little
manipulation, the above sum turns into
\begin{multline*} 
\sum _{k=1} ^{\fl{(t-s+1)/2}}\frac {1} {t-s+2}\(2\cos\frac {\pi k}
{t-s+2}\)^{c+d-a-b}\\
\cdot
\(e^{-\frac {\pi ik} {t-s+2}(c-d+t+1)}-
e^{\frac {\pi ik} {t-s+2}(c-d+t+1)}\) 
{\(e^{\frac {\pi ik} {t-s+2}(a-b+t+1)}-
e^{-\frac {\pi ik} {t-s+2}(a-b+t+1)}\)}.
\end{multline*}
Clearly, this formula is equivalent to \eqref{e1.6a}.
\end{proof}

As we already indicated before,
the formula in Theorem~\ref{T1.3a} has an advantage over that in
Theorem~\ref{T1.3} if starting and end point of the paths are far
apart. First, the number of
summands in \eqref{e1.6a} is roughly half of the ``distance" between
the two boundaries, regardless how far starting and end point are
apart, whereas the number of summands in \eqref{e1.6} increases with
the distance of the starting and end point. 
Second, formula
\eqref{e1.6a} allows to make precise asymptotic statements when the
distance between starting and end point goes to infinity. More
precisely, suppose that we want to know the number of paths between
the two boundaries $y=x+s$ and $y=x+t$ from $(a,b)$ to $(c+n,d+n)$ as
$n$ tends to infinity. Then the dominating term in the sum
\eqref{e1.6a} is clearly the summand for $k=1$. Hence, we have
\begin{multline} \label{e1.6asy}
\v{\L{(a,b)\to (c+n,d+n)\mid x+t\ge y\ge x+s}}\\
\sim \frac {4} {t-s+2}\,
\sin\(\frac {\pi (a-b+t+1)} {t-s+2}\)\cdot
\sin\(\frac {\pi (c-d+t+1)} {t-s+2}\)\\
\times
\(2\cos\frac {\pi }
{t-s+2}\)^{2n+c+d-a-b}
\end{multline}
as $n$ tends to infinity.
We will show in Chapter~\ref{ch3}, ??Section~\ref{s3.5}, that, from a
generating functions point of view, this asymptotic formula comes
from 
\index{Chebyshev, ??}%
\index{polynomial, Chebyshev}\index{Chebyshev polynomial}{\em Chebyshev
polynomials}.

More on counting paths between two lines with slope~1 and $q$-analogues
will be discussed in Chapter~\ref{??}, Section~\ref{??}.

\section{Simple paths with boundaries of type $x=\mu y$} \label{s1.2}
When we want to count lattice paths bounded by an arbitrary line
$y=kx+d$, $k,d\in\R$, the reflection principle obviously does not
help, since the reflection of a lattice path in a generic
line does not necessarily give a lattice path. In
fact, a solution in form of a determinant can be given when the
boundary is viewed as a special case of a set of general boundaries
(see Section~\ref{s1.6}, Theorem~\ref{T1.15}). However, there are cases where
simpler expressions can be obtained, and these are discussed in this
section. ??refer to Sato??

The first case, where a nicer answer can be obtained, is when counting
lattice paths from the $(0,0)$ to $(c,d)$ which stay below the line
$x=\mu y$, where $\mu$ is a positive integer. Of course we have to
assume $c\ge \mu d$. Since, as already remarked, the reflection
principle will not help (except for $\mu=1$), we have to use another
method. The most straight-forward method is by decomposition of paths
and use of generating functions.

\begin{Theorem} \label{T1.4}
Let $\mu$ be a nonnegative integer and
$c\ge \mu d$. The number of all lattice paths from the origin to
$(c,d)$ which lie below $x=\mu y$ is given by
\begin{equation} \label{e1.8}
\v{\L{(0,0)\to (c,d)\mid x\ge\mu y}}=\frac {c-\mu d+1} {c+d+1}\binom
{c+d+1} {d}  .
\end{equation}
\end{Theorem}

\begin{proof}We start with the simpler case that the end point also lies
on $x=\mu y$. Let $P$ be a path in $\L{(0,0) \to (\mu d,d)\mid x\ge\mu
y}$ (see Figure~\ref{F1.2}). 
\begin{Figure} \label{F1.2}
$$
\Gitter(12,8)(-1,0)
\Koordinatenachsen(12,8)(-1,0)
\Pfad(0,0),111212111211122\endPfad
\raise-1 \Einheit\hbox to0pt{\hskip-2 \Einheit
         \unitlength\Einheit
         \line(2,1){13}\hss}
\DickPunkt(0,0)
\DickPunkt(4,2)
\DickPunkt(5,2)
\DickPunkt(7,3)
\DickPunkt(8,3)
\DickPunkt(10,4)
\DickPunkt(10,5)
\Label\ru{\raise10pt\hbox{\hskip4pt$s_h$}}(4,2)
\Label\ru{\raise10pt\hbox{\hskip4pt$s_h$}}(7,3)
\Label\ru{\hskip-2pt s_v}(10,5)
\Label\ro{x=\mu y}(12,5)
\Label\o{S_0}(4,2)
\Label\o{S_1}(7,3)
\SDPfad(5,2),3\endSDPfad
\SDPfad(8,3),3\endSDPfad
\hbox to0pt{$\underbrace{\vrule height0pt width4 \Einheit
depth0pt}_{\textstyle P_0}\hss$}
\hbox to0pt{$\vrule height0pt width5 \Einheit depth0pt
\underbrace{\vrule height0pt width2 \Einheit depth0pt}_{\textstyle P_1}\hss$}
\hbox to0pt{$\vrule height0pt width8 \Einheit depth0pt
\underbrace{\vrule height0pt width2 \Einheit depth0pt}_{\textstyle P_2}\hss$}
\hskip6cm
$$
\end{Figure}
For $l=0,1,\dots,\mu-1$ the path $P$ will
meet the line $x=\mu y+l$ (which is parallel to our boundary $x=\mu
y$) for the last time. Denote this point by $S_l$. Clearly, the path
$P$ must leave $S_l$ by a horizontal step, which we denote by $s_h$
for short. This gives us a unique decomposition of $P$ of the form
$$P=P_0s_hP_1s_h\dots s_hP_\mu s_v$$
where $P_0$ is $P$'s portion from the origin up to $S_0$, $P_1$ is
$P$'s portion from the point immediately following $S_0$ up to $S_1$,
etc. By $s_v$ we denote a vertical step. All the portions $P_i$ (when
shifted appropriately) belong to $\L{(0,0)\to (\mu n,n)\mid x\ge\mu
y}$ for some $n$. Let
$$\mathcal L_0=\bigcup _{n\ge 0} ^{}\L{(0,0)\to (\mu n,n)\mid
x\ge\mu y}.$$
Then we have the following decomposition:
\begin{equation} \label{e1.8z}
\mathcal L_0=\{\ep\}\cup \big((\mathcal L_0 s_h)^\mu \mathcal L_0 s_v\big).
\end{equation}
Here, as always in the sequel, \glossary{$\ep$}$\ep$ denotes the empty path.

??Maybe: $P:(0,0)\to (0,n)$ $\longrightarrow$ $z^n$!!

By \eqref{??} this immediately translates into a functional equation
for the generating function
$$F_0(z):=\sum _{n\ge 0} ^{}\v{\L{(0,0)\to (\mu n,n)\mid x\ge\mu
y}}z^n$$
for $\mathcal L_0$,
\begin{equation} \label{e1.9}
F_0(z)=1+zF_0(z)^{\mu +1}. 
\end{equation}
The coefficients of $F_0(z)$, which we are interested in, are easily
extracted by use of the Lagrange inversion. To be able to apply the Lagrange
inversion, we only have to write $F_0(z)=1+G_0(z)$. Equation
\eqref{e1.9} then reads
\begin{equation} \label{e1.10}
\frac {G_0(z)} {(1+G_0(z))^{\mu+1}}=z, 
\end{equation}
which simply says that $G_0(z)$ is the compositional inverse of
$z/(1+z)^{\mu+1}$. For convenience, let us denote the coefficient of
$z^n$ in some power series $f(z)$ by $\coef{z^n}f(z)$.
Then, an application of \eqref{??} gives
\begin{align} \notag
\L{(0,0)\to (\mu n,n)\mid x\ge\mu y}&=\coef{z^n}\,G_0(z)\\
\notag
&\hskip-2cm = \frac {1} {n}\coef{z^{-1}}\frac {(1+z)^{n(\mu+1)}} {z^n}\\
\notag
&\hskip-2cm = \frac {1} {n}\binom {n(\mu+1)} {n-1}=\frac {1}
{1+n(\mu+1)} \binom {1+n(\mu+1)} {n}.
\end{align}

Turning to the more general problem,
consider a lattice path $P$ in $\big\vert\L{(0,0)\to \linebreak[4](\mu d+k,d)\mid
x\ge \mu y}\big\vert$ (see Figure~\ref{F1.3}). 
\begin{Figure} \label{F1.3}
$$
\Gitter(13,8)(-1,0)
\Koordinatenachsen(13,8)(-1,0)
\Pfad(0,0),112112111211112\endPfad
\raise-1 \Einheit\hbox to0pt{\hskip-2 \Einheit
         \unitlength\Einheit
         \line(2,1){14}\hss}
\DickPunkt(0,0)
\DickPunkt(4,2)
\DickPunkt(5,2)
\DickPunkt(7,3)
\DickPunkt(8,3)
\DickPunkt(9,3)
\DickPunkt(11,4)
\Label\ru{\raise10pt\hbox{\hskip4pt$s_h$}}(4,2)
\Label\ru{\raise10pt\hbox{\hskip4pt$s_h$}}(7,3)
\Label\ru{\raise10pt\hbox{\hskip4pt$s_h$}}(8,3)
\Label\lo{x=\mu y}(10,5)
\Label\o{S_0}(4,2)
\Label\o{S_1}(7,3)
\Label\o{S_2}(8,3)
\Label\ro{(c,d)}(11,4)
\SDPfad(5,2),3\endSDPfad
\SDPfad(9,3),3\endSDPfad
\hbox to0pt{$\underbrace{\vrule height0pt width4 \Einheit
depth0pt}_{\textstyle P_0}\hss$}
\hbox to0pt{$\vrule height0pt width5 \Einheit depth0pt
\underbrace{\vrule height0pt width2 \Einheit depth0pt}_{\textstyle P_1}\hss$}
\hbox to0pt{$\vrule height0pt width7.5 \Einheit depth0pt
\underbrace{\vrule height0pt width0 \Einheit depth0pt}_{\textstyle P_2}\hss$}
\hbox to0pt{$\vrule height0pt width9 \Einheit depth0pt
\underbrace{\vrule height0pt width2 \Einheit depth0pt}_{\textstyle P_3}\hss$}
\hskip6.5cm
$$
\end{Figure}
For $l=0,1,\dots,k-1$ the
path will meet the line $x=\mu y+l$ 
for the last time. Denote this point by $S_l$. Clearly, the path
$P$ must leave $S_l$ by a horizontal step, for which we again write
$s_h$. This gives us a decomposition of $P$ of the form
$$P=P_0s_hP_1s_h\dots s_h P_{k},$$
where $P_0$ is the portion of $P$ from the origin up to $S_0$, $P_1$ is
the portion of $P$ from the point immediately following $S_0$ up to $S_1$,
and so on. Observe that again the portions $P_l$ belong $\mathcal L_0$ (being
defined immediately before \eqref{e1.8z}).
Let
$$\mathcal L_k=
\bigcup _{n\ge 0} ^{}\L{(0,0)\to (\mu n +k,n)\mid x\ge \mu y}.$$
Then we have the following decomposition:
$$\mathcal L_k=(\mathcal L_0s_h)^{k}\mathcal L_0.$$
By \eqref{??} this translates into an equation for the generating
function 
$$F_k(z):=\sum _{n\ge0} ^{}\v{\L{(0,0)\to (\mu n+k,n)\mid x\ge\mu y}}
z^n$$
for $\mathcal L_k$, namely
\begin{equation} \label{e1.11}
F_k(z)=F_0(z)^{k+1}=(1+G_0(z))^{k+1}, 
\end{equation}
or equivalently
\begin{equation} \label{e1.12}
\sum _{n\ge0} ^{}\v{\L{(0,0)\to (\mu
n+k, n)\mid x\ge\mu y}}\frac {z^n} {(1+z)^{n(\mu +1)}}= (1+z)^{k+1}. 
\end{equation}
Again, use of the Lagrange formula \eqref{??} with $g(z)=(1+z)^{k+1}$,
$f(z)=z/(1+z)^{\mu +1}$ from \eqref{e1.12} yields
\begin{align} \notag
\L{(0,0)\to (\mu n+k,n)\mid x\ge \mu y}&=\frac {1} {n}\coef{z^{-1}}
(k+1) \,(1+z)^k\frac {(1+z)^{n(\mu +1)}} {z^n}\\
\notag
&\hskip-2cm = \frac {k+1} {n}\binom {\mu n+k +n} {n-1}\\
\notag
&\hskip-2cm = \frac {k+1} {\mu n+k +n+1} \binom {\mu n+k+n+1}{n},
\end{align}
which turns into \eqref{e1.8} once we replace $\mu n+k$ by $c$ and $n$
by $d$.
\end{proof}

In particular, for $\mu=1$ the generating function $F_0(z)$ can be
explicitly evaluated from solving the quadratic equation
\eqref{e1.9}. 
This gives the familiar generating function for the Catalan numbers
(compare with the second paragraph after Corollary~\ref{T1.2})
\begin{equation} \label{e1.13}\sum _{n\ge0} ^{} C_n z^n= \frac
{1-\sqrt {1-4z}} {2z}. 
\end{equation}
The reason that we are allowed to forget 
about the second solution of the quadratic equation is that it does
not give a proper formal power series. So in this case we do not
actually need the Lagrange inversion to extract the coefficients of
$F_0(z)$, since the binomial theorem applied to $(1-4z)^{1/2}$ also 
leads to the solution. 

Identity \eqref{e1.12} written in the equivalent form
\begin{equation} \label{e1.14}
\sum _{n\ge0} ^{}\v{\L{(0,0)\to (\mu
n+k, n)\mid x\ge\mu y}}\frac {z^n} {(1+z)^{n(\mu +1)+k+1}}= 1
\end{equation}
will be generalized to weighted counting in Proposition~\ref{T4.3}
and ?? by using
different methods.

\medskip
Since the answer \eqref{e1.8} to our last counting problem is so nice,
it suggests itself to look for a combinatorial proof. Indeed, there
is. It is sometimes know under the name ``\index{penetrating 
analysis}penetrating 
analysis". It
bases on a lemma due to \index{Dvoretzky, A.}Dvoretzky and 
\index{Motzkin, T.}Motzkin 
\cite{DvMoAA}, called
the ``\index{cycle lemma}cycle lemma", which has
been rediscovered a lot of times (see \index{Dershovitz,
N.}Dershovitz?? and \index{Zaks, S.}Zaks??
\cite{ZaDeAA} for a list of references.) 

\begin{Lemma}[Cycle Lemma] \label{T1.5}
Let $\mu$ be a nonnegative integer. For any sequence $p_1p_2\dots
p_{m+n}$ of $m$ $1$'s and $n$ $2$'s, $m\ge\mu n$, there exist exactly
$m-\mu n$ cyclic permutations $p_ip_{i+1}\dots p_{m+n}p_1\dots
p_{i-1}$, $1\le i\le m+n$, that have the property that for all
$j=1,2,\dots,m+n$ the first $j$ letters of this permutation contain
more 1's than $\mu$ times the number of 2's. 
\end{Lemma}
\begin{proof} A sequence $p_1p_2\dots p_{m+n}$ of $m$ 1's and $n$ 2's can
be seen as a lattice path from $(0,0)$ to $(m,n)$ by interpreting the
1's as horizontal steps and the 2's as vertical steps. Cyclically
permuting $p_1p_2\dots p_{m+n}$ means to cut the corresponding lattice
path into two pieces and put them together in exchanged order, thus
obtaining a new lattice path from $(0,0)$ to $(m,n)$. Finally, the
property that in each initial string of a sequence the number of 1's
dominates (i.e., 
is larger than) $\mu$ times the number of 2's means that the corresponding
lattice path stays strictly below the line $x=\mu y$, with the
exception of the starting point $(0,0)$. 

For the proof of the lemma interpret $p_1p_2\dots p_{m+n}$ as a path,
as described before, and join a shifted copy of this path at the end
point $(m,n)$, another shifted copy at $(2m,2n)$, etc.
Figure~\ref{F1.4} shows an example with $\mu=2$, $m=9$, $n=3$. The
path $P$ corresponds to the sequence $12111211$.
\begin{Figure} \label{F1.4}
$$
\Gitter(20,10)(-1,0)
\Koordinatenachsen(20,10)(-1,0)
\Pfad(0,0),121111122111 121111122111\endPfad
\SPfad(18,6),121\endSPfad
\PfadDicke{2.5pt}
\Pfad(1,1),1\endPfad
\Pfad(6,3),11\endPfad
\Pfad(10,4),1\endPfad
\Pfad(15,6),11\endPfad
\DickPunkt(0,0)
\DickPunkt(9,3)
\DickPunkt(18,6)
\SDPfad(-1,0),3\endSDPfad
\SDPfad(2,1),3\endSDPfad
\SDPfad(4,2),3\endSDPfad
\SDPfad(8,3),3\endSDPfad
\SDPfad(11,4),3\endSDPfad
\SDPfad(13,5),3\endSDPfad
\SDPfad(17,6),3\endSDPfad
\Label\u{(m,n)}(9,3)
\hbox to0pt{$\underbrace{\vrule height0pt width9 \Einheit
depth0pt}_{\textstyle P}\hss$}
\hskip11cm
$$
\end{Figure}
Cyclic permutations of $p_1p_2\dots p_{m+n}$ correspond to cutting a
piece of $m+n$ successive steps out of this lattice path structure.
Then imagine a sun to be located in direction $(\mu,1)$ illuminating
the lattice path structure. A cyclic permutation will satisfy the
dominance property for each initial string if and only if the first
step of the corresponding lattice path is illuminated. 
In Figure~\ref{F1.4} the illuminated steps are
indicated by thick lines. It is an easy
matter of fact that of any $m+n$ successive steps there are exactly $m-\mu n$
illuminated steps. Therefore out of the $m+n$ cyclic permutations of
$p_1p_2\dots p_{m+n}$ there are exactly $m-\mu n$ cyclic permutations
having the
dominance property for each initial string.
\end{proof}

\begin{proof} [Combinatorial Proof of Theorem~\ref{T1.4}]
We want to count paths from $(0,0)$ to $(c,d)$ staying (weakly) below $x=\mu
y$. To fit with the cycle lemma we adjoin a horizontal step at the
beginning and shift everything by one unit to the right. Thus we are
now asking for the number of paths from $(0,0)$ to $(c+1,d)$ staying
{\em strictly\/} below $x=\mu y$, except for the starting point $(0,0)$.
To find this number, $N$ say, we count in
two different ways the set of all pairs $(P,Q)$,
where 
\begin{enumerate}
\item $P$ is any path from $(0,0)$ to $(c+1,d)$,
\item $Q$ is a path
from $(0,0)$ to $(c+1,d)$ staying strictly below $x=\mu y$ except for
$(0,0)$,
\item $P$ and $Q$ are related by a cyclic permutation of their steps.
\end{enumerate} 
Figure~\ref{F1.4A} displays an example of such a pair $(P,Q)$, with
$\mu=2$, $c=6$, $d=2$, where $Q$ is the cyclic permutation of $P$
which starts with the third step of $P$. The bold steps in the Figure
indicate the possible beginnings of a path $Q$.

\begin{Figure}\label{F1.4A}
$$
\underset {\text {a. Arbitrary path}}
{
\Gitter(9,5)(0,0)
\Koordinatenachsen(9,5)(0,0)
\Pfad(0,0),211112111\endPfad
\PfadDicke{2.5pt}
\Pfad(0,1),11\endPfad
\Pfad(4,2),1\endPfad
\Label\lo{P}(2,1)
\Label\lo{(c+1,d)}(9,2)
\Label\lo{x=\mu y}(6,3)
\PfadDicke{.5pt}
\raise-.5\Einheit\hbox to0pt{\hskip-1 \Einheit
         \unitlength\Einheit
         \line(2,1){10}\hss}
\DickPunkt(0,0)
\DickPunkt(7,2)
\hskip5cm
}
\hbox{\hskip3cm}
\underset {\text {b. Path staying strictly below $x=\mu y$}}
{
\Gitter(9,5)(0,0)
\Koordinatenachsen(9,5)(0,0)
\PfadDicke{1pt}
\Pfad(0,0),111211121\endPfad
\Label\ro{Q}(5,1)
\Label\lo{(c+1,d)}(9,2)
\Label\lo{x=\mu y}(6,3)
\PfadDicke{.5pt}
\raise-.5\Einheit\hbox to0pt{\hskip-1 \Einheit
         \unitlength\Einheit
         \line(2,1){10}\hss}
\DickPunkt(0,0)
\DickPunkt(7,2)
\hskip5cm
}
$$
\end{Figure}


First of all, there are $\binom {c+d+1}d$
possible paths $P$, and, by the cycle lemma~\ref{T1.5}, for each $P$
there are exactly $c+1-\mu d$ cyclic permutations $Q$ staying
strictly below $x=\mu y$ except for $(0,0)$. So our set of pairs
$(P,Q)$ has cardinality $(c+1-\mu d)\binom {c+d+1}d$. On the other
hand, there are $N$ possible paths $Q$, and for each $Q$ there are $c+d+1$
cyclic permutations $P$. Therefore the cardinality of our set of
pairs $(P,Q)$ is also equal to $(c+d+1)N$. Equating the two
expressions for the cardinality
gives the desired result for the number $N$ that we are
looking for.
\end{proof}

??Put Krat/Mohanty multi-one correspondence proof

??give Chapter 3-Takacs/Narayana cyclic things here?

So far we only counted paths bounded by $x=\mu y$ where the starting
point lies on the boundary. If we drop this latter assumption
and now want to 
enumerate all paths from $(a,b)$ to $(c,d)$ staying below $x=\mu y$,
the problem becomes more difficult. Yet there is an answer, although
only in terms of a sum. In fact, we can offer two different
expressions. Which of these two is preferable depends on the
particular situation, to be more precise, on which of the numbers
$({a/\mu}-b)$ or $(d-{a/\mu})$ being larger (see
Figure~\ref{F1.5} for the pictorial significance of these numbers). 
While the
proof for the first expression is rather straight-forward, the
proof for the second expression is trickier. 
??cite Niederhausen, Sato
??Prove, at least for $\mu=2$ or 3 that there cannot be a ``NICE"
solution by Zeilberger-Petkov\hacek{s}ek
\begin{Figure} \label{F1.5}
$$
\Diagonale(-2,0)8
\DickPunkt(0,0)
\DickPunkt(5,5)
%\DuennPunkt(0,2)
\Label\o{(c,d)}(5,5)
\Label\u{(a,b)}(0,0)
\SPfad(0,0),22\endSPfad
\SPfad(0,2),11111\endSPfad
\SPfad(5,0),22222\endSPfad
\SPfad(0,0),11111\endSPfad
\Label\ro{\,d-{a/\mu}}(6.5,3)
\Label\r{\,{a/\mu}-b}(6.5,1)
\Label\ru{\hskip-20pt x=\mu y}(7,8)
\hskip5\Einheit
\raise0.8\Einheit
\hbox to0pt{$\left.\vrule height1.2\Einheit depth0pt width0pt\right\}$\hss}
\raise3.3\Einheit
\hbox to0pt{$\left.\vrule height1.7\Einheit depth0pt width0pt\right\}$\hss}
$$
\end{Figure}

\begin{Theorem} \label{T1.6}
Let $\mu$ be a nonnegative integer, $a\ge \mu b$ and $c\ge\mu d$. The
number of all lattice paths from $(a,b)$ to $(c,d)$ staying below
$x=\mu y$ is given by
\begin{multline} \label{e1.15}
\v{\L{(a,b)\to (c,d)\mid x\ge\mu y}} 
=\binom {c+d-a-b}{c-a}\\
-\sum _{i=\floor {a/\mu}+1} ^{c}\binom {i(\mu+1)-a-b-1}{i-b} 
\frac {c-\mu i+1} {c+d-i(\mu+1)+1}\binom {c+d-i(\mu+1)+1} {d-i},\\
\end{multline}
and also
\begin{multline} \label{e1.16}
\v{\L{(a,b)\to (c,d)\mid x\ge\mu y}}
=\sum _{i=0} ^{\floor{a/\mu}-b}
(-1)^{i} \binom {a-\mu (b+i)}i \\
\times\frac {c-\mu d +1} {c+d-(\mu+1)(b+i)+1}
\binom {c+d-(\mu+1)(b+i)+1} {d-b-i}.
\end{multline}
\end{Theorem}
\begin{proof}[Proof of \eqref{e1.15}]
The number of paths in question equals the number of all paths from
$(a,b)$ to $(c,d)$ minus those paths which cross $x=\mu y$. To count
the latter observe that any path crossing $x=\mu y$ must meet the line
$x=\mu y-1$, and for the last time in some point $(\mu i-1,i)$ where
$\floor {a/\mu}+1\le i\le c$. Fix any $i$, then the number of all
these paths is
$$\v{\L{(a,b)\to (\mu i-1,i)}}\cdot \v{\L{(\mu i,i)\to (c,d)\mid x\ge
\mu y}}.$$
We already know the first number thanks to \eqref{e1.1},
and we also know the second number thanks to \eqref{e1.8},
since a shift in direction $(-\mu i,-i)$ shows that the second number
equals $\v{\L{(0,0)\to (c-\mu i, d-i)\mid x\ge \mu y}}$.
\end{proof}
\begin{proof}[Proof of \eqref{e1.16}]
Formula~\eqref{e1.16} is an inclusion-exclusion formula (observe the
alternating sign). As in Theorem~\ref{T1.3} we prefer to prove
\eqref{e1.16} by means of a cancelling bijection, more precisely by a
cancelling involution, i.e\@. by a map $\ph$ with $\ph\circ
\ph=\text{id}$. 

First we give a combinatorial interpretation of the right-hand side of
\eqref{e1.16}. For convenience, given a set $\mathcal M$, let us denote
the collection of all $k$-element subsets of $\mathcal M$ by $S_k(\mathcal
M)$\glossary{S_k(\mathcal M)}. Then \eqref{e1.16} can be written as 
\begin{equation} \label{e1.17}\sum _{(S,P)} ^{}(-1)^{\v S} ,
\end{equation}
where the sum is over all pairs $(S,P)$ in
\begin{multline} \label{e1.18}
\bigcup _{i=0} ^{\floor{a/\mu}-b}S_i(\{\mu(b+i),\mu(b+i)+1,\dots
,a-1\})\\
\times \L{(\mu(b+i),b+i)\to (c,d)\mid x\ge \mu y} ,
\end{multline}
i.e\@. $S$ is an $i$-element subset of $\{\mu (b+i),\mu (b+i)+1,\dots,
a-1\}$, and $P$ is a path from $(\mu(b+i),b+i)$ to $(c,d)$ staying
below $x=\mu y$, for some $i=0,1,\dots,\floor{a/\mu}-b$. 
Figure~\ref{F1.5A} illustrates the situation. Both, $P_1$ and $P_2$
are examples of $P$. It is clear that
by \eqref{e1.17} we have written the right-hand side of
\eqref{e1.16} as a generating function for the set \eqref{e1.18}. What
we shall do is to construct an involution $\ph$ on the set of all pairs $(S,P)$
in \eqref{e1.18} where either $S$ is nonempty or $P$ contains at
least one
vertical step strictly to the left of the vertical line $x=a$.
This involution will be shown to be sign-reversing, in the sense that if
$\ph((S,P))=(S',P')$ then $(-1)^{\v S}=-(-1)^{\v{S'}}$.


\begin{Figure} \label{F1.5A}
$$
\Gitter(10,8)(-10,-1)
\raise-.5\Einheit\hbox to0pt{\hskip-10 \Einheit
         \unitlength\Einheit
         \line(2,1){16}\hss}
\SPfad(0,-2),2222222222\endSPfad
\Pfad(-9,0),111111111211112111112222\endPfad
\Pfad(-5,2),111211112111122111\endPfad
\DickPunkt(0,0)
\DickPunkt(9,6)
\DickPunkt(-9,0)
\DickPunkt(-5,2)
\Label\ru{\hskip6pt(a,b)}(0,0)
\Label\r{\hskip20pt(c,d)}(9,6)
\Label\lo{(\mu b,b)\hskip8pt}(-9,0)
\Label\lo{(\mu(b+i),b+i)\hskip40pt}(-5,2)
\Label\o{x=\mu y}(4,7)
\Label\l{\raise6pt\hbox{$x=a$\hskip15pt}}(0,6)
\Label\o{P_1}(4,4)
\Label\lu{P_2}(6,2)
$$
\end{Figure}

Suppose that this had been done. Then in the sum \eqref{e1.17} all
contributions of pairs $(S,P)$ in \eqref{e1.18} where either $S$ is
nonempty or $P$ contains at least one vertical step strictly to the left of $x=a$
will cancel. Thus only the contributions $(\emptyset,P)$ in
$S_0(\emptyset)\times \L{(\mu b,b)\to (c,d)\mid x\ge \mu y}$ will survive
where $P$ does not contain a vertical step strictly to the left of
$x=a$, i.e\@. starts with $a-\mu b$ horizontal steps. The path
$P_2$ in Figure~\ref{F1.5A} is an example of a ``surviving" path. 
Clearly the set
of pairs $(\emptyset,P)$ as described above 
is equinumerous with $\L{(a,b)\to (c,d)\mid x\ge\mu y}$ which
is what we need.

Now we construct the involution $\ph$. Let $(S,P)$ be a pair in 
$S_i(\{\mu(b+i),\mu(b+i)+1,\dots,a-1\})
\times \L{(\mu(b+i),b+i)\to (c,d)\mid x\ge \mu y}$ with either $S$
being nonempty or $P$ containing a vertical step strictly left of
$x=a$. Let $s$ be the smallest element in $S$ and $t$ be the
$x$-coordinate of a left-most vertical step in $P$. Then, introducing
notations which will be explained below, we define
$\ph$ by 
$$\ph((S,P))=\begin{cases} (S\setminus \{s\},P\oplus \{s\})&s\le t,\\
(S\cup \{t\},P\ominus \{t\})&s>t.\end{cases}$$
This has to be understood in the following sense. If $s\le t$ then
take $s$ out of $S$, insert a vertical step with $x$-coordinate $s$
into $P$ leaving the end point invariant, and add $\mu$
horizontal steps at the beginning of $P$, again leaving the end point
invariant, thus obtaining $P\oplus\{s\}$. It is easy to see that
$(S\setminus \{s\},P\oplus \{s\})$ belongs to  
$S_{i-1}(\{\mu(b+{i-1}),\mu(b+{i-1})+1,\dots,a-1\})
\times \L{(\mu(b+{i-1}),b+{i-1})\to (c,d)\mid x\ge \mu y}$. Besides,
$P\oplus\{s\}$ 
contains a vertical step strictly to the left of $x=a$ since $s\le
a-1$. 
On the other hand, if $s>t$ we add $t$ to $S$, delete a vertical
step with $x$-coordinate $t$ from $P$ leaving the end point invariant,
and delete $\mu $ horizontal steps at the beginning of $P$
(which must be there because $P$ starts at the line $x=\mu y$ and 
is staying below $x=\mu y$) again leaving the end point invariant,
thus obtaining $P\ominus \{t\}$. It is easy to see that
$(S\cup\{t\},P\ominus \{t\})$ belongs to 
$S_{i+1}(\{\mu(b+{i+1}),\mu(b+{i+1})+1,\dots,a-1\})
\times \L{(\mu(b+{i+1}),b+{i+1})\to (c,d)\mid x\ge \mu y}$ with
$S\cup\{t\}$ being nonempty.

It is not difficult to show that $\ph$ is an involution, i.e\@. when
applying $\ph$ again one arrives back at the original pair. Since
exactly one element is added to $S$ or deleted from $S$ the mapping
$\ph$ is sign-reversing.
\end{proof}



\section{Simple paths with a piecewise linear boundary} \label{s1.3}
In this section we generalize the one-sided linear boundary
results Theorems~\ref{T1.2}, \ref{T1.4}, \ref{T1.6} to piecewise
linear boundaries. To be more precise, we want to count lattice paths
from the origin $(0,0)$ to $(c,d)$ staying below the line segments
$\{(x,y):x=\mu _1y+\nu_1,0=y_0\le y\le y_1\}$,
$\{(x,y):x=\mu _2y+\nu_2,y_1\le y\le y_2\}$,\dots,
$\{(x,y):x=\mu _my+\nu_m,y_{m-1}\le y\le y_m=d\}$ for some sequence
$0=y_0<y_1<\dots,y_m=d$, nonnegative integers
$\mu_1,\mu_2,\dots,\mu_m$, and integers $\nu_1,\nu_2,\dots,\nu_m$ such
that the bound is monotone?? and to the right of the $y$-axis. Let us
denote this piecewise linear restriction by $R$.?? 
See Figure~\ref{F1.5B} for an example.
By an
iteration argument it will be seen that the solution to this problem
can be given in form of an $(m-1)$-fold sum. In fact, suppose that
$\mu_i y_{i-2}+\nu_i\ge0$ 
for all $i$. 

\begin{Figure}\label{F1.5B}
$$
\Einheit.5cm
\def\SternPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss$\bigstar$\hss}\hss}}
\def\ZweiSchritt{\leavevmode\raise-.4pt\hbox to0pt{%
  \hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.1\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.3\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.5\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.7\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.8\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit
  \raise.9\Einheit\hbox to0pt{\hss.\hss}\hss}}
\Gitter(20,10)(0,0)
\Koordinatenachsen(20,10)(0,0)
\raise0\Einheit\hbox to0pt{\hskip0 \Einheit
         \unitlength\Einheit
         \line(3,1){9}\hss}
\raise3\Einheit\hbox to0pt{\hskip9 \Einheit
         \unitlength\Einheit
         \line(2,1){4}\hss}
\raise5\Einheit\hbox to0pt{\hskip13 \Einheit
         \unitlength\Einheit
         \line(1,1){3}\hss}
%\thinlines
%\Pfad(13,5),33333\endPfad
%\SPfad(9,0),222\endSPfad
%\SPfad(13,0),22222\endSPfad
%\SPfad(18,0),2222222222\endSPfad
\raise0 \Einheit\hbox to0pt{\hskip3 \Einheit
         \ZweiSchritt\hss}
\raise1 \Einheit\hbox to0pt{\hskip5 \Einheit
         \ZweiSchritt\hss}
\raise2 \Einheit\hbox to0pt{\hskip7 \Einheit
         \ZweiSchritt\hss}
\SPfad(8,0),33333\endSPfad
\Pfad(0,0),11112111211111112212212121\endPfad
\DickPunkt(0,0)
\DickPunkt(18,8)
\DickPunkt(9,3)
\DickPunkt(13,5)
\DickPunkt(16,8)
\SternPunkt(7,2)
\SternPunkt(10,2)
\Label\ru{P}(12,2)
\Label\lo{\hskip0pt x=\mu_1 y+\nu_1}(2,1)
\Label\lo{\hskip0pt x=\mu_2 y+\nu_2}(10,4)
\Label\lo{\hskip0pt x=\mu_3 y+\nu_3}(13,6)
\Label\l{y_0}(0,0)
\Label\l{y_1}(0,3)
\Label\l{y_2}(0,5)
\Label\l{y_3=d}(-1,8)
\Label\o{(c,d)}(19,8)
\hskip9cm
$$
\end{Figure}


Evidently, any path from $(0,0)$ to $(c,d)$
has to touch $x=\mu_m y+\nu_m$ for the last time, say in $(\mu_m
i+\nu_m,i)$. In Figure~\ref{F1.5B} we have $m=3$, the last
touching point of the path $P$ with $x=\mu_m y+\nu_m$ is $(10,2)$, it is marked by a
star.
Then we could utilize the same idea which
led to the formula \eqref{e1.15}  
to obtain the number in
question being equal to
\begin{align} \notag
&\v{\L{(0,0)\to (c,d)\mid R}}\\
\notag
&\hskip1cm=
\sum _{i=0} ^{y_{m-1}}\v{\L{(0,0)\to (\mu_m i+\nu_m-1,i)\mid R}}\\
\notag
&\hskip3cm
\v{\L{(\mu_m i+\nu_m,i)\to (c,d)\mid x\ge \mu_m y+\nu_m}}
\\\notag
&\hskip1cm
=\sum _{i=0} ^{y_{m-1}}\v{\L{(0,0)\to (\mu_m i+\nu_m-1,i)\mid R}}\\
\notag
&\hskip3cm
\frac {c-\mu_m(i+d)-\nu_m+1} {c+d-\mu_m(i+1)-\nu_m+1}
\binom{c+d-\mu_m(i+1)-\nu_m+1}{d-i},\\\label{e1.19}
\end{align}
by virtue of Theorem~\ref{T1.4}. Now we can iterate this argument
which involves the last touching points with the other lines. The
last touching point of the path $P$ with $x=\mu_1 y+\nu$ is 
marked again by a star.
Thus we obtain a certain sum for $\v{\L{(0,0)\to (\mu_m
i+\nu_m-1,i)\mid R}}$, etc., until we get an $(m-1)$-fold sum
involving binomial expressions. 

Unfortunately, in case our favourable
assumption $\mu_iy_{i-2}+\mu_i\ge0$ is violated for some $i$, then the
argument breaks down. However, the situation can be rescued by
``extending the path numbers". This bases on the observation that in
our situation the numbers of paths to be counted will always be
polynomials, hence can be extended to negative values ...

\section{Simple paths with linear boundaries with rational slope}
 \label{s1.4}
??Bizley!!
In Section~\ref{s1.3} we considered lattice paths bounded by a line
$x=\mu y$, with $\mu$ a nonnegative integer. 
Now we want to consider a more general linear boundary of the form
$\nu x=\mu y$, where $\nu,\mu$ are nonnegative integers. We describe
a generating function approach, due to \index{Sato, M.}Sato \cite{SatoAA}, which
works for a large class of cases. Alternative solutions, which work
in all cases, in the form of a determinant can be given as a special
case of a set of general boundaries. These are discussed in
Section~\ref{s1.6}, see Theorems~\ref{T1.15}, \ref{T1.17}.

??Figure!! what does it mean? It means from (0,0) to "very close" to the
boundary!!
The problem that we want to attack here is to enumerate all lattice
paths from an arbitrary starting point to an arbitrary end point 
staying below the line $\nu x=\mu y$.
A simple shift of the plane shows that this is equivalent to
enumerating paths from the origin to an arbitrary end point 
staying below $\nu x= \mu
y-\rho$, for an appropriate $\rho$. Without loss of generality we
may assume in the sequel that $\nu<\mu$.
For the approach of Sato this is the more convenient
formulation of the problem. The idea is to introduce $\nu\times\nu$
matrices which contain the path numbers that we are looking for. More
precisely, define the $\nu\times\nu$ matrix $W(z;c,\rh)$ by
\begin{equation} \label{e1.20a}
W(z;c,\rh):=\big(w(z;c+g,\rh+h)\big)_{0\le g,h\le \nu-1},
\end{equation}
where 
\begin{equation} \label{e1.21b}
w(z;c,\rh)=\sum _{\mu n+c\equiv\rh\pmod\nu} ^{}w(n;c,\rh)\,z^n,
\end{equation}
with
\begin{multline} \label{e1.21c}
w(n;c,\rh)=\begin{cases} \v{\L{(0,0)\to(\frac {\mu n+c-\rh}
{\nu},n)\mid \nu x\ge\mu y-\rh}}&\mu n+c\equiv \rh\pmod\nu\\
&\text {and }\mu n+c\ge\rh\\
\binom {n+\frac {\mu n+c-\rh} {\nu}}{n}&\mu n+c\equiv \rh\pmod\nu\\
&\text {and }\mu n+c<\rh.
\end{cases}\\
\end{multline}
So, what the matrix $W(z;c,\rh)$ contains is generating functions
of the path numbers $w(n;c,\rh)$ 
that we want to know. The definition of $w(n;c,\rh)$ for $\mu n+c<\rh$
(in which case there cannot be any paths from $(0,0)$ to $(\frac {\mu n+c-\rh}
{\nu},n)$) is just for technical convenience. Basically, the matrix
$W(z;c,\rh)$ is
\begin{multline} \label{e1.22}
W(z;c,\rh)=\Big(\sum _{\mu n+c+g-h\equiv \rh\pmod \nu} ^{}
\left\vert\L{(0,0)\to(\frac {\mu n+c+g-\rh-h}
{\nu},n)\mid\right. \\
\nu x\ge\mu y-\rh-h}\Big\vert\, z^n\Big)_{0\le g,h\le \nu-1}.
\end{multline}

The following theorem of \index{Sato, M.}Sato \cite[Theorem~1]{SatoAA} tells how to
compute $W(z;c,\rh)$.
\begin{Theorem} \label{T1.7}
Let
\begin{equation} \label{e1.23f}
M=\((-1)^{\nu-h-1} 
s_{(c+g+1,1^{\nu-h-1})}\big(u_0(z),\dots,u_{\nu-1}(z)\big)\)_{0\le
g,h\le \nu-1},
\end{equation}
where
\begin{multline} \label{e1.23g}
s_{(\al,1^\be)}(u_0,\dots,u_{\nu-1})\\
=\sum _{\nu-1\ge 
i_\al\ge i_{\al-1}\ge\dots i_1<j_1<\dots<j_\be\le \nu-1} ^{}
u_{i_\al}(z)u_{i_{\al-1}}(z)\cdots u_{i_1}(z)u_{j_1}(z)\cdots u_{j_\be}(z),
\end{multline}
$u_l(z)$ being defined by
\begin{multline} \label{e1.23e}
u_l(z)=e^{(2\pi il/\nu)}\sum _{n\ge0} ^{}\frac {1}
{1+(\nu+\mu)n}\binom {\frac {1} {\nu}+(1+\frac {\mu}
{\nu})n}n\(ze^{2\pi il\mu/\nu}\)^n,\\
l=0,1,\dots,\nu-1.
\end{multline}
Furthermore, let
\begin{equation} \label{e1.23b}
\Phi(z;\rh)=\bigg(\underset{\mu l\le \rh-g+h}{\sum _{\mu l\equiv
\rh-g+h\pmod\nu}
^{}}(-1)^l\binom {(\rh-g+h-\mu l)/\nu}lz^l\bigg)_{0\le g,h\le \nu-1}.
\end{equation}
Then, 
for any nonnegative integers $c$, $\rh$, $\nu$, $\mu$, with $\nu<\mu$, we have
\begin{equation} \label{e1.23a}
W(z;c,\rh)=M(z;c,\rh)\,\Phi(z;\rh).
\end{equation}
\end{Theorem}
\begin{Note} Note that $s_{(\al,1^\be)}(u_0,\dots,u_{\nu-1})$
is a {\em Schur function\/} of {\em hook shape}, which is to be
explained in Chapter~\ref{ch2}, Section~\ref{s2.2}.
\end{Note}
Before we proceed to the proof of the theorem, it might be useful
first to
discuss an example, in order to illustrate what this is all about.

??remark that everything works also for $\nu=2$, $\mu$ arbitrary
\begin{Example}We take $\nu=2$, $\mu=3$. 
So, by \eqref{e1.21c}, the quantity $w(n;c,\rh)$ represents the
number of all lattice paths from $(0,0)$ to $((3n+c-\rh)/2,n)$ which
stay below the line $2x= 3y-\rh$, where $c\equiv 3n-\rh\pmod2$, i.e.,
$c\equiv n+\rh\pmod2$.
??Figure

By definition \eqref{e1.20a}, we have
\begin{align} \notag
W(z;c,\rh)&=\big(w(z;c+g,\rh+h)\big)_{0\le g,h\le 1}\\
&=\begin{pmatrix} w(z;c,\rh)&w(z;c,\rh+1)\\
w(z;c+1,\rh)&w(z;c+1,\rh+1)\end{pmatrix}.\notag
\end{align}
Using \eqref{e1.23a}, it can be written as 
$$W(z;c,\rh)=M(z;c,2)\,\Phi(z;\rh),$$
where 
$$\Phi(z;\rh)=\begin{pmatrix} 
\underset{\mu l\le \rh}{\sum _{\mu l\equiv \rh\pmod\nu}
^{}}(-1)^l\binom {(\rh-\mu l)/\nu}lz^l&
\underset{\mu l\le \rh+1}{\sum _{\mu l\equiv \rh+1\pmod\nu}
^{}}(-1)^l\binom {(\rh+1-\mu l)/\nu}lz^l\\
\underset{\mu l\le \rh-1}{\sum _{\mu l\equiv \rh-1\pmod\nu}
^{}}(-1)^l\binom {(\rh-1-\mu l)/\nu}lz^l&
\underset{\mu l\le \rh}{\sum _{\mu l\equiv \rh\pmod\nu}
^{}}(-1)^l\binom {(\rh-\mu l)/\nu}lz^l
\end{pmatrix}$$
by \eqref{e1.23b},
and 
$$M(z;c,2)=\pmatrix 
-s_{(c+1,1)}\big(u_0(z),u_{1}(z)\big)&
s_{(c+1)}\big(u_0(z),u_{1}(z)\big)\\
-s_{(c+2,1)}\big(u_0(z),u_{1}(z)\big)&
s_{(c+2)}\big(u_0(z),u_{1}(z)\big)
\endpmatrix$$
by \eqref{e1.23f}, with $s_{(\al,1^\be)}(u_0(z),u_1(z))$ being defined
in \eqref{e1.23g}, and
$$u_l(z)=(-1)^l\sum _{n\ge0} ^{}\frac {(-1)^{ln}} {1+5n}\binom {\frac {1}
{2}+\frac {5} {2}n}nz^n,$$
as given in \eqref{e1.23e}.

So, in particular, in case that $c=\rh=0$ the matrix $\Phi(z;0)$ is
the $2\times 2$ identity matrix, and so we have
\begin{multline} \notag
W(z;0,0)=\begin{pmatrix} w(z;0,0)&w(z;0,1)\\
w(z;1,0)&w(z;1,1)\end{pmatrix}\\
=M(z;0,2)=
\begin{pmatrix} -u_0(z)u_1(z)&u_0(z)+u_1(z)\\
-u_0(z)u_1(z)(u_0(z)+u_1(z))&u_0^2(z)+u_0(z)u_1(z)+u_1^2(z)\end{pmatrix}.
\end{multline}
Whence, for even $n$ the number of all lattice paths from $(0,0)$ to
$(3n/2,n)$ which stay below the line $2x\ge 3y$ equals
\begin{multline} \notag
\v{\L{(0,0)\to(\tfrac {3n} {2},n)\mid 2x\ge 3y}}=\coef{z^n}w(z;0,0)\\
=\sum _{l=0} ^{n}(-1)^l\frac {1} {1+5l}\binom {\frac {1} {2}+\frac {5}
{2}l}l\cdot \frac {1} {1+5(n-l)}\binom {\frac {1} {2}+\frac {5}
{2}(n-l)}{n-l},
\end{multline}
and for odd $n$ the number of all lattice paths from $(0,0)$ to
$((3n-1)/2,n)$ which stay below the line $2x\ge 3y-1$ equals
\begin{multline} \notag
\v{\L{(0,0)\to(\tfrac {3n-1} {2},n)\mid 2x\ge
3y-1}}=\coef{z^n}w(z;0,1)=\frac {2} {1+5n}\binom {\frac {1} {2}+\frac
{5} {2}n}n.
\end{multline}
Clearly, as $\rh$ and $c$ increase (the geometrical meaning being
that the starting and end point, respectively, move away from the
boundary) the (explicit) expressions become more complicated.

??mention that this can also be derived using the cycle lemma, also
mention that this nice expression can always obtained for arbitrary
$\mu,\nu$ in one particular case, $w(z;0,\nu-1)$??

??$\nu=1$: compare with reflection principle results.



\end{Example}


\begin{proof}[Proof of Theorem~\ref{T1.7}]
The proof is divided into
four steps.

{\em First step}. Let $\mu n+c\equiv \rh$ and $\mu n+c\ge \rh$. 
Consider paths from $(0,0)$ to $((\mu n+c-\rh)/\nu,n)$. There are 
$\binom {n+(\mu n+c-\rh)/\nu}n$ such paths. Among them there
are some which stay below the line $\nu x=\mu y-\rh$. These are
counted by
$$\v{\L{(0,0)\to(\frac {\mu n+c-\rh}
{\nu},n)\mid \nu x\ge\mu y-\rh}}=w(n;c,\rh).$$
The rest consists of paths which cross the line $\nu x=\mu y-\rh$
somewhere. In such a lattice path consider the last step which
connects a lattice point outside the region $\nu x\ge \mu y-\rh$ to a lattice
point inside the region $\nu x\ge \mu y-\rh$, 
say $(\cl{(\mu l-\rh)/\nu}-1,l)$ to $(\cl{(\mu
l-\rh)/\nu},l)$. This defines a unique decomposition of such a path
into an arbitrary path from $(0,0)$ to $(\cl{(\mu l-\rh)/\nu}-1,l)$,
followed by a horizontal step, and then by a path in 
$$\L{(\cl{(\mu l-\rh)/\nu},l)\to((\mu n+c-\rh)/\nu,n)\mid \nu x\ge
\mu y-\rh}.$$
Putting everything together, we obtain
??Figure!!
\begin{align} &\binom {n+\frac {\mu n+c-\rh} {\nu}}n=\v{\L{(0,0)\to
((\mu n+c-\rh)/\nu,n)\mid \nu x\ge \mu y-\rh}}\notag\\
\notag %\label{e1.24a}
&\hskip1cm+\sum _{\rh< \mu l\le \mu n+c} ^{}\binom {l+\cl{\frac
{\mu l-\rh} {\nu}}-1}l \\
&\cdot\v{\L{(\cl{(\mu l-\rh)/\nu},l)\to((\mu n+c-\rh)/\nu,n)\mid \nu
x\ge\mu y-\rh}}\\
&=\v{\L{(0,0)\to
((\mu n+c-\rh)/\nu,n)\mid \nu x\ge \mu y-\rh}}\notag\\
\notag %\label{e1.24a}
&\hskip1cm+\sum _{r=0} ^{\nu-1}\underset {\rh+\nu\le \mu l+r\le \mu
n+c}
{\sum _{\mu l+r\equiv \rh\pmod\nu} ^{}}\binom {l+{\frac
{\mu l-\rh+r} {\nu}}-1}l \\
&\cdot\v{\L{({(\mu l-\rh+r)/\nu},l)\to((\mu n+c-\rh)/\nu,n)\mid \nu
x\ge\mu y-\rh}}\\
&=w(n;c,\rh)+\sum _{r=0} ^{\nu-1}\bigg(\sum _{\mu l+r\equiv \rh\pmod
\nu} ^{}w(n-l;c,r)\binom {l+\frac {\mu l+r-\rh} {\nu}-1}l
\notag\\
\label{e1.24b}
&\hskip3cm -\underset {\mu l+r\le\rh}{\sum _{\mu l+r\equiv \rh\pmod
\nu} ^{}}w(n-l;c,r)\binom {l+\frac {\mu l+r-\rh} {\nu}-1}l\bigg).
\end{align}
Note that the equation \eqref{e1.24b} also holds if $\mu n+c<\rh$ because
of our definition of $w(n;c,\rh)$ for the case $\mu n+c<\rh$.

If we define the matrix $F(z;a)$ by
\begin{equation} \label{e1.24c}
F(z;a):=\bigg(\suml _{\mu n+a\equiv0\pmod \nu} ^{}\binom {n+\frac
{\mu n+a+g-h} {n}}nz^n\bigg)_{0\le g,h\le \nu-1}\, ,
\end{equation}
equation \eqref{e1.24b} translates into the matrix identity
\begin{equation} \label{e1.24'}
F(z;c-\rh)=W(z;c,\rh)+W(z;c,0)\big(F(z;-\rh-\nu)-\Phi(z;\rh)\big).
\end{equation}
If in this identity we put $\rh=0$ we get
$$F(z;c)=W(z;c,0)+W(z;c,0)\big(F(z;-\nu)-\Phi(z;0)\big).$$
Now, because of our assumption $\nu<\mu$ we have from the definition
\eqref{e1.23b} of $\Phi(z;\rh)$ that $\Phi(z;0)=I$, the $\nu\times\nu$
identity matrix. Hence our last equation gives
\begin{equation} \label{e1.24d}
F(z;c)=W(z;c,0)F(z;-\nu).
\end{equation}

\smallskip
{\em Second step}. We define four matrices $V_1$, $V_2$, $\Lambda$,
$H$ as follows:
\begin{gather} \label{e1.23d}
V_1=\(u_h^g(z)\)_{0\le g,h\le \nu-1},\quad 
V_2:=\(u_g^{-h}(z)\)_{0\le g,h\le \nu-1},\quad 
\Lambda=\(\chi(g=h)\,u_g(z)\)_{1\le g,h\le \nu-1},\\
H:=\(\chi(g=h)\frac {1} {\nu-(\nu+\mu)zu_g(z)^\mu}\)_{0\le g,h\le
\nu-1},
\end{gather}
where $u_g(z)$ is given by \eqref{e1.23e}, as before, and 
$\chi(\mathcal A)$=1 if $\mathcal A$ is
true and $\chi(\mathcal A)$=0 otherwise.


Then we claim that
\begin{equation} \label{e1.25a}
F(z;c)=V_1\Lambda^cHV_2.
\end{equation}

For the proof of the claim consider the equation
\begin{equation} \label{e1.25b}
z=\frac {v(z)} {\big(1+v(z)\big)^{1+\frac {\mu} {\nu}}},
\end{equation}
to be solved for some formal power series $v(z)$. By the Lagrange inversion
?? with $g(z)=(1+z)^{1/\nu}$ and $f(z)=z/(1+z)^{1+\mu/\nu}$, the unique
power series solution of this equation satisfies
\begin{align} \notag
(1+v(z))^{\frac {1} {\nu}}&=\sum _{n\ge0} ^{}z^n\(\frac {1} {n}\coef{t^{-1}}\frac
{(1+t)^{\frac {1} {\nu}+(1+\frac {\mu} {\nu})n-1}} {t^n}\)\\
\notag
&=\sum _{n\ge0} ^{}z^n\frac {1} {\nu n}\binom {\frac {1} {\nu}+(1+\frac
{\mu} {\nu})n-1}{n-1}\\
\notag
&=\sum _{n\ge0} ^{}z^n\frac {1} {1+(\mu+\nu)n}\binom {\frac {1} {\nu}+(1+\frac
{\mu} {\nu})n}{n}.
\end{align}
So, comparing this with $u_0(z)$ in \eqref{e1.23},
we have
\begin{equation} \label{e1.25'}
u_0(z)=(1+v(z))^{1/\nu}.
\end{equation}

Now, by \eqref{e1.25b} we obtain
$$\frac {(1+v(z))^{\frac {c} {\nu}}} {1-(1+\frac {\mu}
{\nu})z(1+v(z))^{\frac {\mu} {\nu}}}=
\frac {(1+v(z))^{\frac {c} {\nu}}} {1-(1+\frac {\mu}
{\nu})\frac {v(z)} {(1+v(z))}},
$$
and therefore by the second form ?? of the Lagrange inversion with
??, we get
\begin{align} \notag
&\frac {(1+v(z))^{\frac {C} {\nu}}} {1-(1+\frac {\mu}
{\nu})z(1+v(z))^{\frac {\mu} {\nu}}}\\
\notag
&=\sum _{n\ge0} ^{}z^n\coef{t^{-1}}\frac {(1+z)^{\frac {C} {\nu}}}
{\(1-(1+\frac {\mu} {\nu})\frac {z} {1+z}\)}\cdot\frac 
{\(1-(1+\frac {\mu} {\nu})\frac {z} {1+z}\)} {z^{n+1}}(1+z)^{(1+\frac
{\mu} {\nu})n}\\
\notag
&=\sum _{n\ge0} ^{}z^n\coef{t^{n}}(1+z)^{\frac {C} {\nu}+(1+\frac {\mu}
{\nu})n}\\
&=\sum _{n\ge0} ^{}\binom {\frac {C} {\nu}+(1+\frac {\mu}
{\nu})n}nz^n.\label{e1.25c}
\end{align}
Let us write $f(z;C)$ for the last line in the above computation,
$$f(z;C):=\sum _{n\ge0} ^{}\binom {\frac {C} {\nu}+(1+\frac {\mu}
{\nu})n}nz^n.$$
It should be noted that the matrix $F(z;a)$, defined in
\eqref{e1.24c}, can be written as
\begin{equation} \label{e1.25d}
F(z;a)=(f(z;a+g-h))_{0\le g,h\le \nu-1}.
\end{equation}
Now, if we combine \eqref{e1.25c} with \eqref{e1.25'}, we obtain
\begin{equation} \label{e1.25e}
f(z;C)=\frac {u_0(z)^C} {1-(1+\frac {\mu} {\nu})zu_0(z)^\mu}.
\end{equation}
On the other hand, we have
\begin{align} \notag
f(z;C)&=\sum _{\nu n+C\equiv0\pmod\nu} ^{}\binom {\frac {C} {\nu}+(1+\frac
{\mu} {\nu}n)}nz^n\\
\notag
&=\sum _{\nu n+C\equiv0\pmod\nu} ^{}\binom {\frac {C} {\nu}+(1+\frac
{\mu} {\nu}n)}nz^n\frac {1} {\nu}\sum _{l=0} ^{\nu-1}e^{2\pi il(\mu
n+C)/\nu}\\
\notag
&=\frac {1} {\nu}\sum _{l=0} ^{\nu-1}e^{2\pi ilC/\nu}
\sum _{\nu n+C\equiv0\pmod\nu} ^{}\binom {\frac {C} {\nu}+(1+\frac
{\mu} {\nu}n)}n\(ze^{2\pi il\mu/\nu}\)^n\\
\notag
&=\frac {1} {\nu}\sum _{l=0} ^{\nu-1}\(e^{2\pi i/\nu}\)^{lc}
f\(z\(e^{2\pi i/\nu}\)^{l\mu};C\).
\end{align}
Combined with \eqref{e1.25e} this gives, writing $\om$ for $e^{2\pi
i/\nu}$,
\begin{align} \notag
f(z;C)&=\sum _{l=0} ^{\nu-1}\om^{lC}\frac {u_0\(z\om^{\mu l}\)^C}
{\nu-(\mu+\nu)z\om^{\mu l} u_0^\mu(z)\om^{\mu l}}\\
&=\sum _{l=0} ^{\nu-1}\frac {u_l(z)^C} {\nu-(\mu+\nu)zu_l^\mu(z)},
\label{e1.25f}
\end{align}
the last line because of $u_l(z)=\om^lu_0(z\om^{\mu l})$, see
\eqref{e1.23e}.
Recalling our remark \eqref{e1.25d}, we see 
that this last equation implies our claim \eqref{e1.25a}.

{\em Third step}. Now we are able to finish the proof of the theorem.
If we substitute \eqref{e1.25a} into \eqref{e1.24d}, and rearrange terms a
little, we get
\begin{equation} \label{e1.26a}
W(z;c,0)=V_1\Lambda^{c+\nu}V_1^{-1}.
\end{equation}
On the other hand, a combination of \eqref{e1.25a} and \eqref{e1.26a}
implies
$$F(z;c-\rh)=V_1\Lambda^{c+\nu}V_1^{-1}F(z;-\rh-\nu).$$
Use of this identity reduces equation \eqref{e1.24'} to
\begin{equation} \label{e1.26c}
W(z;c,\rh)=V_1\Lambda^{c+\nu}V_1^{-1}\Phi(z;\rh).
\end{equation}

{\em Fourth step}. If we compare \eqref{e1.26c} with \eqref{e1.23a}
we see that $M(z;c,\rh)=V_1\Lambda^{c+\nu}V_1^{-1}$. So it remains to
establish the claim \eqref{e1.23f} about the explicit form of the
coefficients of $V_1\Lambda^{c+\nu}V_1^{-1}$.

The matrices $V_1$ and $\Lambda$ are defined in \eqref{e1.23d}.
So the $(g,h)$-entry of $V_1\Lambda^{c+\nu}V_1^{-1}$ is given by
\begin{equation} \notag
\sum _{k=0} ^{\nu-1}u_k(z)^{c+\nu+g}\cdot \frac {(-1)^{k+h}\,(h,k)\text
{{}-minor of $V_1$}} {\det(V_1)}
=\frac {\det\tilde V_1} {\det V_1},
\end{equation}
where $\tilde V_1$ arises from $V_1$ by replacing the $h$-th row by
$\(u_0^{c+\nu+g}(z),\dots,u_{\nu-1}^{c+\nu+g}(z)\)$. In the matrix
$\tilde V_1$ we rearrange the rows so that the $h$-th row of $\tilde
V_1$ becomes the last row of the new matrix and the other rows keep
their relative position. Thus we see that the $(g,h)$-entry of
$V_1\Lambda^{c+\nu}V_1^{-1}$ equals
\begin{equation} \label{e1.27c}
(-1)^{\nu-h-1}\frac {\det_{0\le g,h\le \nu-1}\(u_h^{\la_g+g}(z)\)} 
{\det_{0\le g,h\le \nu-1}\(u_h^{g}(z)\)},
\end{equation}
where 
$$\La=(\la_0,\dots,\la_{\nu-1})=(0^{h-1}, 1^{\nu-h-1},c+g+1),$$
the notation $a^r$ denoting a sequence of $r$ $a$'s.
The quotient of determinants in
\eqref{e1.27c} is exactly the Schur function
$s_{(c+g+1,1^{\nu-h-1})}\big(u_0(z),\dots,u_{\nu-1}(z)\big)$, see
e.g\@. \index{Macdonald, Ian G.}Macdonald \cite{MacdAC}.
\end{proof}

It should be observed that equation \eqref{??} is exactly the matrix
formulation of \eqref{??} for large $C$??connection to
Niederhausen??


\index{Sato, M.}Sato \cite{SatoAA} also derived a result of similar type
for two parallel linear boundaries with rational slope. To be precise,
we want to enumerate all lattice
paths from an arbitrary starting point to an arbitrary end point 
staying below a given line $\nu x=\mu y-\rh$ and above 
another given line $\nu x=\mu y+\si$, where $\mu,\nu,\rh,\si$ are
nonnegative integers. Again, without loss of generality we may assume
that $\nu<\mu$ and that the starting point is the origin.

Following the approach we have taken earlier, 
we define the $\nu\times\nu$ matrix $T(z;c,\rh,\si)$ by
\begin{equation} \label{e1.28a}
T(z;c,\rh,\si):=\big(t(z;c+g,\rh+h,\si-h)\big)_{0\le g,h\le \nu-1},
\end{equation}
where 
\begin{equation} \label{e1.28b}
t(z;c,\rh,\si)=\sum _{\mu n+c\equiv\rh\pmod\nu} ^{}t(n;c,\rh,\si)\,z^n,
\end{equation}
with
\begin{multline} \label{e1.28c}
t(n;c,\rh,\si)=\begin{cases} \v{\L{(0,0)\to(\frac {\mu n+c-\rh}
{\nu},n)\mid \mu y+\si\ge\nu x\ge\mu y-\rh}}&\mu n+c\equiv \rh\pmod\nu\\
&\text {and }\mu n+c\ge\rh\\
\binom {n+\frac {\mu n+c-\rh} {\nu}}{n}&\mu n+c\equiv \rh\pmod\nu\\
&\text {and }\mu n+c<\rh.
\end{cases}\\
\end{multline}
Similar to the one boundary case, 
what the matrix $T(z;c,\rh,\si)$ contains is generating functions
of the path numbers $t(n;c,\rh,\si)$ 
that we want to evaluate. The definition of $t(n;c,\rh,\si)$ for $\mu n+c<\rh$
(in which case there cannot be any paths from $(0,0)$ to $(\frac {\mu n+c-\rh}
{\nu},n)$) is just for technical convenience. Basically, the matrix
$T(z;c,\rh,\si)$ is
\begin{multline} \label{e1.28d}
T(z;c,\rh,\si)=\Big(\sum _{\mu n+c+g-h\equiv \rh\pmod \nu} ^{}
\left\vert\L{(0,0)\to(\frac {\mu n+c+g-\rh-h}
{\nu},n)\mid\right. \\
\mu y+\si-h\ge\nu x\ge\mu y-\rh-g}\Big\vert\, z^n\Big)_{0\le g,h\le \nu-1}.
\end{multline}


The following theorem of \index{Sato, M.}Sato \cite[Theorem~4]{SatoAA} tells how to
compute $T(z;c,\rh,\si)$.

\begin{Theorem} \label{T1.8}
For any nonnegative integers $c$, $\rh$, $\si$, 
$\nu$, $\mu$, with $\nu<\mu$, we have
\begin{equation} \label{e1.28e}
T(z;c,\rh,\si)=\Phi(z;\rh+\si+1-c-\mu)\, \Phi^{-1}(z;\rh+\si+1)\,
\Phi(z;\rh),
\end{equation}
where $\Phi(z;\th)$ is given by \eqref{e1.23b}.

\end{Theorem}
\begin{proof} We proceed in a similar way as in the proof of
Theorem~\ref{T1.7}. Namely, first we derive a recurrence from
combinatorial considerations, which is subsequently trasformed into a
matrix equation from which finally \eqref{e1.28e} can be derived.

Let $\mu n+c\equiv \rh\pmod \nu$ and $\mu n+c> \rh+\si$. 
Consider paths from $(0,0)$ to $((\mu n+c-\rh)/\nu,n)$ which stay
below $\nu x=\mu y-\rh$. There are 
$w(z;c,\rh)$ such paths (see \eqref{e1.21c} for notation). 
Among them there
are some which also stay above the line $\nu x=\mu y+\si$. The number
of these is
$$\v{\L{(0,0)\to\(\frac {\mu n+c-\rh}
{\nu},n\)\mid \mu y+\si\ge\nu x\ge\mu y-\rh}}=t(n;c,\rh,\si).$$
The rest consists of paths which cross the line $\nu x=\mu y+\si$
somewhere. In such a lattice path consider the first step which
connects a lattice point inside the region $\nu x\le \mu y+\si$ to a lattice
point outside the region $\nu x\le \mu y+\si$, 
say $(\fl{(\mu l+\si)/\nu},l)$ to $(\fl{(\mu
l+\si)/\nu}+1,l)$. This defines a unique decomposition of such a path
into a path in 
$$\L{(0,0)\to (\fl{(\mu l+\si)/\nu},l)\mid \mu y+\si\ge\nu x\ge\mu y-\rh},$$
followed by a horizontal step, and then by a path in 
$$\L{(\fl{(\mu l+\si)/\nu}+1,l)\to((\mu n+c-\rh)/\nu,n)\mid \nu x\ge
\mu y-\rh}.$$
Putting everything together, we obtain
??Figure!!
\begin{align} &w(n;c,\rh)=\v{\L{(0,0)\to ((\mu n+c-\rh)/\nu,n)\mid \nu x\ge\mu
y-\rh}}\\
&=\v{\L{(0,0)\to
((\mu n+c-\rh)/\nu,n)\mid \mu y+\si\ge\nu x\ge \mu y-\rh}}\notag\\
\notag %\label{e1.24a}
&\hskip1cm+\sum _{0\le \mu l+\si< \mu n+c-\rh} ^{}
\v{\L{(0,0)\to (\fl{(\mu l+\si)/\nu},l)\mid \mu y+\si\ge\nu x\ge\mu y-\rh} }
\\
&\hskip2cm\cdot\v{\L{(\fl{(\mu l+\si)/\nu}+1,l)\to((\mu n+c-\rh)/\nu,n)\mid 
\nu x\ge\mu y-\rh}}\\
&=\v{\L{(0,0)\to
((\mu n+c-\rh)/\nu,n)\mid \mu y+\si\ge\nu x\ge \mu y-\rh}}\notag\\
\notag %\label{e1.24a}
&\hskip1cm+\sum _{r=0} ^{\nu-1}\underset {0\le \mu l+\si-r\le \mu
n+c-\rh-\nu}
{\sum _{\mu l+\si\equiv r\pmod\nu} ^{}}
\v{\L{(0,0)\to ({(\mu l+\si-r)/\nu},l)\mid \mu y+\si\ge\nu x\ge\mu y-\rh} }
\\
&\hskip2cm\cdot\v{\L{({(\mu l+\si-r)/\nu}+1,l)\to((\mu n+c-\rh)/\nu,n)\mid 
\nu x\ge\mu y-\rh}}\\
&=t(n;c,\rh,\si)+\sum _{r=0} ^{\nu-1}\bigg(
\sum _{\mu l+\si
\equiv r\pmod\nu} ^{}t(l;\si+\rh-r,\rh,\si)\,
w(n-l;c,\si+\rh+\nu-r)
\notag\\
%\label{e1.28f}
&\hskip3cm -\underset {\mu l+\si-r\ge \mu
n+c-\rh}{\sum _{\mu l+\si\equiv r\pmod
\nu} ^{}}t(l;\si+\rh-r,\rh,\si)\,
w(n-l;c,\si+\rh+\nu-r)\bigg),
\end{align}
or, after the index transformation $r\to \nu-1-r$,
\begin{align} \notag
&w(n;c,\rh)=t(n;c,\rh,\si)\\
&\quad +\sum _{r=0} ^{\nu-1}\bigg(
\sum _{\mu l+\si+r+1
\equiv 0\pmod\nu} ^{}t(l;\si+\rh+r+1-\nu,\rh,\si)\,
w(n-l;c,\si+\rh+r+1)
\notag\\
&\hskip3cm -\underset {\mu l+\si+r+1-\nu\ge \mu
n+c-\rh}{\sum _{\mu l+\si+r+1\equiv 0\pmod
\nu} ^{}}t(l;\si+\rh+r+1-\nu,\rh,\si)\,
w(n-l;c,\si+\rh+r+1)\bigg).
\label{e1.28f}
\end{align}
The equation \eqref{e1.28f} also holds if $\mu n+c\le\rh+\si$.
For, if $\rh+\si\ge\mu n+c\ge \rh$ then no path from the origin to
the end point $\big((\mu n+c-\rh)/\nu,n\big)$ can have a point below
the line $\nu x=\mu y+\si$, since any point $(a,b)$ of such a path
satisfies 
$$\nu a\le \nu\frac {\mu n+c-\rh} {\nu}\le \si\le \mu y+\si.$$
Therefore the sums in \eqref{e1.28f} are empty, and so \eqref{e1.28f}
is true since $t(n;c,\rh,\si)$ must equal $w(n;c,\rh)$ since the
boundary $\nu x=\mu y+\si$ can never be crossed in this case.
On the other hand, if $\mu n+c<\rh$ then the definitions of 
$t(n;c,\rh,\si)$ and $w(n;c,\rh)$ in this exceptional case guarantee
the validity of \eqref{e1.28f}, the sums in \eqref{e1.28f} being
again empty.

Equation \eqref{e1.28f} implies the following identity for the
associated matrices,
\begin{multline} \label{e1.28g}
W(z;c,\rh)=T(z;c,\rh,\si)\\
\hskip.5cm+\big(W(z;c,\rh+\si+1)-
\Phi(z;\rh+\si+1-c-\nu)\big)T(z;\rh+\si+1-\nu,\rh,\si).
\end{multline}
If in this identity we put $c=\rh+\si+1-\nu$ we get
$$
W(z;\rh+\si+1-\nu,\rh)=
W(z;\rh+\si+1-\nu,\rh+\si+1)T(z;\rh+\si+1-\nu,\rh,\si),
$$
again because our assumption $\nu<\mu$ implies that
$\Phi(z;0)$ equals the $\nu\times\nu$
identity matrix. If we use \eqref{e1.23a} in this equation, we find
\begin{equation} \label{e1.28h}
T(z;\rh+\si+1-\nu,\rh,\si)=\Phi^{-1}(z;\rh+\si+1)\,\Phi(z;\rh).
\end{equation}
Now, if we substitute \eqref{e1.28h} and \eqref{e1.23a} into \eqref{e1.28g}
then we obtain \eqref{e1.28e} after simplification.

\end{proof}



\begin{Example}As an illustration, let us again consider the case
$\nu=2$, $\mu=3$. By \eqref{e1.28c}, the quantity $t(n;c,\rh,\si)$ 
represents the
number of all lattice paths from $(0,0)$ to $((3n+c-\rh)/2,n)$ which
stay below the line $2x= 3y-\rh$ and above the line $2x=3y+\si$, 
where $c\equiv 3n-\rh\pmod2$, i.e.,
$c\equiv n+\rh\pmod2$.
??Figure

By definition \eqref{e1.20a}, we have
\begin{align} \notag
T(z;c,\rh)&=\big(t(z;c+g,\rh+h,\si-h)\big)_{0\le g,h\le 1}\\
&=\begin{pmatrix} t(z;c,\rh,\si)&t(z;c,\rh+1,\si-1)\\
t(z;c+1,\rh,\si)&t(z;c+1,\rh+1,\si-1)\end{pmatrix}.\notag
\end{align}
By Theorem~\ref{T1.8}, it can be written as
\begin{align} \notag
T(z;c,\rh,\si)=&\begin{pmatrix} \phi(z;\rh+\si-c-1)&
\phi(z;\rh+\si-c)\\
\phi(z;\rh+\si-c-2)&\phi(z;\rh+\si-c-1)\end{pmatrix}\\
&\times \begin{pmatrix} \phi(z;\rh+\si+1)&
\phi(z;\rh+\si+2)\\
\phi(z;\rh+\si)&\phi(z;\rh+\si+1)\end{pmatrix}^{-1}\\
&\times\begin{pmatrix} \phi(z;\rh)&
\phi(z;\rh+1)\\
\phi(z;\rh-1)&\phi(z;\rh)\end{pmatrix},\label{e1.29a}
\end{align}
where
\begin{equation} \notag
\phi(z;a)=\underset{\mu l\le a}{\sum _{\mu l\equiv
a\pmod\nu}
^{}}(-1)^l\binom {(a-\mu l)/\nu}lz^l.
\end{equation}

In particular, if $c=\si$ and $\rh=0$, so that we are interested
e.g\@.?? in
the number of all lattice paths from $(0,0)$ to $((3n+c)/2,n)$ which
stay below the line $2x= 3y$ and above the line $2x=3y+c$ (the reader
should observe that this means that the starting point is on the
first line whereas the end point is on the second line), then our
formula \eqref{e1.29a} reduces to
\begin{align} \notag
T(z;c,\rh)&=\begin{pmatrix} t(z;c,0,c)&t(z;c,1,c-1)\\
t(z;c+1,0,c)&t(z;c+1,1,c-1)\end{pmatrix}\\
&=\frac {1} {\phi^2(z;c+1)-\phi(z;c)\phi(z;c+2)}
\begin{pmatrix} \phi(z;c)&\phi(z;c+1)\\0&0\end{pmatrix}.
\end{align}
Thus we obtain
\begin{align} \notag
t(z;c,0,c)&=\sum _{ n\equiv c\pmod2} ^{}
\v{\L{(0,0)\to(\frac {3 n+c}
{2},n)\mid 3 y+c\ge2 x\ge3 y}}\,z^n\\
&=\frac {\phi(z;c)} {\phi^2(z;c+1)-\phi(z;c)\phi(z;c+2)},
\end{align}
with 
$$\phi(z;a)=\underset{3 l\le a}{\sum _{3 l\equiv
a\pmod2}
^{}}(-1)^l\binom {(a-3 l)/2}lz^l.
$$


\end{Example}


\section{Simple paths with general boundaries} \label{s1.6}
The most general problem to encounter is to count paths in a region
that is bounded by nonlinear upper and lower boundaries as exemplified
in Figure~\ref{F1.6}.
\begin{Figure}\label{F1.6}
$$
\Gitter(8,9)(0,0)
\Koordinatenachsen(0,9)(1,-1)
\Pfad(0,0),22111221221221\endPfad
\PfadDicke{.5pt}
\SPfad(0,3),12212212111\endSPfad
\SPfad(0,0),12112122211222\endSPfad
\Label\ro{a_1}(0,3)
\Label\ro{a_2}(1,5)
\Label\ro{a_3}(2,7)
\Label\ro{a_4}(3,8)
%\Label\ro{a_5}(4,8)
%\Label\ro{a_6}(5,8)
\Label\ro{\hskip18pt(n,a_n)}(6,8)
\Label\lu{(0,b_1)\hskip14pt}(0,0)
\Label\ru{b_1}(0,0)
\Label\ru{b_2}(1,1)
\Label\ru{b_3}(2,1)
\Label\ru{b_4}(3,2)
%\Label\ru{b_5}(4,5)
%\Label\ru{b_6}(5,5)
\Label\ro{\raise-10pt\hbox{$y_1$}}(0,2)
\Label\ro{\raise-10pt\hbox{$y_2$}}(1,2)
\Label\ro{\raise-10pt\hbox{$y_3$}}(2,2)
\Label\ro{\raise-10pt\hbox{$y_4$}}(3,4)
\DickPunkt(0,0)
\DickPunkt(6,8)
\hskip4cm
$$
\end{Figure}

To have a convenient notation, let $a_1\le a_2\le \dots\le a_n$ and
$b_1\le b_2\le \dots\le b_n$ be integers with $a_i\ge b_i$. We
abbreviate $\mathbf a=(a_1,a_2,\dots,a_n)$ and $\mathbf
b=(b_1,b_2,\dots,b_n)$. By $\L{(0,b_1)\to (n,a_n)\mid \mathbf a\ge \mathbf
y\ge \mathbf b}$ we denote the set of all lattice paths from $(0,b_1)$
to $(n,a_n)$ that satisfy the property that for all $i=1,2,\dots,n$
the height $y_i$ of the $i$-th horizontal step is in the interval
$[b_i,a_i]$. If we also write $\mathbf y(P)=(y_1,y_2,\dots,y_n)$ for the
sequence of horizontal steps of a path $P$, then the notation just
introduced explains itself. Pictorially (see Figure~\ref{F1.6}) the
described restriction means that we consider paths in a ladder-shaped
region, the upper ladder being determined by $\mathbf a$, the lower
ladder being determined by $\mathbf b$.

Curiously enough, the most conceptual and most elegant way to attack
this problem is by seemingly complicating it, namely by replacing our
restricted (single) lattice paths by whole {\em families of paths\/}, more
precisely by families of {\em \index{lattice paths, 
nonintersecting}\index{nonintersecting}nonintersecting\/} 
(by which we actually mean
{\em non-touching\index{lattice paths, non-touching}}; 
see Chapter~\ref{ch2}) lattice paths. This transformation
works as follows. First, given any lattice path $P$ from $(0,b_1)$ to
$(n,a_n)$, we encode $P$ by its sequence 
\glossary{$\mathbf y(P)$}$\mathbf y(P)=(y_1,y_2,\dots,y_n)$
of heights of its horizontal steps, see Figures~\ref{F1.6} and
\ref{F1.7}.a. Clearly, this sets up a one-to-one
correspondence between $\L{(0,b_1)\to (n,a_n)\mid \mathbf a\ge \mathbf
y\ge \mathbf b}$ and sequences $(y_1,y_2,\dots,y_n)$ that satisfy
$a_i\ge y_i\ge b_i$, $i=1,2,\dots,n$. Such a sequence is now replaced
by a set $(P_1,P_2,\dots,P_n)$ of lattice paths $P_i$, where for
$i=1,2,\dots, n$ the path $P_i$ runs from $(n-i,b_i+i)$ to
$(n+1-i,a_i+i)$, having its unique horizontal step at height $y_i+i$.
This can be achieved by a series of transformations, as is illustrated
in Figure~\ref{F1.7}, which displays an example 
with $n=6$, $\mathbf a=(3,5,7,8,8,8)$,
$\mathbf b=(0,1,1,2,5,5)$, $\mathbf y(P_0)=(2,2,2,4,6,8)$.
\begin{figure}
\begin{Figure}\label{F1.7}
$$
\underset {\text {a. A bounded lattice path}}
{
\Gitter(8,9)(0,0)
\Koordinatenachsen(8,9)(0,0)
\Pfad(0,0),22111221221221\endPfad
\Label\l{P_0}(4,6)
\PfadDicke{.5pt}
\SPfad(0,3),12212212111\endSPfad
\SPfad(0,0),12112122211222\endSPfad
\Label\ro{3}(0,3)
\Label\ro{5}(1,5)
\Label\ro{7}(2,7)
\Label\ro{8}(3,8)
\Label\ro{8}(4,8)
\Label\ro{8}(5,8)
\Label\ru{0}(0,0)
\Label\ru{1}(1,1)
\Label\ru{1}(2,1)
\Label\ru{2}(3,2)
\Label\ru{5}(4,5)
\Label\ru{5}(5,5)
\Label\ro{2}(0,2)
\Label\ro{2}(1,2)
\Label\ro{2}(2,2)
\Label\ro{4}(3,4)
\Label\ro{6}(4,6)
\DickPunkt(0,0)
\DickPunkt(6,8)
\hskip5cm
}
\raise3cm\hbox{$\longleftrightarrow$\hskip.5cm}
\underset {\text {b. Family of lattice paths}}
{
\Gitter(8,9)(0,0)
\Koordinatenachsen(8,9)(0,0)
\PfadDicke{1pt}
\hskip-2pt
\raise-2pt\hbox to0pt{
\Pfad(0,2),2\endPfad
\Pfad(0,2),1\endPfad
\Pfad(1,0),22\endPfad
\hss}
\hskip2pt
\Pfad(1,2),222\endPfad
\Pfad(1,2),1\endPfad
\Pfad(2,1),2\endPfad
\hskip2pt
\raise2pt\hbox to0pt{
\Pfad(2,2),22222\endPfad
\Pfad(2,2),1\endPfad
\Pfad(3,1),2\endPfad
\hss}
\hskip-2pt
\Pfad(3,4),2222\endPfad
\Pfad(3,4),1\endPfad
\Pfad(4,2),22\endPfad
\Pfad(4,6),22\endPfad
\Pfad(4,6),1\endPfad
\Pfad(5,5),2\endPfad
\Pfad(5,8),1\endPfad
\Pfad(6,5),222\endPfad
\DickPunkt(0,3)
\DickPunkt(1,5)
\DickPunkt(2,7)
\DickPunkt(3,8)
\DickPunkt(4,8)
\DickPunkt(5,8)
\DickPunkt(1,0)
\DickPunkt(2,1)
\DickPunkt(3,1)
\DickPunkt(4,2)
\DickPunkt(5,5)
\DickPunkt(6,5)
\PfadDicke{.5pt}
\SPfad(0,3),12212212111\endSPfad
\SPfad(0,0),12112122211222\endSPfad
\hskip5cm
}
$$
$$
\raise7cm\hbox to0pt{\hskip9cm$\updownarrow$\hss}
\underset {\text {d. Family of nonintersecting lattice paths}}
{
\Einheit.4cm
\PfadDicke{1pt}
\Gitter(8,15)(0,0)
\Koordinatenachsen(8,15)(0,0)
\Pfad(5,1),2212\endPfad
\Pfad(4,3),21222\endPfad
\Pfad(3,4),2122222\endPfad
\Pfad(2,6),2212222\endPfad
\Pfad(1,10),2122\endPfad
\Pfad(0,11),2221\endPfad
\DickPunkt(5,1)
\DickPunkt(6,4)
\DickPunkt(4,3)
\DickPunkt(5,7)
\DickPunkt(3,4)
\DickPunkt(4,10)
\DickPunkt(2,6)
\DickPunkt(3,12)
\DickPunkt(1,10)
\DickPunkt(2,13)
\DickPunkt(0,11)
\DickPunkt(1,14)
\hskip3cm
}
\raise3cm\hbox{\hskip0cm$\longleftrightarrow$\hskip0cm}
\underset {\text {c. Lattice paths shifted by one unit relative to
each other}}
{
\Einheit.4cm
\Gitter(8,15)(0,0)
\Koordinatenachsen(8,15)(0,0)
\PfadDicke{1pt}
\Pfad(0,3),2\endPfad
\Pfad(0,3),1\endPfad
\Pfad(1,1),22\endPfad
\Pfad(1,4),222\endPfad
\Pfad(1,4),1\endPfad
\Pfad(2,3),2\endPfad
\Pfad(2,5),22222\endPfad
\Pfad(2,5),1\endPfad
\Pfad(3,4),2\endPfad
\Pfad(3,8),2222\endPfad
\Pfad(3,8),1\endPfad
\Pfad(4,6),22\endPfad
\Pfad(4,11),22\endPfad
\Pfad(4,11),1\endPfad
\Pfad(5,10),2\endPfad
\Pfad(5,14),1\endPfad
\Pfad(6,11),222\endPfad
\DickPunkt(0,4)
\DickPunkt(1,7)
\DickPunkt(2,10)
\DickPunkt(3,12)
\DickPunkt(4,13)
\DickPunkt(5,14)
\DickPunkt(1,1)
\DickPunkt(2,3)
\DickPunkt(3,4)
\DickPunkt(4,6)
\DickPunkt(5,10)
\DickPunkt(6,11)
\hskip3.5cm
}
$$
\end{Figure}
\end{figure}

What becomes immediately evident from the Figure~\ref{F1.7} is, that the
construction guarantees that no two of the lattice paths
$P_1,P_2,\dots,P_n$ have a point in common, and its converse, namely 
that any family
$(P_1,P_2,\dots,P_n)$ of lattice paths, where $P_i$ runs from
$(n-i,b_i+i)$ to $(n+1-i,a_i+i)$ and no two of the paths have a point
in common, corresponds to a sequence $(y_1,y_2,\dots ,y_n)$ with
$a_i\ge y_i\ge b_i$. 
Thus we have set up a
one-to-one correspondence between $\L{(0,b_1)\to (n,a_n)\mid \mathbf
a\ge \mathbf y\ge \mathbf b}$ and the set of all families
$(P_1,P_2,\dots,P_n)$ of nonintersecting lattice paths, where 
$P_i$ runs from $(n-i,b_i+i)$ to $(n+1-i,a_i+i)$. As we shall learn
from Chapter~\ref{ch2}, the main theorem on nonintersecting lattice
paths (Theorem~\ref{T2.1})
immediately gives the answer to our counting problem.

\begin{Theorem} \label{T1.15}
Let $\mathbf a=(a_1,a_2,\dots,a_n)$ and $\mathbf b=(b_1,b_2,\dots,b_n)$ be
integer sequences with $a_1\le a_2\le \dots\le a_n$, $b_1\le b_2\le
\dots\le b_n$, and $a_i\ge b_i$, $i=1,2,\dots,n$. The number of all
paths from $(0,b_1)$ to $(n,a_n)$ satisfying the property that 
for all $i=1,2,\dots,n$ the height of the $i$-th horizontal step is
between $b_i$ and $a_i$ is given by
\begin{equation} \label{e1.30}
\v{\L{(0,b_1)\to (n,a_n)\mid \mathbf a\ge \mathbf y\ge \mathbf b}}=
\det_{1\le i,j\le n}\(\binom {a_i-b_j+1}{j-i+1}\). 
\end{equation}
\end{Theorem}
\begin{proof}Apply Theorem~\ref{T2.1} with $A_i=(n-i,b_i+i)$,
$E_i=(n+1-i,a_i+i)$.
\end{proof}
Originally, the above result was derived by 
\index{Kreweras, Germain}Kreweras \cite{KrewAB}
using recurrence relations. In the one-sided boundary case, the
result was given by 
\index{Narayana, T. V.}Narayana \cite{NaraAA??}. He used properties of
the determinant and induction to derive the result (see 
\index{Mohanty, Sri Gopal}Mohanty \cite[p.~??]{MohaAE}).
The above proof is due to \index{Sulanke, Robert A.}Sulanke \cite{SulaAC}.

Of course, with increasing $n$ this formula will become less
tractable. An alternative formula can be obtained by rotating the
whole picture by $90^\circ$ and applying formula \eqref{e1.30} to the
new situation. Now the size of the determinant is $a_n$, which is smaller 
than before if
$a_n<n$, i.e., if the difference between the $y$-coordinates of
end and starting point is less than the difference between the
respective $x$-coordinates. 

In some cases, a different type of
formula might be preferrable, which we are going to describe next.
This different type of formula is derived by a method which we call
{\em dummy path technique\/}\index{dummy path
technique}\index{path, dummy},
as proposed
in \index{Krattenthaler, Christian}Krattenthaler and \index{Mohanty,
Sri Gopal}Mohanty 
\cite{KrMoAA}. Again, it comes from
nonintersecting lattice paths. It is based on the following
observation (see \index{Stanley, Richard P.}Stanley \cite[??]{StanAP}). 

\begin{Lemma} \label{T1.16}
Let $C_1,C_2,\dots,C_n$ be pairwise distinct points in $\Z^2$. Then
the number of lattice paths from $(a,b)$ to $(c,d)$ which avoid
$C_1,C_2,\dots, C_n$ is given by
\begin{equation} \label{e1.31}
\det_{1\le i,j\le n+1}\big(\v{L(A_j\to E_i)}\big) ,
\end{equation}
where $A_1=(a,b)$, $A_2=C_1$, \dots, $A_{n+1}=C_{n+1}$, $E_1=(c,d)$,
$E_2=C_1$, \dots, $E_{n+1}=C_n$.
\end{Lemma}
\begin{proof}We reformulate our counting problem in the weird way that we
want to determine the number of families $(P_1,P_2,\dots,P_{n+1})$ of
nonintersecting lattice paths, where $P_1$ runs from $A_1=(a,b)$ to
$E_1=(c,d)$, and for $i=1,2,\dots,n$ the ``dummy path" $P_{i+1}$ runs
from $A_{i+1}=C_i$ to $E_{i+1}=C_i$. By Theorem~\ref{T2.1}, with
$\SS=\{(1,0), (0,1)\}$, $A_i$ and $E_i$ as above, this number would
equal the determinant in \eqref{e1.31}, provided the
compatability condition is true. Indeed, suppose that $(P_1,
P_2,\dots,P_{n+1})$ is a family of nonintersecting lattice paths,
where for $i=1,2,\dots,n+1$ the path 
$P_i$ runs from $A_{\si(i)}$ to $E_i$, for
some permutation $\si\in\S_{n+1}$. Suppose that $\si(i)\ne i$ for some
$i\ge 2$. Then the path $P_i$ starts at $A_{\si(i)}=C_{\si(i)-1}$ and
terminates at $E_i=C_{i-1}$. Since $C_{\si(i)-1}\ne C_{i-1}$, there
must be another path, $P_j$ say, starting in $C_{i-1}$. But then $P_i$
and $P_j$ would intersect in $C_{i-1}$, which is absurd. Therefore
$\si(i)=i$ for all $i=2,3,\dots,n+1$, hence also for $i=1$.
\end{proof}


(??refer to a Figure??)

Now, in order to count paths from $(0,b_1)$ to $(n,a_n)$ which stay
between the ladder-shaped boundaries induced by $\mathbf a$ and $\mathbf
b$, we would proceed by counting all paths from $(0,b_1)$ to $(n,a_n)$
which avoid the points $(0,a_1+1)$, $(1,a_2+1)$, \dots,
$(n-2,a_{n-1}+1)$, $(2,b_2-1)$, \dots, $(n,b_{n}-1)$. By
Lemma~\ref{T1.16} we would obtain a
$(2n-1)\times(2n-1)$-determinant for the desired number. 
In general, this is of course much
worse than the $n\times n$ determinant in Theorem~\ref{T1.15}.
However, this determinant would reduce in size if some of the $a_i$'s
would equal $a_n$ or some of the $b_i$'s would equal $b_1$, which is
reflected by the fact that one could forget about dummy paths at
points $(i,a_n+1)$ or $(i,b_1-1)$. For concreteness, we state what is
obtained by the dummy path technique for the one-boundary case
$b_i\equiv0$. The reader should be reminded, that also this
determinant would reduce in size if some of the $a_i$'s would equal
$a_n$. The result was first derived in \index{Mohanty, Sri Gopal}Mohanty 
\cite[??]{MohaAE} by use of
recurrence, similar in type to \eqref{e1.24a}. The method in
\index{Mohanty, Sri Gopal}Mohanty \cite{MohaAE} 
also led to a formula for the two-boundary case which
however is not as elegant as the one suggested above (and also not as
the one in Theorem~\ref{T1.15}).
(The reader should be warned that there are misprints in
\index{Mohanty, Sri Gopal}Mohanty \cite[??]{MohaAE}.)

\begin{Theorem} \label{T1.17}
Let $\mathbf a=(a_1,a_2,\dots,a_n)$ be a sequence of integers satisfying
$a_1\le a_2\le \dots\le a_n$. The number of all lattice paths from
$(0,0)$ to $(n,a_n)$ satisfying the property that for $i=1,2,\dots,n$
the height of the $i$-th horizontal step is at most $a_i$ equals
\begin{equation} \label{e1.32} 
\v{\L{(0,0)\to(n,a_n)\mid \mathbf a\ge \mathbf y}}=\det_{1\le i,j\le n}
(d_{ij}),
\end{equation}
where
$$d_{ij}=\begin{cases} \binom{a_n+n} n &i=j=1\\
\binom {a_{n-i+1}+n-i+1}{n-i}&i\ne1,\ j=1\\
\binom {a_n-a_{n-j+1}+j-1}{j}&i=1,\ j\ne1\\
\binom {a_{n-i+1}-a_{n-j+1}+j-i}{j-i}&i\ne1,\ j\ne1.\end{cases}$$
\end{Theorem}
\begin{proof}Apply Lemma~\ref{T1.16} with $(a,b)=(0,0)$, $(c,d)=(n,a_n)$,
$C_i=(n-i-1,a_{n-i}+1)$, $i=1,2,\dots,n-1$.
\end{proof}


\section{A first excursion to weighted counting} \label{s1.7}. 
\index{weighted
counting}
In this section we lay the ground work for weighted counting of
lattice paths. More precisely, given a function $w$ acting on
lattice paths, called a {\em
weight function\/}\index{weight}\index{weight function}, 
we are interested in determining the generating
function $GF(\mathcal M;w)=\sum _{P} ^{}w(P)$, where the sum is over all
lattice paths $P$ in some particular set $\mathcal M$ of lattice paths. In
most cases $w$ will map $P$ to a monomial $q^{s(P)}$ (or more
generally $q_1^{s_1(P)}q_2^{s_2(P)}\cdots q_m^{s_m(P)}$), where $s(P)$
(respectively $s_1(P),s_2(P),\dots, s_m(P)$) is some ``lattice path
statistics"\index{path statistics}\index{lattice path
statistics}\index{statistics}, that is an integer-valued (very rarely
real-valued) function on lattice paths. Once an expression for
$GF(\mathcal M;q^{s(.)})$, say, is obtained, extraction of the coefficient
of $q^n$ gives the number of paths $P$ in $\mathcal M$ for which the value
$s(P)$ is exactly $n$. Before reading this section the reader should
recall the $q$-notations introduced in the introduction (??).

In this section we exclusively concentrate on one statistics,
namely the {\em area statistics}. (More remarks, that here are basic things,
also important for the folowing??) To be more concrete, let $P$ be a
path from $(a,b)$ to $(c,d)$. We denote the {\em signed
area\/}\index{area} of the region between $P$ and the $x$-axes by
$\area(P)$\glossary{$\area(P)$}\index{area of a path}\index{path, 
area}. 
For the path $P_1$ in Figure~\ref{F1.8a} we would have
$\area(P_1)=7$, for the path $P_2$ we would have $\area(P_2)=1$.
\begin{Figure}\label{F1.8a}
$$
\Gitter(4,5)(0,0)
\Koordinatenachsen(4,5)(0,0)
\Pfad(0,1),122112\endPfad
\SPfad(3,0),222\endSPfad
\DickPunkt(0,1)
\DickPunkt(3,4)
\Label\u{P_1}(2,3)
\hbox{\hskip5cm}
\Gitter(5,4)(-2,-2)
\Koordinatenachsen(5,4)(-2,-2)
\Pfad(-2,-2),12112211221\endPfad
\SPfad(-2,-2),22\endSPfad
\SPfad(4,0),222\endSPfad
\DickPunkt(-2,-2)
\DickPunkt(4,3)
\Label\o{P_2}(2,1)
\hskip2.5cm
$$
\end{Figure}
Let $P$ be a lattice path from $(a,b)$ to $(c,d)$.
Recalling the encoding $\mathbf y(P)=(y_1,y_2,\dots,y_{c-a})$ in terms of
heights of horizontal steps of $P$ (see Section~\ref{s1.6}), we
observe that 
\begin{equation} \label{e1.33} 
\area(P)=y_1+y_2+\dots+y_{c-a}\ .
\end{equation}

The study of the area statistics arises in ?? Also it immediately
connects to {\em partition theory\/}\index{partition of an integer}.
This connection is elaborated in the next paragraph. A general
reference for partition theory is 
\index{Andrews, George E.}Andrews \cite{AndrAF}.

A ({\em linear\/}) {\em partition\/}\index{linear partition} of the
positive integer $m$ is a sequence $\La=(\la_1,\la_2,\dots,\la_r)$ of
positive integers $\la_1\ge\la_2\ge\dots\ge\la_r>0$ and
$\la_1+\la_2+\dots +\la_r=m$. If $\La$ is a partition of $m$ we also
say that {\em $\La$ partitions $m$\/} and write $\La\vdash
n$\glossary{$\vdash$}\glossary{$\La\vdash n$}. The
components $\la_i$ are called {\em parts\/}\index{part of a linear
partition}\index{partition, part}\index{linear partition, part} of
$\La$. We write $n(\La)=\la_1+\la_2+\dots+\la_r$\glossary{n(\La)} 
for the sum of all
parts of $\La$ and call it the {\em norm\/}\index{linear partition,
norm}\index{partition, norm}\index{norm of a linear partition} of
$\La$. A partition $\La$ is frequently viewed pictorially in form of a
so-called {\em Ferrer's diagram\/}\index{Ferrer's diagram}. In English
convention, the Ferrer's diagram of $\La=(\la_1,\la_2,\dots,\la_r)$ is
the collection of $r$ left-justified rows, the $i$-th row consisting
of $\la_i$ cells (see Figure~\ref{F1.8}).

\begin{Figure}\label{F1.8}
$$\La=(6,6,5,2,1)\quad \quad \quad 
\begin{array}{|c|c|c|c|c|c|}
\hline
\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut
\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut\hphantom{,}\\
\hline
\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut
\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut\hphantom{,}\\
\hline
\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\mathstrut
\hphantom{,}&\mathstrut\hphantom{,}&\omit\\
\cline{1-5}
\mathstrut\hphantom{,}&\mathstrut\hphantom{,}&\omit&\omit&\omit&\omit\\
\cline{1-2}
\mathstrut\hphantom{,}&\omit&\omit&\omit&\omit&\omit\\
\cline{1-1}
\end{array}
$$
\centerline{\small A partition and its Ferrer's diagram}
\end{Figure}

An immediate observation is that, by the encoding in terms of heights
of horizonatal steps, lattice paths from $(0,0)$ to
$(c,d)$ with area $m$ bijectively correspond to partitions of $m$ with
at most $c$ parts, each part being at most $d$. (This is also seen
pictorially by reflecting the region between such a lattice path and
the $x$-axes with respect to the line $x=y$. Thus this region is turned into a
Ferrer's diagram corresponding to one of the above described
partitions.) To enumerate the latter is a basic question in partition
theory. A closed expression is not available. But a nice answer can be
given in generating function form. The next theorem (see in particular
\eqref{e1.35}) tells that the generating function $\sum _{\La}
^{}q^{n(\La)}$ for these partitions $\La$ is a
$q$-binomial coefficient\index{$q$-binomial coefficient}. 
Starting with this expression for
the generating function, Andrews\index{Andrews, George E.} and 
Almkvist\index{Almkvist, Gert} \cite{AlAnAA} derived an
asymptotic expression for the number of restricted partitions. We
remark that the theorem below is a $q$-analogue of \eqref{e1.1}.

\begin{Theorem} \label{T1.18}
The generating function $\sum _{P} ^{}q^{\area(P)}$ for all paths from
$(a,b)$ to $(c,d)$ is
\begin{equation} \label{e1.34} 
\GF{\L{(a,b)\to (c,d)};q^{\area(.)}}=q^{b(c-a)}\qbinom {c+d-a-b}{c-a}q.
\end{equation}
\end{Theorem}
\begin{proof}By a translation in direction $(-a,-b)$ we see that 
$$\GF{\L{(a,b)\to (c,d)};q^{\area(.)}}=
q^{b(c-a)}\GF{\L{(0,0)\to (c-a,d-b)};q^{\area(.)}}.$$
Therefore it suffices to establish
\begin{equation} \label{e1.35} 
\GF{\L{(0,0)\to (c,d)};q^{\area(.)}}=\qbinom{c+d}cq.
\end{equation}
This is easily verified inductively, by using the lattice path recurrence
\begin{multline} \notag
\GF{\L{(0,0)\to (c,d};q^{\area(.)}}=q^d\, \GF{\L{(0,0)\to
(c-1,d)};q^{\area(.)}}\\
\notag
+\GF{\L{(0,0)\to (c,d-1)};q^{\area(.)}},
\end{multline}
and comparing with the recurrence \eqref{e0.??} for $q$-binomial
coefficients.
\end{proof}

We point out yet another equivalent formulation of \eqref{e1.35}.
Recall (see ??) that lattice paths from $(0,0)$ to $(c,d)$ can be seen
as multiset pemutations of $\{1^c,2^d\}$ by writing a 1 for each
horizontal step and a 2 for each vertical step. A statistics for
permutations $\pi$ of multisets, introduced by MacMahon\index{MacMahon, 
Percy?? Alexander} 
\cite[??]{MacMAA??}, is the number of {\em
inversions\/}\index{inversion of a permutation}\index{permutation,
inversion} of $\pi$, for which we write $\inv(\pi)$. 
If $\pi=\pi_1\pi_2\dots\pi_r$ then an {\em
inversion\/} is a pair $(i,j)$ with $i<j$ and $\pi_i>\pi_j$.
??Example!! A moment's
thought shows that if $P$ is a path from $(0,0)$ to $(c,d)$, and
$\pi_P$ is the permutation of $\{1^c,2^d\}$ corresponding to $P$, then
$\area(P)=\inv(\pi_P)$, which can be checked in Figure~\ref{F1.8a}. 
Thus \eqref{e1.35} can also be formulated as
\begin{equation} \label{e1.36} \sum _{\pi} ^{}q^{\inv(\pi)}=
\qbinom {c+d}cq,
\end{equation}
where the sum is over all permutations of $\{1^c,2^d\}$. This result
is due to MacMahon\index{MacMahon, 
Percy Alexander} \cite[??]{MacMAA??}. A multidimensional
generalization of both Theorem~\ref{T1.18} and \eqref{e1.35} will be
given in ??. Lattice path counting based on other permutation
statistics is discussed in Chapter~\ref{??}, Section~??.

\medskip
Having answered the question of area counting of unrestricted paths,
we proceed by considering the area counting of paths with
restrictions. The simplest restriction to consider would be a linear
boundary of the type $x=\mu y$. Disappointingly, neither of the
Theorem~\ref{T1.1}, Corollary~\ref{T1.2}, Theorems~\ref{T1.3}--\ref{T1.6}
generalize. (However, Theorems~\ref{T1.1}, \ref{T1.3}, and
Corollary~\ref{T1.2} do generalize, if a different statistics is
considered. This connects to counting paths by their number of turns.
See Chapter~\ref{ch4}, Section~\ref{??}). There is only a $q$-analogue of the generating
function identity \eqref{e1.14}, which gives at least an implicit answer.

\begin{Theorem} \label{T1.19}
Let $\mu, k$ be nonnegative integers. Then 
\begin{multline} \label{e1.37} \sum _{n\ge0} ^{}\GF{\L{(0,0)\to (\mu
n+k,n)\mid x\ge \mu y};q^{\area(.)}}\\
 \frac {q^{\binom n2}z^n} {(1+z)
(1+qz) \cdots (1+q^{(\mu+1)n+k}z)}=1.
\end{multline}
\end{Theorem}
\begin{proof}Our proof works by multiplying both sides of \eqref{e1.37}
by $(1+z)(1+qz)\dots(1+q^{(\mu+1)N+k}z)$, for some nonnegative integer
$N$, and verifying that in the resulting formal power series the
coefficients of $z^l$ agree for all $l=0,1,\dots,N$.
??In den Notizen behaupte ich, dass es reicht $z^N$ statt $z^l$ zu
betrachten?? Having proved
this to hold for all $N$, \eqref{e1.37} would be established.

If we do this multiplication, \eqref{e1.37} is turned into
\begin{multline} \label{e1.38}
\sum _{n\ge0} ^{}\GF{\L{(0,0)\to (\mu
n+k,n)\mid x\ge \mu y};q^{\area(.)}}\\
q^{\binom n2}z^n (1+q^{(\mu+1)n+k+1}z)\cdots (1+q^{(\mu+1)N+k})\\ 
=(1+z)(1+qz)\cdots(1+q^{(\mu+1)N+k}z).
\end{multline}
Note that if $n>N$ then the expression in the second line of
\eqref{e1.38} should read as
$$q^{\binom n2}\frac {z^n} {(1+q^{(\mu+1)N+k+1}z)\cdot
(1+q^{(\mu+1)n+k})}.$$
In order to prove that the coefficients of $z^l$ on both sides of
\eqref{e1.38} agree, we would have to prove
\begin{equation} \label{e1.39} 
\sum _{n\ge0} ^{}\underset {U\in
S_{l-n}(\{(\mu+1)n+k+1,\dots,(\mu+1)N+k\})}{\sum _{P\in L((0,0) \to
(\mu n+k,n)\mid x\ge \mu y)} ^{}}\hskip-0.5cm q^{\binom
n2}q^{\area(P)} q^{\V U}=\sum _{V\in S_l(\{0,1,\dots,(\mu+1)N+k\})}
^{}\hskip-.3cm q^{\V V},
\end{equation}
where $S_k(\mathcal M)$ was defined before \eqref{e1.17}, and $\V M$
stands for the sum of all the elements of a set $M$. We prove
\eqref{e1.39} by exhibiting a weight-preserving bijection $\ph$ 
between the
``left-hand side objects" $(n,P,U)$, $n$ a nonnegative integer, $P\in
\L{(0,0)\to (\mu n+k,n)\mid x\ge \mu y}$, $U\in
S_{l-n}(\{(\mu+1)n+k+1, \dots,(\mu+1)N+k\})$, and the ``right-hand
side objects" $V\in S_l(\{0,1,\dots,(\mu+1)N+k\})$. By
weight-preserving we mean that if $\ph((n,P,U))=V$ then 
\begin{equation} \label{e1.40} 
\binom n2+\area(P)+\V U=\V V.
\end{equation}

Let $(n,P,U)$ be a left-hand side object. We represent $P$ by the
sequence $\mathbf z(P)=(z_1,z_2,\dots,z_n)$, where $z_i$ denotes the
distance of the $(n-i+1)$-st vertical step from the vertical line
$x=\mu n+k$. Note that $\area(P)=z_1+z_2+\dots+z_n$. (Figure??) Then
we define
$$\ph((n,P,U))=\{z_1,z_2+1,\dots,z_n+n-1\}\cup U.$$
Evidently, $\ph((n,P,U))$ is in $S_l(\{0,1,\dots,(\mu+1)N+k\})$ and
satisfies \eqref{e1.40}. 

To construct the inverse, take a
$V=\{v_1,v_2,\dots v_l\}\in S_l(\{0,1,\dots,(\mu+1)N+k\})$. Let $n$ be
maximal with $v_n\le (\mu+1)(n-1)+k$. Then it can be
verified that $\ph^{-1}$ is given by
$$\ph^{-1}(V)=(n,P,\{v_{n+1},v_{n+2},\dots,v_l\}),$$
where the path $P$ is determined by defining the height 
of the $i$-th vertical step to be $(\mu+1)n+k-v_{n-i+1}+i-1$.
??Example of map and inverse!!

This establishes that the coefficients of $z^l$, $l=0,1,\dots,N$, in
\eqref{e1.38} agree, thus completing the proof of \eqref{e1.37}.
\end{proof}

What we basically did in the first proof of Theorem~\ref{T1.4} was
extraction of the coefficients of $z^n$ in \eqref{e1.14} (actually in
the equivalent identity \eqref{e1.12}) by use of the 
Lagrange inversion. Thus, in attempting to compute the coefficients in
\eqref{e1.37}, which we are intested in, it is natural to ask for
$q$-analogues\index{$q$-analogue of the Lagrange inversion}\index{Lagrange
inversion, $q$-analogue} of the Lagrange inversion that would be
applicable to \eqref{e1.37}. Of particular interest, of course, is the
special case $\mu=1$, $k=0$ which gives rise to a $q$-analogue of the
Catalan numbers\index{Catalan numbers,
$q$-analogue}\index{$q$-analogue of Catalan numbers}. (??Bring
\index{Andrews, George E.}Andrews 
$q$-Catalan numbers \cite{AndrAR} at some place??) Indeed,
motivated by finding expressions for these $q$-Catalan numbers,
\index{Andrews, George E.}Andrews \cite{AndrAM}, 
\index{Gessel, Ira Martin??}Gessel \cite{GessAB}, 
\index{Garsia, Adriano M.}Garsia \cite{GarsAB}
developed a $q$-Lagrange theory that basically centers around the
question of finding the coefficients in the expansion
\begin{equation}\label{e1.42}
g(z)=\sum _{n\ge0} ^{}c_n f(z)f(qz)\cdots f(q^{n-1}z),
\end{equation}
where $g(z)=g_0+g_1z+g_2z^2+\cdots$ and $f(z)=f_1z+f_2z^2+\cdots$ are
given formal power series. In spite of the beauty of the theory, in
particular in \index{Gessel, Ira Martin??}Gessel \cite{GessAB} 
and \index{Garsia, Adriano M.}Garsia \cite{GarsAB}, the applicability of
the theory, even in the simple case $f(z)=z/(1+z)(1+\sqrt qz)$ (which
would correspond to our $q$-Catalan numbers with $q$ replaced by
$\sqrt q$) is limited, as far as explicit expressions are concerned.
For the interested reader we record Andrews' expansion for these
$q$-Catalan numbers,
\begin{equation} \label{e1.41} 
\GF{\L{(0,0)\to (n,n)\mid x\ge y};q^{\area(.)}}=??
\end{equation}

The search for $q$-Lagrange inversion formulas that was initiated by
the $\mu=1$, $k=0$ case of \eqref{e1.37} also gave rise to other
$q$-Lagrange inversion formulas in
\index{Hofbauer, Josef}Hofbauer \cite{HofbAF}, 
\index{Krattenthaler, Christian}Krattenthaler \cite{KratAB}, \index{Gessel,
Ira Martin??}Gessel and
\index{Stanton, Dennis}Stanton \cite{GeStAB}, \cite{GeStAD},
\index{Garsia, Adriano M.}Garsia and \index{Remmel, Jeff B.}Remmel\cite{GaReAD},
which apply to
expansions of different type than \eqref{e1.42}. We shall meet one of
these in ??, also in connection with $q$-Catalan numbers. See also
\index{Stanton, Dennis}Stanton \cite{StatAB} for a survey article on 
$q$-Lagrange inversion.

??More on $q$-Catalan numbers, recurrences,...??

??Mention explicitly the name Gould numbers??

If we look for an explicit expression for the coefficients in
\eqref{e1.37} we have to be satisfied
with a determinant. This is also true for general $\mu$ and $k$.
In fact, both Theorem~\ref{T1.15} and the dummy
path technique described in Section~\ref{s1.6} generalize 
to area counting. Theorem~\ref{T1.20} below gives the
$q$-analogue of Theorem~\ref{T1.15}. It is Theorem~?? in
\index{Handa, B. R.}Handa and
\index{Mohanty, Sri Gopal}Mohanty \cite{HaMoAC}. So, replacing $n$ by $\mu n+k$,
$a_i$ by $\floor{i/\mu}$, $b_i$ by $0$ in Theorem~\ref{T1.20} gives an
explicit expression for the coefficients in \eqref{e1.37}.

\begin{Theorem} \label{T1.20}
Let $\mathbf a=(a_1,a_2,\dots,a_n)$ and $\mathbf b=(b_1,b_2,\dots,b_n)$ be
integer sequences with $a_1\le a_2\le \dots\le a_n$, $b_1\le b_2\le
\dots\le b_n$, and $a_i\ge b_i$, $i=1,2,\dots,n$. The generating
function $\sum _{P} ^{}q^{\area(P)}$ of all
paths $P$ from $(0,b_1)$ to $(n,a_n)$ satisfying the property that 
for all $i=1,2,\dots,n$ the height of the $i$-th horizontal step of 
$P$ is between $b_i$ and $a_i$ is given by
\begin{multline} \label{e1.43}
\GF{\L{(0,b_1)\to (n,a_n)\mid \mathbf a\ge \mathbf y\ge \mathbf b};
q^{\area(P)}}\\=
\det_{1\le i,j\le n}\(q^{b_j(j-i+1)+j(j-i)}
\qbinom {a_i-b_j+1}{j-i+1}q\). 
\end{multline}
\end{Theorem}
\begin{proof}
Of course, we use the correspondence of Section~\ref{s1.6}
(??give it a name??) between the
paths under consideration and families $(P_1,P_2,\dots,P_n)$ of
nonintersecting lattice paths, where $P_i$ runs from $(n-i,b_i+i)$ to
$(n-i+1,a_i+i)$. Observe
that under this correspondence the weight property
\begin{equation} \label{e1.44} 
\area(P)=\area(P_1)+\area(P_2)+\dots+\area(P_n)-\binom{n+1}2
\end{equation}
holds. Thus, if we define
\begin{equation}\label{e1.45}
w_{\area}((P_1,P_2,\dots,P_n))=q^{\sum _{i=1} ^{n}\area(P_i)},
\end{equation} 
by \eqref{e1.44}
the generating function $\GF{\L{(0,b_1)\to (n,a_n)\mid \mathbf a\ge
\mathbf y\ge \mathbf b}; q^{\area(P)}}$ equals $q^{-\binom{n+1}2}$ times
the generating function $\sum _{\P} ^{}w_{\area}(\P)$, 
where the sum is over
all families of nonintersecting lattice paths which were described
above. Application of Theorem~\ref{T2.2} with $\SS=\{(1,0),(0,1)\}$,
$A_i=(n-i,b_i+i)$, $E_i=(n-i+1,a_i+i)$, $w_{\area}$ 
as in \eqref{e1.45}, and
use of \eqref{e1.34} give
\begin{align} \notag
\GF{\L{(&0,b_1)\to (n,a_n)\mid \mathbf a\ge \mathbf y\ge \mathbf b};
q^{\area(P)}}\\
\notag
&=q^{-\binom{n+1}2}\det_{1\le i,j\le n}\(\GF{\L{(n-j,b_j+j)\to
(n-i+1,a_i+i)}; q^{\area(.)}}\)\\
\notag
&=q^{-\binom{n+1}2}\det_{1\le i,j\le n}\Big(q^{(b_j+j)(j-i+1)}
\qbinom{a_i-b_j+1}{j-i+1}q\Big),
\end{align}
which can be transformed into \eqref{e1.43}.
\end{proof}
 Finally, we turn to the dummy path technique of Section~\ref{s1.6}.
As already remarked, it generalizes to area counting. This is because
Lemma~\ref{T1.16} has a straight-forward $q$-analogue.
\begin{Lemma} \label{T1.21}
Let $C_1,C_2,\dots,C_n$ be pairwise distinct points in $\Z^2$. Then
the generating function $\sum _{P} ^{}q^{\area(P)}$ for all lattice
paths $P$ from $(a,b)$ to $(c,d)$ which avoid
$C_1,C_2,\dots, C_n$ is given by
\begin{equation} \label{e1.46}
\det_{1\le i,j\le n+1}\big(\GF{L(A_j\to E_i);q^{\area(.)}}\big) ,
\end{equation}
where $A_1=(a,b)$, $A_2=C_1$, \dots, $A_{n+1}=C_{n+1}$, $E_1=(c,d)$,
$E_2=C_1$, \dots, $E_{n+1}=C_n$.
\end{Lemma}
\begin{proof}Use the arguments of the proof of Lemma~\ref{T1.16} and
apply Theorem~\ref{T2.2} with
$w_{\area}((P_1,P_2,\dots,P_{n+1}))=q^{\sum _{i+1} ^{n+1}\area(P_i)}$.
\end{proof}

Thus, in order to obtain an alternative determinant for 
$\GF{\L{(0,b_1)\to (n,a_n)\mid \mathbf a\ge \mathbf y\ge \mathbf b};
q^{\area(P)}}$, one would use Lemma~\ref{T1.21} with $(a,b)=(0,b_1)$,
$(c,d)=(n,a_n)$, $C_1=(0,a_1+1)$, \dots, $C_{n-1}=(n-2,a_{n-1}+1)$,
$C_n=(2,b_1-1)$, \dots, $C_{2n-2}=(n,b_n-1)$ in combination with
\eqref{e1.34}. Again, the reader should be aware that this alternative
determinant would reduce in size if some of the bounds are negligible,
i.e\@. if $a_i=a_n$ or $b_i=b_1$ for some $i$. We content ourselves
with stating the $q$-analogue of Theorem~\ref{T1.17}.
\begin{Theorem} \label{T1.22}
Let $\mathbf a=(a_1,a_2,\dots,a_n)$ be a sequence of integers satisfying
$a_1\le a_2\le \dots\le a_n$. The generating function $\sum _{P}
^{}q^{\area(P)}$ of all lattice paths $P$ from
$(0,0)$ to $(n,a_n)$ satisfying the property that for $i=1,2,\dots,n$
the height of the $i$-th horizontal step is at most $a_i$ equals
\begin{equation} \label{e1.47} 
\GF{\L{(0,0)\to(n,a_n)\mid \mathbf a\ge \mathbf y};q^{\area(.)}}
=\det_{1\le i,j\le n}
(d_{ij}),
\end{equation}
where
$$d_{ij}=\begin{cases} \qbinom{a_n+n} n q&i=j=1\\
\qbinom {a_{n-i+1}+n-i+1}{n-i}q&i\ne1,\ j=1\\
q^{(a_{n-j}+1)(j+1)}\qbinom {a_n-a_{n-j+1}+j-1}{j}q&i=1,\ j\ne1\\
q^{(a_{n-j}+1)(j-i)}
\qbinom {a_{n-i+1}-a_{n-j+1}+j-i}{j-i}q&i\ne1,\ j\ne1.\end{cases}$$
\end{Theorem}



??Handa-Mohanty Lehmann formula
??refer to Steck higher dimensional determinant

\bigskip

\setcounter{EXnum}{0}
\small
\centerline{\bf Examples}
\nobreak
\vskip6pt plus 2pt minus 2pt
\nobreak
\begin{EX} \label{EX-1} 
The number of all paths from $(0,0)$ to any point on the line $x+2y=n$
is the $n$-th {\em Fibonacci number}\index{Fibonacci
number}\index{Fibonacci} $F_n$, given by $F_0=F_1=1$ and
$F_{k+1}=F_k+F_{k-1}$, $k\ge1$. This is easily seen by recurrence. In
particular, by splitting the set of these paths into subsets
according which point on $x+2y=n$ is the end point of a path, we
obtain the identity
\begin{equation} \label{eFibonacci}
F_n=\sum _{l\ge0} ^{}\binom {n-l}l.
\end{equation}
\end{EX}
\begin{EX} \label{EX1} 
If $k\le m+n$,
every path from $(0,0)$ to $(m,n)$ must hit the antidiagonal
line $x+y=k$ somewhere, say in the point $(l,k-l)$. Thus, by
\eqref{e1.1} we obtain the identity
\begin{equation} \label{ee0}
\sum _{l=0} ^{k}\binom kl \binom {m+n-k} {m-l}=\binom {m+n}m.
\end{equation}
This is the so-called {\em Chu--Vandermonde identity}\index{Chu--Vandermonde 
identity}\index{Chu, ??}\index{Vandermonde, ??}. 
In hypergeometric terms, it can be rewritten as follows.
Recall the definition of a ({\em generalized}) {\em hypergeometric
series}\index{hypergeometric series},
\def\po#1#2{(#1)_#2}
\glossary{$_pF_q$}
\begin{equation} \label{ee3}
{}_r F_s\!\left[\matrix a_1,\dots,a_r\\ b_1,\dots,b_s\endmatrix; 
z\right]=\sum _{k=0} ^{\infty}\frac {\po{a_1}{k}\cdots\po{a_r}{k}}
{k!\,\po{b_1}{k}\cdots\po{b_s}{k}} z^k\ ,
\end{equation}
where the {\em shifted factorial\/}\index{shifted factorial}
\glossary{$(a)_k$}$(a)_k$ is given by $(a)_k:=a(a+1)\cdots(a+k-1)$,
$k\ge1$, $(a)_0:=1$. Then the left-hand side of \eqref{ee0} is equal
to
$$\binom {m+n-k} {m}{}_2F_1\!\left[\matrix -m,-k\\ n-k+1\endmatrix; 
1\right],$$
so that \eqref{ee0} is equivalent to
$${}_2F_1\!\left[\matrix -m,-k\\ n-k+1\endmatrix; 
1\right]=\frac {\binom {m+n}m} {\binom {m+n-k}m}.$$
After substitution of parameters, this becomes
(cf\@. \cite[(1.7.7); Appendix (III.4)]{SlatAC})
\begin{equation} \label{echu}
{} _{2} F _{1} \!\left [ \matrix { a, -k}\\ { c}\endmatrix ; {\displaystyle
   1}\right ]  = {\frac{({ \textstyle c-a}) _{k} }
    {({ \textstyle c}) _{k} }}.
\end{equation}
The above argument shows that this is true for $k$ a nonnegative
integer, $a$ a nonpositive integer, and $c$ a positive integer. However, a
polynomial argument (clear denominators in \eqref{echu}; thus both
sides become polynomials in $a$ and $c$ which equal each other for
infinitely many values of $a$ and $c$, and, hence must be identical)
shows that \eqref{echu} is in fact valid for any $a$ and $c$ as long
as $c$ is not a nonpositive integer.

Gau{\ss} generalized this summation to nonterminating series (cf\@.
\cite[(1.7.6); Appendix (III.3)]{SlatAC}),
$$
{} _{2} F _{1} \!\left [ \matrix { a, b}\\ { c}\endmatrix ; {\displaystyle
   1}\right ]  = \frac {\Gamma (c)\,\Gamma( c-a-b)} {\Gamma(
c-a)\,\Gamma( -b + c)},
$$
valid for complex $a,b,c$ with $\Re(c-a-b)>0$.
\end{EX}
\begin{EX} \label{EX1a}
The idea of the previous example may be applied to other situations
as well. Consider lattice paths from $(0,0)$ to $(c,d)$. 
If $h<c-\mu d$, there is a last touching point of
the path with the line $x=\mu y+h$, the point $(\mu l+h,l)$ say. Then from
\eqref{e1.1} and Theorem~\ref{T1.4} we infer the identity
\begin{equation} \label{ee0a}
\sum _{l=0} ^{d}\binom {l(\mu+1)+h}l
\frac {c-\mu d-h} {c+d-h-l(\mu+1)}\binom {c+d-h-\mu(l+1)} {d-l} 
=\binom {c+d}d.
\end{equation}
After substitution of parameters this becomes the {\em Rothe??
identity}\index{??} (cf\@. \cite{??})
\begin{equation} \label{eerothe}
\sum _{k=0} ^{n}\binom {a+k\mu}k \frac {c}
{c+(n-k)\mu}\binom {c+(n-k)\mu}{n-k}
=\binom {a+c+n\mu}n.
\end{equation}
The sum cannot be written in hypergeometric notation, except when
$\mu$ is an integer. If $\mu=0$ then we recover the Chu--Vandermonde
summation \eqref{ee0}.
\end{EX}

\begin{EX} \label{EX1b}
Now consider lattice paths from $(0,0)$ to $(c,d)$ which lie
below $x=\mu y$, $c\ge \mu d$. Then, if $h<c-\mu d$, 
there is a last touching point of
the path with the line $x=\mu y+h$, the point $(\mu l+h,l)$ say. Then from
Theorem~\ref{T1.4} we infer the identity
\begin{multline} \label{ee0b}
\sum _{l=0} ^{d}\frac {h+1} {l(\mu+1)+h+1}\binom
{l(\mu+1)+h+1} {l} \frac {c-\mu d-h} {c+d-h-l(\mu+1)}\binom
{c+d-h-\mu(l+1)} {d-l} \\
=\frac {c-\mu d+1} {c+d+1}\binom {c+d+1} {d} .
\end{multline}
After substitution of parameters this becomes the {\em Hagen??
identity}\index{??} (cf\@. \cite{??})
\begin{equation} \label{eehagen}
\sum _{k=0} ^{n}\frac {a} {a+k\mu}\binom {a+k\mu}k \frac {c}
{c+(n-k)\mu}\binom {c+(n-k)\mu}{n-k}
=\frac {a+c} {a+c+n\mu}\binom {a+c+n\mu}n.
\end{equation}
Again, the sum cannot be written in hypergeometric notation, except when
$\mu$ is an integer. 
\end{EX}

\begin{EX} \label{EX2}
The number of all paths from $(0,0)$ to $(n,n)$ 
staying below the line $y=x+t$ and above the
line $y=x-t$ is given by
\begin{equation} \label{ee1}
\v{\L{(0,0)\to (n,n)\mid x+t\ge y\ge x-t}}
=\sum _{k\in\Z} ^{}(-1)^k\binom
{2n} {n+k(t+1)}.
\end{equation}
This follows immediately from Theorem~\ref{T1.3} by setting $a=b=0$,
$c=d=n$, and $s=-t$, on combining the two sums on the right-hand side
of \eqref{e1.6} into the sum on the right-hand side of \eqref{ee1}.
\end{EX}

\begin{EX} \label{EX3}
Since the number of paths from $(0,0)$ to $(n,n)$ between the
lines $y=x+1$ and $y=x-1$ is $2^{n-1}$, from \eqref{ee1} we obtain the identity
\begin{equation} \label{ee2}
\sum _{k\in\Z} ^{}(-1)^k\binom {2n}{n+2k}=2^{n-1}.
\end{equation}
This identity follows from \index{Kummer's
identity}\index{Kummer, ??}Kummer's $_2F_1$
summation (see \eqref{ee4} below). 
Namely, using hypergeometric notation \eqref{ee3},
if $n$ is even, the sum in \eqref{ee2} can
be written as
$${{{\left( -1 \right) }^{{ n/ 2}}}}
{{{} _{2} F _{1} \!\left [ \matrix { -n, {\frac 1 2} - n}\\ { {\frac 1
     2}}\endmatrix ; {\displaystyle -1}\right ] }
   },
$$
while if $n$ is odd, it can be written as
$${{\left( -1 \right) }^{{(n-1)/ 2}}}(2n)\,
{{{} _{2} F _{1} \!\left [ \matrix { 1 - n, {\frac 1 2} - n}\\ {
{\frac 3
   2}}\endmatrix ; {\displaystyle -1}\right ]  }
    }.
$$
Both $_2F_1$-series can be summed by means of the identity (cf\@.
\cite[(1.7.1.6), corrected, (2.3.2.9); Appendix (III.5)]{SlatAC})
\begin{equation} \label{ee4}
{} _{2} F _{1} \!\left [ \matrix { a, b}\\ { 1 + a - b}\endmatrix ;
   {\displaystyle -1}\right ]  = 
  {\frac{\Gamma({ \textstyle 1 + {a\over 2}}) \,
      \Gamma({ \textstyle 1 + a - b}) }
    {\Gamma({ \textstyle 1 + a}) \,\Gamma({ \textstyle 1 + {a\over 2} - b})
}}.
\end{equation}
\end{EX}

\end{document}
