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

\textwidth35pc
\textheight47pc
\hoffset-1.5truecm



%\begin{document}

\chapter{Three-step lattice paths} \label{ch3}
The subject of this chapter is lattice paths in $\Z^2$, which consist of
\index{up-step}{\em up-steps} $(1,1)$, \index{down-step}{\em down-steps} 
$(1,-1)$, and \index{level step}{\em level-steps} $(1,0)$ or
$(2,0)$, and which do not pass below the $x$-axis. If the only allowed
level-steps are unit steps $(1,0)$, then the corresponding paths are called
\index{path, Motzkin}\index{Motzkin path}{\em Motzkin paths}. 
If the only allowed
level-steps are double steps $(2,0)$, then the corresponding paths are called
\index{path, Schr\"oder}\index{Schr\"oder path}{\em Schr\"oder paths}. 
We call the special paths which consist of just up- and down-steps
(but contain no level-steps) 
\index{path, Catalan}\index{Catalan path}{\em Catalan paths}. 

\begin{Figure} \label{F3.1}
$$
\Gitter(12,5)(-1,0)
\Koordinatenachsen(12,5)(-1,0)
\Pfad(0,0),33141133443\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,2)
\DickPunkt(4,1)
\DickPunkt(5,1)
\DickPunkt(6,1)
\DickPunkt(7,2)
\DickPunkt(8,3)
\DickPunkt(9,2)
\DickPunkt(10,1)
\DickPunkt(11,2)
\hbox{\hskip6.5cm}
$$
\centerline{\small A Motzkin path}
\end{Figure}

\begin{Figure} \label{F3.2}
$$
\Gitter(15,5)(-1,0)
\Koordinatenachsen(15,5)(-1,0)
\Pfad(0,0),33114111133444\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(4,2)
\DickPunkt(5,1)
\DickPunkt(7,1)
\DickPunkt(9,1)
\DickPunkt(10,2)
\DickPunkt(11,3)
\DickPunkt(12,2)
\DickPunkt(13,1)
\DickPunkt(14,0)
\hbox{\hskip7.5cm}
$$
\centerline{\small A Schr\"oder path}
\end{Figure}


\begin{Figure} \label{F3.C}
$$
\Gitter(15,5)(-1,0)
\Koordinatenachsen(15,5)(-1,0)
\Pfad(0,4),44433444334344\endPfad
\DickPunkt(0,4)
\DickPunkt(1,3)
\DickPunkt(2,2)
\DickPunkt(3,1)
\DickPunkt(4,2)
\DickPunkt(5,3)
\DickPunkt(6,2)
\DickPunkt(7,1)
\DickPunkt(8,0)
\DickPunkt(9,1)
\DickPunkt(10,2)
\DickPunkt(11,1)
\DickPunkt(12,2)
\DickPunkt(13,1)
\DickPunkt(14,0)
\hbox{\hskip6.5cm}
$$
\centerline{\small A Catalan path}
\end{Figure}


\section{Elementary results on Motzkin and Schr\"oder paths}
\label{s3.1}
Let $M=\{(1,1),(1,-1),(1,0)\}$ and 
$S=\{(1,1),(1,-1),(2,0)\}$, so that $M$ is the set of steps allowed
in Motzkin paths (see Figure~\ref{F3.1} for an example) 
and $S$ is the set of steps allowed
in Schr\"oder paths (see Figure~\ref{F3.2} for an example).  

A frequently used alternative way to view Schr\"oder paths is by
reflecting the picture with respect to the $x$-axis, rotating the
result by $45^\circ$, and finally scaling everything by a factor of
$1/\sqrt{2}$, so that the steps $(1,1),(1,-1),(2,0)$ 
are replaced by the steps $(1,0),(0,1),(1,1)$, in that order.
Figure~\ref{F3.3} shows the result of this translation when applied
to the Schr\"oder path in Figure~\ref{F3.2}. It translates Schr\"oder
paths into paths which consist of unit horizontal and vertical steps in
the positive direction and of upwards diagonal steps and which stay below
the main diagonal $y=x$ (being allowed to touch it).

\begin{Figure} \label{F3.3}
$$
\Gitter(9,9)(-1,0)
\Koordinatenachsen(9,9)(-1,0)
\Pfad(0,0),11323311222\endPfad
\DickPunkt(0,0)
\DickPunkt(1,0)
\DickPunkt(2,0)
\DickPunkt(3,1)
\DickPunkt(3,2)
\DickPunkt(4,3)
\DickPunkt(5,4)
\DickPunkt(6,4)
\DickPunkt(7,4)
\DickPunkt(7,5)
\DickPunkt(7,6)
\DickPunkt(7,7)
\thinlines
\Diagonale(-1,-1)9
\hbox{\hskip3.5cm}
$$
\end{Figure}

This translation, combined with Theorem~\ref{T1.1},
already tells us how to enumerate Motzkin and Schr\"oder paths with
given starting and end point.

\begin{Theorem} \label{T3.1}
Let $b\ge 0$ and $d\ge0$. The number of all paths from $(a,b)$ to
$(c,d)$ which consist of steps out of $M=\{(1,1),(1,-1),(1,0)\}$ and
do not pass below the $x$-axis 
\index{path, Motzkin}\index{Motzkin path}{\em (Motzkin paths)} is given by
\begin{multline} \label{e3.1}
\v{\L{(a,b)\to (c,d);M\mid y\ge0}}\\=
\sum _{k=0} ^{c-a}\binom {c-a}k\(\binom {c-a-k} {(c+d-k-a-b)/2} -
\binom {c-a-k}{(c+d-k-a+b+2)/2}\),
\end{multline}
where, by convention, a binomial coefficient is $0$ if its bottom
parameter is not an integer.

Furthermore, if $c-a$ is even, the number of all paths from $(a,b)$ to
$(c,d)$ which consist of steps out of $S=\{(1,1),(1,-1),(2,0)\}$ and
do not pass below the $x$-axis 
\index{path, Schr\"oder}\index{Schr\"oder path}{\em (Schr\"oder paths)} is given by
\begin{multline} \label{e3.2}
\v{\L{(a,b)\to (c,d);S\mid y\ge0}}=
\sum _{k=0} ^{(c-a)/2}\binom {c-a-k}k\\
\cdot\(\binom {c-a-2k} {(c+d-2k-a-b)/2} -
\binom {c-a-2k}{(c+d-2k-a+b+2)/2}\),
\end{multline}
with the same convention for binomial coefficients.
\end{Theorem}

\begin{proof} By the above described translation (reflection +
rotation), a Motzkin path from $(a,b)$ to $(c,d)$ with exactly $k$
level-steps is translated into
a path from $\(\frac {a+b} {2},\frac {a-b} {2}\)$ to 
$\(\frac {c+d} {2},\frac {c-d} {2}\)$, which consists of steps from 
$\{(1,0),(0,1),(\frac {1} {2},\frac {1} {2})\}$, among them exactly $k$ diagonal steps
$(\frac {1} {2},\frac {1} {2})$, and which stays below the main diagonal $y=x$
(being allowed to touch it). Clearly, if we remove the $k$ diagonal
steps and concatenate the resulting path pieces, we obtain a simple
path from $\(\frac {a+b} {2},\frac {a-b} {2}\)$ to
$\(\frac {c+d} {2}-\frac {k} {2},\frac {c-d} {2}-\frac {k} {2}\)$ which stays below $y=x$. The
number of the latter paths was determined in Theorem~\ref{T1.1}. On
the other hand, there are $\binom {c-a}k$ ways to reinsert the $k$
diagonal steps. Thus, Eq.~\eqref{e3.1} is established.

The proof of \eqref{e3.2} is analogous.
\end{proof}

??We will derive expressions for generating functions, 
in Section~\ref{s3.3}, and in Theorem~\ref{??}.

\medskip
It is worth stating the special case of Theorem~\ref{T3.1} 
where the paths start and
terminate on the $x$-axis separately.

\begin{Corollary} \label{C3.2}
The number of 
\index{path, Motzkin}\index{Motzkin path}Motzkin paths from $(0,0)$ to $(n,0)$ is given by
\begin{equation} \label{e3.3}
\v{\L{(0,0)\to (n,0);M\mid y\ge0}}=
\sum _{k=0} ^{\fl{n/2}}\binom {n}{2k}\frac {1} {k+1}\binom {2k} {k}.
\end{equation}
If $n$ is even, 
the number of 
\index{path, Schr\"oder}\index{Schr\"oder path}Schr\"oder paths from $(0,0)$ to $(n,0)$ is given by
\begin{equation} \label{e3.4}
\v{\L{(a,b)\to (c,d);S\mid y\ge0}}=
\sum _{k=0} ^{n/2}\binom {n/2+k}{2k}\frac {1} {k+1}\binom {2k}{k}.
\end{equation}
\noproof
\end{Corollary}

??large Schr\"oder numbers -- small Schr\"oder numbers??

The summations in \eqref{e3.1} and \eqref{e3.2} do not simplify, not
even in the special cases given in \eqref{e3.3} and \eqref{e3.4}. 

\section{A continued fraction for the weighted counting of Motzkin
paths}
\label{s3.3}\index{continued fraction}\index{fraction, continued}
We now assign a weight to each Motzkin path which starts
and ends on the $x$-axis, and express
the corresponding generating function in terms of a {\em continued
fraction}, due to \index{Flajolet, Philippe}Flajolet
\cite{FlajAA}. The weight is so general that the result covers also
Schr\"oder paths and Catalan paths.

Given a Motzkin path $P$, we define the weight $w(P)$ to be the
product of the weight of all its steps, where the weight of an
up-step is $1$ (hence, does not contribute anything to the weight), the
weight of a level-step at height $h$ is $b_h$, and the weight of
a down-step from height $h$ to $h-1$ is $\la_h$. Figure~\ref{F3.4}
shows a Motzkin paths the steps of which are labelled by their
corresponding weights, so that the weight of the path is
$b_2\la_2b_1b_1\la_3\la_2\la_1=b_1^2b_2\la_1\la_2^2\la_3$.

\begin{Figure} \label{F3.4}
$$
\Gitter(12,5)(-1,0)
\Koordinatenachsen(12,5)(-1,0)
\Pfad(0,0),33141133444\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,2)
\DickPunkt(4,1)
\DickPunkt(5,1)
\DickPunkt(6,1)
\DickPunkt(7,2)
\DickPunkt(8,3)
\DickPunkt(9,2)
\DickPunkt(10,1)
\DickPunkt(11,0)
\Label\l{1\kern3pt}(1,1)
\Label\l{1\kern3pt}(2,2)
\Label\lo{b_2}(3,2)
\Label\l{\kern3pt\la_2}(4,2)
\Label\lo{b_1}(5,1)
\Label\lo{b_1}(6,1)
\Label\l{1\kern2pt}(7,2)
\Label\l{1\kern2pt}(8,3)
\Label\l{\kern3pt\la_3}(9,3)
\Label\l{\kern3pt\la_2}(10,2)
\Label\l{\kern3pt\la_1}(11,1)
\hbox{\hskip6.5cm}
$$
\end{Figure}

Then the following theorem is true.

\begin{Theorem} \label{T3.4}
With the weight $w$ defined as above, the generating function for
\index{path, Motzkin}\index{Motzkin path}Motzkin paths running from the origin back to the $x$-axis, and 
which stay below the line $y=k$, is given by
\begin{multline} \label{e3.5}
\GF{\L{(0,0)\to(*,0);M\mid 0\le y\le k};w}\\
=\cfrac 1{1-b_0-
\cfrac {\la_1}{1-b_1-
\cfrac {\la_2}{1-b_2-\cdots-
\cfrac {\la_{k}}{1-b_k}}}}\ .
\end{multline}
In particular, the generating function for {\em all} Motzkin paths is
given by
\begin{equation} \label{e3.6}
\GF{\L{(0,0)\to*;M\mid 0\le y};w}=\cfrac 1{1-b_0-
\cfrac {\la_1}{1-b_1-
\cfrac {\la_2}{1-b_2-\cdots}}}\ .
\end{equation}

\end{Theorem}

\begin{proof} Clearly, it suffices to prove \eqref{e3.5}.
Equation~\eqref{e3.6} then follows upon letting $k\to\infty$.

We prove \eqref{e3.5} by induction on $k$. For $k=0$,
Equation~\eqref{e3.5} is trivially true. Hence, let us assume the
truth of \eqref{e3.5} for $k$ replaced by $k-1$. For accomplishing
the induction step, we consider a Motzkin path starting at the
origin, staying below $y=k$, and finally returning to the $x$-axis, 
see Figure~\ref{F3.5} for an example with $k=3$.

\begin{Figure} \label{F3.5}
$$
\Gitter(19,5)(-1,0)
\Koordinatenachsen(19,5)(-1,0)
\Pfad(0,0),13314411343133444\endPfad
\DickPunkt(0,0)
\DickPunkt(1,0)
\DickPunkt(2,1)
\DickPunkt(3,2)
\DickPunkt(4,2)
\DickPunkt(5,1)
\DickPunkt(6,0)
\DickPunkt(7,0)
\DickPunkt(8,0)
\DickPunkt(9,1)
\DickPunkt(10,0)
\DickPunkt(11,1)
\DickPunkt(12,1)
\DickPunkt(13,2)
\DickPunkt(14,3)
\DickPunkt(15,2)
\DickPunkt(16,1)
\DickPunkt(17,0)
\PfadDicke{.3pt}
\Pfad(-2,3),111111111111111111111\endPfad
\hbox{\hskip9.5cm}
$$
\end{Figure}

Such a path can be uniquely decomposed into
$$l^{e_0}uP_1d\,l^{e_1}uP_2d\,l^{e_2}\dots ,$$
where $l$ denotes a level-step, $u$ an up-step, and $d$ a down-step,
where $e_i$ are nonnegative integers, and where, for any $i$, 
$P_i$ is some path between the lines $y=1$ and $y=k$ which
starts at and returns to the line $y=1$. For example, this
decomposition applied to the path in Figure~\ref{F3.5} yields
$$l^1uP_1d\,l^2uP_2d\,l^0uP_3d,$$
where $P_1=uld$, $P_2$ is the empty path, and $P_3=luudd$.
This implies immediately the
generating function equation
\begin{multline*} 
\GF{\L{(0,0)\to(*,0);M\mid 0\le y\le k};w}\\=\frac {1} 
{1-b_0-\la_1 \cdot\GF{\L{(0,1)\to(*,1);M\mid 1\le y\le k};w}}.
\end{multline*}
By induction, the generating function on the right-hand side is
known: it is given by \eqref{e3.5} with $k$ replaced by $k-1$, 
$b_i$ replaced by $b_{i+1}$, and $\la_i$ replaced by $\la_{i+1}$, for
all $i$. This completes the induction step.
\end{proof}

This result has numerous consequences. First of all, it allows to
derive algebraic expressions for the generating functions $\sum
_{n\ge0} M_nz^n$ and $\sum _{n\ge0} S_nz^n$, where $M_n$ denotes the
number of all Motzkin paths from $(0,0)$ to $(n,0)$, and where $S_n$
denotes the number of all Schr\"oder paths from $(0,0)$ to $(n,0)$.
By definition, $M_0=S_0=1$.
The numbers $M_n$ are called 
\index{number, Motzkin}\index{Motzkin number}{\em Motzkin
numbers}, while the numbers $S_n$ are called (large??)
\index{number, Schr\"oder}\index{Schr\"oder number}{\em Schr\"oder numbers}. The first of these
numbers are given in the table below.
$$
\begin{tabular} {r|c|c|c|c|c|c|c|c|c|c|c}
&0&1&2&3&4&5&6&7&8&9&10\\ \hline
$M_n$&1& 1& 2& 4& 9& 21& 51& 127& 323& 835& 2188\\ \hline
$S_n$&1& 0& 2& 0& 6&  0& 22&   0&  90&   0&  394
\end{tabular}$$


\begin{Theorem} \label{T3.5}
We have
\begin{equation} \label{e3.7}
\sum _{n\ge0} ^{}M_nz^n=\frac {1-z-\sqrt{1-2z-3z^2}} {2z^2}
\end{equation}
and
\begin{equation} \label{e3.8}
\sum _{n\ge0} ^{}S_{2n}z^n=\frac {1-z-\sqrt{1-6z+z^2}} {2z}.
\end{equation}
\end{Theorem}
\begin{proof} 
By \eqref{e3.6} with $b_i=z$ and $\la_i=z^2$ for all $i$, we have 
$$\sum _{n\ge0} ^{}M_nz^n=\cfrac 1{1-z-
\cfrac {z^2}{1-z-
\cfrac {z^2}{1-z-\cdots}}}\ .
$$
Thus, in particular, we have $M(z)=1/(1-z-M(z))$. The appropriate
solution of this quadratic equation is exactly the right-hand side of
\eqref{e3.7}. 

Similarly, by setting $b_i=\la_i=z^2$ in \eqref{e3.6} for all $i$, we
obtain 
$$\sum _{n\ge0} ^{}S_nz^n=\cfrac 1{1-z^2-
\cfrac {z^2}{1-z^2-
\cfrac {z^2}{1-z^2-\cdots}}}\ ,
$$
and eventually \eqref{e3.8} after solving the analogous quadratic
equation.
\end{proof}

In Section~\ref{s3.6}, we will express the continued fraction
\eqref{e3.5} in numerator/denominator form, the numerator and
denominator being orthogonal polynomials.

??Ramanujan continued fraction?? -> area counting of Catalan paths??
(Flajolet p.~136)


\section{Lattice paths and orthogonal polynomials}
\label{s3.4}\index{orthogonal polynomial}\index{polynomial,
orthogonal}

Orthogonal polynomials are very important in \dots

It is the discovery of \index{Viennot, Xavier G\'erard}Viennot
\cite{VienAE} that large parts of the theory of orthogonal
polynomials is in fact combinatorics. The key in this {\em
combinatorial theory of orthogonal polynomials} is \index{path,
Motzkin}\index{Motzkin path}{\em Motzkin paths}. We
present an extract from this combinatorial theory in this section.

The objects of study are sequences $(p_n(x))_{n\ge0}$ of polynomials
over $\C$??,
where $p_n(x)$ is of degree $n$. Such a sequence $(p_n(x))_{n\ge0}$
is called \index{orthogonal}\index{polynomial, orthogonal}{\em
orthogonal} if there exists a \index{linear functional}\index{functional,
linear}linear functional $L$ on polynomials
over $\C$?? (i.e., a linear map, which maps a polynomial to a complex
number??) such that
\begin{equation} \label{e3.10}
L(p_n(x)p_m(x))=\begin{cases} 0&\text {if $n\ne m$,}\\
\text {nonzero}&\text {if $n=m$.}\end{cases}
\end{equation}
We alert the reader that our definition deviates from the classical
{\em analytic} definition in that we {\em do not} require $L(p_n(x)^2)$
to be positive. The above somewhat weaker notion of
orthogonality is sometimes referred to as {\em formal orthogonality}.
The term `formal' expresses that the corresponding theory does not
require any analytic tools, just formal, algebraic computations. In
fact, the formal theory could be equally well developed over any
field $K$ of characteristic 0?? (instead of $\C$). However, as the
definition of formal orthogonality is weaker than the classical
definition, it is obvious that not all of the classical theory can be
derived within the formal context. A typical example is the
facts about zeroes of orthogonal (in the sense of the classical
analytical definition) polynomials (see e.g\@.
\cite{??}), which are very important in applications. These cannot be
derived within the formal theory.

\medskip
Given the definition \eqref{e3.10}, there are two obvious questions:

\medskip
\hangafter1\hangindent2\parindent
Question 1: For which linear functionals $L$ does there exist a sequence of
orthogonal polynomials? How many?

\hangafter1\hangindent2\parindent
Question 2: Given a sequence $(p_n(x))_{n\ge0}$ of polynomials, how can one
check whether they are orthogonal or not? Is there an easy method to
compute a corresponding linear functional $L$? 
\medskip


Although it is not our main goal, 
we will, at least partially, answer these questions below. 
Ubiquitous in the answers (and in the whole theory) are the  
\index{moment (of orthogonal polynomials)}{\em moments} of the linear
functional $L$. The {\em $n$-th moment\/} of a linear functional $L$
is the value $L(x^n)$. Clearly, the moments determine a linear
functional on the set of polynomials uniquely. Hence, knowing the
moments is equivalent to knowing the linear functional.

The first question is answered in Corollary~\ref{C3.1}. 
The answer, a nonvanishing
condition on \index{Hankel determinant}\index{determinant, Hankel}Hankel 
determinants built from the \index{moment (of orthogonal
polynomials)}moments, is very simple an elegant. 

The first part of
the second question has an equally simple and elegant answer, in
terms of a three-term recurrence satisfied by the polynomials. This
criterion is known under the name of \index{Favard,
??}\index{Favard's Theorem}\index{theorem, Favard's}{\em 
Favard's Theorem}, and is given below in Theorem~\ref{T3.6}. The second
part of the question, the question of whether or not there exists an easy
method to compute the linear functional $L$ for a given sequence of
polynomials, such that they are orthogonal with respect to this
functional, can come in two different degrees of sophistication. On
the one hand, one could be satisfied with finding the moments of $L$.
Then Corollary~\ref{C3.0} provides the answer, in form of a continued
fraction, and thus ties back to \index{Flajolet, Philippe}Flajolet's
continued fraction result, Theorem~\ref{T3.4}, given in the previous
section. On the other hand, one may wish to express $L$ in form of an
integral,
\begin{equation} \label{e3.11}
L(p(x))=\int _{-\infty} ^{\infty}p(x)\,dw(x),
\end{equation}
with some measure $dw(x)$, which may have continuous and
discrete parts. Since, by Corollary~\ref{C3.0}, we know the moments of
$L$, the question can be rephrased as: Given the moments of a linear
functional, is it possible to construct a measure $dw(x)$, such that
\eqref{e3.11} holds for $p(x)=x^n$, $n=0,1,2,\dots$? This question is
known under the name of
\index{Hamburger's moment problem}\index{moment problem}{\em Hamburger's 
moment problem}, and is a very difficult, but on the other hand,
extremely interesting question. It turns out that such measures need
not even be unique. We refer the reader to the excellent survey
article ?? \cite{Uebersichtsartikel in arXiv}.

Beyond that, our main goal is, of course, to demonstrate the
significance of Motzkin paths behind the objects and formulas in the theory of
orthogonal polynomials. 

\medskip
To begin with, let us come back to Question~1. It is easy to see that
not for every linear functional $L$ there is a corresponding sequence
of orthogonal polynomials. Let us consider the example of the linear
functional defined by $L(x^n):=1$, $n=0,1,2,\dots$. Equivalently,
this means that $L(p(x))=p(1)$. In order to construct a corresponding
sequence of orthogonal polynomials, we start with $p_0(x)$. This must
be a polynomial of degree $0$, but otherwise we are completely free.
Without loss of generality we may choose $p_0(x)\equiv 1$. To
determine $p_1(x)$, we use \eqref{e3.10} with $m=0$ and $n=1$. Thus we
obtain $p_1(x)=x-1$. But then we have $L(p_1(x)^2)=L((x-1)^2)=0$,
which violates the requirement \eqref{e3.10}, with $m=n=1$, that
$L(p_1(x)^2)$ should be nonzero.

On the other hand, if we have a linear functional $L$ such that there
exists a sequence of orthogonal polynomials, then all other sequences
are just linear multiples of the former sequence.

\begin{Lemma} \label{L3.1}
Let $L$ be a linear functional on polynomials and $(p_n(x))_{n\ge0}$
be a sequence of polynomials orthogonal with respect to $L$. If
$(q_n(x))_{n \ge0}$ is another sequence of polynomials orthogonal
with respect to $L$, then there are nonzero numbers $a_n\in\C$ such
that $q_n(x)=a_n\,p_n(x)$.
\end{Lemma}
\begin{proof} The polynomial $p_n(x)$ is of degree $n$,
$n=0,1,\dots$. Hence, we can express the polynomial
$q_n(x)$ as a linear combination of the form
\begin{equation} \label{e3.12}
q_n(x)=\sum _{k=0} ^{n}a_{nk}\,p_n(x),
\end{equation}
with some coefficients $a_{nk}$. By multiplying both sides of
\eqref{e3.12} by $p_i(x)$, applying $L$ on both sides, 
and making use of the orthogonality
\eqref{e3.10} of the polynomials $p_k(x)$, we obtain
\begin{equation} \label{e3.13}
L\big(p_i(x)q_n(x)\big)=a_{ni}L\big(p_i(x)^2\big).
\end{equation}
On the other hand, since $q_j(x)$ is of degree $j$, $j=0,1,\dots$, we
may also write $p_i(x)=\sum _{j=0} ^{i}b_{ij}q_j(x)$. Then, if $i<n$,
orthogonality of the polynomials $q_j(x)$ implies
\begin{equation} \label{e3.14}
L\big(p_i(x)q_n(x)\big)=L\bigg(\sum _{j=0}
^{i}b_{ij}q_j(x)q_n(x)\bigg)=0.
\end{equation}
If combined with \eqref{e3.13} and the fact (recall the second case
of \eqref{e3.10}) that\break
$L\big(p_i(x)^2\big)\ne0$, this yields $a_{ni}=0$ for $i<n$. Thus,
from \eqref{e3.12}, and \eqref{e3.13} with $i=n$, we have
$$q_n(x)=\frac {L\big(p_n(x)q_n(x)\big)} {L\big(p_n(x)^2\big)}p_n(x).$$
This proves the claim of the lemma.
\end{proof}

Lemma~\ref{L3.1} justifies that from now on we will restricted our
attention to sequences of \index{monic polynomial}\index{polynomial,
monic}{\em monic} polynomials.

As already mentioned, one of the key results in the theory of
orthogonal polynomials is \index{Favard,
??}\index{Favard's Theorem}\index{theorem, Favard's}{\em 
Favard's Theorem}, which we will state next. 

\begin{Theorem} \label{T3.6}
A sequence $(p_n(x))_{n\ge0}$ of monic polynomials, $p_n(x)$ being of
degree $n$, is orthogonal if and only if 
there exist sequences $(b_n)_{n\ge0}$ and $(\la_n)_{n\ge1}$, with
$\la_n\ne0$ for all $n\ge1$, such that the three-term recurrence
\begin{equation}
\label{eq:three-term}
xp_{n}(x)=p_{n+1}(x)+b_np_n(x)+\la_{n}p_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
holds, with initial conditions $p_0(x)=1$ and $p_1(x)=x-b_0$.

\end{Theorem}

In our
context, more important than the statement of the theorem itself is its
proof, which introduces Motzkin paths in a surprising way in
\eqref{e3.16}, and in
particular Proposition~\ref{P3.1} below, which is the key ingredient
in the proof. 

However, at this point we have to defer the proof of the theorem.
(It is given after the proof of Proposition~\ref{P3.1}.)
We must first introduce a combinatorial
interpretation of polynomials $p_n(x)$ which satisfy the three-term
recurrence \eqref{eq:three-term}, 
in terms of certain coverings of the set $\{1,2,\dots,n\}$.
More precisely, we define a {\em covering} of $[1,n]:=\{1,2,\dots,n\}$ to be
a sequence of {\em points}, {\em monominos}, and {\em dominos}, a
point consisting of just one element of $[1,n]$, and represented by a
labelled dot, a monomino also consisting of just one element of $[1,n]$, 
but represented by a labelled square, and a domino 
consisting of two consecutive elements of $[1,n]$, and represented by a
labelled rectangle. For an example see Figure~\ref{F3.6} which shows
a covering consisting of a point, a domino, a monomino, a point, a
monomino, a point, and a domino, in that order.

\begin{Figure} \label{F3.6}
$$
\Einheit.6cm
\Pfad(0,0),1111111111111111\endPfad
\DickPunkt(0,0)
\Kreis(2,0)
\Kreis(4,0)
\Kreis(6,0)
\DickPunkt(8,0)
\Kreis(10,0)
\DickPunkt(12,0)
\Kreis(14,0)
\Kreis(16,0)
\Pfad(1,-1),111122\endPfad
\Pfad(1,-1),221111\endPfad
\Pfad(5,-1),1122\endPfad
\Pfad(5,-1),2211\endPfad
\Pfad(9,-1),1122\endPfad
\Pfad(9,-1),2211\endPfad
\Pfad(13,-1),111122\endPfad
\Pfad(13,-1),221111\endPfad
\Label\u{1}(0,0)
\Label\u{2}(2,0)
\Label\u{3}(4,0)
\Label\u{4}(6,0)
\Label\u{5}(8,0)
\Label\u{6}(10,0)
\Label\u{7}(12,0)
\Label\u{8}(14,0)
\Label\u{9}(16,0)
\hskip10.2cm
$$
\end{Figure}

We define the weight of a point by $x$, the weight of a monomino
with label $i$ by $-b_{i-1}$, and the weight of a domino with labels $i,i+1$ by
$-\la_i$.
Given a covering $\al$, the weight $w(\al)$ of $\al$ is defined as
the product of all the weights of its points, monominos and dominos.
Thus, the weight of the covering in Figure~\ref{F3.6} is
$$x(-\la_2)(-b_3)x(-b_5)x(-\la_8)=
\la_2b_3b_5\la_8x^3.$$


\begin{Lemma} \label{L3.2}
Let the polynomials $p_n(x)$ be defined through the three-term
recurrence \eqref{eq:three-term}, 
with initial conditions $p_0(x)=1$ and $p_1(x)=x-b_1$.
Then $p_n(x)$
can be written as a generating function for coverings of $[1,n]$,
\begin{equation} \label{e3.19}
p_n(x)=\sum _{\al\text { a covering of }[1,n]} ^{}w(\al).
\end{equation}
\end{Lemma}
\begin{proof}Write the three-term recurrence in the
equivalent form 
\begin{equation*} \label{e3.18}
p_{n+1}(x)=(x-b_n)p_n(x)-\la_np_{n-1}(x),
\end{equation*}
Then the formula \eqref{e3.19} can easily be verified by induction 
on $n$.
\end{proof}

\begin{Proposition} \label{P3.1}
Let $L$ be a linear functional the moments of which are given by
\eqref{e3.16}, with the weight $w$ of Motzkin paths as defined before
Theorem~\ref{T3.4}. Furthermore, let the polynomials $p_n(x)$ be
given by the three-term recurrence \eqref{eq:three-term}. Then
\begin{equation} \label{e3.17}
L\big(x^n\,p_k(x)\,p_l(x)\big)=\la_1\cdots\la_l\cdot
\GF{\L{(0,k)\to(n,l);M\mid 0\le y};w}.
\end{equation}
\end{Proposition}
\begin{proof} 
In view of Lemma~\ref{L3.2}, the left-hand side of \eqref{e3.17} is equal to
\begin{equation} \label{e3.20}
L\big(x^n\,p_k(x)\,p_l(x)\big)=\sum _{(\al,\be,P)}
^{}w(\al)w(\be)w(P)\big\vert_{x=1},
\end{equation}
where the sum is over all triples $(\al,\be,P)$ where
\begin{enumerate}
\item[(a)] $\al$ is a covering of $[1,k]$,
\item[(b)] $\be$ is a covering of $[1,l]$,
\item[(c)] $P$ is a Motzkin path of length
$$n+\#(\text {points in $\al$})+\#(\text {points in $\be$}).$$
\end{enumerate}

We are going to demonstrate that most of the terms on the
right-hand side of \eqref{e3.20} cancel, so that in fact we have
\begin{equation} \label{e3.21}
L\big(x^n\,p_k(x)\,p_l(x)\big)=\sum _{(\al,\be,P)}
^{}w(\al)w(\be)w(P)\big\vert_{x=1},
\end{equation}
where the sum is just over those triples $(\al,\be,P)$ where
\begin{enumerate}
\item[(a')] $\al$ is a covering of $[1,k]$ consisting just of points,
\item[(b')] $\be$ is a covering of $[1,l]$ consisting just of points,
\item[(c')] $P$ is a Motzkin path of length
$$n+\#(\text {points in $\al$})+\#(\text {points in $\be$}),$$
which starts with $k$ up-steps and ends with $l$ down-steps.
\end{enumerate}
Clearly, this would immediately imply \eqref{e3.17} and thus prove
the proposition.

We prove our claim by constructing a weight-preserving and
sign-reversing involution on the set of all triples $(\al,\be,P)$
which satisfy (a)--(c) but violate one of (a')--(c'). More precisely,
we are going to construct an involution on the set of all these
triples which maps $(\al,\be,P)$ to $(\al',\be',P')$, say, such that
\begin{equation} \label{e3.22}
w(\al')w(\be')w(P')=
-w(\al)w(\be)w(P).
\end{equation}
Given such a map, the terms corresponding to these triples in the sum
on the right-hand side of \eqref{e3.20} would cancel each other, and
only the terms corresponding to triples which satisfy (a')--(c')
would remain, thus establishing our claim \eqref{e3.21}.

Now we define the involution.
Let $(\al,\be,P)$ be a triple satisfying (a)--(c) but violating one
of (a')--(c'). If this is a triple which violates (a') or where one of the
first $k$ steps of $P$ is not an up-step, then let $i$ be minimal
such that 
\begin{itemize}
\item[(1)] there is a monomino with label $i$ in $\al$,
\item[(2)] or the $i$-th step of $P$ is a level-step,
\item[(3)] or there is a domino with labels $i,i+1$ in $\al$,
\item[(4)] or the $(i+1)$-st step of $P$ is a down-step.
\end{itemize}
If (1) holds then replace the monomino with label $i$ in $\al$ 
by a point labelled $i$ and
insert a level-step as the $i$-th step into $P$, see Figure~\ref{F3.7}
where $i=3$ (read the figure from left to right; $\al$ and $P$ on the
left are mapped to $\al$ and $P$ on the right). 
If (3) holds then replace the domino with labels $i,i+1$ in $\al$ 
by two points labelled $i$ and $i+1$ and
insert an up-step and a down-step as the $i$-th and $(i+1)$-st steps,
respectively, into $P$, see Figure~\ref{F3.8}
where $i=2$ (read the figure from left to right; $\al$ and $P$ on the
left are mapped to $\al$ and $P$ on the right). 
If neither (1) or (3) hold, then one of (2) and (4) must hold.
If (2) holds, then replace the point labelled $i$ in $\al$ by a 
monomino with label $i$ and remove the $i$-th step (a level step)
from $P$, see Figure~\ref{F3.7} where $i=3$
(read the figure from right to left).
If none of (1)--(3) hold, and hence (4) holds, 
then replace the points labelled $i$ and $i+1$ in $\al$ by a 
domino with labels $i,i+1$ and remove the $i$-th and $(i+1)$-th step 
(these must necessarily be an up-step and a down-step)
from $P$, see Figure~\ref{F3.8} where $i=3$
(read the figure from right to left).

\begin{Figure} \label{F3.7}
$$
\Pfad(0,0),1111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(2,0)
\Kreis(4,0)
\Kreis(6,0)
\Kreis(8,0)
\DickPunkt(10,0)
\Pfad(3,-1),1122\endPfad
\Pfad(3,-1),2211\endPfad
\Pfad(5,-1),111122\endPfad
\Pfad(5,-1),221111\endPfad
\Label\u{1}(0,0)
\Label\u{2}(2,0)
\Label\u{3}(4,0)
\Label\u{4}(6,0)
\Label\u{5}(8,0)
\Label\u{6}(10,0)
\Label\o{-b_2}(4,1)
\Label\o{-\la_4}(7,1)
\Label\l{\al\kern7pt}(0,0)
\hbox{\hskip7.8cm}
\Pfad(0,0),1111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(2,0)
\DickPunkt(4,0)
\Kreis(6,0)
\Kreis(8,0)
\DickPunkt(10,0)
\Pfad(5,-1),111122\endPfad
\Pfad(5,-1),221111\endPfad
\Label\u{1}(0,0)
\Label\u{2}(2,0)
\Label\u{3}(4,0)
\Label\u{4}(6,0)
\Label\u{5}(8,0)
\Label\u{6}(10,0)
\Label\o{-\la_4}(7,1)
\Label\l{\al\kern7pt}(0,0)
\hbox{\hskip5.5cm}
$$
\vskip.5cm
$$\longleftrightarrow\kern.5cm$$
$$
\Einheit1cm
\PfadDicke{.6pt}
\Pfad(0,0),334\endPfad
\PfadDicke{.2pt}
\Pfad(0,0),111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,1)
\DickPunkt(6,0)
\Label\r{\raise-16pt\hbox{$\kern20pt\la_2$}}(2,2)
\Label\lo{P}(2,0)
\hbox{\hskip3cm}
\begin{picture}(4,4)
\unitlength1cm
\put(.5,1){\oval(1,1)[t]}
\put(1.5,1){\oval(1,1)[b]}
\put(2.5,1){\oval(1,1)[t]}
\put(3,0){\line(0,1){1}}
\end{picture}
\hbox{\hskip4cm}
\PfadDicke{.6pt}
\Pfad(0,0),3314\endPfad
\PfadDicke{.2pt}
\Pfad(0,0),1111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,2)
\DickPunkt(4,1)
\DickPunkt(7,0)
\Label\ro{\kern4ptb_2}(2,2)
\Label\r{\raise-16pt\hbox{$\kern20pt\la_2$}}(3,2)
\Label\lo{P}(2,0)
\hbox{\hskip4cm}
\begin{picture}(4,4)
\unitlength1cm
\put(.5,1){\oval(1,1)[t]}
\put(1.5,1){\oval(1,1)[b]}
\put(2.5,1){\oval(1,1)[t]}
\put(3,0){\line(0,1){1}}
\end{picture}
\hbox{\hskip3cm}
$$
\end{Figure}

\begin{Figure} \label{F3.8}
$$
\Pfad(0,0),1111111111\endPfad
\DickPunkt(0,0)
\Kreis(2,0)
\Kreis(4,0)
\DickPunkt(6,0)
\DickPunkt(8,0)
\DickPunkt(10,0)
\Pfad(1,-1),111122\endPfad
\Pfad(1,-1),221111\endPfad
\Label\u{1}(0,0)
\Label\u{2}(2,0)
\Label\u{3}(4,0)
\Label\u{4}(6,0)
\Label\u{5}(8,0)
\Label\u{6}(10,0)
\Label\o{-\la_2}(3,1)
\Label\l{\al\kern7pt}(0,0)
\hbox{\hskip7.8cm}
\Pfad(0,0),1111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(2,0)
\DickPunkt(4,0)
\DickPunkt(6,0)
\DickPunkt(8,0)
\DickPunkt(10,0)
\Label\u{1}(0,0)
\Label\u{2}(2,0)
\Label\u{3}(4,0)
\Label\u{4}(6,0)
\Label\u{5}(8,0)
\Label\u{6}(10,0)
\Label\l{\al\kern7pt}(0,0)
\hbox{\hskip5.5cm}
$$
\vskip.5cm
$$\longleftrightarrow\kern.5cm$$
$$
\Einheit1cm
\PfadDicke{.6pt}
\Pfad(0,0),331\endPfad
\PfadDicke{.2pt}
\Pfad(0,0),11111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,2)
\DickPunkt(5,0)
\Label\ro{\kern4ptb_2}(2,2)
\Label\lo{P}(2,0)
\hbox{\hskip3cm}
\begin{picture}(4,4)
\unitlength1cm
\put(.5,2){\oval(1,1)[b]}
\put(1.5,2){\oval(1,1)[t]}
\put(2,0){\line(0,1){2}}
\end{picture}
\hbox{\hskip4cm}
\PfadDicke{.6pt}
\Pfad(0,0),33431\endPfad
\PfadDicke{.2pt}
\Pfad(0,0),1111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,1)
\DickPunkt(4,2)
\DickPunkt(5,2)
\DickPunkt(7,0)
\Label\ro{\kern4ptb_2}(4,2)
\Label\r{\raise-16pt\hbox{$\kern20pt\la_2$}}(2,2)
\Label\lo{P}(2,0)
\hbox{\hskip5cm}
\begin{picture}(4,4)
\unitlength1cm
\put(.5,2){\oval(1,1)[b]}
\put(1.5,2){\oval(1,1)[t]}
\put(2,0){\line(0,1){2}}
\end{picture}
\hbox{\hskip2cm}
$$
\end{Figure}

If we encounter a triple $(\al,\be,P)$ which satisfies (a') and where the
first $k$ steps of $P$ are up-steps throughout, but which violates
(b') or where one of the last $l$ steps is not a down-step, then we
define analogous operations on $\be$ and $P$. We leave the details to
the reader.

From the construction it is obvious that the map is an involution and
that \eqref{e3.22} is satisfied. Thus, the proof of the proposition
is complete.
\end{proof}

Now we have all the prerequisites available
in order to prove Theorem~\ref{T3.6}.

\begin{proof}[Proof of Theorem~\ref{T3.6}]
For showing the forward implication, let
$(p_n(x))_{n\ge0}$ be a sequence of monic polynomials, $p_n(x)$ of
degree $n$, which is orthogonal with respect to the linear functional
$L$. Then we can express $xp_n(x)$ in terms of a linear combination
of the polynomials $p_{n+1}(x)$, $p_n(x)$, \dots, $p_0(x)$,
\begin{equation} \label{e3.15}
xp_n(x)=p_{n+1}(x)+b_np_n(x)+\la_np_{n-1}(x)+\om_{n,n-2}p_{n-2}(x)
+\dots+\om_{n,0}p_0(x).
\end{equation} 
We have to show that in fact the first three terms on the right-hand
side suffice, i.e., that all other terms are zero. 

In order to that we multiply both sides of \eqref{e3.15} by $p_i(x)$,
for some $i<n-1$, and apply $L$ on both sides. Because of
\eqref{e3.10}, on the right-hand side it is only the term
$\om_{n,i}L\big(p_i(x)^2\big)$ which survives. On the left-hand side we
obtain $L\big(xp_i(x)p_n(x)\big)$. The polynomial $xp_i(x)$ of degree
$i+1$ can be expressed as a linear combination of the polynomials
$p_{i+1}(x)$, $p_i(x)$, \dots, $p_0(x)$. Because of
\eqref{e3.10} and $i<n-1$, we therefore conclude that
$L\big(xp_i(x)p_n(x)\big)=0$. Hence, $\om_{n,i}$ is indeed $0$ for
$i<n-1$. Similarly, we have
$$\la_n\,L\big(p_{n-1}(x)^2\big)=L\big(xp_{n-1}(x)p_n(x)\big)=
L\big(p_n(x)^2\big),$$
which is nonzero because of \eqref{e3.10}. Hence, we have $\la_n\ne0$, as
desired.

\medskip
For the proof of the backward implication, we must construct a linear
functional $L$ such that \eqref{e3.10} holds, given a sequence
$(p_n(x))$ of polynomials, $p_n(x)$ of degree $n$, satisfying the
three-term recurrence \eqref{eq:three-term}. We construct $L$ by
defining the moments $\mu_n:=L(x^n)$ by
\begin{equation} \label{e3.16}
\mu_n=\GF{\L{(0,0)\to(n,0);M\mid 0\le y};w}=
\underset{\text {from $(0,0)$ to $(n,0)$}}
{\sum _{P\text { a Motzkin path}} ^{}}w(P),
\end{equation}
where $w$ is the weight of Motzkin paths as defined before
Theorem~\ref{T3.4}. Proposition~\ref{P3.1} with $n=0$
immediately implies that $L\big(p_k(x)p_l(x)\big)=0$ if $k\ne l$, as there
is no Motzkin path from $(0,k)$ to $(0,l)$, and
that $L\big(p_k(x)^2\big)=\la_1\cdots\la_k\ne0$. This completes the proof of
the theorem.
\end{proof}

In the above proof, we have found a linear functional $L$ by
defining, in \eqref{e3.16}, 
its moments to be generating functions for Motzkin paths, the
weights of the paths carrying the coefficients in the three-term recurrence
\eqref{eq:three-term}. This definition generates a linear functional
with $\mu_0=L(1)=1$. Are there other possibilities for the linear
functional, given the polynomials $(p_n(x))_{n\ge0}$ which ought to
be orthogonal with respect to the linear functional? The answer is
that all other such linear functionals are constant nonzero multiples of the
linear functional defined by \eqref{e3.16}. It is obvious that the
sequence $(p_n(x))_{n\ge0}$ is also orthogonal with respect to all of
them. On the other hand, once we choose the first moment
$\mu_0=L(1)$, then everything else is uniquely determined because of
the fact, derived from the definition \eqref{e3.10} with $m=0$, that
$L(p_n(x))=0$ for $n\ge1$. Hence, indeed, the constant nonzero
multiples of the linear functional defined by \eqref{e3.16} are the
only ones with orthogonal polynomials $p_n(x)$. This justifies that
from now on we will restrict ourselves to linear functionals with
first moment equal to $1$.

In view of Theorem~\ref{T3.4}, the above
observations allow us to provide a compact (partial) answer to the second
part of Question~2 posed at the beginning of this section.

\begin{Corollary} \label{C3.0}
Let $(p_n(x))_{n\ge0}$ be a sequence of polynomials satisfying the
three-term recurrence \ref{eq:three-term} with initial
conditions $p_0(x)=1$ and $p_1(x)=x-b_0$. Then $(p_n(x))_{n\ge0}$ is
orthogonal with respect to the linear functional $L$, where the generating
function of its moments $\mu_n=L(x^n)$ is given by
\begin{equation} \label{e3.16a}
\sum _{n\ge0} ^{}\mu_n\, z^n=
\cfrac 1{1-b_0z-
\cfrac {\la_1z^2}{1-b_1z-
\cfrac {\la_2z^2}{1-b_2z-\cdots}}}\ .
\end{equation}
All other linear functionals with respect to which the sequence
$(p_n(x))_{n\ge0}$ is orthogonal are constant nonzero multiples of $L$.
\end{Corollary}


\begin{Remark} 
A continued fraction of the type \eqref{e3.16a} is called a
\index{J-fraction}\index{fraction, J-fraction}{\em J-fraction}.
\end{Remark}

\begin{proof}[Proof of the Corollary]
Combine \eqref{e3.16} and \eqref{e3.6} with $b_i$ replace by $b_iz$
and $\la_i$ replaced by $\la_iz$.
\end{proof}

Before we move on, we demonstrate what we have found so far by an
example. The polynomials which appear in this example, the 
\index{Chebyshev, ??}%
\index{polynomial, Chebyshev}\index{Chebyshev polynomial}{\em Chebyshev
polynomials}, are of particular importance for path counting.
\begin{Example}We choose $b_i=0$ and $\la_i=1$ for all $i$. Then the
three-term recurrence \eqref{eq:three-term} becomes
\begin{equation} \label{et3.1}
xu_{n}(x)=u_{n+1}(x)+u_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial values $u_0(x)=1$ and $u_1(x)=x$. These polynomials are,
up to reparametrization, 
\index{Chebyshev, ??}%
\index{polynomial, Chebyshev}\index{Chebyshev polynomial}{\em Chebyshev
polynomials of the second kind}. To see that, recall that the latter
are defined by
$$U_n(\cos\th)=\frac {\sin((n+1)\th)} {\sin\th},$$
or, equivalently,
$$U_n(x)=\frac {\sin((n+1)\arccos x)} {\sqrt {1-x^2}}.$$
Because of the easily verified fact that
$$\sin((n+1)\th)+\sin((n-1)\th)=2\cos\th\cos n\th,$$
the Chebyshev polynomials of the second kind satisfy the three-term
recurrence
\begin{equation} \label{et3.2}
2xU_{n}(x)=U_{n+1}(x)+U_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial values $U_0(x)=1$ and $U_1(x)=2x$. Therefore we have
\begin{equation} \label{et3.3}
U_n(x)=u_n(2x)
\end{equation}
for all $n$.

By our combinatorial theory we are now able to derive several facts
about these Chebyshev polynomials. For example, in order to derive an
explicit formula for the polynomials, we start with Lemma~\ref{L3.2}.
It says that
$$u_n(x)=\sum _{\al} ^{}w(\al),$$
where the sum is over all coverings $\al$ of $[1,n]$ without
monominos (because $b_i=0$ for all $i$), and where the weight $w(\al)$ of a
covering with $k$ dominos and, hence, $n-2k$ points is $(-1)^kx^{n-2k}$
(because $\la_i=0$ for all $i$). The number of coverings with $k$
dominos and $n-2k$ points is clearly $\binom {n-k}k$. Therefore we
have
$$u_n(x)=\sum _{k\ge0} ^{}(-1)^k\binom {n-k}k x^{n-2k},$$
whence, by \eqref{et3.3}, we have
\begin{equation} \label{et3.3a}
U_n(x)=\sum _{k\ge0} ^{}(-1)^k\binom {n-k}k (2x)^{n-2k}.
\end{equation}

Another well-known fact is
$$\frac {2} {\pi}\int _{0} ^{\pi}\sin((n+1)\th)\sin((m+1)\th)\,d\th =
\begin{cases} 1&n=m\\ 0&n\ne m.\end{cases}$$
Substitution of $x=\cos\th$ then yields
\begin{equation} \label{et3.4}
\frac {2} {\pi}\int _{-1} ^{1}U_n(x)U_m(x)\sqrt{1-x^2}\,dx =
\de_{nm}.
\end{equation}
Thus the linear functional $L$ for Chebyshev polynomials of the
second kind is given by
$$L(p(x))=\frac {2} {\pi}\int _{0} ^{\pi}p(x)\sqrt{1-x^2}\,dx.$$

Using \eqref{e3.16} we can now easily evaluate the corresponding
moments. On the right-hand side of \eqref{e3.16} all the terms
corresponding to paths which contain a level-step vanish, because
$b_i=0$ for all $i$. Therefore, what the right-hand side counts are
paths which contain only up-steps and down-steps (and never pass
below the $x$-axis). Clearly, there cannot be such a path if $n$ is
odd. If $n$ is even, then by \eqref{e1.5} the number of these paths
is the \index{Catalan numbers}\index{Catalan, Eug\`ene??}Catalan number 
$\frac {1} {n/2+1}\binom {n}{n/2}$. Hence, by also taking into
account \eqref{et3.3}, we have shown that
$$\frac {2} {\pi}\int _{-1} ^{1}x^m\sqrt{1-x^2}=\begin{cases} \frac
{1} {4^n}\frac {1} {n+1}\binom {2n}{n}&m=2n\\0&m=2n+1.\end{cases}$$

\medskip
The 
\index{Chebyshev, ??}%
\index{polynomial, Chebyshev}\index{Chebyshev polynomial}{\em Chebyshev
polynomials of the first kind\/} can also be treated in this manner.
Recall that they are defined by 
$$T_n(\cos\th)=\cos n\th,$$
or, equivalently,
$$T_n(x)=\cos(\arccos x).$$
They satisfy the same three-term recurrence
\begin{equation} \label{et3.5}
T_{n+1}(x)=2xT_{n}(x)+T_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
but with initial values $T_0(x)=1$ and $T_1(x)=x$. Hence, we have to
modify the combinatorial setup slightly. We choose $b_i=0$ for all
$i$, $\la_i=1/4$ for $i\ge2$ and $\la_1=1/2$. Thus
the three-term recurrence \eqref{eq:three-term} becomes
\begin{equation} \label{et3.6}
t_{n+1}(x)=xt_{n}(x)+\frac {1} {4}t_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial values $t_0(x)=1$ and $t_1(x)=x$. The polynomials $t_n(x)$
are related to the Chebyshev polynomials by
\begin{equation} \label{et3.7}
T_n(x)={2^{n-1}}t_n(x).
\end{equation}
Then, again, an explicit form can be derived for the Chebyshev
polynomials, using Lemma~\ref{L3.2}. It is
\begin{equation} \label{et3.7a}
T_n(x)=\frac {1} {2}
\sum _{k\ge0} ^{}(-1)^k\frac {n} {n-k}\binom {n-k}k (2x)^{n-2k}.
\end{equation}
Furthermore, the orthogonality relation for the Chebyshev polynomials
of the second kind is
\begin{equation} \label{et3.8}
\int _{-1} ^{1}T_n(x)T_m(x)\frac {dx} {\sqrt{1-x^2}} =
\cases \pi&n=m=0\\ \pi/2&n=m\ge1\\ 0&n\ne m.\endcases
\end{equation}
It is then not very difficult, to derive the following formula for
the moments from \eqref{e3.16},
$$\frac {1} {\pi}\int _{-1} ^{1}x^m\frac {dx} {\sqrt{1-x^2}}=
\begin{cases} \frac
{1} {4^n}\binom {2n}{n}&m=2n\\0&m=2n+1.\end{cases}$$
We leave the details to the reader. (Alternatively, consult Viennot
\cite[??]{VienAE}.)

\medskip
\index{Chebyshev, ??}%
\index{polynomial, Chebyshev}\index{Chebyshev polynomial}Chebyshev 
polynomials are not only tied to Catalan paths, i.e., paths
that consist of just up- and down-steps, but also to Motzkin paths.
To see this, let us now choose $b_i=\la_i=1$ for all $i$. Then the
three-term recurrence \eqref{eq:three-term} becomes
\begin{equation} \label{et3.9}
xm_{n}(x)=m_{n+1}(x)+m_n(x)+m_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial values $m_0(x)=1$ and $m_1(x)=x-1$. Comparison with
\eqref{et3.2} reveals that these polynomials are expressible by means
of Chebyshev polynomials of the second kind as
\begin{equation} \label{et3.10}
m_n(x)=U_n\(\frac {x-1} {2}\).
\end{equation}
We will take advantage of this relation in Section~\ref{s3.6} to
obtain further enumerative results on Motzkin paths.
\end{Example}

We have now answered, by
Favard's theorem, Theorem~\ref{T3.6}, the first part of
Question~2 posed at the beginning of this section, and also the
second part, by Corollary~\ref{C3.0}. Our next goal is
to answer Question~1. We have already seen that not for every linear
functional $L$ there is a corresponding sequence of orthogonal
polynomials. The next theorem allows to precisely say when there exists such
a sequence. The criterion, given as Corollary~\ref{C3.1} after the
proof of the theorem, is formulated in terms of
\index{determinant, Hankel}\index{Hankel determinant}{\em Hankel
determinants} of the moments of $L$. A Hankel determinant 
(or \index{determinant, persymmetric}\index{persymmetric
determinant}{\em persymmetric} or \index{Tur\'anian
determinant}\index{determinant, Tur\'anian}{\em Tur\'anian determinant}) 
is a determinant of a matrix which has
constant entries along antidiagonals, i.e., it is a determinant of
the form $\det_{1\le i,j,\le n}(a_{i+j}).$ 
In our context, what is particularly interesting about the theorem,
is that its proof is entirely combinatorial, 
by an elegant application of the
main theorem on \index{nonintersecting lattice paths}%
\index{lattice paths, nonintersecting}nonintersecting 
lattice paths, Theorem~\ref{T2.2}.

\begin{Theorem} \label{T3.7}
Let $L$ be a linear functional on polynomials with $n$-th moment
$\mu_n=L(x^n)$.
For any nonnegative integer $n$ let
$$\De_n=\det\begin{pmatrix} \mu_0&\mu_1&\mu_2&\dots&\mu_n\\
\mu_1&\mu_2&\hdotsfor2 &\mu_{n+1}\\
\mu_2&\hdotsfor3&\mu_{n+2}\\
\vdots&&&&\vdots\\
\mu_n&\hdotsfor3&\mu_{2n}
\end{pmatrix}$$
and
$$\chi_n=\det\begin{pmatrix} \mu_0&\mu_1&\dots&\mu_{n-1}&\mu_n\\
\mu_1&\mu_2&\dots&\mu_n&\mu_{n+1}\\
%\hdotsfor5\\
\vdots&\vdots&&\vdots&\vdots\\
\mu_{n-1}&\mu_{n}&\dots&\mu_{2n-2}&\mu_{2n-1}\\
\mu_{n+1}&\mu_{n+2}&\dots&\mu_{2n}&\mu_{2n+1}
\end{pmatrix}$$
Let $(p_n(x))_{n\ge0}$ be the sequence
of monic polynomials which is orthogonal with respect
to $L$. Then the
polynomials satisfy the three-term recurrence \eqref{eq:three-term}
with 
\begin{equation} \label{e3.23}
\la_n=\frac {\De_n\De_{n-2}} {\De_{n-1}^2}
\end{equation}
and
\begin{equation} \label{e3.24}
b_n=\frac {\chi_{n}} {\De_{n}}-\frac {\chi_{n-1}} {\De_{n-1}}.
\end{equation}
\end{Theorem}
\begin{proof}We have already proved in Theorem~\ref{T3.6} that any
sequence of monic orthogonal polynomials satisfies a three-term
recurrence of the form \eqref{eq:three-term}. Therefore, the only
thing which has to be established is that the coefficients in the
three-term recurrence can be expressed in terms of the moments of $L$
as shown in \eqref{e3.23} and \eqref{e3.24}.

We first prove \eqref{e3.23}. Because of \eqref{e3.16}, we can
interpret $\De_n$ as a determinant in which the entries are
generating functions for Motzkin paths in the following way:
\begin{align} \notag
\De_n&=\det_{0\le i,j\le n}(\mu_{i+j})\\
&=\det_{0\le i,j\le n}\(\GF{\L{(n-j,0)\to(n+i,0);M\mid 0\le y};w}\).
\label{e3.25}
\end{align}
On the other hand, by Theorem~\ref{T2.2}, the latter determinant is
the generating function $\sum _{(P_0,\dots,P_n)} ^{}w(P_0)\cdots
w(P_n)$ for families $(P_0,\dots,P_n)$ of nonintersecting lattice
paths, where $P_i$ is a Motzkin path from $A_i=(-i,0)$ to
$E_i=(i,0)$, $i=0,1,\dots,n$. A moment's thought shows that there
is exactly one possibility of such a family of nonintersecting
lattice paths, see Figure~\ref{F3.9} where $n=4$. Therefore we have
\begin{equation} \label{e3.26}
\De_n=\la_1^n\la_2^{n-1}\cdots\la_n^1,
\end{equation}
from which \eqref{e3.23} follows immediately.

\begin{Figure} \label{F3.9}
$$
\Einheit1cm
\Pfad(0,0),33334444\endPfad
\Pfad(1,0),333444\endPfad
\Pfad(2,0),3344\endPfad
\Pfad(3,0),34\endPfad
\PfadDicke{.2pt}
\Pfad(-1,0),1111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,0)
\DickPunkt(2,0)
\DickPunkt(3,0)
\DickPunkt(4,0)
\DickPunkt(5,0)
\DickPunkt(6,0)
\DickPunkt(7,0)
\DickPunkt(8,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,3)
\DickPunkt(4,4)
\DickPunkt(5,3)
\DickPunkt(6,2)
\DickPunkt(7,1)
\DickPunkt(2,1)
\DickPunkt(3,2)
\DickPunkt(4,3)
\DickPunkt(5,2)
\DickPunkt(6,1)
\DickPunkt(3,1)
\DickPunkt(4,2)
\DickPunkt(5,1)
\DickPunkt(4,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_4$}}(4,4)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_3$}}(5,3)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_2$}}(6,2)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(7,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_3$}}(4,3)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_2$}}(5,2)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(6,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_2$}}(4,2)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(5,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(4,1)
\Label\u{A_4}(0,0)
\Label\u{A_3}(1,0)
\Label\u{A_2}(2,0)
\Label\u{A_1}(3,0)
\Label\u{A_0}(4,0)
\Label\o{E_0}(4,-1)
\Label\u{E_1}(5,0)
\Label\u{E_2}(6,0)
\Label\u{E_3}(7,0)
\Label\u{E_4}(8,0)
\hskip8cm
$$
\end{Figure}
The proof of \eqref{e3.24} is very similar. 
As before, because of \eqref{e3.16}, we can
interpret $\chi_n$ as a determinant in which the entries are
generating functions for Motzkin paths:
\begin{align} \notag
\chi_n&=\det_{0\le i,j\le n}(\mu_{i+\chi(i=n)+j})\\
&=\det_{0\le i,j\le n}\(\GF{\L{(n-j,0)\to(n+i+\chi(i=n),0);M\mid 0\le
y};w}\).
\label{e3.27}
\end{align}
Again we have used the notation $\chi(\mathcal A)$=1 if $\mathcal A$ is
true and $\chi(\mathcal A)$=0 otherwise.
On the other hand, by Theorem~\ref{T2.2}, the determinant on the
right-hand side of \eqref{e3.27} is
the generating function $\sum _{(P_0,\dots,P_n)} ^{}w(P_0)\cdots
w(P_n)$ for families $(P_0,\dots,P_n)$ of nonintersecting lattice
paths, where $P_i$ is a Motzkin path from $A_i=(-i,0)$ to
$E_i=(i+\chi(i=n),0)$, $i=0,1,\dots,n$. The only difference to the
previous situation is that the last end point, $E_n$, is shifted 
by one unit to the right. Now the only possibility
of such a family of nonintersecting
lattice paths is that path $P_i$ starts with $i$ up-steps and ends
with $i$ down-steps, $i=0,1,\dots,n-1$, whereas path $P_n$ starts
with $n$ up-steps, and then follow $n$ down-steps and a level step,
in any order, see Figure~\ref{F3.10} which shows a possibility for 
$n=4$. Therefore we have
\begin{equation} \label{e3.28}
\chi_n=\la_1^n\la_2^{n-1}\cdots\la_n^1(b_0+b_1+\dots+b_n),
\end{equation}
from which \eqref{e3.24} follows immediately.
\begin{Figure} \label{F3.10}
$$
\Einheit1cm
\Pfad(0,0),333344144\endPfad
\Pfad(1,0),333444\endPfad
\Pfad(2,0),3344\endPfad
\Pfad(3,0),34\endPfad
\PfadDicke{.2pt}
\Pfad(-1,0),11111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,0)
\DickPunkt(2,0)
\DickPunkt(3,0)
\DickPunkt(4,0)
\DickPunkt(5,0)
\DickPunkt(6,0)
\DickPunkt(7,0)
\DickPunkt(9,0)
\DickPunkt(1,1)
\DickPunkt(2,2)
\DickPunkt(3,3)
\DickPunkt(4,4)
\DickPunkt(5,3)
\DickPunkt(6,2)
\DickPunkt(7,2)
\DickPunkt(8,1)
\DickPunkt(2,1)
\DickPunkt(3,2)
\DickPunkt(4,3)
\DickPunkt(5,2)
\DickPunkt(6,1)
\DickPunkt(3,1)
\DickPunkt(4,2)
\DickPunkt(5,1)
\DickPunkt(4,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_4$}}(4,4)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_3$}}(5,3)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_2$}}(7,2)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(8,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_3$}}(4,3)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_2$}}(5,2)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(6,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_2$}}(4,2)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(5,1)
\Label\r{\raise-22pt\hbox{$\kern20pt\la_1$}}(4,1)
\Label\ro{\raise-20pt\hbox{$b_2$}}(6,2)
\Label\u{A_4}(0,0)
\Label\u{A_3}(1,0)
\Label\u{A_2}(2,0)
\Label\u{A_1}(3,0)
\Label\u{A_0}(4,0)
\Label\o{E_0}(4,-1)
\Label\u{E_1}(5,0)
\Label\u{E_2}(6,0)
\Label\u{E_3}(7,0)
\Label\u{E_4}(9,0)
\hskip8.5cm
$$
\end{Figure}
This completes the proof of the theorem.
\end{proof}

\begin{Corollary} \label{C3.1}
Let $L$ be a linear functional on the set of polynomials. Then there
exists a sequence of orthogonal polynomials which are orthogonal with
respect to $L$ if and only if all Hankeldeterminants
$\De_n=\det_{0\le i,j\le n}(\mu_{i+j})$ of moments are nonzero.
\end{Corollary}
\begin{proof} If there is a sequence of orthogonal polynomials, then
they satisfy \eqref{eq:three-term} with $\la_n\ne0$ for all $n$. The
corresponding linear functional $L$ is unique up to a nonzero
constant, $C$ say. Then, because of \eqref{e3.26}, we have 
$$\det_{0\le i,j\le
n}(\mu_{i+j})=C^{n+1}\la_1^n\la_2^{n-1}\cdots\la_n^1.$$
(Recall that \eqref{e3.26} holds only for a linear functional where
the $0$-th moment is normalized to $1$.) 
In particular, the determinant must be nonzero.

On the other hand, if all Hankel determinants of moments are nonzero,
then, by means of Theorem~\ref{T3.7}, 
we can determine coefficients $b_n$ and $\la_n$ for all $n$, and then
find the orthogonal polynomials by solving 
the three-term reccurence \eqref{eq:three-term}.
\end{proof}

The equation \eqref{e3.26}, which arose in the proof of
Theorem~\ref{T3.7}, is so important that it deserves separate
mention. It says that a Hankel determinant can be evaluated
by determining the three-term recurrence of the orthogonal
polynomials which are orthogonal with respect to the linear
functional the moments of which are the entries of the Hankel
determinant (and then it is only one set of cofficients in the
recurrence, the $\la_i$, which enter the formula). 
This is an extremely useful observation because a lot is
known about orthogonal polynomials. In particular, there is an
extensive list of \index{orthogonal polynomial, hypergeometric}%
\index{hypergeometric orthogonal polynomial}{\em 
hypergeometric} ({\em and $q$-hypergeometric}) 
{\em orthogonal polynomials}, which comprises all the
classical orthogonal polynomials. This list is today known under the
name of the \index{Askey, Richard}\index{Askey scheme}{\em Askey scheme}. 
A comprehensive volume
which has everything one wants to know about these 
polynomials (definition of
polynomials, orthogonality measure, three-term recurrence relation,
differential/difference equations, generating functions) was compiled
by \index{Koekoek, Roloef??}Koekoek and \index{Swarttouw, Ren\'e}Swarttouw
\cite{KoSwAA}. Thus, numerous Hankel determinant evaluations are
hidden in what is known about orthogonal polynomials, cf\@.
\cite[Sec.~2.6 and Theorem~52]{KratBN}.

\begin{Corollary} \label{C3.3}
Let $(\mu_n)_{n\ge0}$ be a sequence, and let
$L$ be a linear functional on the set of polynomials such that its
$n$-th moment is $\mu_n$, i.e., $\mu_n=L(x^n)$.
Let $(p_n(x))_{n\ge0}$ be the sequence of monic
orthogonal polynomials which is orthogonal with respect to $L$.
Let the three-term recurrence which is guaranteed by
Theorem~\ref{T3.6} be
\begin{equation}
xp_{n}(x)=p_{n+1}(x)+b_np_n(x)+\la_{n}p_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial conditions $p_0(x)=1$ and $p_1(x)=x-b_0$. Then
$$\det_{0\le i,j\le n}(\mu_{i+j})=\la_1^n\la_2^{n-1}\cdots\la_n^1.$$
\noproof
\end{Corollary}

Our next theorem expresses each polynomial in a sequence of
orthogonal polynomials in terms of the moments of the associated
linear functional. We provide two proofs of the formula, a
determinant. The first proof is by linear algebraic verification,
whereas the second proof uses again 
\index{nonintersecting lattice paths}%
\index{lattice paths, nonintersecting}nonintersecting lattice paths.

\begin{Theorem} \label{T3.8}
Let $L$ be a linear functional defined on polynomials with moments
$\mu_n=L(x^n)$. Then the corresponding sequence
$(p_n(x))_{n\ge0}$ of monic orthogonal polynomials is given by
\begin{equation}
\label{eq:ortho}
p_{n}(x)=\frac {1} {\De_{n-1}}\det\begin{pmatrix}
		\mu_0	&	\mu_1	&	\mu_2	&	\dots &	\mu_n \\
		\mu_1	&	\mu_2	&	\dots	&	\mu_n	&	\mu_{n+1} \\
		\mu_2	&	\dots	&	\mu_n	&	\mu_{n+1}&\mu_{n+2} \\
		\hdotsfor{5} \\
		\mu_{n-1} &	\mu_n	&	\mu_{n+1}&\dots	&\mu_{2n-1} \\
		1	&	x&\dots&	x^{n-1}&x^n 
	\end{pmatrix},
\end{equation}
where, again, $\De_{n-1}=\det_{0\le i,j\le n-1}(\mu_{i+j})$.
\end{Theorem}

\begin{proof}[First proof]
It suffices to check that $L(x^mp_n(x))=0$ for $0\le m<n$. Indeed, by
\eqref{eq:ortho} we have
\begin{equation*}
L(x^mp_{n}(x))=\frac {1} {\De_{n-1}}\det\begin{pmatrix}
		\mu_0	&	\mu_1	&	\mu_2	&	\dots &	\mu_n \\
		\mu_1	&	\mu_2	&	\dots	&	\mu_n	&	\mu_{n+1} \\
		\mu_2	&	\dots	&	\mu_n	&	\mu_{n+1}&\mu_{n+2} \\
		\hdotsfor{5} \\
		\mu_{n-1} &	\mu_n	&	\mu_{n+1}&\dots	&\mu_{2n-1} \\
		\mu_m	&	\mu_{m+1}&\dots&
\mu_{m+n-1}&\mu_{m+n}
	\end{pmatrix}.
\end{equation*}
Thus the result is zero, because for $0\le m<n$ the $m$-th and the
last row in the above determinant are identical.
\end{proof}

\begin{proof}[Second proof]
We will interpret the determinant on the right-hand side of
\eqref{eq:ortho} in terms of nonintersecting lattice paths.
Subsequently, we will show that these nonintersecting paths are in
one-to-one correspondence with the coverings of $[1,n]$ that we introduced
before Lemma~\ref{L3.2}. Thus, we may appeal to the lemma itself,
which will then imply that right-hand and left-hand in \eqref{eq:ortho}
are indeed equal.

By elementary determinant calculus, the coefficient of $x^k$ on the
right-hand side of \eqref{eq:ortho} is 
\begin{equation} \label{e3.29}
\frac {(-1)^{n+k}} {\De_{n-1}}\det_{0\le i,j\le
n-1}(\mu_{i+j+\chi(j\ge k)}),
\end{equation}
where again $\chi(\mathcal A)$=1 if $\mathcal A$ is
true and $\chi(\mathcal A)$=0 otherwise.
This observation allows the application of the general form of the
main theorem on nonintersecting lattice paths, Theorem~\ref{T2.3}.
It says that the determinant on the
right-hand side of \eqref{eq:ortho} is
the generating function 
\begin{equation} \label{e3.30}
\sum _{\si,\,(P_0,\dots,P_{n-1})} ^{}\sgn \si \cdot w(P_0)\cdots
w(P_{n-1}) ,
\end{equation}
where the sum is over all permutations
$\si$ of $\{0,1,\dots,n-1\}$ and
families $(P_0,\dots,\break P_{n-1})$ of nonintersecting lattice
paths, $P_i$ a Motzkin path from $A_{\si(i)}=(-\si(i),0)$ to
$E_i=(i+\chi(i\ge k),0)$, $i=0,1,\dots,n-1$. 

\begin{Figure} \label{F3.11}
$$
\Einheit.352cm
\Pfad(-18,0),33333333333333333344114444444444444444\endPfad
\Pfad(-16,0),33333333333333334444444444444444\endPfad
\Pfad(-14,0),33333333333333444433444444444444\endPfad
\Pfad(-12,0),333333333333444444444444\endPfad
\Pfad(-10,0),333333333344444433444444\endPfad
\Pfad(-8,0),333333334444441144\endPfad
\Pfad(-6,0),333333444444\endPfad
\Pfad(-4,0),33334444\endPfad
\Pfad(-2,0),3344\endPfad
\PfadDicke{2pt}
\Pfad(2,16),11\endPfad
\Pfad(4,12),44\endPfad
\Pfad(6,6),44\endPfad
\Pfad(6,2),11\endPfad
\PfadDicke{.2pt}
\Pfad(-19,0),1111111111111111111111111111111111111111\endPfad
\DickPunkt(-18,0)
\NormalPunkt(-16,2)
\NormalPunkt(-14,4)
\NormalPunkt(-12,6)
\NormalPunkt(-10,8)
\NormalPunkt(-8,10)
\NormalPunkt(-6,12)
\NormalPunkt(-4,14)
\NormalPunkt(-2,16)
\NormalPunkt(0,18)
\NormalPunkt(2,16)
\NormalPunkt(4,16)
\NormalPunkt(6,14)
\NormalPunkt(8,12)
\NormalPunkt(10,10)
\NormalPunkt(12,8)
\NormalPunkt(14,6)
\NormalPunkt(16,4)
\NormalPunkt(18,2)
\DickPunkt(20,0)
\DickPunkt(-16,0)
\NormalPunkt(-14,2)
\NormalPunkt(-12,4)
\NormalPunkt(-10,6)
\NormalPunkt(-8,8)
\NormalPunkt(-6,10)
\NormalPunkt(-4,12)
\NormalPunkt(-2,14)
\NormalPunkt(0,16)
\NormalPunkt(2,14)
\NormalPunkt(4,12)
\NormalPunkt(6,10)
\NormalPunkt(8,8)
\NormalPunkt(10,6)
\NormalPunkt(12,4)
\NormalPunkt(14,2)
\DickPunkt(16,0)
\DickPunkt(-14,0)
\NormalPunkt(-12,2)
\NormalPunkt(-10,4)
\NormalPunkt(-8,6)
\NormalPunkt(-6,8)
\NormalPunkt(-4,10)
\NormalPunkt(-2,12)
\NormalPunkt(0,14)
\NormalPunkt(2,12)
\NormalPunkt(4,10)
\NormalPunkt(6,12)
\NormalPunkt(8,10)
\NormalPunkt(10,8)
\NormalPunkt(12,6)
\NormalPunkt(14,4)
\NormalPunkt(16,2)
\DickPunkt(18,0)
\DickPunkt(-12,0)
\NormalPunkt(-10,2)
\NormalPunkt(-8,4)
\NormalPunkt(-6,6)
\NormalPunkt(-4,8)
\NormalPunkt(-2,10)
\NormalPunkt(0,12)
\NormalPunkt(2,10)
\NormalPunkt(4,8)
\NormalPunkt(6,6)
\NormalPunkt(8,4)
\NormalPunkt(10,2)
\DickPunkt(12,0)
\DickPunkt(-10,0)
\NormalPunkt(-8,2)
\NormalPunkt(-6,4)
\NormalPunkt(-4,6)
\NormalPunkt(-2,8)
\NormalPunkt(0,10)
\NormalPunkt(2,8)
\NormalPunkt(4,6)
\NormalPunkt(6,4)
\NormalPunkt(8,6)
\NormalPunkt(10,4)
\NormalPunkt(12,2)
\DickPunkt(14,0)
\DickPunkt(-8,0)
\NormalPunkt(-6,2)
\NormalPunkt(-4,4)
\NormalPunkt(-2,6)
\NormalPunkt(0,8)
\NormalPunkt(2,6)
\NormalPunkt(4,4)
\NormalPunkt(6,2)
\NormalPunkt(8,2)
\DickPunkt(10,0)
\DickPunkt(-6,0)
\NormalPunkt(-4,2)
\NormalPunkt(-2,4)
\NormalPunkt(0,6)
\NormalPunkt(2,4)
\NormalPunkt(4,2)
\DickPunkt(6,0)
\DickPunkt(-4,0)
\NormalPunkt(-2,2)
\NormalPunkt(0,4)
\NormalPunkt(2,2)
\DickPunkt(4,0)
\DickPunkt(-2,0)
\NormalPunkt(0,2)
\DickPunkt(2,0)
\DickPunkt(0,0)
%
\Kreis(1,19)
\Kreis(9,-1)
\Kreis(3,17)
\Kreis(3,15)
\Kreis(5,13)
\Kreis(5,9)
\Kreis(7,7)
\Kreis(7,3)
\Kreis(7,1)
\SPfad(1,19),44\endSPfad
\SPfad(3,15),22\endSPfad
\SPfad(3,15),44\endSPfad
\SPfad(5,9),2222\endSPfad
\SPfad(5,9),44\endSPfad
\SPfad(7,1),222222\endSPfad
\SPfad(7,1),44\endSPfad
\Label\u{A_9}(-18,0)
\Label\u{A_8}(-16,0)
\Label\u{A_7}(-14,0)
\Label\u{A_6}(-12,0)
\Label\u{A_5}(-10,0)
\Label\u{A_4}(-8,0)
\Label\u{A_3}(-6,0)
\Label\u{A_2}(-4,0)
\Label\u{A_1}(-2,0)
\Label\u{A_0}(0,0)
\Label\u{E_0}(0,-1)
\Label\u{E_1}(2,0)
\Label\u{E_2}(4,0)
\Label\u{E_3}(6,0)
\Label\u{E_4}(10,0)
\Label\u{E_5}(12,0)
\Label\u{E_6}(14,0)
\Label\u{E_7}(16,0)
\Label\u{E_8}(18,0)
\Label\u{E_9}(20,0)
$$
\end{Figure}

Now the situation is even more demanding than in the proof of
\eqref{e3.24} (compare Figures~\ref{F3.11} and \ref{F3.10}). 
Here, there is a gap between the $(k-1)$-st and the $k$-th end point
(whereas previously the gap was between the next-to-last and the last
end point). In this situation 
we have to be very careful to understand correctly what
the term {\em nonintersecting} means. It means that paths do not
touch each other in {\em lattice points} (cf\@. the beginning of
Chapter~\ref{ch2}). However, this does not
necessarily imply that the paths may not cross! They may very
well cross in points {\em which are no lattice points}!
Figure~\ref{F3.11} shows a typical example for $n=10$ and $k=4$. (At the
moment, the path indicated by dotted lines should be ignored.)
Indeed, in this example, the $5$-th and $6$-th path cross each other,
as well as the $7$-th and $8$-th.


Let $(P_0,\dots,P_{n-1})$ a such a family of nonintersecting Motzkin
paths, $P_i$ running from $A_{\si(i)}$ to $E_i$, $i=0,1,\dots,n-1$,
for some permutation $\si$. We
introduce a path from $(1/2,n-1/2)$ to $(k+1/2,-1/2)$ which 
``penetrates" through
the ``anomalities" of the path family, in the following way. We start
at $(1/2,n-1/2)$ and move by diagonal down-steps $(1,-1)$ as long as the way
is not blocked by any path. If the way is blocked, then, locally,
there are two possilibities, shown in the left of Figure~\ref{F3.12}. 
(There, the
circle indicates the point of the path that we are constructing which
we have already reached.) Roughly, either the way is blocked by a
horizontal step, or the way is blocked by a crossing of two paths. In
the first case we continue our way by a vertical down-step $(0,-1)$
of length 1, in the latter case by a vertical double step $(0,-2)$,
see the right of Figure~\ref{F3.12}. The resulting path in the case
of our example in Figure~\ref{F3.11} is the dotted path.
\begin{Figure} \label{F3.12}
$$
\Pfad(-2,9),441144\endPfad
\Kreis(1,8)
\DickPunkt(-2,9)
\DickPunkt(0,7)
\DickPunkt(2,7)
\DickPunkt(4,5)
\Pfad(-2,2),443344\endPfad
\Pfad(-2,4),444444\endPfad
\Kreis(1,3)
\DickPunkt(-2,2)
\DickPunkt(-2,4)
\DickPunkt(0,0)
\DickPunkt(0,2)
\DickPunkt(2,0)
\DickPunkt(2,2)
\DickPunkt(4,0)
\DickPunkt(4,-2)
%
\Pfad(8,9),441144\endPfad
\SPfad(11,6),22\endSPfad
\Kreis(11,8)
\Kreis(11,6)
\DickPunkt(8,9)
\DickPunkt(10,7)
\DickPunkt(12,7)
\DickPunkt(14,5)
\Pfad(8,2),443344\endPfad
\Pfad(8,4),444444\endPfad
\SPfad(11,-1),2222\endSPfad
\Kreis(11,3)
\Kreis(11,-1)
\DickPunkt(8,2)
\DickPunkt(8,4)
\DickPunkt(10,0)
\DickPunkt(10,2)
\DickPunkt(12,0)
\DickPunkt(12,2)
\DickPunkt(14,0)
\DickPunkt(14,-2)
\hskip7.5cm
$$
\end{Figure}

Thus we obtain a path from $(1/2,n-1/2)$ to $(k+1/2,-1/2)$ consisting
of steps from $\{(1,-1),(0,-1),(0,-2)\}$. It is easy to see that this
is a bijection between our families of Motzkin paths and the former
paths. 

A path from $(1/2,n-1/2)$ to $(k+1/2,-1/2)$ consisting
of steps from $\{(1,-1),\break (0,-1),(0,-2)\}$ is in obvious one-to-one
correspondence with our coverings of $[1,n]$, by interpreting a
diagonal down-step $(1,-1)$ as a points, a vertical step $(0,-1)$ as
a monomino, and a vertical double step $(0,-2)$ as a domino.
Figure~\ref{F3.13} shows the covering of $[1,10]$ that corresponds to
the path from Figure~\ref{F3.11}.

\begin{Figure} \label{F3.13}
$$
%\Einheit.6cm
\Pfad(0,0),111111111111111111\endPfad
\DickPunkt(0,0)
\Kreis(2,0)
\DickPunkt(4,0)
\Kreis(6,0)
\Kreis(8,0)
\DickPunkt(10,0)
\Kreis(12,0)
\Kreis(14,0)
\Kreis(16,0)
\DickPunkt(18,0)
\Pfad(1,-1),1122\endPfad
\Pfad(1,-1),2211\endPfad
\Pfad(5,-1),111122\endPfad
\Pfad(5,-1),221111\endPfad
\Pfad(11,-1),111122\endPfad
\Pfad(11,-1),221111\endPfad
\Pfad(15,-1),1122\endPfad
\Pfad(15,-1),2211\endPfad
\Label\u{1}(0,0)
\Label\u{2}(2,0)
\Label\u{3}(4,0)
\Label\u{4}(6,0)
\Label\u{5}(8,0)
\Label\u{6}(10,0)
\Label\u{7}(12,0)
\Label\u{8}(14,0)
\Label\u{9}(16,0)
\Label\u{10}(18,0)
\hskip11cm
$$
\end{Figure}

Thus we have found a bijection between 
families $(P_0,\dots,P_{n-1})$ of nonintersecting Motzkin
paths, $P_i$ running from $A_{\si(i)}=(-\si(i),0)$ to $E_i=(i+\chi(i\ge k),0)$, 
$i=0,1,\dots,n-1$, for some permutation $\si$, 
and coverings $\al$ of $[1,10]$ with exactly $k$ points.
Clearly, under this correspondence, the sign of the permutation $\si$
is exactly equal to $(-1)^d$, where $d$ is the number of dominos in
the corresponding covering $\al$. Furthermore we have
$$n-k=\#(\text {monominos in $\al$})+2\#(\text {dominos in $\al$}),$$
so that
$$(-1)^{n+k}\sgn\si=(-1)^{\#(\text {monominos in $\al$})+\#(\text {dominos in
$\al$})}.$$
Therefore, if the covering $\al$ corresponds to the
family $(P_0,\dots,P_{n-1})$ with associated permutation $\si$, then we have
$$(-1)^{n+k}(\sgn\si)\,x^k \,w\big((P_0,\dots,P_{n-1})\big)=
\la_1^{n-1}\la_2^{n-2}\cdots\la_{n-1}^1\cdot w(\al).$$
In view of \eqref{e3.29}, \eqref{e3.30}, and \eqref{e3.26}, and
because of Lemma~\ref{L3.2}, this establishes the theorem.
\end{proof}

In Section~\ref{s3.6} we derive several further enumeration results on Motzkin
paths which feature orthogonal polynomials.

\section{The theory of heaps}
\label{s3.5}\index{heaps of pieces}
In \cite{VienAF}, \index{Viennot, Xavier G\'erard}Viennot 
introduced a combinatorial theory which he
termed the theory of ``{\em heaps of pieces}." 
As it turned out, this theory had
already appeared earlier, in a purely algebraic fashion, in 
\index{Cartier, Pierre}Cartier
and \index{Foata, Dominique}Foata \cite{CaFoAA}, and is now called the 
\index{monoid, Cartier--Foata}\index{Cartier--Foata monoid}``{\em 
Cartier--Foata monoid}." Viennot discovered many beautiful
applications of this theory in combinatorics \cite{??}, in particular
in the enumeration of polyominoes (see also Chapter~\ref{??},
Section~\ref{??}) and Motzkin paths, 
and in the theory of orthogonal polynomials. 
In this section we provide a brief introduction into the theory of
heaps. The applications to the enumeration of Motzkin paths and
the theory of orthogonal polynomials are given in Section~\ref{s3.6}.

Informally, a {\em heap} is what we would imagine. We take a
collection of
``pieces," say $B_1,B_2,\dots$, and put them one upon the other,
sometimes also sideways, to form a ``heap," see Figure~\ref{F3.14}.

\begin{Figure}\label{F3.14}
\unitlength1cm
\begin{picture}(10,5)
\thicklines
\put(5.2,1){\oval(2,1)}
\put(9.5,1){\oval(2,1)}
\put(10,2){\oval(1,1)}
\put(3,2){\oval(4.5,1)}
\put(6,2){\oval(1,1)}
\put(3,3){\oval(2,1)}
\put(5.2,3){\oval(2,1)}
\put(4,4){\oval(3,1)}
\put(5.1,.9){$B_2$}
\put(9.4,.9){$B_7$}
\put(9.9,1.9){$B_6$}
\put(2.9,1.9){$B_4$}
\put(5.9,1.9){$B_5$}
\put(2.9,2.9){$B_3$}
\put(5.1,2.9){$B_2$}
\put(3.9,3.9){$B_1$}
\put(0,0.5){\line(1,0){11}}
\end{picture}
\centerline{\small A heap of pieces}
\end{Figure}

We imagine that pieces can only move vertically (so that the heap in
Figure~\ref{F3.14} would indeed form a stable arrangement). Note that
we allow that several copies of a piece to appear in a heap. (This
means that they differ only by a vertical translation.) For
example, in Figure~\ref{F3.14} there appear two copies of $B_2$.
Under these assumptions, there are pieces which can move past each
other, and others which cannot. For example, in Figure~\ref{F3.14},
we can move the piece $B_6$ higher up, thus moving it higher than
$B_1$ if we wish. However, we cannot move $B_7$ higher than $B_6$,
because $B_6$ blocks the way. On the other hand, we can move $B_7$
past $B_1$ (thus taking $B_6$ with us). 

\begin{Figure} \label{F3.15}
$$
\Einheit1.5cm
\Pfad(0,2),443\endPfad
\Pfad(0,2),34\endPfad
\Pfad(1,1),3\endPfad
\Pfad(2,0),3\endPfad
\Pfad(4,0),2\endPfad
\DickPunkt(2,0)
\DickPunkt(1,1)
\DickPunkt(3,1)
\DickPunkt(0,2)
\DickPunkt(2,2)
\DickPunkt(1,3)
\DickPunkt(4,0)
\DickPunkt(4,1)
\Label\u{\raise-8pt\hbox{$B_2$}}(2,0)
\Label\l{B_4\kern7pt}(1,1)
\Label\r{\kern7ptB_5}(3,1)
\Label\l{B_3\kern7pt}(0,2)
\Label\r{\kern7ptB_2}(2,2)
\Label\o{\raise8pt\hbox{$B_1$}}(1,3)
\Label\u{\raise-8pt\hbox{$B_7$}}(4,0)
\Label\o{\raise8pt\hbox{$B_6$}}(4,1)
\hskip6cm
$$
\vskip8pt
\centerline{\small The skeleton of the heap in Figure~\ref{F3.14}}
\end{Figure}

To make these considerations mathematically rigorous, consider the
``skeleton" of a heap. This is obtained by replacing each piece by a
vertex, and by joining to vertices by an edge whenever one vertex
blocks the way of the other in the sense described above. The
skeleton of the heap in Figure~\ref{F3.14} is shown in
Figure~\ref{F3.15}. (There, we have labelled each vertex by the name
of the corresponding piece.) Mathematically, a skeleton is 
a labelled \index{partially ordered set}\index{poset}{\em
partially ordered set\/} or {\em poset}. 

\begin{Definition}A {\em partially ordered set} {\em (poset)} is a
pair $(P,\preceq)$, where $P$ is a set, and where $\preceq$ is a binary
relation defined on $P$ which is
\begin{enumerate}
\item[(1)] reflexive, i.e., $x\preceq x$ for all $x$ in $P$,
\item[(2)] antisymmetric, i.e., if $x\preceq y$ and $y\preceq x$, then $x=y$ for
all $x,y$ in $P$,
\item[(3)] transitive, i.e., if $x\preceq y$ and $y\preceq z$ then $x\preceq z$ for all
$x,y,z$ in $P$.
\end{enumerate}
\end{Definition}

Posets are usually shown graphically 
in the form of \index{Hasse diagram}{\em Hasse diagrams}. 
The Hasse diagram of a poset is the graph with
vertices $P$, in which $x$ and $y$ are connected by an edge if $x\preceq
y$ and there is no $z$ different from $x$ and $y$ with $x\preceq z\preceq y$.
Moreover, in the diagram, $x$ is shown at a lower level than $y$. 
Clearly, the diagram in Figure~\ref{F3.15} is the Hasse diagram of a
poset, with vertices labelled by pieces.

Now we can rigorously define what a heap is.
\begin{Definition} Let \glossary{$\Bau$}$\Bau$ be a set (of pieces) with a
symmetric and reflexive binary relation \glossary{$\Rel$}$\Rel$. A heap is a triple
$(P,\preceq, \ell)$, where $(P,\preceq)$ is a poset, and where $\ell$
is a labelling of the elements of $P$ by elements of $\Bau$, such that:
\begin{enumerate}
\item[(1)] If $x,y\in P$ and $\ell(x)\Rel \ell(y)$, then either
$x\preceq y$ or $y\preceq x$.
\item[(2)] The relation $\preceq$ is the transitive closure of the
relations from (1).
\end{enumerate}
\end{Definition}


\begin{Remark}\label{R3.5}
The meaning of the relation $\Rel$ is that it expresses
which pieces cannot be moved past each other. I.e., a relation $x\Rel
y$ means that $x$ blocks the way of $y$, and vice versa. Requirement (1)
above then says that, hence, in
(any realization of) a heap, either $x$ must be above $y$, symbolized
by $y\preceq x$, or $x$ must be below $y$, symbolized by $x\preceq
y$. 
\end{Remark}

We illustrate this concept with the heap in Figure~\ref{F3.14}. The
pieces are $\Bau=\{B_1,B_2,\dots,B_7\}$. The relations are (not
mentioning the relations of the form $B_i\Rel B_i$; if a
relation $B_i\Rel B_j$ holds then also $B_j\mathcal B_i$) 
\begin{multline} \label{e3.31}
B_1\Rel B_2,\
B_1\Rel B_3,\
B_1\Rel B_4,\
B_2\Rel B_4,\\
B_3\Rel B_4,\
B_2\Rel B_5,\
B_6\Rel B_7. 
\end{multline}
According to Remark~\ref{R3.5}, these relations mean that 
if $B_i\Rel B_j$, then in any heap a piece $B_i$ must be
either below or above a piece $B_j$, more precisely, in the
corresponding poset a vertex $u$ labelled $B_i$ and a vertex $v$ labelled
$B_j$ must either satisfy $u\preceq v$ or $v\preceq u$. In our
running example we have $B_2\Rel B_4$, and indeed there is one piece
$B_2$ which is above $B_4$, and there is another piece $B_2$ which is
below $B_4$, see Figure~\ref{F3.14}. 

The class of heaps which is most important in our context of Motzkin
paths and orthogonal polynomials is the class of heaps of 
\index{monomer}{\em monomers} and \index{dimer}{\em dimers}, which we
now introduce.
\begin{Example}\label{Emondim}
Let $\Bau=M\cup D$, where $\Monomer=\{m_0,m_1,\dots\}$ is the set of
\index{monomer}monomers and $\Dimer=\{d_1,d_2,\dots\}$ is the set of
dimers. We think of a monomer $m_i$ as a point, symbolized by a
circle, with $x$-coordinate $i$, see Figure~\ref{F3.16}.
We think of a dimer $d_i$ as two points, symbolized by 
circles, with $x$-coordinates $i-1$ and $i$ which are connected by an edge, 
see Figure~\ref{F3.16}.

\begin{Figure} \label{F3.16}
$$
\Einheit1cm
\Pfad(-1,0),111111111\endPfad
\SPfad(0,0),222222\endPfad
\SPfad(1,0),222222\endPfad
\SPfad(2,0),222222\endSPfad
\SPfad(3,0),222222\endSPfad
\SPfad(4,0),222222\endSPfad
\SPfad(5,0),222222\endSPfad
\SPfad(6,0),222222\endSPfad
\SPfad(7,0),222222\endSPfad
\Kreis(0,1)
\Kreis(1,1)
\Kreis(2,1)
\Kreis(3,1)
\Kreis(4,1)
\Kreis(5,1)
\Kreis(6,1)
\Kreis(7,1)
\Label\u{m_0}(0,1)
\Label\u{m_1}(1,1)
\Label\u{m_2}(2,1)
\Label\u{m_3}(3,1)
\Label\u{m_4}(4,1)
\Label\u{m_5}(5,1)
\Label\u{m_6}(6,1)
\Label\u{m_7}(7,1)
\Kreis(0,2)
\Kreis(1,2)
\Kreis(1,3)
\Kreis(2,3)
\Kreis(2,4)
\Kreis(3,4)
\Kreis(3,5)
\Kreis(4,5)
\Pfad(0,2),1\endPfad
\Pfad(1,3),1\endPfad
\Pfad(2,4),1\endPfad
\Pfad(3,5),1\endPfad
\Label\ro{d_1}(0,2)
\Label\ro{d_2}(1,3)
\Label\ro{d_3}(2,4)
\Label\ro{d_4}(3,5)
\Label\u{0}(0,0)
\Label\u{1}(1,0)
\Label\u{2}(2,0)
\Label\u{3}(3,0)
\Label\u{4}(4,0)
\Label\u{5}(5,0)
\Label\u{6}(6,0)
\Label\u{7}(7,0)
\hskip7cm
$$
\vskip10pt
\centerline{\small Monomers and dimers}
\end{Figure}
We impose the relations $m_i\Rel m_i$, $m_i\Rel d_i$, $m_i\Rel
d_{i+1}$, $i=0,1,\dots$, $d_i\Rel d_j$, $i-1\le j\le i$, and extend
$\Rel$ to a symmetric relation. Figure~\ref{F3.17} shows two heaps of
momomers and dimers.
\begin{Figure} \label{F3.17}
$$
\Einheit.35cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Kreis(0,2)
\Kreis(0,3)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(4,1)
\Kreis(8,1)
\Kreis(10,2)
\Kreis(12,1)
\Kreis(12,2)
\Kreis(14,1)
\Pfad(0,2),11\endPfad
\Pfad(2,1),11\endPfad
\Pfad(10,2),11\endPfad
\hbox{\hskip7cm}
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Kreis(2,2)
\Kreis(4,1)
\Kreis(4,2)
\Kreis(4,3)
\Kreis(6,1)
\Kreis(6,2)
\Kreis(8,2)
\Kreis(10,1)
\Pfad(2,2),11\endPfad
\Pfad(4,1),11\endPfad
\Pfad(6,2),11\endPfad
\hskip5cm
$$
\vskip10pt
\centerline{\small Two heaps of monomers and dimers}
\end{Figure}
\end{Example}

Next we make heaps into a \index{monoid}{\em monoid} by introducing a
\index{composition of heaps}{\em composition} of heaps. (A monoid is a
set with a binary operation which is associative.) Intuitively, given
two heaps $H_1$ and $H_2$, the composition of $H_1$ and $H_2$, 
the heap $H_1\circ H_2$, is the heap which
results by putting $H_2$ on top of $H_1$. The rigorous definition is
the following.

\begin{Definition}\label{D3.5}
Let $H_1$ and $H_2$ be heaps,
$H_1=(P_1,\preceq_1,\ell_1)$,
$H_2=(P_2,\preceq_2,\ell_2)$. 
Then the composition of $H_1$ and $H_2$, $H_1\circ H_2$, 
is the heap $(H_3,\preceq_3,\ell_3)$ with
\begin{enumerate}
\item[(1)] $P_3=P_1\cup P_2$.
\item[(2)] The partial order $\preceq_3$ on $P_3$ is the transitive
closure of
\begin{enumerate}
\item[(a)] $v_1\preceq_3 v_2$ if $v_1\preceq_1 v_2$,
\item[(b)] $v_1\preceq_3 v_2$ if $v_1\preceq_2 v_2$,
\item[(c)] $v_1\preceq_3 v_2$ if $v_1\in P_1$, $v_2\in P_2$ and
$\ell_1(v_1)\Rel \ell_2(v_2)$.
\end{enumerate}
\end{enumerate}
\end{Definition}

The composition of the two heaps in Figure~\ref{F3.17} is shown in
FIgure~\ref{F3.18}.

\begin{Figure} \label{F3.18}
$$
\Einheit.35cm
\Pfad(-2,0),11111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\SPfad(16,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Label\u{8}(16,0)
\Kreis(0,2)
\Kreis(0,3)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(2,3)
\Kreis(4,1)
\Kreis(4,2)
\Kreis(4,3)
\Kreis(4,4)
\Kreis(6,2)
\Kreis(6,3)
\Kreis(8,1)
\Kreis(8,3)
\Kreis(10,2)
\Kreis(10,3)
\Kreis(12,1)
\Kreis(12,2)
\Kreis(14,1)
\Pfad(0,2),11\endPfad
\Pfad(2,1),11\endPfad
\Pfad(2,3),11\endPfad
\Pfad(4,2),11\endPfad
\Pfad(6,3),11\endPfad
\Pfad(10,2),11\endPfad
\hskip5.6cm
$$
\vskip10pt
\centerline{\small The composition of the heaps in Figure~\ref{F3.17}}
\end{Figure}


Given pieces $\Bau$ with relation $\Rel$,
let \glossary{$\mathcal H(\Bau, \Rel)$}$\mathcal H(\Bau, \Rel)$ 
be the set of all heaps consisting of pieces
from $\Bau$, including the empty heap, denoted by $\emptyset$. It is easy
to see that Definition~\ref{D3.5} makes $(\mathcal H(\Bau,\Rel),\circ)$
into a monoid with unit $\emptyset$.

This monoid had been introduced earlier by \index{Cartier, Pierre}Cartier
and \index{Foata, Dominique}Foata \cite{CaFoAA}, and is now known as
the \index{monoid, Cartier--Foata}\index{Cartier--Foata monoid}``{\em 
Cartier--Foata monoid}." In order to explain this monoid, we first
observe that heaps could also be encoded by \index{word}{em words}
with letters from $\Bau$, i.e., by sequences of pieces. To obtain a
word from a heap $H=(P,\preceq,\ell)$, 
one considers a \index{linear extension of a poset}{\em 
linear extension} of the poset $P$ (i.e., a linear ordering $\le$ of the
elements of $P$ in which $x\le y$ whenever $x\preceq y$), and then
reads the labels $\ell(x)$ of the elements of $P$, while $x$ runs
through all elements of $P$ in the linear order, bottom to top.
Clearly, since there may be several linear extensions of a poset,
several different words may be read off from the same heap.
For
the heap in Figure~\ref{F3.14} (see Figure~\ref{F3.15} for the
corresponding poset), possible such readings are
\begin{equation} \label{e3.32}
B_2B_7B_4B_5B_6B_3B_2B_1 \text { and } B_2B_5B_4B_2B_3B_1B_7B_6.
\end{equation}

Of course, we want to identify words that are read off from the same
heap. Therefore we introduce an equivalence relation on words: We say
that the words $u$ and $w$ are equivalent, in symbols $u\sim w$, if
$w$ arises from $u$ by a squence of interchanges of two adjacent letters 
$x$ and $y$ for which $\hbox{$x\not\kern-5pt\Rel y$}$. For example, given the
relation $\Rel$ as in \eqref{e3.31}, the words in \eqref{e3.32} arise
from each other by the following sequence of interchanges:
\begin{multline*} 
B_2B_7B_4B_5B_6B_3B_2B_1 \sim 
B_2B_7B_5B_4B_6B_3B_2B_1 \sim 
B_2B_5B_7B_4B_6B_3B_2B_1 \\
\sim 
B_2B_5B_4B_7B_6B_3B_2B_1 \sim 
B_2B_5B_4B_7B_6B_2B_3B_1 \sim 
B_2B_5B_4B_7B_2B_6B_3B_1 \\
\sim 
B_2B_5B_4B_2B_7B_6B_3B_1 \sim 
B_2B_5B_4B_2B_7B_3B_6B_1 \sim 
B_2B_5B_4B_2B_3B_7B_6B_1 \\
\sim 
B_2B_5B_4B_2B_3B_7B_1B_6 \sim 
B_2B_5B_4B_2B_3B_1B_7B_6.
\end{multline*}
Thus, heaps
in $\mathcal H(\Bau,\Rel)$ correspond to equivalence classes of words
modulo $\sim$. Denoting, as usual, the set of all words with letters
from $\Bau$ by $\Bau^*$, the set of equivalence classes of words is
$\Bau^*/\sim$. In $\Bau^*/\sim$, we write $\tilde u$ for the
equivalence class of the word $u$.

In $\Bau^*$ there is an obvious composition of two words $u$ and $w$,
the concatenation $uw$. Clearly, if $u\sim u'$ and $w\sim w'$, then
$uw\sim u'w'$. Hence, concatenation induces a composition $\tilde
u\circ\tilde w:=\widetilde{uw}$ of
equivalence classes $\tilde u$ and $\tilde w$ in $\Bau^*/\sim$. Under
the above described correspondence between heaps and
equivalence classes of words, the composition of heaps corresponds
exactly to the composition of equivalence classes of words.

\begin{Definition}
Let $\bar \Rel$ be a symmetric and {\em antireflexive} relation on
$\Bau$ (i.e., $\hbox{$x\not\kern-5pt{\bar\Rel} x$}$ for all $x\in \Bau$). The
\index{monoid, Cartier--Foata}\index{Cartier--Foata monoid}Cartier--Foata 
monoid $Mo(\Bau,\bar \Rel)$ is the monoid, whose elements are the
equivalence classes of words in $\Bau^*/\sim$, where $\sim$ is the
equivalence relation defined by $u\sim w$ whenever $w$ arises from $u$ 
by a sequence of interchanges of adjacent letters $x$ and $y$ for
which $x\bar\Rel y$, and 
with composition on $\Bau^*/\sim$ induced by concatentation of words.
\end{Definition}

Clearly, under the correspondence between heaps and equivalence
classes of words in the Cartier--Foata monoid the relation $\bar\Rel$
is the negation of the relation $\Rel$.

\medskip
For the statement of the main theorem in the theory of heaps, we need
two more terms. A \index{heap, trivial}\index{trivial heap}{\em
trivial heap} is a heap consisting of pieces all of which are
pairwise unrelated, i.e., $\hbox{$x\not\kern-5pt\Rel y$}$ for all pieces $x,y$
in $H$. Figure~\ref{F3.19}.a shows a trivial heap consisting of
monomers and dimers. 
A \index{pyramid}{\em pyramid\/} is a heap with exactly one
maximal element (in the corresponding poset).
Figure~\ref{F3.19}.a shows a pyramid consisting of
monomers and dimers. Finally, if $H$ is a heap, then we write $\v{H}$
for the number of pieces in $H$.

\begin{Figure} \label{F3.19}
$$
\Einheit.35cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),22222\endPfad
\SPfad(2,0),22222\endPfad
\SPfad(4,0),22222\endSPfad
\SPfad(6,0),22222\endSPfad
\SPfad(8,0),22222\endSPfad
\SPfad(10,0),22222\endSPfad
\SPfad(12,0),22222\endSPfad
\SPfad(14,0),22222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Label\u{7}(14,0)
\Kreis(2,1)
\Kreis(4,1)
\Kreis(8,1)
\Kreis(10,1)
\Kreis(12,1)
\Kreis(14,1)
\Pfad(2,1),11\endPfad
\Pfad(10,1),11\endPfad
\hbox{\hskip7cm}
\Pfad(-2,0),1111111111111111\endPfad
\SPfad(0,0),2222222\endPfad
\SPfad(2,0),2222222\endPfad
\SPfad(4,0),2222222\endSPfad
\SPfad(6,0),2222222\endSPfad
\SPfad(8,0),2222222\endSPfad
\SPfad(10,0),2222222\endSPfad
\SPfad(12,0),2222222\endSPfad
\Label\u{0}(0,0)
\Label\u{1}(2,0)
\Label\u{2}(4,0)
\Label\u{3}(6,0)
\Label\u{4}(8,0)
\Label\u{5}(10,0)
\Label\u{6}(12,0)
\Kreis(0,2)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(2,3)
\Kreis(4,1)
\Kreis(4,2)
\Kreis(4,3)
\Kreis(4,4)
\Kreis(6,2)
\Kreis(6,3)
\Kreis(8,1)
\Kreis(8,3)
\Kreis(10,2)
\Kreis(10,3)
\Kreis(12,1)
\Kreis(12,2)
\Kreis(8,4)
\Kreis(10,4)
\Kreis(6,4)
\Kreis(8,5)
\Kreis(6,6)
\Kreis(8,6)
\Pfad(0,2),11\endPfad
\Pfad(2,1),11\endPfad
\Pfad(2,3),11\endPfad
\Pfad(4,2),11\endPfad
\Pfad(6,3),11\endPfad
\Pfad(10,2),11\endPfad
\Pfad(8,4),11\endPfad
\Pfad(4,4),11\endPfad
\Pfad(6,6),11\endPfad
\hskip5cm
$$
\vskip10pt
\centerline{\small a. A trivial heap\hskip5cm b. A pyramid}
\end{Figure}


\begin{Theorem} \label{T3.9}
Let $\mathcal M$ be a subset of the pieces $\Bau$. Then, in the
Cartier--Foata monoid, the (formal) sum of all heaps with maximal pieces
(by which we mean 
the labels of the maximal elements in the corresponding posets)
contained in $\mathcal M$ is given by
\begin{equation} \label{e3.34}
\underset{\text {maximal pieces }\subseteq\mathcal M}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}\kern-15pt H=
\bigg(\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}T\bigg)^{-1}
\bigg(\suml _{T\in \mathcal T(\Bau\backslash\mathcal M,\Rel)} 
^{}(-1)^{\v{T}}T\bigg),
\end{equation}
where $\mathcal T(\Bau,\Rel)$ denotes the set of all trivial heaps
with pieces from $\Bau$, and similarly for $\mathcal
T(\Bau\backslash\mathcal M,\Rel)$.
In particular, the sum of all heaps if given by
\begin{equation} \label{e3.35}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}H=
\bigg(\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}T\bigg)^{-1}.
\end{equation}
\end{Theorem}

\begin{Remark} The inverse of the series which appears on the
right-hand sides of \eqref{e3.34} and \eqref{e3.35} exists because it
has the form $(1-X)^{-1}=\sum _{j\ge0} ^{}X^j$.
\end{Remark}

\begin{proof} Formula \eqref{e3.35} is the special case of
\eqref{e3.34} in which $\mathcal M=\Bau$. Therefore it suffices to
establish \eqref{e3.34}. By multiplication at the left by 
$\sum _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}T$, the
latter is equivalent to
\begin{equation} \label{e3.36}
\underset{\text {maximal pieces of $H$ }\subseteq\mathcal M}
{\sum _{H\in \mathcal H(\Bau,\Rel),\ T\in \mathcal T(\Bau,\Rel)} ^{}}
(-1)^{\v{T}}T\circ H=
\bigg(\sum _{T\in \mathcal T(\Bau\backslash\mathcal M,\Rel)} 
^{}(-1)^{\v{T}}T\bigg).
\end{equation}
We show that most of the terms on the left-hand side of \eqref{e3.36} cancel
each other pairwise. In order to do this, we first fix an arbitrary
linear order on the set of pieces $\Bau$.
Now, let $(H,T)$ be a pair of a heap $H$ in $\mathcal H(\Bau,\Rel)$
with maximal pieces contained in $\mathcal M$ and a trivial heap $T$.
Consider the minimal pieces in $T\circ H$ 
(again, this means the labels of the
minimal elements in the poset corresponding to $T\circ H$) which are
below some maximal piece in $T\circ H$ that belongs to $\mathcal M$. 
Let $B$ be the first such minimal piece in the linear order of
pieces. Then we form a new pair $(H',T')$ by:
\begin{itemize}
\item If $B\in T$, then $H'=B\circ H$ and $T'=T\backslash B$.
\item If $B\notin T$, then $H'=H\backslash B$ and $T'=T\circ B$.
\end{itemize}
In particular, nothing chances in the composed heap, i.e.,
we have $T'\circ H'=T\circ H$.
Hence, we have $(-1)^{\v{T'}}T'\circ H'=-(-1)^{\v{T}}T\circ H$.
When the same mapping is applied to $(H',T')$ then we obtain back
$(H,T)$. Therefore, all the summands on the left-hand side of
\eqref{e3.36} which are indexed by pairs to which the above map is
applicable cancel. The remaining summands are those indexed by pairs
$(H,T)$ for which $T\circ H$ does not contain any maximal piece in
$\mathcal M$. This forces $H$ (which ``sits" on top of $T$ in $T\circ
H$) to be the empty heap, and $T$ to consist of pieces in
$\Bau\backslash \mathcal M$ only (all the pieces in a trivial heap
are maximal). Thus, \eqref{e3.36} is established.
\end{proof}

In applications, heaps will have weights, which are defined by
introducing a weight $w(B)$ for each piece $B$ in $\Bau$, and by
extending the weight $w$ to all heaps $H$ by letting $w(H)$ denote
the product of all weights of the pieces in $H$. Theorem~\ref{T3.9}
immediately implies the following corollary on the corresponding 
generating function of heaps.

\begin{Corollary} \label{C3.4}
Let $\mathcal M$ be a subset of the pieces $\Bau$. Then, 
the generating function for all heaps with maximal pieces
contained in $\mathcal M$ is given by
\begin{equation} \label{e3.37}
\underset{\text {maximal pieces }\subseteq\mathcal M}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}\kern-15pt w(H)=
\frac {\suml _{T\in \mathcal T(\Bau\backslash\mathcal M,\Rel)} 
^{}(-1)^{\v{T}}w(T)}
{\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T)},
\end{equation}
where again $\mathcal T(\Bau,\Rel)$ denotes the set of all trivial heaps
with pieces from $\Bau$.
In particular, the generating function for all heaps if given by
\begin{equation} \label{e3.38}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}w(H)=
\frac {1} {\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T)}.
\end{equation}
\end{Corollary}

\section{Motzkin paths and heaps of monomers and dimers}
\label{s3.6}
In Sections~\ref{s3.1} and \ref{s3.3} we have derived enumeration
results for Motzkin paths which start and terminate on the $x$-axis.
In particular, Theorem~\ref{T3.4} provided a continued fraction for
the generating function with respect to a very general weight.
We now use the heap theorem (Corollary~\ref{C3.4}) to write this
continued fraction compactly in numerator/denominator form, using
orthogonal polynomials, and then derive a compact
expression for the generating function of Motzkin paths which
start and terminate at {\em arbitrary} points, again using orthogonal
polynomials.

We recall the basic setup from Section~\ref{s3.3}. We consider paths
with steps from $M=\{(1,1),(1,-1),(1,0)\}$, i.e., paths with
diagonal up- and down-steps and level-steps, which do not pass below
the $x$-axis. We call such paths
\index{path, Motzkin}\index{Motzkin path}{\em
Motzkin paths}. The weight of a Motzkin path is the product of all
the weights of its steps, where the weight of an
up-step $(1,1)$ is $1$, the weight of a down-step $(1,-1)$ from
height $h$ to $h-1$ is $\la_h$, and the weight of a level-step $(1,0)$
at height is $b_h$. See Figure~\ref{F3.4}. 

Furthermore, given sequences $(b_n)_{n\ge0}$ and $(\la_n)_{n\ge1}$, with
$\la_n\ne0$ for all $n\ge1$, we need the corresponding sequence
$(p_n(x))_{n\ge0}$ of 
orthogonal polynomials which are given by the three-term recurrence
\eqref{eq:three-term},
\begin{equation} \label{eq:three-term2}
xp_{n}(x)=p_{n+1}(x)+b_np_n(x)+\la_{n}p_{n-1}(x),\quad \quad 
\text{ for } n\geq 1,
\end{equation}
with initial conditions $p_0(x)=1$ and $p_1(x)=x-b_0$. Given a
sequence $(p_n(x))_{n\ge0}$ of orthogonal polynomials, we also need
associated ``shifted" polynomials (often?? simply called
\index{associated orthogonal polynomials}\index{polynomial,
associated orthogonal}{\em
associated orthogonal polynomials}), denoted by $(Sp_n(x))_{n\ge0}$,
which arise from the sequence $(p_n(x))$ by replacing $\la_i$ by
$\la_{i+1}$ and $b_i$ by $b_{i+1}$, $i=0,1,2,\dots$, everywhere in
the three-term recurrence \eqref{eq:three-term2} and in the initial
conditions. Finally, given a polynomial $p(x)$ of degree $n$, we
denote the corresponding \index{polynomial,
recipocal}\index{reciprocal polynomial}{\em reciprocal polynomial}
$x^np(1/x)$ by $p^*(x)$.

The first theorem in this section provides an alternative for
Theorem~\ref{T3.4}. It expresses the generating function for Motzkin
paths which start at the origin and return to the $x$-axis as a
quotient of two orthogonal polynomials, instead of as a continued
fraction. It should be noted that the generating function 
in Theorem~\ref{T3.10} is slightly different from the generating
function in Theorem~\ref{T3.4}. To be precise, in Theorem~\ref{T3.10} 
a Motzkin path $P$ of length $n$ is counted with weight $w(P)x^n$,
while in Theorem~\ref{T3.4} it is counted with weight $w(P)$.
However, these two different weightings are equivalent. This
equivalence is made explicit by observing that replacement of 
$b_i$ by $b_ix$ and $\la_i$ by $\la_ix^2$ for all $i$ transforms $w(P)$
into $w(P)x^n$ for a Motzkin path of length $n$ 
which starts and terminates on the $x$-axis.

\begin{Theorem} \label{T3.10}
With the weight $w$ defined as above, the generating function for
\index{path, Motzkin}\index{Motzkin path}Motzkin paths running from 
the origin back to the $x$-axis
which stay below the line $y=k$, is given by
\begin{equation} \label{e3.39}
\sum _{n\ge0} ^{}\GF{\L{(0,0)\to(n,0);M\mid 0\le y\le k};w}x^n
=\frac {Sp_k^*(x)} {p_{k+1}^*(x)}.
\end{equation}
\end{Theorem}
\begin{proof}We construct a bijection between Motzkin paths and heaps
of monomers and dimers (see Example~\ref{Emondim}). Given a Motzkin
path, we read the steps of the path from the beginning to the end.
Whenever we read a level-step at height $h$, we make it into a
monomer with $x$-coordinate $h$, whenever we read a down-step from height $h$ to
height $h-1$, we make it into a dimer whose end points have
$x$-coordinates $h-1$ and $h$. Up-steps are ignored. 
Figure~\ref{F3.20} shows an example.
In the figure, the heap is not in ``standard" fashion, in the sense
that the $x$-axis is not shown as a horizontal line but as a vertical
line (compare with Figure~\ref{F3.16}). But it could be easily
transformed into ``standard" fashion by a simple reflection with
respect to a line of slope $1$.

\begin{Figure} \label{F3.20}
$$
\Einheit.7cm
\Pfad(0,0),3134133444134\endPfad
\PfadDicke{.5pt}
\Pfad(0,0),1111111111111\endPfad
\DickPunkt(0,0)
\DickPunkt(1,1)
\DickPunkt(2,1)
\DickPunkt(3,2)
\DickPunkt(4,1)
\DickPunkt(5,1)
\DickPunkt(6,2)
\DickPunkt(7,3)
\DickPunkt(8,2)
\DickPunkt(9,1)
\DickPunkt(10,0)
\DickPunkt(11,0)
\DickPunkt(12,1)
\DickPunkt(13,0)
\kern1.5pt
\Pfad(3,2),4\endPfad
\Pfad(7,3),444\endPfad
\Pfad(12,1),4\endPfad
\hbox{\hskip9.5cm}
\raise.7cm\hbox{$\longrightarrow$\hskip.8cm}
\Einheit.35cm
\Pfad(0,-2),2222222222\endPfad
\SPfad(0,0),11111111\endSPfad
\SPfad(0,2),11111111\endSPfad
\SPfad(0,4),11111111\endSPfad
\SPfad(0,6),11111111\endSPfad
\Kreis(1,2)
\Kreis(2,2)
\Kreis(2,4)
\Kreis(3,2)
\Kreis(3,4)
\Kreis(3,6)
\Kreis(4,2)
\Kreis(4,4)
\Kreis(5,0)
\Kreis(5,2)
\Kreis(6,0)
\Kreis(7,0)
\Kreis(7,2)
\Pfad(2,2),22\endPfad
\Pfad(3,4),22\endPfad
\Pfad(4,2),22\endPfad
\Pfad(5,0),22\endPfad
\Pfad(7,0),22\endPfad
\Label\l{0}(0,0)
\Label\l{1}(0,2)
\Label\l{2}(0,4)
\Label\l{3}(0,6)
\hskip3.5cm
$$
\centerline{\small Bijection between Motzkin paths and heaps of monomers and
dimers}
\end{Figure}

It is not difficult to see that this sets up a bijection between
Motzkin paths starting at the origin and returning to the $x$-axis
which stay below the line $y=k$ and pyramids of monomers
$\{m_0,m_1,\dots,m_k\}$ and dimers $\{d_1,d_2\dots,d_k\}$
with maximal piece being either $m_0$ (a monomer with $x$-coordinate
$0$) or $d_1$ (a dimer whose end points have $x$-coordinates $0$ and
$1$). In particular, the set of pieces is
$\Bau=\{m_0,m_1,\dots,m_k,d_1,d_2,\dots,d_k\}$, with relation $\Rel$
as in Example~\ref{Emondim}. 

In order to make this bijection weight-preserving in the sense that a
heap corresponding to path $P$ has weight $w(P)x^n$, we define the
weight of a heap as follows (compare the paragraph before the
statement of Theorem~\ref{T3.10}): The weight of a monomer with
$x$-coordinate $h$ is defined as $w_x(m_h)=b_hx$, and the weight of 
a dimer whose end points have $x$-coordinates $h-1$ and $h$ 
is defined as $w_x(d_h)=\la_hx^2$. As always, the weight $w_x(H)$ of
a heap is defined to be the product of all weights of its pieces. 
Then, by Corollary~\ref{C3.4} we have
\begin{multline} \label{e3.40}
\sum _{n\ge0} ^{}\GF{\L{(0,0)\to(n,0);M\mid 0\le y\le k};w}x^n\\
=\underset{\text {maximal pieces }\subseteq\mathcal \{m_0,d_1\}}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}w(H)=
\frac {\suml _{T\in \mathcal T(\Bau\backslash\mathcal \{m_0,d_1\},\Rel)} 
^{}(-1)^{\v{T}}w(T)}
{\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T)},
\end{multline}
where, as before, 
$\mathcal T(\Bau,\Rel)$ denotes the set of all trivial heaps with
pieces from $\Bau$. 

A trivial heap consisting of monomers and dimers is a collection of
monomers and dimers that do not ``overlap." More precisely, there is
an obvious bijection between trivial heaps in $\mathcal T(\Bau,\Rel)$
and coverings of $[1,k+1]$ (see the paragraphs before
Lemma~\ref{L3.2}), in which a monomer $m_i$ corresponds to the
monomino labelled $i+1$ and a dimer $d_i$ corresponds to the
domino with labels $i,i+1$. Lemma~\ref{L3.2} then implies that we
have
\begin{align} 
\sum _{T\in \mathcal T(\Bau,\Rel)} 
^{}(-1)^{\v{T}}w(T)&=x^{k+1}\sum _{\al\text { covering of }[1,k+1]}
^{}w(\al)\big\vert_{x\to 1/x}\\
&=x^{k+1}p_{k+1}(1/x)=p^*_{k+1}(x).
\label{e3.41}
\end{align}
Analogously, trivial heaps in $\mathcal T(\Bau\backslash\mathcal
\{m_0,d_1\},\Rel)$ are in one-to-one correspondence with coverings of
$[1,k]$. In this correspondence, a monomer $m_i$ corresponds to the
monomino labelled $i$ and a dimer $d_i$ corresponds to the
domino with labels $i-1,i$. Then, again by Lemma~\ref{L3.2}, we have
\begin{equation} 
\label{e3.42}
\sum _{T\in \mathcal T(\Bau\backslash\mathcal \{m_0,d_1\},\Rel)} 
^{}(-1)^{\v{T}}w(T)=x^{k}p_{k}(1/x)\Big\vert_{\begin{smallmatrix}
b_i\to b_{i+1}\\\la_i\to\la_{i+1}\end{smallmatrix}}=Sp^*_{k}(x).
\end{equation}
This establishes \eqref{e3.39}.
\end{proof}

This theorem can be generalized to Motzkin paths with {\em arbitrary}
starting and end points. The corresponding result is in the folklore of
combinatorics, probability, and statistics. However, the only explicit mention
that we are able to provide is \cite[Ch.~V, (27)]{VienAE}, which is a volume
that is not easily accessible. We provide two proofs. The first uses
the fact that Motzkin paths with bounded height can be seen as walks on
a linear graph (which, confusingly, in graph theory is called 
\index{path (the graph)}{\em path}). The second proof uses heaps, and
is taken from \cite{GarsAF}.

\begin{Theorem} \label{T3.11}
With the weight $w$ defined as before, the generating function for
\index{path, Motzkin}\index{Motzkin path}Motzkin paths running from 
height $r$ to height $s$
which stay below the line $y=k$, is given by
\begin{multline} \label{e3.43}
\sum _{n\ge0} ^{}\GF{\L{(0,r)\to(n,s);M\mid 0\le y\le k};w}x^n\\
=\cases \dfrac {x^{s-r}p^*_r(x)S^{s+1}p_{k-s}^*(x)} {p_{k+1}^*(x)}
&r\le s,\\
\la_r\cdots\la_{s+1}\dfrac {x^{r-s}p^*_s(x)S^{r+1}p_{k-r}^*(x)}
{p_{k+1}^*(x)}
&r\ge s.
\endcases
\end{multline}
\end{Theorem}
\begin{proof}[First proof]
Consider the directed graph, $P_{k+1}$ say, with vertices 
$v_0,v_1,\dots v_k$, where for $h=0,1,\dots, k-1$ there is an arc
from $v_h$ to $v_{h+1}$ as well as an arc from $v_{h+1}$ to $v_h$, 
and where there is a loop for each vertex $v_h$. 
Motzkin paths which never exceed height $k$ 
correspond in a one-to-one fashion to 
{\em walks} on $P_{k+1}$.
In this correspondence, an up-step from height $h$ to
$h+1$ in the Motzkin path corresponds to a step from vertex $v_h$ to
vertex $v_{h+1}$ in the walk, and similarly for level- and
down-steps. To make the correspondence also weight-preserving, we
attach a weight of $1$ to an arc from $v_h$ to $v_{h+1}$,
$h=0,1,\dots,k-1$, a weight of $\la_h$ to an arc from $v_{h+1}$ to
$v_h$, and a weight of $b_h$ to a loop at $v_h$.

It is ??well-known (see e.g\@. \cite[Theorem~4.7.2]{StanAP})
that the generating function for walks from $v_r$ to $v_s$ is given by 
$$\frac {(-1)^{r+s}\det(I-xA;s,r)} {\det(I-xA)},$$
where $A$ is the (weighted) {\it adjacency matrix} of $P_{k+1}$, where $I$
is the $(k+1)\times (k+1)$ identity matrix, and where $\det(I-xA;s,r)$
is the minor of $(I-xA)$ with the $s$-th row and $r$-th column
deleted. 

Now, the (weighted) adjacency matrix of $P_{k+1}$ with the property
that the weight of a particular walk would correspond to the weight $w$ of the
corresponding Motzkin path is the tridiagonal matrix
$$A=\pmatrix b_0&1&0&\dots\\
\la_1&b_1&1&0&\dots\\
0&\la_2&b_2&1&0&\dots\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\
&\dots&0&\la_{k-2}&b_{k-2}&1&0\\
&&\dots&0&\la_{k-1}&b_{k-1}&1\\
&&&\dots&0&\la_{k}&b_k\endpmatrix.$$
It is easily verified that, with this choice of $A$, we have
$\det(I-xA)=p_{k+1}^*(x)$ (by expanding the determinant 
with respect to the last row
and comparing with the three-term recurrence \eqref{eq:three-term}), 
and, similarly, that the numerator in \eqref{e3.43} agrees with  
$(-1)^{r+s}\det(I-xA;r,s)$.
\end{proof}

\begin{proof}[Second proof]
We treat the case $r\le s$, the other case being completely
analogous.

By considerations which are analogous to those which explain
\eqref{e3.41} and \eqref{e3.42}, it is seen that the right-hand
side of \eqref{e3.43} can be written as
$$\frac {\suml _{T\in \mathcal T(\Bau\backslash\mathcal
\{m_r,\dots,m_s,d_r,\dots,d_{s+1}\},\Rel)} 
^{}\kern-2cm(-1)^{\v{T}}w(T)}
{\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T)}.
$$
By the heap theorem (Corollary~\ref{C3.4}), this is the generating
function
$$\underset{\text {maximal pieces }\subseteq
\{m_r,\dots,m_s,d_r,\dots,d_{s+1}\}}
{\sum _{H\in \mathcal H(\Bau,\Rel)} ^{}}\kern-2cm w(H)
$$
for heaps the maximal pieces of which are contained in 
$\{m_r,\dots,m_s,d_r,\dots,d_{s+1}\}$. Hence, it suffices to
establish a weight-preserving bijection between these heaps and the
Motzkin paths in the statement of the theorem.

We describe such a bijection by starting with such a Motzkin path, a
Motzkin path $P$ running from height $r$ to height $s$
which stays below the line $y=k$, see Figure~\ref{F3.21}.a. We
decompose this path into many pieces. 

\begin{figure}
\begin{Figure} \label{F3.21}
$$
\Einheit.4cm
\PfadDicke{.25pt}
\Pfad(0,0),111111111111111111111111111111111111\endPfad
\Pfad(0,-1),22222222222\endPfad
\PfadDicke{.5pt}
\Pfad(0,3),131344444313131134331344133131334141\endPfad
\SPfad(0,3),111111111111111111111111111111111111\endSPfad
\SPfad(0,7),111111111111111111111111111111111111\endSPfad
\Pfad(0,9),111111111111111111111111111111111111\endPfad
\DickPunkt(0,3)
\Kreis(1,3)
\DuennPunkt(2,4)
\DuennPunkt(3,4)
\DuennPunkt(4,5)
\DuennPunkt(5,4)
\Kreis(6,3)
\DuennPunkt(7,2)
\DuennPunkt(8,1)
\DuennPunkt(9,0)
\DuennPunkt(10,1)
\DuennPunkt(11,1)
\DuennPunkt(12,2)
\DuennPunkt(13,2)
\Kreis(14,3)
\Kreis(15,3)
\Kreis(16,3)
\DuennPunkt(17,4)
\DickPunkt(18,3)
\DickPunkt(19,4)
\DuennPunkt(20,5)
\DuennPunkt(21,5)
\DuennPunkt(22,6)
\DuennPunkt(23,5)
\DuennPunkt(24,4)
\DickPunkt(25,4)
\DickPunkt(26,5)
\DickPunkt(27,6)
\DickPunkt(28,6)
\DickPunkt(29,7)
\DuennPunkt(30,7)
\DuennPunkt(31,8)
\DuennPunkt(32,9)
\DuennPunkt(33,8)
\DuennPunkt(34,8)
\DuennPunkt(35,7)
\DickPunkt(36,7)
\Label\l{0}(0,0)
\Label\l{r}(0,3)
\Label\l{s}(0,7)
\Label\l{k}(0,9)
\kern1.5pt
\Pfad(18,3),3\endPfad
\Pfad(25,4),3\endPfad
\Pfad(26,5),3\endPfad
\Pfad(28,6),3\endPfad
\hskip13cm
$$
\centerline{\small a. A Motzkin path from height $r$ to height $s$}
$$
\Pfad(0,-1),22222222222\endPfad
\SPfad(0,0),1111111111\endSPfad
\SPfad(0,1),1111111111\endSPfad
\SPfad(0,2),1111111111\endSPfad
\SPfad(0,3),1111111111\endSPfad
\SPfad(0,4),1111111111\endSPfad
\SPfad(0,5),1111111111\endSPfad
\SPfad(0,6),1111111111\endSPfad
\SPfad(0,7),1111111111\endSPfad
\SPfad(0,8),1111111111\endSPfad
\SPfad(0,9),1111111111\endSPfad
\Kreis(1,0)
\Kreis(1,1)
\Kreis(1,3)
\Kreis(1,4)
\Kreis(1,7)
\Kreis(1,8)
\Kreis(1,9)
\Kreis(2,1)
\Kreis(2,4)
\Kreis(2,5)
\Kreis(2,8)
\Kreis(3,1)
\Kreis(3,2)
\Kreis(3,3)
\Kreis(3,4)
\Kreis(3,5)
\Kreis(3,7)
\Kreis(3,8)
\Kreis(4,2)
\Kreis(4,5)
\Kreis(4,6)
\Kreis(4,7)
\Kreis(5,2)
\Kreis(5,3)
\Kreis(5,6)
\Kreis(6,3)
\Kreis(7,3)
\Kreis(8,3)
\Kreis(8,4)
\Kreis(9,4)
\Kreis(9,5)
\Pfad(1,0),2\endPfad
\Pfad(3,1),2\endPfad
\Pfad(2,4),2\endPfad
\Pfad(3,3),2\endPfad
\Pfad(1,8),2\endPfad
\Pfad(5,2),2\endPfad
\Pfad(4,5),2\endPfad
\Pfad(3,7),2\endPfad
\Pfad(8,3),2\endPfad
\Pfad(9,4),2\endPfad
\Label\l{0}(0,0)
\Label\l{r}(0,3)
\Label\l{s}(0,7)
\Label\l{k}(0,9)
\Label\r{H_r}(5,1)
\Label\r{H_{r+1}}(10,4)
\Label\r{H_{s-1}}(6,6)
\Label\r{H_s}(4,8)
\thinlines
\begin{picture}(10,10)
\unitlength.6cm
\put(1,9){\oval(1,1)[t]}
\put(1,7){\oval(1,1)[bl]}
\put(4,7){\oval(1,1)[r]}
\put(4,8){\oval(1,1)[bl]}
\put(3,8){\oval(1,1)[tr]}
\put(2,9){\oval(1,1)[bl]}
\put(1,6.5){\line(1,0)3}
\put(2,8.5){\line(1,0)1}
\put(.5,7){\line(0,1)2}
\put(5,6){\oval(1,1)}
\put(3,5){\oval(1,1)[l]}
\put(3,6){\oval(1,1)[br]}
\put(4,6){\oval(1,1)[t]}
\put(5,6){\oval(1,1)[bl]}
\put(9,5){\oval(1,1)[tr]}
\put(9,4){\oval(1,1)[b]}
\put(8,4){\oval(1,1)[tr]}
\put(5,5.5){\line(1,0)4}
\put(3,4.5){\line(1,0)5}
\put(9.5,4){\line(0,1)1}
\put(1,0){\oval(1,1)[b]}
\put(1,4){\oval(1,1)[tl]}
\put(1,5){\oval(1,1)[br]}
\put(2,5){\oval(1,1)[t]}
\put(8,3){\oval(1,1)[br]}
\put(6,2){\oval(1,1)[tl]}
\put(5,2){\oval(1,1)[br]}
\put(4,1){\oval(1,1)[tl]}
\put(3,1){\oval(1,1)[br]}
\put(2,0){\oval(1,1)[tl]}
\put(.5,0){\line(0,1)4}
\put(8.5,3){\line(0,1)1}
\put(6,2.5){\line(1,0)2}
\put(4,1.5){\line(1,0)1}
\put(2,0.5){\line(1,0)1}
%
\put(1,0){\oval(.7,.7)[b]}
\put(1,4){\oval(.7,.7)[l]}
\put(1,5){\oval(1.3,1.3)[br]}
\put(2,5){\oval(.7,.7)[t]}
\put(8,3){\oval(.7,.7)[br]}
\put(5,2){\oval(.7,.7)[br]}
\put(4,1){\oval(1.3,1.3)[tl]}
\put(3,1){\oval(.7,.7)[br]}
\put(2,0){\oval(1.3,1.3)[tl]}
\put(.65,0){\line(0,1)1}
\put(1,1){\oval(.7,.7)[tl]}
\put(2,2){\oval(1.3,1.3)[br]}
\put(3,2){\oval(.7,.7)[tl]}
\put(3,2.35){\line(1,0)1}
\put(4,3){\oval(1.3,1.3)[br]}
\put(5,3){\oval(.7,.7)[t]}
\put(5.35,2){\line(0,1)1}
\put(2,.65){\line(1,0)1}
\put(1,1.35){\line(1,0)1}
\put(1,3){\oval(.7,.7)}
\put(6,3){\oval(.7,.7)}
\put(7,3){\oval(.7,.7)}
\put(8,3){\oval(.7,.7)[b]}
\put(8,4){\oval(.7,.7)[t]}
\put(7.65,3){\line(0,1)1}
\put(8.35,3){\line(0,1)1}
\put(3,4){\oval(.7,.7)[tr]}
\put(3,3){\oval(.7,.7)[b]}
\put(2,3){\oval(1.3,1.3)[tr]}
\put(3,5){\oval(1.3,1.3)[bl]}
\put(3.35,3){\line(0,1)1}
\put(1,3.65){\line(1,0)1}
\put(4,1.65){\line(1,0)1}
\end{picture}
\hskip5cm
$$
\centerline{\small b. The corresponding heap of monomers and dimers}
\end{Figure}
\end{figure}

The basic decomposition of $P$ has the form
\begin{equation} \label{e3.44}
P=P_ruP_{r+1}u\dots uP_s,
\end{equation}
where $P_r$ is the initial portion of $P$
until the last point at height $r$, where for
$i=r+1,\dots,s$ the path portion $P_i$ is a 
path starting and terminating at height $r$ which never passes below 
height $r$ (and never beyond height $k$, of course), and where $u$
denotes an up-step. Any of the portions $P_i$ can be paths of length
$0$.
In Figure~\ref{F3.21}.a, this decomposition is
indicated by the thick dots, the up-steps which appear in the decomposition
\eqref{e3.44} also appearing in boldface. 

The first path, $P_r$, is further decomposed into the portions which
start and end at height $r$ but do not return to height $r$ in
between. In Figure~\ref{F3.21}, this decomposition is indicated by
circles. 

Now each of the subportions of $P_r$, and the paths $P_i$,
$i=r+1,\dots,s$, are converted into heaps of monomers and dimers,
which are finally put on top of each other. A subportion of $P_r$
which stays above height $r$ is converted into a pyramid with maximal
piece $m_r$ or $d_{r+1}$ (and the other pieces from
$\{m_r,m_{r+1},\dots,m_k,d_{r+1},d_{r+2},\dots,d_k\}$) 
in the same manner as in the proof of
Theorem~\ref{T3.10} (cf\@. Figure~\ref{F3.20}). A subportion of $P_r$
which stays below height $r$ is treated slightly differently. It is
converted into a pyramid with maximal
piece $m_r$ or $d_{r}$ (and the other pieces from
$\{m_0,m_{1},\dots,m_{r-1},d_{1},d_{2},\dots,d_r\}$)
by modifying this correspondence in the proof
of Theorem~\ref{T3.10} by making every {\em up-step} from height $h-1$ to
height $h$ into a dimer whose end points have
$x$-coordinates $h-1$ and $h$, and ignoring down-steps instead.
Finally, each of the resulting heaps is put on top of the preceding
one. As a result, the initial portion $P_r$ is translated into a
pyramid with maximal piece from $\{m_r,d_r,d_{r+1}\}$, and the other
pieces from $\{m_0,\dots,m_k,d_1,\dots,d_k\}$. See
Figure~\ref{F3.21}.b for the pyramid $H_r$ resulting from $P_r$.

The portion $P_i$, $i=r+1,\dots,s$, is now converted to a pyramid
with maximal piece $m_i$ or $m_{i+1}$ (and the other pieces from
$\{m_i,m_{i+1},\dots,m_k,d_{i+1},d_{i+2},\dots,d_k\}$) by the map
that was used in the proof of Theorem~\ref{T3.10} (cf\@. again
Figure~\ref{F3.20}). Finally the pyramid resulting from $P_{r+1}$,
denoted by $H_{r+1}$, is put on $H_r$, etc.
See Figure~\ref{F3.21}.b for the heap which results from the Motzkin
path in Figure~\ref{F3.21}.b.

It is rather straightforward to see that this map is
weight-preserving and that it is indeed a bijection. Thus, the
theorem is established.
\end{proof}

\section{$T$-fractions??}
\label{s3.7}
Roblet and Viennot??

\section{Motzkin paths and permutations}
\label{s3.8}
??Fran\c con and Viennot, Foata--Zeilberger, Zeng, Randrianarivony

\section{Motzkin paths and partitions}
\label{s3.9}
??Flajolet's partition bijection, ??Biane

%\end{document}
