%\documentclass[12pt]{amsbook}
%\input pathlate.sty
%\input priv

%\makeindex
%\begin{document}

\chapter{Introduction} \label{ch0}
Let $\Z$\glossary{$\Z$} denote the set of integers.
Consider the $d$-dimensional integer lattice $\Z^d$\glossary{$\Z^d$}. 
A {\em lattice path\index{lattice 
path}\index{path}\/} 
({\em path\/} for short) $P$ is a sequence $P=(P_0,P_1,\dots,P_l)$ of
points $P_i$ in $\Z^d$. The left-hand picture in
Figure~\ref{F0.1} shows the lattice path $((0,0),
(1,1),(2,1),(3,1),\break (3,2),(4,3))$.
The point $P_0$ is called the {\em starting point\index{starting
point of a path}\/} and $P_l$ is called the {\em end 
point\index{end point of a path}\/} of $P$. The vectors
$\overrightarrow {P_0P_1},\overrightarrow {P_1P_2}, \dots, \overrightarrow
{P_{l-1}P_{l}}$ are called the {\em steps\index{steps of a 
path}\/} of $P$. The number of
steps, $l$, is called the {\em length\index{length of a path}\/} 
of $P$. Alternatively, the
lattice path $P$ could be considered as a pair $(P_0,s_1s_2\dots s_l)$
of a point $P_0$ in $\Z^d$, the starting point of $P$, and a sequence
$s_1s_2\dots s_l$ of vectors in $\Z^d$, the steps of $P$. Clearly, the
relation between these two notations is given by $s_i=\overrightarrow
{P_{i-1}P_i}$, or $P_i=P_0+\sum _{j=1} ^{i}s_j$. We shall very often
switch between these two different ways of writing down lattice paths.
Also, as shown by Figure~\ref{F0.1}, pictorially a lattice path is
always viewed with its points being connected so that the steps become
visible. 
\begin{Figure} \label{F0.1}
$$
\Gitter(6,5)(0,0)
\Koordinatenachsen(6,5)(0,0)
\Pfad(0,0),31123\endPfad
\DickPunkt(0,0)
\DickPunkt(4,3)
\DickPunkt(1,1)
\DickPunkt(2,1)
\DickPunkt(3,1)
\DickPunkt(3,2)
\hbox{\hskip5cm}
\Gitter(6,5)(0,0)
\Koordinatenachsen(6,5)(0,0)
\Pfad(0,0),1223211\endPfad
\Pfad(4,3),2\endPfad
\DickPunkt(0,0)
\DickPunkt(1,0)
\DickPunkt(1,1)
\DickPunkt(1,2)
\DickPunkt(2,3)
\DickPunkt(2,4)
\DickPunkt(3,4)
\DickPunkt(4,4)
\DickPunkt(4,3)
\hskip3cm
$$
\end{Figure}

\medskip
The standard problem is to count all lattice paths from a given
starting point $A\in \Z^d$ to a given end point $E\in \Z^d$ with steps
from a given set $\SS\in \Z^d$ subject to some restrictions $R$. In
order to have a uniform notation, we shall denote this set of paths by
\glossary{$L(A\to E;\SS\mid R)$}$L(A\to E;\SS\mid R)$. 
For instance, the set of all lattice paths in the
plane $\Z^2$ from $(0,0)$ to $(4,3)$ which consist of positive unit steps
and diagonal steps $(1,1)$ and stay below the main diagonal will be
denoted by
$$\L{(0,0)\to (4,3);\{(1,0),(0,1),(1,1)\}\mid x\ge y}.$$
An example of such a lattice path is depicted in the left-hand picture
of Figure~\ref{F0.1}.

There could be a misunderstanding of how to interpret
the restriction $x\ge y$ in
this notation. Therefore, for convenience, let us make the convention
that, if a restriction is an {\em affirmative\/} statement then it is meant
to hold for {\em all\/} points of a lattice path, while if a restriction is a
{\em negative\/} statement then it is meant to hold only for {\em at least
one\/} point of a lattice path. Thus the set 
$$\L{(0,0)\to (4,3);\{(1,0),(0,1),(1,1),(0,-1)\}\mid x\not\ge y}$$
would be the set of all lattice paths from $(0,0)$ to $(4,3)$ with
steps from $\{(1,0),\break 
(0,1),(1,1),(0,-1)\}$ which {\em do not always\/} stay below
the line $x=y$. An example of a lattice path from this set is depicted
in the right-hand picture of Figure~\ref{F0.1}.

Sometimes, if we are given a function $f$ on lattice paths, we may
write $\L{A\to E;\SS\mid f(.)=\ell}$ meaning the set of all paths $P$
from $A$ to $E$ with steps from $\SS$ which satisfy $f(P)=\ell$.

If there is no restriction on the paths then we simply write $L(A\to
E;\SS)$. Also, if we are considering lattice paths consisting of
only positive unit steps parallel to the coordinate axes, 
then we shall drop the step set and write
$L(A\to E\mid R)$, or briefly $L(A\to E)$ if there is also no restriction on
the lattice paths. Lattice paths consisting of only positive unit steps
parallel to the coordinate axes 
are sometimes called \index{minimal lattice path}{\em minimal\/}
lattice paths or {\em simple\/} lattice paths\index{simple lattice path}.

\medskip
In many places, we shall consider \index{weighted counting}{\em weighted
counting}. 
Also here, we
shall use a uniform notation. Given a set $\mathcal M$ and a \index{weight
function}weight
function $w$ on $\mathcal M$ we denote by 
$GF(\mathcal M;w)$\glossary{$GF(\mathcal M;w)$} the
\index{generating function}{\em generating function\/} 
for $\mathcal M$ with respect to $w$, i.e.
\begin{equation}\label{e0.1}
GF(\mathcal M;w):=\sum _{x\in \mathcal M} ^{}w(x).
\end{equation}

\medskip
Binomial coefficients will appear at many places. Since we deal with
lattice paths, the binomial
coefficient in this book will have a definition slightly deviating
from the usual one. Namely, for integers $a$ and $b$ we define the
{\em binomial
coefficient\/}\index{binomial coefficient} 
$\binom ab$ by ??(everywhere true)??
$$\binom ab:=\cases \dfrac {a!} {b!\,(a-b)!}&\text {if
}a\ge b\ge0,\\0&\text {otherwise.}\endcases$$
Note that this makes a difference if $a<0$.

Similarly, we define the {\em $q$-binomial
coefficient\/}\index{$q$-binomial coefficient}
$\[\begin{smallmatrix} a\\b
\end{smallmatrix}\]_q$ by
$$\begin{bmatrix} a\\b\end{bmatrix}_q:=\cases \dfrac {[a]_q!}
{[b]_q!\,[a-b]_q!}&\text {if
}a\ge b\ge0,\\0&\text {otherwise,}\endcases$$
where the {\em $q$-factorial\/}\index{$q$-factorial} $[m]_q!$ is defined by 
$$[m]_q!:=1\cdot(1+q)\cdot(1+q+q^2)\cdots(1+q+\dots+q^{m-1}).$$

Furthermore, we use the usual multidimensional notation. If 
$\boldsymbol \lambda
=(\lambda
\sb
1,\lambda
\sb
2,\dots,\lambda
\sb
n)$ and
$\boldsymbol\mu=(\mu\sb
1,\mu\sb
2,\dots,\mu\sb
n)$, then
$\vert\boldsymbol\lambda
\vert=\lambda
\sb
1+\lambda
\sb
2+\dots +\lambda
\sb
n$, and $\boldsymbol\lambda
 -\boldsymbol\mu
=(\lambda
\sb
1-\mu\sb
1,\lambda
\sb
2-\mu\sb
2,\dots,\lambda
\sb
n-\mu\sb
n)$. 
If $\lambda
\sb
i\geq\mu\sb
i$ for all
$i=1,2,\dots,n$, we write $\boldsymbol\lambda
\geq \boldsymbol \mu$. If $\boldsymbol\la=(\la_1,\la_2,\dots,\la_n)$ is a
vector and if 
$\si$ is a permutation in $\S_n$, the set
of permutations of $\{1,2,\dots,n\}$, then we write $\boldsymbol\la_\si$
for the ``permuted" vector
$(v_{\si(1)},v_{\si(2)},\dots,v_{\si(n)})$.

Given a vector $\boldsymbol \la=(\la_1,\la_2,\dots,\la_n)$ of
integers we define
the {\em multinomial coefficient\/}\index{multinomial coefficient}
$\binom {\v{\boldsymbol\la}}\la=\binom
{\la_1+\la_2+\dots+\la_n}{\la_1,\la_2,\dots,\la_n}$ by
$$\begin{pmatrix} \v{\boldsymbol\la}\\\la\end{pmatrix}=\cases 
\dfrac {(\la_1+\la_2+\dots+\la_n)!} {\la_1!\,\la_2!\cdots\la_n!}&\text
{if $\la_i\ge0$ for all $i$,}\\0&\text {otherwise.}\endcases
$$
When $n=2$ the above expression gives the binomial coefficient as
defined before,
$$\begin{pmatrix} \la_1+\la_2\\\la_1,\la_2\end{pmatrix}=
\begin{pmatrix} \la_1+\la_2\\\la_1\end{pmatrix}=
\begin{pmatrix} \la_1+\la_2\\\la_2\end{pmatrix}.$$

Similarly, given a vector $\boldsymbol \la=(\la_1,\la_2,\dots,\la_n)$ of
integers we define
the {\em $q$-multi\-nom\-ial coefficient\/}\index{$q$-multinomial coefficient}
$\[\begin{smallmatrix} \v{\boldsymbol\la}\\\la\end{smallmatrix}\]_q=
\[\begin{smallmatrix}
\la_1+\la_2+\dots+\la_n\\\la_1,\la_2,\dots,\la_n\end{smallmatrix}\]_q$ by
$$\begin{bmatrix} \v{\boldsymbol\la}\\\la\end{bmatrix}_q=\cases 
\dfrac {[\la_1+\la_2+\dots+\la_n]_q!}
{[\la_1]_q!\,[\la_2]_q!\cdots[\la_n]_q!}&\text
{if $\la_i\ge0$ for all $i$,}\\0&\text {otherwise.}\endcases
$$
When $n=2$ the above expression gives the $q$-binomial coefficient as
defined before,
$$\begin{bmatrix} \la_1+\la_2\\\la_1,\la_2\end{bmatrix}_q=
\begin{bmatrix} \la_1+\la_2\\\la_1\end{bmatrix}_q=
\begin{bmatrix} \la_1+\la_2\\\la_2\end{bmatrix}_q.$$


??upper factorials
??self-avoiding walk

??appendix: partitions and q-binomials, better: chapter on lattice paths
            partitions, q-binomials, q-multinomials, independently
            developing. Also here area-counting-determinant formula.
??appendix: species and generating functions
??appendix: Lagrange inversion (also multivariable)
??appendix: hypergeometric and basic hypergeometric series + Gosper + 
            Zeilberger
??appendix: Tree of connections
??appendix: Glossary of all counting problems with references to the book
            or literature

%\end{document}
