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



%\begin{document}

\chapter{Multidimensional lattice paths}\label{ch7}
This chapter contains enumeration results for lattice paths in spaces
of higher dimension.

??$\Z^d$, remind of meaning of simple lattice paths

Denote coordinates by $x_1,x_2,\dots,x_d$.

Of course, as a basis to start with, we need the number of all simple
paths in $\Z^d$ from $(a_1,a_2,\dots,a_d)$ to $(e_1,e_2,\dots,e_d)$.
Since these lattice paths can be seen as \index{permutation}permutations 
of $e_1-a_1$
steps in $x_1$-direction, $e_2-a_2$ steps in $x_2$-direction, \dots,
$e_d-a_d$ steps in $x_d$-direction, the answer is a multinomial
coefficient,
\begin{equation} \label{e7.1} 
\v{\L{(a_1,\dots,a_d)\to (e_1,\dots,e_d)}}=\binom {\sum _{i=1}
^{d}(e_i-a_i)} {e_1-a_1,e_2-a_2,\dots,e_d-a_d}.
\end{equation}

\section{Simple lattice paths subject to boundaries $x_i\ge x_{i+1}$}
 \label{s7.1}
The results of this and the following 
section generalize those of Chapter~\ref{ch1}, Section~\ref{s1.1}. 

First we want to find the number of all paths from
$(a_1,a_2,\dots,a_d)$ to $(e_1,e_2,\dots,e_d)$ which always stay in
the region $x_1\ge x_2\ge \dots\ge x_d$. This problem is related to
the {\em $d$-candidate ballot problem\/}\index{ballot problem,
$d$-candidate} (for the 2-candidate ballot problem see
Chapter~\ref{ch1}, Section~\ref{s1.1}).
Let $E_1,E_2,\dots,E_d$ be
candidates in an election, $E_1$ receiving $e_1$ votes, $E_2$
receiving $e_2$ votes, \dots, $E_d$ receiving $e_d$ votes. How many
ways of counting the votes are there, such that  at any stage during
the counting $E_1$ has at least as many votes as $E_2$, $E_2$ has at
least as many votes as $E_3$, etc.? It is evident that by encoding
each vote for candidate $E_i$ by a step in $x_i$-direction this ballot
problem is transferred into counting paths from the origin to
$(e_1,e_2,\dots,e_d)$ which are staying in the region $x_1\ge x_2\ge \dots \ge
x_d$. It has been known for a long time \cite{??} that the answer is a
determinant. But only not too long back, it was \index{Zeilberger,
Doron}Zeilberger 
\cite{ZeilAD} who discovered how to generalize \index{Andr\'e, 
D.}Andr\'e's reflection
principle\index{reflection principle} 
(which was described in Chapter~\ref{ch1}, Section~\ref{s1.1}) to the
$d$-dimensional problem.

\begin{Theorem} \label{T7.1}
Let $A=(a_1,a_2,\dots,a_d)$ and $E=(e_1,e_2,\dots,e_d)$ be points in
$\Z^d$ with $a_1\ge a_2\ge\dots\ge a_d$ and $e_1\ge e_2\ge\dots\ge
e_d$. The number of all paths from $A$ to $E$ staying in the region
$x_1\ge x_2\ge\dots\ge x_d$ equals
\begin{equation} \label{e7.2} 
\v{L(A\to E\mid x_1\ge x_2\ge\dots\ge x_d)}=\Big(\sum _{i=1}
^{d}(e_i-a_i)\Big)! \det_{1\le i,j\le d}\(\frac {1} {(e_i-a_j-i+j)!}\).
\end{equation}
\end{Theorem}
\begin{proof}Following the idea of the proof of Theorem~\ref{T1.1} one
would argue that the desired number is the number of {\em all\/} paths
from $A$ to $E$ minus those which cross one of the hyperplanes
$x_i=x_{i+1}$. If a path crosses $x_i=x_{i+1}$ then it has to touch the
hyperplane $H_i$ given by
\begin{equation} \label{e7.3} 
H_i:\quad x_i-x_{i+1}=-1,\quad i=1,2,\dots,d-1.
\end{equation}
For a fixed $i$, the number of paths touching $H_i$ can be found using
the reflection principle with respect to $H_i$. What the reflection
with respect to $H_i$ does is to map
\begin{equation} \label{e7.3'}
(\dots,y_i,y_{i+1},\dots) \text { to } (\dots,y_{i+1}-1,y_i+1,\dots).
\end{equation}
But there are also
paths touching some $H_i$ {\em and\/} $H_j$, etc. So one would have to
argue by inclusion-exclusion, which leads to the task of finding the
number of paths touching $H_{i_1}, H_{i_2}, \dots, H_{i_k}$.
Experienced with the proof of Theorem~\ref{T1.3}, one would apply
iterated reflection, see \index{Watanabe, Toshihiro??}Watanabe and
\index{Mohanty, Sri Gopal}Mohanty \cite{WaMoAA}. 
Ultimately, we would consider lattice paths
starting from points that result from reflecting $A$ with respect to
$H_i$'s, any number of times, to $E$. These reflections of $A$ can be
made explicit. The underlying mechanism will be described in the
setting of ``Weyl chambers" in Section~\ref{s7.2}.

In fact, all reflections of $A=(a_1,a_2,\dots,a_d)$ 
with respect to $H_i$'s are the points
$$(a_{\si(1)}+1-\si(1),a_{\si(2)}+2-\si(2),\dots,a_{\si(d)}+d-\si(d)),$$
where $\si$ is some \index{permutation}permutation 
in $\S_d$. Let us write $\si(A)$ for
$(a_{\si(1)}, a_{\si(2)},\dots,a_{\si(d)})$, and $V_{\si}$ for
$(1-\si(1),2-\si(2), \dots, d-\si(d))$ so that 
\begin{equation} \label{e7.4}
A_\si+V_\si=
(a_{\si(1)}+1-\si(1),a_{\si(2)}+2-\si(2),\dots,a_{\si(d)}+d-\si(d)).
\end{equation}
So, what we consider is the
set of paths
$$
\bigcup _{\si\in\S_d} ^{}L(\si(A)+V_\si\to E) .
$$
We claim that 
\begin{equation} \label{e7.5} 
\v{L(A\to E\mid x_1\ge x_2\ge \dots\ge x_d)}=\sum _{\si\in\S_d} ^{}
\sgn \si\,\v{L(\si(A)+V_\si\to E)}.
\end{equation}
It is easily checked that by \eqref{e7.1} this identity immediately
implies \eqref{e7.2}.

We may rewrite \eqref{e7.5} in the form
\begin{equation} \label{e7.6} 
\v{L(A\to E\mid x_1\ge x_2\ge \dots\ge x_d)}=
\sum _{(\si,P)} ^{}\sgn\si,
\end{equation}
where the sum is over all pairs $(\si,P)$ with $\si\in\S_d$ and $P\in
L(\si(A)+V_\si\to E)$.
The proof of \eqref{e7.6} is done by a sign-reversing involution on the set
of all such pairs $(\si,P)$ where $P$ touches at least one of the
hyperplanes $H_i$ defined in \eqref{e7.3}. Sign-reversing has to be
understood with respect to $\sgn\si$. Provided the existence of such an
involution, the only contributions to the sum in \eqref{e7.6} would be
by pairs $(\si,P)$ where $P$ does not touch any of the hyperplanes
$H_i$. This can be only the case for $\si=\text{id}$. For, if
$\si\ne \text{id}$ then there exists an $i$ with $\si(i)>\si(i+1)$.
This implies $a_{\si(i)}\le a_{\si(i+1)}$, and hence
$a_{\si(i)}+i-\si(i) <a_{\si(i+1)}+i+1-\si(i+1)$. Since $e_i\ge
e_{i+1}$, the path $P$ from $\si(A)+V_\si$ to $E$, would have
to cross $x_i=x_{i+1}$ and therefore would touch $H_i$.
This would prove \eqref{e7.6} and hence the theorem.

Now we construct the promised involution. Let $(\si,P)$ be a pair
with $\si\in\S_d$ and $P\in L(A_\si+V_\si\to E)$ 
with $P$ touching at least one of the hyperplanes $H_i$.
Consider all meeting points of $P$ with hyperplanes $H_i$. Choose the
last meeting point and denote it by $M$. Let $I$ be minimal such that 
$H_I$ is a hyperplane that contains $M$. Then we form the new path
$P'$ by reflecting the portion of $P$ from the starting point
$\si(A)+V_\si$ up to $M$ with respect to $H_I$ and leaving the portion
from $M$ to $P$ invariant. Using \eqref{e7.4} and \eqref{e7.3'},
it is easily checked that the starting point
of $P'$ is $A_{\si\circ(I,I+1)}+V_{\si\circ(I,I+1)}$ (with $(I,I+1)$
denotes the transposition interchanging $I$ and $I+1$.) Hence,
$(\si\circ(I,I+1),P')$ is a pair under consideration for the sum in
\eqref{e7.6} and $P'$ touches one of the
hyperplanes $H_i$ (namely $H_I$). This mapping is an involution since
nothing was changed after $M$. Besides, we have
$\sgn\si\circ(I,I+1)=-\sgn\si$. Therefore it is also sign-reversing.
This completes the proof of the theorem.
\end{proof}

The result \eqref{e7.2} should remind us of Theorem~\ref{T2.7},
\eqref{e2.36}. There, the number of standard Young
tableaux\index{standard Young tableau} of a given
shape is computed. Indeed, given $\La=(\la_1,\la_2,\dots,\la_n)$ and
$\Mu=(\mu_1,\mu_2,\dots,\mu_n)$ a standard Young tableaux $T$ of shape
$\La/\Mu$ can be converted into a lattice path in $\Z^n$ from $\La$ to
$\Mu$ staying in the region $x_1\ge x_2\ge\dots\ge x_n$. This is seen
by starting the path at $\Mu$ and for $i=1,2,\dots,\sum _{k=1}
^{n}(\la_k-\mu_k)$ joining a step in $x_j$-direction if $i$ is in the
$j$-th row of $T$. Thus both enumeration problems are equivalent. But
they were derived in different ways, namely by using nonintersecting
lattice paths for Theorem~\ref{T2.7} and multidimensional reflection
principle for Theorem~\ref{T7.1}, respectively. That both methods,
\index{nonintersecting lattice paths}\index{lattice paths,
nonintersecting}nonintersecting 
lattice paths in the plane and multidimensional
\index{reflection principle}reflection principle, 
are in fact not too far apart, can be seen from
the fact that $n$ nonintersecting lattice paths in the plane can be
``merged together" into a single lattice path in $\Z^n$ staying in the
region $x_1\ge x_2\ge\dots\ge x_n$, and vice versa. The ``merging" of
a family $(P_1,P_2,\dots,P_n)$ of lattice paths is done (see for
example \index{Fisher, Michael E.}Fisher \cite{Fish??}) by scanning the strips 
$S_p:=\{p-1\le x+y\le p\}$,
$p=\dots,-1,0,1,\dots$, and joining a step in direction
$(\ep_1,\ep_2,\dots,\ep_n)$, where $\ep_i$ is 0 or 1 depending on
whether the path $P_i$ takes a step in horizontal or vertical
direction in this strip. On the other hand, a simple lattice path $P$
in $\Z^d$ from $(a_1,a_2,\dots,a_d)$ to $(e_1,e_2,\dots,e_d)$ staying
in the region $x_1\ge x_2\ge \dots\ge x_d$ corresponds to the family
$\P=(P_1,P_2,\dots,P_d)$ of nonintersecting lattice paths in the
plane, $P_i:(-a_i+i,a_i-i)\to (-e_i+i+\sum _{j=1}
^{d}(e_i-a_i),e_i-i)$, where in each strip $S_p$ there is exactly one
vertical step among the paths of $\P$. The $p$-th step of $P$ is in
direction $x_j$ if and only if the vertical step in the region $S_p$
belongs to $P_j$. So, in a sense, enumeration of nonintersecting
lattice paths in the plane and the enumeration of paths in $\Z^d$
staying in the region $x_1\ge x_2\ge \dots\ge x_d$ are equivalent.

\medskip
??Only for $m=2$ or $3$, then mention that it is also possible with
$m$ groups??
The same idea as that in the proof of Theorem~\ref{T7.1} would also
enable us to count lattice paths in a region which is determined by
several {\em disjoint\/} inequality chains, which after a suitable
permutation of coordinates could be described as
\begin{equation} \label{e7.6a}
x_1\ge x_2\ge\dots\ge x_{i_1},\quad x_{i_1+1}\ge x_{i_1+2}\ge
\dots\ge x_{i_2},\quad \dots,x_{i_{r-1}+1}\ge x_{i_{r-1}+2}\ge
\dots\ge x_{i_r}
\end{equation}
($1\le i_1<i_2<\dots<i_r\le d$). The answer would be of the form
$$\sum _{\si_1\in\S_{i_1},\,\dots,\si\in\S_{i_r}}
^{}\text{multinomial} (\si_1,\dots,\si_r,A,E),$$
where the multinomial coefficients would count the number of paths from some
(iterated) reflection of $A$ to $E$. The reflections are with respect
to hyperplanes $x_i-x_{i+1}=-1$,
$i\in\{1,\dots,i_1-1,i_1+1,\dots,i_{r-1}-1,i_{r-1}+1,\dots ,i_r\}$ and
encoded by the permutations $\si_1,\si_2,\dots,\si_r$. See the next
section for a precise formulation and generalizations.

However, if the inequality chains are not disjoint, then the situation
becomes truly difficult. In particular, the reflection principle does
not seem to help anymore. One could consider reflections, as in the
proof of Theorem~\ref{T7.1}, but the nice property that for
permutations other than the identity permutation some hyperplane has
to be touched would fail.
That there is some difference in complexity
can also seen from the fact that only the most simple problem has been
solved and that no really nice and enlightening solution is known. This
problem was originally formulated in terms of a three-candidate ballot
problem\index{ballot problem, three-candidate}. Let 
$E_1,E_2,E_3$ be candidates in an election, $E_1$ receiving $e_1$
votes, $E_2$ receiving $e_2$ votes, and $E_3$ receiving $e_3$ votes,
$e_1\ge \max\{e_2,e_3\}$. How many ways of counting the votes are
there such that at any stage during the counting candidate $E_1$ has
at least as many votes as $E_2$ and as least as many votes as 
$E_3$? In lattice paths formulation
this would mean to count all simple lattice paths in $\Z^3$ from the
origin to $(e_1,e_2,e_3)$ staying in the region
$\{(x_1,x_2,x_3):x_1\ge x_2\text{ and }x_1\ge x_3\}$. We state the
result below. Solutions were given by \index{Kreweras, Germain}Kreweras 
\cite{KrewAB} and
\index{Niederhausen, Heinrich}Niederhausen \cite{NiedAB?,NiedAJ}, see also
\index{Gessel, Ira Martin??}Gessel \cite[??]{GessAF}. It is possible to get
a determinantal solution on the basis of Theorem~\ref{T7.10}, but it
is not as nice as the one given below.

\begin{Theorem} \label{T7.2}
Let $e_1\ge\max\{e_2,e_3\}$. The number of all lattice paths in $\Z^3$
from $(0,0,0)$ to $(e_1,e_2,e_3)$ subject to $x_1\ge x_2$  and $x_1\ge
x_3$ is given by
\begin{multline} \label{e7.7}
\v{\L{(0,0,0)\to (e_1,e_2,e_3)\mid x_1\ge \max\{x_2,x_3\}}}\\
=\binom {e_1+e_2+e_3}{e_1,e_2,e_3} - \frac {e_2+e_3} {1+e_1}\binom
{e_1+e_2+e_3} {e_1,e_2,e_3}\\
+\sum _{i,j\ge 1} ^{}(-1)^{i+j}\frac
{(e_1+e_2+e_3)!\,(2i+2j-2)!\,(i+j-2)!}
{i!\,(e_3-i)!\,j!\,(e_2-j)!\,(2i-1)! \,(2j-1)!\,(i+j+e_1)!}.
\end{multline}
In particular, if $e_1=e_2$ this number simplifies to
\begin{multline} \label{e7.8}
\v{\L{(0,0,0)\to (e_1,e_2,e_3)\mid x_1\ge \max\{x_2,x_3\}}}\\
=2^{2e_3+1}\(\frac {e_1!} {(e_1-e_3)!}\)^2 \frac {(2e_1-2e_3+1)!}
{(2e_1+2)!}. 
\end{multline}
\noproof
\end{Theorem}

\section{Hyperplane boundaries and the reflection principle}
\label{s7.2}
\index{reflection principle}
In the previous section we saw how to apply the reflection principle
to count simple lattice paths in the region $x_1\ge x_2\ge \dots\ge
x_d$. We also indicated some generalizations that would be obtainable
by means of the reflection principle. It is natural to ask: How far
can we go with reflection principle? What is the most general
situation where it applies? This question was raised and answered by
\index{Gessel, Ira Martin??}Gessel and \index{Zeilberger, Doron}Zeilberger 
\cite{GeZeAA}, ??see \index{Grabiner, David J.}Grabiner and
\index{Magyar, Peter}Magyar \cite{GrMrAA}??.

Clearly, the typical situation where reflection principle may be applied
is the problem of counting
lattice paths in $\Z^d$ from some starting point
$A=(a_1,a_2,\dots,a_d)$ to some end point
$E=(e_1,e_2,\dots,e_d)$ with steps in a set $\SS\subseteq \Z^d$, 
which stay in a region bounded by a set $\mathcal H$ of hyperplanes. 
Let us review Theorem~\ref{T7.1} and its proof to see what the
underlying principle is. 

The formula which we proved in Theorem~\ref{T7.1} is \eqref{e7.2}, or
equivalently, equation \eqref{e7.5}, which is
$$
\v{L(A\to E\mid x_1\ge x_2\ge \dots\ge x_d)}=\sum _{\si\in\S_d} ^{}
\sgn \si\,\v{L(\si(A)+V_\si\to E)},
$$
where $\si(A)=(a_{\si(1)}, a_{\si(2)},\dots,a_{\si(d)})$ and $V_\si=
(1-\si(1),2-\si(2), \dots, d-\si(d))$. It is easy to see, by a
translation
in direction $(-1,-2,\dots,-d)$, that this is equivalent to
\begin{equation} \label{e7.9} 
\v{L(A\to E\mid x_1> x_2> \dots> x_d)}=\sum _{\si\in\S_d} ^{}
\sgn \si\,\v{L(\si(A)\to E)}.
\end{equation}
In words, given $A=(a_1,a_2,\dots,a_d)$ and $E=(e_1,e_2,\dots,e_d)$
with $a_1>a_2>\dots>a_d$ and $e_1>e_2>\dots>e_d$, the number of
lattice paths from $A$ to $E$ which do not touch any of the
hyperplanes$H_i$ given by
\begin{equation} \label{e7.10} 
H_i:\quad x_i-x_{i+1}=0,\quad i=1,2,\dots,d-1.
\end{equation}
(note the slight difference with \eqref{e7.3}), is given by a signed sum of
path numbers, each number counting the paths from some ``permutation"
$\si(A)$ of the starting point $A$ to the end point $E$. Recall that
the appearance of these ``permuted starting points" is caused by the
reflection principle which makes it necessary to consider all
possible points that arise from $A$ by iterated reflection with
respect to the hyperplanes $H_i$ in \eqref{e7.10}. Phrased
differently, the group of linear orthogonal transformations of $\R^d$
($\R$ denoting the set of real numbers) which is generated by the
reflections with respect to the hyperplanes $H_i$ in \eqref{e7.10} is
the group $\S_d$ of \index{permutation
group}\index{permutation}permutations.
It acts on the points of $\R^d$
by permuting coordinates.

Hence, the natural environment for a ``general reflection principle" is within
the setting of \index{reflection group}{\em reflection groups\/}. A
{\em reflection group\/} is simply a group which is generated by all
reflections with respect to the hyperplanes $H$ in a given set $\mathcal
H$ of hyperplanes (in some $\R^d$). We review the facts about
reflection groups that are relevant for us below. 
For an excellent exposition of the subject see \index{Humphreys, J.
E.}Humphreys \cite{HumpAC}.
The situation of Theorem~\ref{T7.1} will be our running example.

As above, let $\mathcal H$ be a (finite??) set of hyperplanes in some
$\R^d$. Let $W$ denote the group that is generated by the
corresponding reflections. The group $W$ consists of linear
orthogonal transformations of $\R^d$. Some of these
transformations happen to be reflections
with respect to a hyperplane (not necessarily belonging to $\mathcal H$),
and let $\mathcal R$ denote the collection
of all these hyperplanes. Of course, $\mathcal R$ contains $\mathcal H$. In
the example when $\mathcal H$ is the set of hyperplanes in \eqref{e7.10},
we already saw that the group $W$ is the permutation group $\S_d$,
acting on $\R^d$ by permutating coordinates. All the reflections in
this group are the interchanges of two coordinates $x_i$ and $x_j$,
$1\le i<j\le d$, corresponding to the transpositions $(i,j)$ in
$\S_d$. Hence, the corresponding set $\mathcal R$ of hyperplanes in this
case is 
\begin{equation}\label{e7.11}
\mathcal R=\{x_i-x_j=0:\ 1\le i<j\le d\}.
\end{equation} 

??Figure
The hyperplanes in $\mathcal R$ cut the space into different regions. The
connected components of the complement of $\bigcup
_{H\in\mathcal R} ^{}H$
in $\R^d$  are called \index{chamber}{\em chambers\/}. Each
chamber is enclosed by a set $\mathcal R_0$ of bordering hyperplanes.
Clearly, $\mathcal R_0$ is a subset of $\mathcal R$.
In our
running example a typical chamber is the region
\begin{equation} \label{e7.12}
\{(x_1,x_2,\dots,x_d):\ x_1> x_2> \dots> x_d\},
\end{equation}
which is bounded by the hyperplanes in \eqref{e7.10}.  Actually, in
this special case any chamber has the form
\begin{equation} \label{e7.12'}
\{(x_1,x_2,\dots,x_d):\ x_{\si(1)}> x_{\si(2)}> \dots> x_{\si(d)}\},
\end{equation}
where $\si$ is some permutation in $\S_d$.

It can be
shown that the reflections with respect to the hyperplanes in $\mathcal
R_0$ generate the complete reflection group $W$. Another important
fact is that, given one chamber $C$, all chambers are $w(C)$, where
$w$ runs through the elements of the reflection group $W$, all $w(C)$
being distinct.

For the analysis of reflection groups it is convenient
to associate to each hyperplane $H$ in $\mathcal R$ a pair $\{r_H,-r_H\}$
of vectors perpendicular to $H$. The collection of all these vectors
is called a \index{root system}{\em root system\/} $\Phi$ associated
to the reflection group $W$. The elements of $\Phi$ are called
\index{root}{\em roots\/}. 
In our running example, the set of hyperplanes is given by
\eqref{e7.11}, hence an associated root system is
$\Phi=\{\ep_i-\ep_j:\ 1\le i\ne j\le d\}$, where
$\ep_1,\ep_2,\dots,\ep_d$ are the standard basis vectors.
The properties of a root system $\Phi$ are
\begin{enumerate}
\item If $\al$ belongs to $\Phi$ then also $-\al$.
\item The reflection of $\al\in\Phi$ with respect to a hyperplane
perpendicular to some $\be\in\Phi$ is again an element of $\Phi$.
\end{enumerate}

If a particular chamber $C$ is fixed, the roots which are associated
with the bordering hyperplanes and which point inside the chamber
$C$ are called \index{simple root}\index{root, simple}{\em simple
roots\/}. In our running example, the simple roots associated to the
chamber \eqref{e7.12} are
$\{\ep_1-\ep_2,\ep_2-\ep_3,\dots,\ep_{d-1}-\ep_d\}$.

Now we are in a position to formulate and prove \index{Gessel, I.
M.}Gessel and
\index{Zeilberger, Doron}Zeilberger's result \cite[Theorem~1]{GeZeAA}. The motivation for the
technical conditions in the statement of the theorem will become
apparent from the proof.
??signum von w!! ??see the Remark below??
\begin{Theorem}\label{T7.3}
Let $C$ be a chamber of some reflection group $W$, determined by the
hyperplanes in the set $\mathcal R_0$. Let $\SS$ be a set of steps which is
invariant under $W$, i.e., $w(\SS)=\SS$, and with the property
that for all hyperplanes $H\in \mathcal R_0$ and all steps $s\in \SS$
the Euclidean inner product $(s,r_H)$ is either $0$ or $\pm k_H$,
where $k_H$ is a fixed constant, depending only on the hyperplane
$H$. As above, $r_H$ is a root associated to $H$, i.e., a vector
perpendicular to $H$. Furthermore, let $A,E$ be lattice points inside
the chamber $C$ such that also $w(A),w(E)$ are lattice points for all
$w\in W$, and such that for all hyperplanes $H\in \mathcal R_0$ 
the Euclidean inner product $(A,r_H)$ is an integral multiple of
$k_H$.

Then the number of all lattice paths from $A$ to $E$, with exactly $m$ 
steps from
$\SS$, and which stay strictly inside the chamber $C$ equals
\begin{equation}\label{e7.13}
\v{L_m??(A\to E;\SS\mid \text {\em inside }C)}
=\sum _{w\in W} ^{}\sgn w \v{L_m??(w(A)\to E;\SS)}.
\end{equation}
\end{Theorem}

\begin{Remark} Technical conditions??
\end{Remark}

It is obvious that \eqref{e7.13} specializes to formula \eqref{e7.9}
in the case of our running example, where $W$ is the group of
\index{permutation group}\index{permutation}permutations 
of coordinates, $C$ is given by \eqref{e7.12}, the set
of hyperplanes is \eqref{e7.10}, the set of steps is
$\{(1,0),(0,1)\}$, all constants $k_H$ being $1$. 

In fact, we already
considered a second special case of Theorem~\ref{T7.3}, namely in
Theorem~\ref{T1.??}. In this case, \dots???

What other examples are covered by the general setup in
Theorem~\ref{T7.3}? The answer is that all reflection groups that are
``relevant" in our context are completely classified. The meaning of ``relevant" is as
follows. In order our formula \eqref{e7.13} to make sense, the sum on the
right-hand side of \eqref{e7.13} should be finite. So, only
reflection groups that are ``discrete" and act ``locally finite" will
interest us. And it is exactly these reflection groups that are
precisely known (see \index{Humphreys, J. E.}Humphreys \cite[sec.~4.10]{HumpAC},
\index{Bourbaki, N.}Bourbaki 
\cite[ch.~V, VI]{BourAA}). 

The classification of reflection groups is most conveniently
described by starting with the classification of root systems. Recall
that the roots are vectors orthogonal to the reflecting hyperplanes
of the reflection group. Given
a root system $\Phi$ it may happen that it decomposes as a disjoint
union $\Phi=\Phi_1\cup \Phi_2$, where $\Phi_1$ and $\Phi_2$ are root
systems
orthogonal to each other, i.e., the Euclidean inner product
$(\al_1,\al_2)$ vanishes for all $\al_1\in\Phi_1$ and
$\al_2\in\Phi_2$. In this case the root system $\Phi$ is called
\index{reducible root system}\index{root system, reducible}{\em reducible\/}, otherwise
\index{irreducible root system}\index{root system, irreducible}{\em irreducible\/}. Obviously, every
root system is the disjoint union of irreducible root systems. 

There exist the following irreducible root systems, the five infinite
families $I_2(m)$ ($m=1,2,\dots$), 
$A_n$, $B_n$, $C_n$, $D_n$ ($n=1,2,\dots$), and the seven
exceptional root systems $G_2$, $F_4$, $E_6$, $E_7$, $E_8$, and
$H_3$, $H_4$. (The
indices mark the dimension of the vector space that is spanned by the
roots.) To each root system there is associated a \index{finite
reflection group}\index{reflection
group, finite}{\em finite\/}
reflection group and an 
\index{affine reflection group}\index{reflection group, affine}{\em affine\/} 
reflection group, which is
infinite, except that for $m\ne2,4,6,8,12$?? there is only a finite reflection
group associated to $I_2(m)$, the same being true for $H_3$, $H_4$. 
The finite reflection group is generated by all reflections
with respect to the hyperplanes
which run through a given point (we assume that this is the origin) and 
are perpendicular to a root in the root system. The affine reflection
group is generated by a larger set of hyperplanes, which includes the
aforementioned hyperplanes plus certain translates of them.
The root systems $B_n$ and $C_n$ have the same associated
reflection groups. Therefore we give a joint description. The
reflection groups corresponding to $G_2$ are the same as those for
$I_2(6)$, therefore we need not consider $G_2$. 

Below is the list of the infinite families of reflection groups. 
For the exceptional cases we refer the reader to
\index{Bourbaki, N.}Bourbaki \cite[cartes blanches??]{BourAA}. 
It goes without
saying that the hyperplane realizations are unique only up to
translations and orthogonal transformations of the underlying space.
We give realizations in some $\R^d$, so $\mathbf x$ always denotes the
vector $(x_1,x_2,\dots,x_d)$.

\index{$I_2(m)$}{\em Type $I_2(m)$}: 
The root system is $\Phi=\{\cos (2\pi k/m)\ep_1+\sin (2\pi/m)\ep_2:\
k=0,1,\dots,m-1\}$. 
The set of reflecting hyperplanes is therefore $\mathcal 
R=\{\cos (2\pi k/m) x_1+\sin (2\pi k/m) x_2=0:\ 
k=0,1,\dots,m-1\}$. 

So, the associated finite reflection group is the symmetry group of
a regular $m$-gon. A typical chamber is $\{\mathbf x:\ x_1\ge 0,\ 
\cos (2\pi /m) x_1+\sin (2\pi /m) x_2\ge 0\}$, the corresponding simple
roots are $\ep_1, \cos (2\pi /m) \ep_1+\sin (2\pi /m) \ep_2$.

\index{$A_n$}{\em Type $A_n$}: 
The root system is $\Phi=\{\ep_i-\ep_j:\ 1\le i\ne j\le
n+1\}$. The set of reflecting hyperplanes is therefore $\mathcal 
R=\{x_i-x_j=0:\ 1\le
i<j\le n+1\}$. Obviously, the reflection with respect $x_i-x_j=0$
acts by interchanging the $i$-th and $j$-th coordinate.

So, the associated finite reflection group is the group of
\index{permutation group}\index{permutation}permutations 
of the coordinates $x_1,x_2,\dots,x_{n+1}$, which is
isomorphic to the permutation group $\S_{n+1}$.
A typical chamber is $C=\{\mathbf x:\ x_1> x_2>\dots>x_{n+1}\}$, the
corresponding system of simple roots is 
$\{\ep_1-\ep_2,\ep_2-\ep_3,\dots,\ep_{n}-\ep_{n+1}\}$. 

The associated affine reflection group is generated by the
reflections with respect to the
hyperplanes $\mathcal R=\{x_i-x_j=k:\ 1\le i<j\le n+1,\ k\in\Z\}$. The
elements of this group are called 
\index{affine permutation}\index{permutation,
affine}{\em affine permutations\/}. They act by permuting the
coordinates $x_1,x_2,\dots,x_{n+1}$ and adding a vector
$(k_1,k_2,\dots,k_{n+1},0,0,\dots)$ with $k_1+k_2+\dots+k_{n+1}=0$.
A typical chamber is $C=\{\mathbf x:\ x_1> x_2>\dots>x_{n+1}>x_1-1\}$,
with the same corresponding system of simple roots.

\index{$B_n$}\index{C_n}{\em Type $B_n$, $C_n$}: 
The root system $B_n$ is $\Phi=\{\pm\ep_i\pm\ep_j:\ 1\le i\ne j\le
n\}\cup\{\pm\ep_i:\ 1\le i\le n\}$. 
The root system $C_n$ is $\Phi=\{\pm\ep_i\pm\ep_j:\ 1\le i\ne j\le
n\}\cup\{\pm2\ep_i:\ 1\le i\le n\}$.
The set of reflecting hyperplanes in either case is therefore $\mathcal 
R=\{\pm x_i\pm x_j=0:\ 1\le
i<j\le n\}\cup\{x_i=0\}$. Obviously, the reflection with respect $x_i-x_j=0$
acts by interchanging the $i$-th and $j$-th coordinate, 
the reflection with respect to $x_i+x_j=0$
acts by interchanging the $i$-th and $j$-th coordinate and changing
the sign of both, while the 
reflection with respect to $x_i=0$ acts by changing sign of the $i$-th
coordinate. 

The associated finite reflection group is the group of
\index{permutation, signed}\index{signed permutation}{\em signed
permutations\/} of the coordinates $x_1,x_2,\dots,x_{n}$, which acts
by permuting and changing signs of (some of) the coordinates
$x_1,x_2,\dots,x_n$. This group is
isomorphic to the semidirect product $\S_n\ltimes ??(\Z/2\Z)^n$. 
A typical chamber is $C=\{\mathbf x:\ x_1> x_2>\dots>x_{n}>0\}$, the
corresponding system of simple roots is 
$\{\ep_1-\ep_2,\ep_2-\ep_3,\dots,\ep_{n-1}-\ep_{n},\ep_n\}$. 

The associated affine reflection group is generated by the
reflections with respect to the
hyperplanes $\mathcal R=\{\pm x_i\pm x_j=k:\ 1\le i<j\le n,\ k\in\Z\}\cup
\{x_i=k:\ 1\le i\le n,\ k\in\Z\}$. 
The elements of this group act by permuting and changing signs of
(some of) the
coordinates $x_1,x_2,\dots,x_{n}$ and adding a vector
$(k_1,k_2,\dots,k_{n},0,0,\dots)$ with $k_1+k_2+\dots+k_{n}\equiv
0\pmod2$.
A typical chamber is $C=\{\mathbf x:\ 1>x_1> x_2>\dots>x_{n}>0\}$??, 
with the same corresponding system of simple roots.

\index{$D_n$}{\em Type $D_n$}: 
The root system $D_n$ is $\Phi=\{\pm\ep_i\pm\ep_j:\ 1\le i\ne j\le
n\}$. 
The set of reflecting hyperplanes is therefore $\mathcal 
R=\{\pm x_i-x_j=0:\ 1\le
i<j\le n\}\cup\{x_i=0\}$. Obviously, $D_n$ is a subset of $B_n$ or
$C_n$. The action of the reflection with respect to a hyperplane $\pm
x_i\pm x_j=0$ was already explained there.

The associated finite reflection group is the group of
\index{permutation, signed}\index{signed permutation}signed
permutations of the coordinates $x_1,x_2,\dots,x_{n}$ {\em with an
even number of sign changes\/}. It acts
by permuting the coordinates
$x_1,x_2,\dots,x_n$ and changing an even number of signs thereof. 
This group is
isomorphic to the semidirect product $\S_n\ltimes ??(\Z/2\Z)^{n-1}$. 
A typical chamber is $C=\{\mathbf x:\ x_1> x_2>\dots>x_{n-1}>\v{x_n}\}$, the
corresponding system of simple roots is 
$\{\ep_1-\ep_2,\ep_2-\ep_3,\dots,\ep_{n-1}-\ep_{n},\ep_{n-1}+\ep_n\}$. 

The associated affine reflection group is generated by the
reflections with respect to the
hyperplanes $\mathcal R=\{\pm x_i\pm x_j=k:\ 1\le i<j\le n,\ k\in\Z\}$. 
The elements of this group act by permuting the
coordinates $x_1,x_2,\dots,x_{n}$, changing an even number of signs
thereof??, and adding a vector
$(k_1,k_2,\dots,k_{n},0,0,\dots)$ with $k_1+k_2+\dots+k_{n}\equiv
0\pmod2$.
A typical chamber is $C=\{\mathbf x:\ 1>x_1> x_2>\dots>x_{n-1}>\v{x_n}\}$??, 
with the same corresponding system of simple roots.

%\index{$F_4$}{\em Type $F_4$}: 
%The root system is $\Phi=\{\pm\ep_i\pm\ep_j:\ 1\le i<j\le
%4\}\cup\{\pm\ep_i:\ 1\le i\le4\}\cup\{\frac {1} {2}(\pm\ep_1 \pm\ep_2
%\pm\ep_3 \pm\ep_4)\}$.
%A typical chamber for the corresponding finite reflection group is 
%$C=\{\mathbf x:\ x_1>x_2+x_3+x_4\text { and }x_2> x_3>x_4>0\}$, and
%$C=\{\mathbf x:\ 1>x_1>x_2+x_3+x_4\text { and }x_2> x_3>x_4>0\}$ for the
%affine reflection group.

%\index{$E_6$}{\em Type $E_6$}: 
%The root system is $\Phi=\{\pm\ep_i\pm\ep_j:\ 1\le i<j\le
%5\}\cup\{\pm\frac {1} {2}(\ep_8-\ep_7-\ep_6
%+\sum _{i=1} ^{5}\pm\ep_i)\}$, where the number of minus signs in
%the sum is odd.
%A typical chamber for the corresponding finite reflection group is 
%$C=\{\mathbf x:\ x_1+x_8>\sum _{i=2} ^{7},\ x_1+x_2>0\text { and }
%x_1<x_2<x_3<x_4<x_5\}$, and ??

??Figures!!, also exceptional types??

??list equalities: $I_2(4)=C_2$, etc.


It is now apparent that Theorem~\ref{T7.1} follows from
Theorem~\ref{T7.3} specialized to $A_{d-1}$. Also,
Theorem~\ref{??parallele Diagonalen} follows from Theorem~\ref{T7.3}
in the special case of the {\em affine\/} reflection group
corresponding to $A_1$. To make things more explicit, we state the
specialization of Theorem~\ref{T7.3} to affine $A_{d-1}$, for arbitrary
$d$. It is equivalent to a result which was first discovered by
\index{Filaseta, Michael}Filaseta 
\cite[Theorem~??]{FilaAA}.
\begin{Theorem}
Let $A=(a_1,a_2,\dots,a_d)$ and $E=(e_1,e_2,\dots,e_d)$ be points in
$\Z^d$ with $a_1> a_2>\dots> a_d$ and $e_1> e_2>\dots>
e_d$. The number of all {\em(}simple{\em)} 
paths from $A$ to $E$ staying in the region
$x_1> x_2>\dots> x_d>x_1-K$ equals
\begin{multline} \label{e7.15} 
\v{L(A\to E\mid x_1> x_2>\dots> x_d> x_1-K)}\\
=\Big(\sum _{i=1}
^{d}(e_i-a_i)\Big)!\sum _{k_1+\dots k_d=0} ^{} 
\det_{1\le i,j\le d}\(\frac {1} {(e_i-a_j+u_iK)!}\).
\end{multline}
\end{Theorem}
\begin{proof}We use Theorem~\ref{T7.3} with $\SS=\{(1,0),(0,1)\}$ and
$m=\sum _{i=1} ^{d}(e_i-a_i)$ in the special case of affine
$A_{d-1}$. The region which we consider is $\{\mathbf x:\
x_1>x_2>\dots>x_d>x_1-K\}$. Therefore,
in the prototypical description of the $A_{d-1}$ case we have to
transform the underlying space by a scalar multiplication by the
constant $K$. Thus, the reflection group $W$ which we have to
consider is the group of permutations of coordinates and additions of
vectors $(k_1K,k_2K,\dots,k_{d}K)$ with $k_1+k_2+\dots+k_{d}=0$.
Then, by \eqref{e7.13} we have
\begin{multline}\notag
\v{L(A\to E\mid x_1>x_2>\dots>x_d>x_1-K)}\\
=\sum _{\si\in\S_d} ^{}\sum _{k_1+\dots k_d=0}
^{}\v{L(A_\si+(k_1K,\dots,k_dK)\to E)}.
\end{multline}
It is easily checked that this identity immediately implies
\eqref{e7.15}.
\end{proof}

Next we illustrate the decomposition of reflection groups. We should
remark that if a root system $\Phi$, with associated reflection group
$W$, decomposes into the disjoint
union $\Phi=\Phi_1\cup\dots \Phi_r$ of root systems, then $W$ is the
product $W=W_1\times\dots\times W_r$, if $W_i$ is the reflection
group associated to $\Phi_i$, $i=1,2,\dots,r$. Actually
we already encountered such a case, namely when considering regions
of the form \eqref{e7.6a}. It is straight-forward to check that this
is a chamber for the root system $A_{i_1-1}\cup
A_{i_2-1}\cup\dots\cup A_{i_r-1}$, with associated reflection group
$\S_{i_1}\cup \S_{i_2}\cup\dots\cup \S_{i_r}$, which matches
with what we did there.

Let us conclude with another example. 
$\{K>x_1>0,\ x_2>x_3>0\}$.



Finally we prove Theorem~\ref{T7.3}.
\begin{proof}[Proof of Theorem~\ref{T7.3}] 
We proceed along the lines of the proof of
Theorem~\ref{T7.1}. 

We may rewrite \eqref{e7.5} in the form
\begin{equation} \label{e7.14} 
\v{L_m??(A\to E;\SS\mid \text {inside }C)}
=\sum _{w,P} ^{}\sgn w ,
\end{equation}
where the sum is over all pairs $(w,P)$ with $w\in W$ and $P\in
L_m(w(A)\to E)$.
The proof of \eqref{e7.14} is by a sign-reversing involution on the set
of all such pairs $(w,P)$
where $P$ touches at least one of the
hyperplanes in $\mathcal H_0$. Sign-reversing has to be
understood with respect to $\sgn w$. Provided the existence of such an
involution, the only contributions to the sum in \eqref{e7.14} would be
by pairs $(w,P)$ where $P$ does not touch any of the hyperplanes in
$\mathcal H_0$. We claim that this 
can be only the case for $w=\text{id}$. In fact, as we already mentioned, it
is one of the properties of a reflection group $W$ that, given one
chamber $C$, all chambers are $w(C)$, $w\in W$, and all $w(C)$'s
are distinct. Therefore, if $A$ is in $C$ and $w\ne \text {id}$ then $w(A)$
must be in a different chamber and so cannot be in $C$. Thus evidently,
any path from $w(A)$ to $E$, which is inside $C$, must touch at least
one of the bordering hyperplanes.
This would prove \eqref{e7.14} and hence the theorem.

Now we construct the promised involution. 
Fix some order of the hyperplanes in $\mathcal H_0$.
Let $(w,P)$ be a pair with $w\in W$ and $P\in L(w(A)\to E)$
with $P$ touching at least one of the hyperplanes in $\mathcal H_0$.
Consider all meeting points of $P$ with hyperplanes in $\mathcal H_0$. Choose the
last meeting point and denote it by $M$. $M$ must be a lattice point
because of the assumptions that involve the constants $k_H$. 
Let $H$ be the first
hyperplane (in the chosen order) that meets $P$.
Then we form the new path
$P'$ by reflecting the portion of $P$ from the starting point
$w(A)$ up to $M$ with respect to $H$ and leaving the portion
from $M$ to $P$ invariant. By assumption, reflection of a step from
$\SS$ is again in a step $\SS$. So also $P'$ consists of
steps from $\SS$ only. Evidently, the starting point
of $P'$ is $w_Hw(A)$, where $w_H$ denotes the reflection
with respect to $H$. Hence,
$(w_Hw,P')$ is a pair under consideration for the sum in
\eqref{e7.14} and $P'$ touches one of the
hyperplanes in $\mathcal H_0$ (namely $H$). This mapping is an involution since
nothing was changed after $M$. Besides, we have
$\sgn w_Hw=-\sgn w$. Therefore it is also sign-reversing.
This completes the proof of the theorem.
\end{proof}



\section{Simple lattice paths bounded by $x_0=\sum _{i=1}
^{d}\mu_ix_i$} 
\label{s7.3}
In this section we consider simple lattice paths in $\Z^{d+1}$
restricted by a hyperplane of the form $x_0=\sum _{i=1} ^{d}\mu_ix_i$
where $\mu_i$, $i=0,1,\dots,d$, are nonnegative integers. The results
of this section generalize those of Chapter~\ref{ch1}, Section~\ref{s1.2}. It should be
noted that the reflection principle does not apply because in general
the set of steps (??more precisely) is not invariant under reflection
with respect to such a hyperplane (??except of course when $\mu_i=1$
for all $i$, in which case the reflection principle applies).
It will be seen that the proof methods
for Theorem~\ref{T1.4}, path decomposition combined with generating
function methods and cycle lemma, respectively, carry over to this
higher-dimensional problem.

\begin{Theorem} \label{T7.4}
Let $\mu_0,\mu_1,\dots,\mu_d$ be nonnegative integers and
$c_0,c_1,\dots,c_d$ integers such that $c_0\ge \sum _{i=1}
^{d}\mu_ic_i$. The number of all lattice paths from the origin to
$(c_0,c_1,\dots,c_d)$ not crossing the hyperplane $x_0= \sum _{i=1}
^{d}\mu_ix_i$ is given by
\begin{equation} \label{e7.20} 
\v{\L{\boldsymbol0\to (c_0,c_1,\dots,c_d)\mid x_0\ge\sum _{i=1}
^{d}\mu_ix_i}} =\frac {c_0-\sum _{i=1} ^{d}\mu_ic_i+1} 
{1+\sum _{i=0} ^{d}c_i}\binom {1+\sum _{i=0}
^{d}c_i} {c_0+1,c_1,c_2,\dots,c_d}.
\end{equation}
\end{Theorem}

\begin{proof}Let us denote the hyperplane $x_0=\sum _{i=1} ^{d}\mu_ix_i$
by $H$. For $k\ge0$ 
let $\mathcal L_k$ denote the set of all paths from the origin to
some point on the hyperplane $x_0=k+\sum _{i=1} ^{d}\mu_ix_i$ never
crossing $H$. Let $s_i$ denote the unit step in $x_i$-direction. Very
analogous to the decomposition \eqref{e1.?} in the proof of
Theorem~\ref{T1.4}, the set $\mathcal L_k$ can be decomposed in the form
\begin{equation} \label{e7.21} 
\mathcal L_k=\mathcal L_0(s_0\mathcal L_0)^k.
\end{equation}
Namely, a path $P$ in $\mathcal L_k$ is decomposed into
$$P_0s_0P_1s_0\dots P_{k-1}s_0P_k,$$
where $P_j$ starts at the point immediately following the last
intersection of $P$ with $x_0=j-1+\sum _{i=1} ^{d}\mu_ix_i$ and runs
until the last intersection of $P$ with $x_0=j+\sum _{i=1}
^{d}\mu_ix_i$. The set $\mathcal L_0$ itself can be decomposed with
respect to the last step of paths,
\begin{equation} \label{e7.22} 
\mathcal L_0=\{\ep\}\cup\mathcal L_{\mu_1}s_1\cup\mathcal L_{\mu_2}s_2\cup\dots\cup
\mathcal L_{\mu_d}s_d.
\end{equation}
The decompositions \eqref{e7.21} and \eqref{e7.22} by ?? translate
into equations for the generating functions
??explain multi-notation??
$$F_k(\mathbf z)=\sum _{\mathbf n\ge\boldsymbol 0} ^{}\v{\L{\boldsymbol
0\to (k+\sum _{i=1} ^{d}\mu_in_i,n_1,n_2,\dots,n_d)\mid x_0\ge \sum
_{i=1} ^{d} \mu_ix_i}}\mathbf z^{\mathbf n}.$$
The decomposition \eqref{e7.21} translates into
\begin{equation} \label{e7.23} 
F_k(\mathbf z)=F_0(\mathbf z)^{k+1},
\end{equation}
and \eqref{e7.22} translates into
\begin{equation} \label{e7.24} 
F_0(\mathbf z)=1+z_1F_{\mu_1}(\mathbf z)+\dots+z_dF_{\mu_d}(\mathbf z).
\end{equation}
Inserting \eqref{e7.23} into \eqref{e7.24} gives
\begin{equation} \label{e7.25} 
F_0(\mathbf z)=1+z_1F_0(\mathbf z)^{\mu_1+1}+\dots+z_dF_0(\mathbf z)^{\mu_d+1}.
\end{equation}
To be able to apply Lagrange inversion, we write $F_0(\mathbf
z)=1+G_0(\mathbf z)$. Thus, by replacing $z_i$ by $tz_i$
and a little rearrangement, \eqref{e7.25} becomes 
$$\frac {G_0(t\mathbf z)} {\sum _{i=1} ^{d}z_i(1+G_0(t\mathbf
z))^{\mu_i+1}}=t.$$
From this we infer that, as a formal power series in $t$, $G_0(t\mathbf
z)$ is the compositional inverse of $t/\sum _{i=1}
^{d}z_i(1+t)^{\mu_i}$. We are interested in the coefficients of the
series $F_k(\mathbf z)$ which by \eqref{e7.23} equals $(1+G_0(\mathbf
z))^{k+1}$. By using Lagrange inversion ?? with $f(t)=t/\sum _{i=1}
^{d}z_i(1+t)^{\mu_i+1}$ and $g(t)=(1+G_0(\mathbf t\mathbf z))^{k+1}$
we get
\begin{align} \notag
\coef{t^n}&(1+G_0(t\mathbf z))^{k+1}=\frac {1}
{n}\coef{t^{-1}}(k+1)(1+t)^k t^{-n}(\sum _{i=1}
^{d}z_i(1+t)^{\mu_i+1})^n\\
\notag
&=\frac {k+1} {n}\coef{t^{n-1}}\sum _{n_1+\dots n_d=n} ^{}\binom
{n}{n_1,n_2,\dots,n_d} \mathbf z^{\mathbf n}(1+t)^{k+\sum _{i=1}
^{d}(\mu_i+1)n_i} \\
\notag
&=\frac {k+1} {n}\sum _{n_1+\dots+n_d=n} ^{}\binom
{n}{n_1,n_2,\dots,n_d} \binom {k+\sum _{i=1} ^{d}(\mu_i+1)n_i} 
{n-1}\mathbf z^{\mathbf n}\\
\notag
&=\sum _{n_1+\dots+n_d=n} ^{}\frac {k+1} {k+1+\sum _{i=1}
^{d}(\mu_i+1)n_i} \binom {k+1+\sum _{i=1} ^{d}(\mu_i+1)n_i}
{k+1+\sum _{i=1}
^{d}\mu_in_i,n_1,n_2,\dots,n_d} \mathbf z^{\mathbf n}.
\end{align}
Hence we have
$$F_k(\mathbf z)=\sum _{\mathbf n\ge\boldsymbol 0} 
^{}\frac {k+1} {k+1+\sum _{i=1}
^{d}(\mu_i+1)n_i} \binom {k+1+\sum _{i=1} ^{d}(\mu_i+1)n_i}{k+1+\sum _{i=1}
^{d}\mu_in_i,n_1,n_2,\dots,n_d} \mathbf z^{\mathbf n}.$$
To obtain the desired number of paths we have to take the coefficient
of $z_1^{c_1}z_2^{c_2}\cdots z_d^{c_d}$ in $F_{c_0-\sum _{i=1}
^{d}\mu_ic_i}$. This gives exactly the expression in \eqref{e7.20}.
\end{proof}


\section{Simple paths with a general boundary} \label{s7.5}
\index{Sulanke, Robert A.}Sulanke: Result in \cite{SulaAA}, the below proof
is from \cite{SulaAC}.

In this section we generalize the enumeration problem of
Chapter~\ref{ch1}, Section~\ref{s1.6} to arbitrary dimensions. Let $n_1,n_2,\dots,n_d$
be nonnegative integers and $\mathbf a$ and
$\mathbf b$ be increasing 
integer functions defined on the box $\prod _{i=1}
^{d}\{0,1,\dots,n_i\}$ such that $\mathbf a\ge \mathbf b$. $\mathbf a$
is increasing
means that $\mathbf a(\mathbf i)\le \mathbf a(\mathbf j)$ whenever $\mathbf i\le
\mathbf j$ in the usual product order. We ask for the number of all paths
in $\Z^{d+1}$ from $(\boldsymbol 0,\mathbf b(\boldsymbol 0))$ to
$(\mathbf n,\mathbf a(\mathbf n))$ that always stay in the region ``that is
bounded by $\mathbf a$ and $\mathbf b$" by which we mean the region
\begin{equation} \label{e7.40} 
\{(\mathbf i,y):\mathbf b(\mathbf i)\le y\le\mathbf a(\mathbf i)\}.
\end{equation}
The generalization of Theorem~\ref{T1.15} reads as follows.

\begin{Theorem} \label{T7.10}
Let $n_1,n_2,\dots,n_d$ be nonnegative integers and $p=\prod _{i=1} ^{d}n_i$.
Assume that the points in the box ??$[\boldsymbol0,\mathbf n]$ are
$\boldsymbol0=\mathbf u_0,\mathbf u_1,\mathbf u_2,\dots,\mathbf u_p=\mathbf n$,
ordered lexicographically. Then the number of all lattice paths 
in $\Z^{d+1}$ from $(\boldsymbol 0,\mathbf b(\boldsymbol 0))$ to
$(\mathbf n,\mathbf a(\mathbf n))$ that always stay in the region
\eqref{e7.40} equals
\begin{multline} \label{e7.41} 
\v{\L{(\boldsymbol 0,\mathbf b(\boldsymbol 0))\to
(\mathbf n,\mathbf a(\mathbf n))\mid \mathbf a\ge \mathbf y\ge \mathbf b}}\\
=(-1)^{\sum _{i=1} ^{d}n_i+\prod _{i=1} ^{d}n_i}
\det_{0\le i,j\le \sum _{i=1} ^{d}n_i-1}\(\binom {\mathbf a(\mathbf u_{i})-
\mathbf b(\mathbf u_{j+1})+1} {\mathbf u_{j+1}-\mathbf u_{i}}\).
\end{multline}
\end{Theorem}

\begin{proof}As in the proof of Theorem~\ref{T1.15} we transform the
enumeration problem into one on nonintersecting lattice paths.

Define two sequences of points, $\mathbf A=((\mathbf u_{i-1},\mathbf a(\mathbf
u_{i-1})+ \V{\mathbf u_{i-1}}))_{i=1,2,\dots,\V{\mathbf n}}$ and
$\mathbf E=((\mathbf u_{i},\mathbf b(\mathbf
u_{i})+ \V{\mathbf u_{i}}-1))_{i=1,2,\dots,\V{\mathbf n}}$. We map each
lattice path in $\L{(\boldsymbol 0,\mathbf b(\boldsymbol 0))\to
(\mathbf n,\mathbf a(\mathbf n))\mid \mathbf a\ge \mathbf y\ge \mathbf b}$ to a
family of nonintersecting lattice paths, consisting of unit
steps in positive $x_i$-direction, $i=1,2,\dots,d$, and of unit steps
in negative $x_{d+1}$-direction, which connect some permutation of the
points of $\mathbf A$ (the starting points) to those of $\mathbf E$ (the
end points). This correspondence is defined as follows. See
Figure~\ref{F7.5}. Let $P$ be a
path in $\L{(\boldsymbol 0,\mathbf b(\boldsymbol 0))\to
(\mathbf n,\mathbf a(\mathbf n))\mid \mathbf a\ge \mathbf y\ge \mathbf b}$. Let
$s$ be any step of $P$ that is not a step in $x_{d+1}$-direction, say
$s=(\mathbf u_i,y)\to (\mathbf u_j,y)$. Then shift $s$ by $\V{\mathbf u_i}$
units in $x_{d+1}$-direction and add $\mathbf a(\mathbf u_i)-y$ steps in
(negative) $x_{d+1}$-direction prior to $s$ and $y-\mathbf b(\mathbf u_j)$
steps in (negative) $x_{d+1}$-direction after $s$. Thus a path from
$(\mathbf u_i,\mathbf a(\mathbf u_i)+\V{\mathbf u_i})$ to 
$(\mathbf u_j,\mathbf b(\mathbf u_j)+\V{\mathbf u_j}-1)$ is formed, consisting
only of steps in $x_{d+1}$-direction with the exception of the shifted
step $s$.
\begin{Figure}\label{F7.5}
Figure!!
\end{Figure}
All other points are connected ``vertically'', to be precise, 
$(\mathbf u_i,\mathbf a(\mathbf u_i)+\V{\mathbf u_i})$ is connected with
$(\mathbf u_i,\mathbf b(\mathbf u_i)+\V{\mathbf u_i}-1)$ whenever this does not
intersect $P$. It is not difficult to see that thus we obtain a family
of nonintersecting lattice paths which connects the points of $\mathbf
A$ (in some order) with those of $\mathbf E$.

Now we claim two things.
\begin{enumerate}
\item All families of nonintersecting lattice paths that connect some
permutation of $\mathbf A$ with $\mathbf E$ can be generated by a lattice
paths $P$ in $\L{(\boldsymbol 0,\mathbf b(\boldsymbol 0))\to
(\mathbf n,\mathbf a(\mathbf n))\mid \mathbf a\ge \mathbf y\ge \mathbf b}$ in that
way. Therefore, $\L{(\boldsymbol 0,\mathbf b(\boldsymbol 0))\to
(\mathbf n,\mathbf a(\mathbf n))\mid \mathbf a\ge \mathbf y\ge \mathbf b}$ is in
bijection with these families of nonintersecting lattice paths.
\item The permutations of the starting points corresponding to these
families of nonintersecting lattice paths all have equal sign. In fact
the sign is $(-1)^{\sum _{i=1} ^{d}n_i+\prod _{i=1} ^{d}n_i}$.
\end{enumerate}

Provided these two assertions hold true, Theorem~\ref{T2.3} can be
applied to infer that the number of lattice paths in question is
$$(-1)^{\sum _{i=1} ^{d}n_i+\prod _{i=1} ^{d}n_i}
\det_{0\le i,j\le p-1}\Big(\v{L(A_j\to E_i)}\Big),$$
where $A_j$ is the $j$-th point in the sequence $\mathbf A$ and $E_i$ is
the $i$-th point in the sequence $\mathbf E$. Evidently, by \eqref{e7.1}
this expression agrees with the right-hand side of \eqref{e7.41}.

So it remains to prove the two assertions. We start with proving item
2). Let $P$ be a path in $\L{(\boldsymbol 0,\mathbf b(\boldsymbol 0))\to
(\mathbf n,\mathbf a(\mathbf n))\mid \mathbf a\ge \mathbf y\ge \mathbf b}$ and let
$\boldsymbol 0=\mathbf u_0,\mathbf u_{i_1},\mathbf u_{i_2},\dots,\mathbf
u_{i_{\V{\mathbf n}-1}},u_p=\mathbf n$ be its projection on the hyperplane
$x_{d+1}=0$. Then the permutation corresponding to the family of
lattice paths associated with $P$ is
$$\begin{pmatrix} 1&i_1+1&i_2+1&\dots&i_{\V{\mathbf n}-1}+1&j_1+1
&j_2+1&\dots &j_{p-\V{\mathbf n}}+1\\
i_1&i_2&i_3&\dots&p&j_1
&j_2&\dots &j_{p-\V{\mathbf n}}
\end{pmatrix},$$
where $\mathbf u_{j_1},\mathbf u_{j_2},\dots$ are
the points in the box $[\boldsymbol 0,\mathbf n]$ not in the projection
of $P$, ordered such that $j_1<j_2<\cdots$. In order to determine the
sign of this permutation, we transform it to the identity permutation
and record how many transpositions we need. First we rearrange the
permutation such that the top row becomes $1,2,\dots,p$. (This does
not change the permutation.) Now notice
that $j_1<j_2<\cdots$ and that each value $j_k$ in the bottom row is
offset one place to the right. Hence for each $j_k$ we need exactly
one transposition to put it into its right place, beginning with
$j_1$, continuing with $j_2$, etc. After that the permutation will
already have been converted into the identity permutation. The number
of transpositions needed was the number of $j_k$'s, which is
$p-\V{\mathbf n}=\prod _{i=1} ^{d}n_i-\sum _{i=1} ^{d}n_i$. Therefore
the sign of the permutation is as claimed.

For the proof of item 1) take any family $\P$ of nonintersecting
lattice paths connecting some permutation of $\mathbf A$ with $\mathbf E$.
We have to prove the following:
\begin{enumerate}
\item[(a)] Each path of $\P$ has at most one step not in
$x_{d+1}$-direction. 
\item[(b)] For every $k=0,1,\dots,p-1$ there is exactly one non-straight 
path that starts at a point $(\mathbf
i,\mathbf a (\mathbf i)+\V{\mathbf i})$ with $\V{\mathbf i}=k$.
\end{enumerate}

In order 
to prove (a), suppose in contrary that there is some path $Q$ in $\P$ 
containing at least 2 steps not in $x_{d+1}$-direction. Suppose that
$Q$ starts at $(\mathbf l,\mathbf a (\mathbf l)+\V{\mathbf l})$ with
$\V{\mathbf i}=k$. Consider all paths ending at some point 
$(\mathbf j,\mathbf b (\mathbf j)+\V{\mathbf j})$ where $\V{\mathbf j}\le k$.
All these paths have to start at some point 
$(\mathbf i,\mathbf a (\mathbf i)+\V{\mathbf i})$ with $\V{\mathbf i}\le k$. The
number of the latter points is exactly one more than the number of the
former, therefore the additional path that starts from one of the
latter points is exactly $Q$. And, by assumption, $Q$ leads to an end
point $(\mathbf j,\mathbf b (\mathbf j)+\V{\mathbf j})$ with $\V{\mathbf j}\ge
k+2$. Therefore, all the points $(\mathbf i,\mathbf a (\mathbf i)+\V{\mathbf
i})$ with $\V{\mathbf i}=k+1$ are connected straight with the points 
$(\mathbf i,\mathbf b (\mathbf i)+\V{\mathbf i})$. But one of these paths must
intersect $Q$, which is absurd.

A similar argument leads to a contradiction if we assume that for some
$k$ there are at least two non-straight paths starting at a point
$(\mathbf i,\mathbf a (\mathbf i)+\V{\mathbf i})$ with $\V{\mathbf i}=k$. In
fact, in
this case there would not be enough starting points left to connect to
points $(\mathbf j,\mathbf b (\mathbf j)+\V{\mathbf j})$ with $\V{\mathbf j}\le
k$. 
\end{proof}






%\end{document}
