\documentclass[12pt,reqno]{amsart}
\input sekrl.tex
\input pathlate.sty

\textwidth15.6cm
\textheight22.8cm
\hoffset-2truecm
\voffset-.5truecm

\numberwithin{equation}{section}


\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Satz}[Theorem]{Satz}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Korollar}[Theorem]{Korollar}

\theoremstyle{definition}

\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Beispiel}[Theorem]{Beispiel}

\theoremstyle{remark}

\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Remarks}[Theorem]{Remarks}
\newtheorem{Note}[Theorem]{Note}
\newtheorem{Bemerkung}[Theorem]{Bemerkung}


\newcounter{Figure}
\newenvironment{Figure}%
    {\refstepcounter{Figurenum}%
         \vskip10pt minus 5pt
\vbox\bgroup\hsize\textwidth\begin{center}}%
    {\vskip6pt\centerline{\hfil\small Figure~%
         \arabic{Figurenum}\hfil}\end{center}\egroup\vskip10pt minus 5pt}
\newcounter{Figurenum}

\def\Bau{\mathcal B}
\def\Rel{\mathcal R}
\def\Mo{\operatorname{\it M\!o}}
\def\Monomer{\mathcal M}
\def\Dimer{\mathcal D}
\let\hacek\v
\def\v#1{\left\vert #1\right\vert}


\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc C.~Krattenthaler}
\vskip18pt
\centerline{Fakult\"at f\"ur Mathematik, Universit\"at Wien,}
\centerline{Nordbergstra\3e 15, A-1090 Vienna, Austria.}
\centerline{\footnotesize WWW: \footnotesize\tt http://www.mat.univie.ac.at/\~{}kratt}
}

\title{The theory of heaps and the Cartier--Foata monoid}

\author[C.~Krattenthaler]{\box\Adr}


\address{Fakult\"at f\"ur Mathematik, Universit\"at Wien,
Nordbergstrasze 15, A-1090 Vienna, Austria.
WWW: \tt http://www.mat.univie.ac.at/\~{}kratt}

\begin{abstract}
We present Viennot's theory of heaps of pieces, show that heaps are
equivalent to elements in
the partially commutative monoid of Cartier and
Foata, and illustrate the main results of the theory by reproducing
its application to the enumeration of parallelogram polyominoes due
to Bousquet--M\'elou and Viennot.
\end{abstract}

\maketitle

\section{Introduction} \label{sec:Intro}
The purpose of this note is to present an alternative, geometric 
point of view of the {\it``mono\"\i de partiellement commutatif"} of
Cartier and Foata \cite{CaFoAA}, now known as the {\it
Cartier--Foata monoid}. This alternative point of view is due to
Viennot \cite{VienAF}, who
introduced a combinatorial theory which he
coined the theory of ``{\em heaps of pieces}." 
While theoretically completely equivalent to the theory of Cartier
and Foata, its main feature is the
visualisation of elements of the monoid in terms of so-called
``heaps," which makes it very versatile in combinatorial
applications. 

We explain the basic set-up in the next section, and, in
Section~\ref{sec:CF}, why this is
equivalent to the monoid of Cartier and Foata. 
The two main theorems (generalising results from \cite{CaFoAA}) are
stated and proved in Section~\ref{sec:main}, while a beautiful application
to parallelogram polyominoes, due to Bousquet--M\'elou and Viennot
\cite{BoViAA}, is recalled in Section~\ref{sec:appl}.
Other applications include applications to animals, polyominoes,
Motzkin paths and orthogonal polynomials, Rogers--Ramanujan
identities, Lyndon words, fully commutative elements in Coxeter groups, 
Bessel functions, and Lorentzian quantum gravity, see
\cite{BousAZ,BousBZ,BoReAA,BoViAA,CoDGAA,FedoAA,FedoAB,%
DiGuAA,GarsAF,GreRAD,GreRAE,GreRAF,GreRAG,%
LaloAA,StemAS,StemAT,VienAF,VienAZ,ViJaAA}. 
The reader is also referred to 
the survey \cite{BePeAA}.

\section{Heaps of pieces}
\label{sec:heaps}

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 on top of the other,
sometimes also sideways, to form a ``heap," see Figure~\ref{F3.14}.


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 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.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}

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 two 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 {\em
partially ordered set\/} or {\em poset}. 

\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}

\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 {\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. That is, 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 realisation of) a heap, either $x$ must be above $y$, symbolised
by $y\preceq x$, or $x$ must be below $y$, symbolised 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,\break 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\Rel b_i$) 
\begin{equation} \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{equation}
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}. 

A class of heaps which is of great importance for studying 
animals, polyominoes, Motzkin
paths and orthogonal polynomials (cf.\
\cite{BePeAA,BousAZ,BousBZ,BoReAA,DiGuAA,GarsAF,ViJaAA}), 
is the class of heaps of 
\index{monomer}{\em monomers} and \index{dimer}{\em dimers}, which we
now introduce. (A more general class of heaps will be relevant in our
sample application in Section~\ref{sec:appl}.)

\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}

\begin{Example}\label{Emondim}
Let $\Bau=M\cup D$, where $\Monomer=\{m_0,m_1,\dots\}$ is the set of
monomers and $\Dimer=\{d_1,d_2,\dots\}$ is the set of
dimers. We think of a monomer $m_i$ as a point, symbolised by a
circle, with $x$-coordinate $i$, see Figure~\ref{F3.16}.
We think of a dimer $d_i$ as two points, symbolised by 
circles, with $x$-coordinates $i-1$ and $i$ which are connected by an edge, 
see Figure~\ref{F3.16}.

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 {\em monoid} by introducing a
{\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$.

\section{Equivalence with the Cartier--Foata monoid}
\label{sec:CF}

The monoid which we have just defined in the previous section 
can be seen to be equivalent to the
Cartier--Foata monoid \cite{CaFoAA}. In order to explain this
equivalence, we first
observe that heaps could also be encoded by {\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 {\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 $x\hbox{$\not\kern-4pt\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$. 
Under this correspondence, the composition of heaps corresponds
exactly to the composition of equivalence classes of words induced
by concatenation of words. The equivalence of the heap monoid and the
Cartier--Foata monoid is now obvious.

\section{The main theorems}
\label{sec:main}

For the statement of the main theorems in the theory of heaps, we need
two more terms. A {\em
trivial heap} is a heap consisting of pieces all of which are
pairwise unrelated, i.e., $x\hbox{$\not\kern-4pt\Rel$}y$ for all pieces $x,y$
in $H$. Figure~\ref{F3.19}.a shows a trivial heap consisting of
monomers and dimers. 
A {\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}

The following theorem is Proposition~5.3 from \cite{VienAF}.

\begin{Theorem} \label{T3.9}
Let $\mathcal M$ be a subset of the pieces $\Bau$. Then, in the
monoid $\mathcal H(\Bau,\Rel)$, 
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 {\em 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{Remark} Equation~\eqref{e3.34} generalises 
Eq.~(1) from \cite[Introduction, Part~A]{CaFoAA}, the
latter being equivalent to \eqref{e3.35}. 
\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 changes 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}

The second main theorem, Proposition~5.10 from \cite{VienAF}, 
concerns the set of pyramids in $\mathcal
H(\Bau,\Rel)$, which, for convenience, we denote by $\mathcal
P(\Bau,\Rel)$. 
In contrast to Theorem~\ref{T3.9}, in the result we
must give up non-commutativity. 

\begin{Theorem} \label{T3.9a}
For the following (formal) sum indexed by pyramids in $\mathcal
H(\Bau,\Rel)$, we have
\begin{equation} \label{e3.34a}
{\sum _{P\in\mathcal P(\Bau,\Rel)} ^{}}\kern-0pt 
\frac {1} {\v{P}}P=_{\text
{comm}}\
-\log\bigg(\suml _{T\in \mathcal T(\Bau,\Rel)}
^{}(-1)^{\v{T}}T\bigg),
\end{equation}
where $=_{\text {comm}}$ means that the identity holds in the
commutative extension of $\mathcal H(\Bau,\Rel)$, that is, in the
commutative
monoid which arises from $\mathcal H(\Bau,\Rel)$ by letting all
pieces in $\Bau$ commute.
\end{Theorem}


\begin{proof} We make heaps into {\it labelled} objects.
More precisely, a {\it labelled heap} is a heap from $\mathcal H(\Bau,\Rel)$
with $N$ pieces which are arbitrarily labelled from $1$ up to $N$
(with each label between $1$ and $N$ appearing exactly once). 
Given a labelled heap $H_1$, we decompose it uniquely into labelled
pyramids as follows. 
To begin with, we ``push" the piece labelled $1$ ``downwards."
Let this piece be $b_1$.
(In the language of words, we would push $b_1$ to the left, using
partial commutativity of letters.)
Since some pieces cannot move past others, thereby we will take
several pieces with us. In fact, these will form a pyramid $P_1$ with
maximal piece $b_1$. Let $H_2$ be what remains from $H_1$ after
removing $P_1$. We now repeat the same procedure with the piece $b_2$
which has the minimal label within all pieces of $H_2$. Etc. In the end, we will
have obtained a set of labelled pyramids with the special property
that in each pyramid the label of its maximal element is the smallest
of all labels of pieces of the pyramid. 

Let $\tilde{\mathcal H}(\Bau,\Rel)$ denote the set of all labelled
heaps, and let
$\tilde{\mathcal P}(\Bau,\Rel)$ denote the set of all labelled
pyramids in $\tilde{\mathcal H}(\Bau,\Rel)$ with the above special
property. Then, by the exponential
principle for labelled combinatorial objects (cf.\ 
\cite[Eqs.~(20), (70)]{BeLLAA},
\cite[Sec.~II.2.1]{FlSeAA}, or \cite[Cor.~5.1.6]{StanBI}), 
we have immediately
$$
{\sum _{H\in\tilde{\mathcal H}(\Bau,\Rel)} ^{}}\kern-0pt 
\frac {1} {\v{H}!}H=_{\text
{comm}}\
\exp\left({\sum _{P\in\tilde{\mathcal P}(\Bau,\Rel)} ^{}}\kern-0pt 
\frac {1} {\v{P}!}P\right).
$$
However, for any (unlabelled) heap in $\mathcal H(\Bau,\Rel)$ with $N$
pieces there are exactly $N!$ ways to label the pieces to obtain a
labelled heap in $\tilde{\mathcal H}(\Bau,\Rel)$, while for any
(unlabelled) pyramid from $\mathcal H(\Bau,\Rel)$ with $N$ pieces there a
exactly $(N-1)!$ ways to label the pieces to obtain a labelled
pyramid in $\tilde{\mathcal P}(\Bau,\Rel)$. (The reader should recall
that the maximal element of the pyramid must get the smallest label.)
Hence,
$$
{\sum _{H\in{\mathcal H}(\Bau,\Rel)} ^{}}\kern-0pt 
H=_{\text
{comm}}\
\exp\left({\sum _{P\in{\mathcal P}(\Bau,\Rel)} ^{}}\kern-0pt 
\frac {1} {\v{P}}P\right),
$$
which, in view of \eqref{e3.35}, is equivalent to \eqref{e3.34a}.
\end{proof}

In applications, heaps will have weights, which are defined by
introducing a weight $w(b)$ (being an element in some commutative
ring with unit element) 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$. Theorems~\ref{T3.9}
and \ref{T3.9a}
immediately imply 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 {\em 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 is 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}
Furthermore,
\begin{equation} \label{e3.38a}
{\sum _{P\in\mathcal P(\Bau,\Rel)} ^{}}\kern-0pt 
\frac {1} {\v{P}}w(P)=
-\log\bigg(\suml _{T\in \mathcal T(\Bau,\Rel)}
^{}(-1)^{\v{T}}w(T)\bigg),
\end{equation}
where again $\mathcal P(\Bau,\Rel)$ denotes the set of all pyramids
in $\mathcal H(\Bau,\Rel)$.
\end{Corollary}

\section{A sample application}
\label{sec:appl}

As an illustration, we show how to use the results from 
Section~\ref{sec:main} in order to obtain a formula for 
a multivariate generating function for {\it parallelogram
polyominoes}. This beautiful application of heaps is due to
Bousquet--M\'elou and Viennot \cite{BoViAA}.

A parallelogram polyomino is a non-empty set of square cells in the plane 
without holes which are enclosed by two paths consisting of 
unit horizontal and vertical steps in the positive direction, both of
which starting in the same point and ending in the same point.
An example is shown in Figure~\ref{F1}.

\begin{Figure}\label{F1}
$$
\Einheit.7cm
\Pfad(0,0),112112122211122\endPfad
\Pfad(0,0),222121121212111\endPfad
\Pfad(0,1),11\endPfad
\Pfad(0,2),11111\endPfad
\Pfad(0,3),11111\endPfad
\Pfad(1,4),1111\endPfad
\Pfad(3,5),11\endPfad
\Pfad(4,6),1111\endPfad
\Pfad(1,0),2222\endPfad
\Pfad(2,1),222\endPfad
\Pfad(3,1),2222\endPfad
\Pfad(4,1),2222\endPfad
\Pfad(5,2),2222\endPfad
\Pfad(6,5),22\endPfad
\Pfad(7,5),22\endPfad
\hskip4cm
$$
\centerline{\small A parallogram polyomino}
\end{Figure}

The {\it area\/} $a(P)$ of a parallelogram polyomino $P$ is the
number of cells of $P$. 
The {\it width\/} $b(P)$ of a parallelogram polyomino $P$ is the
number of columns of cells of $P$. 
The {\it height\/} $h(P)$ of a parallelogram polyomino $P$ is the
number of rows of cells of $P$. 
For our parallogram polyomino in Figure~\ref{F1}, $P_0$ say, 
we have $a(P_0)=24$, $b(P_0)=8$, and $h(P_0)=7$.

We would like to compute the generating function
$$
\sum _{P} ^{}x^{b(P)}y^{h(P)}q^{a(P)},$$
summed over all parallogram polyominoes $P$. In order to do so, we
show that the latter are in bijection with heaps, the pieces of which
are segments of the form $[a,c]$, $1\le a\le c$, with the ``obvious"
commutation relations: two segments $[a_1,c_1]$ and $[a_2,c_2]$
commute if and only if one segment ``is to the left of the other," that is,
if $c_1<a_2$ or if $c_2<a_1$. See Figure~\ref{F2} for an example of a
heap formed out of pieces of that form. (More precisely, the
segments in this figure are $S_1=[1,3]$,
$S_2=[3,4]$,
$S_3=[3,3]$,
$S_4=[3,4]$,
$S_5=[3,4]$,
$S_6=[1,2]$,
$S_7=[2,2]$,
$S_8=[2,2]$.)

\begin{Figure} \label{F2}
$$
\Einheit.5cm
\Pfad(-2,0),111111111111111111\endPfad
\SPfad(0,0),222222\endPfad
\SPfad(2,0),222222\endPfad
\SPfad(4,0),222222\endSPfad
\SPfad(6,0),222222\endSPfad
\SPfad(8,0),222222\endSPfad
\SPfad(10,0),222222\endSPfad
\SPfad(12,0),222222\endSPfad
\SPfad(14,0),222222\endSPfad
\Kreis(0,3)
\Kreis(2,3)
\Kreis(2,1)
\Kreis(2,2)
\Kreis(4,1)
\Kreis(6,1)
\Kreis(4,2)
\Kreis(6,2)
\Kreis(4,3)
\Kreis(4,4)
\Kreis(6,4)
\Kreis(4,5)
\Kreis(0,5)
\Pfad(4,1),11\endPfad
\Pfad(4,2),11\endPfad
\Pfad(4,4),11\endPfad
\Pfad(0,3),11\endPfad
\Pfad(0,5),1111\endPfad
\Label\l{S_8}(2,1)
\Label\r{S_5}(6,1)
\Label\l{S_7}(2,2)
\Label\l{S_6}(0,3)
\Label\r{S_4}(6,2)
\Label\r{S_3}(4,3)
\Label\r{S_2}(6,4)
\Label\o{S_1}(2,5)
\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)
\hskip7cm
$$
\vskip8pt
\centerline{\small A heap of segments}
\end{Figure}

Given a parallelogram polyomino $P$ consisting of $n$ columns, 
we obtain a heap of segments in
the following way: Let $(c_1,c_2,\dots,c_n)$ be the sequence of column
lengths of $P$ (considering the columns from left to right). In our
example in Figure~\ref{F1}, these are $(3,4,3,4,4,2,2,2)$.
Furthermore, define $(a_1,a_2,\dots,a_n)$ to be the sequence with
$a_1=1$ and, for $i>1$, $a_i$ being equal to the length of the 
segment along which the $(i-1)$-st and the $i$-th column of $P$
touch each other. In our
example in Figure~\ref{F1}, these are $(1,3,3,3,3,1,2,2)$.
Now form the heap by piling the segments $[a_i,c_i]$,
$i=n,n-1,\dots,1$, on each other, that is, we form the heap
$$[a_n,c_n]\circ[a_{n-1},c_{n-1}]\circ\dots\circ[a_1,c_1].$$
It can be checked that the heap in Figure~\ref{F2} corresponds to the
parallelogram polyomino in Figure~\ref{F1} under this
correspondence. 

It can be shown that this correspondence is, in fact, a bijection
between parallelogram polyominoes $P$ and heaps of segments $H$
with a maximal piece of the form $[1,c]$. 
Moreover, under this correspondence,

\begin{enumerate} 
\item $b(P)$ is the number of pieces of $H$;
\item $h(P)$ is one more than the sum of all the lengths of pieces of
$H$; 
\item $a(P)$ is the sum of the right abscissae of the pieces of $H$
(i.e., the sum of the $c_i$'s).
\end{enumerate}

For details, we refer the reader to \cite{BoViAA}.

Now we apply Corollary~\ref{C3.4} with $\mathcal H(\Bau,\Rel)$
being our heaps of segments, $\mathcal M$ being the set 
of all pieces of the form $[1,c]$, and with the weight $w$
being defined as
$$w(H)=x^{\vert H\vert}y^{\sum(\text{lengths of pieces of
$H$)}}
q^{\sum(\text{right abscissae of pieces of $H$)}}.$$ 
In order to do so, first of all, we must compute the sum
$$\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T).$$
Now, a trivial heap consisting of $n$ pieces has the form
$$[a_1,c_1]\circ[a_2,c_2]\circ\dots\circ[a_n,c_n],$$
where $1\le a_1\le c_1<a_2\le c_2<\dots<a_n\le c_n$.
Therefore,
$$\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T)=
\sum _{n=0} ^{\infty}(-1)^n x^n
\sum _{1\le a_1\le c_1<a_2\le c_2<\dots<a_n\le c_n} ^{}
y^{\sum _{i=1} ^{n}(c_i-a_i)}
q^{\sum _{i=1} ^{n}c_i}.
$$
Now the sums over $c_n,a_n,c_{n-1},a_{n-1},\dots,c_1,a_1$ can
be evaluated, in this order, all of them being geometric sums.
The result is
$$
\suml _{T\in \mathcal T(\Bau,\Rel)} ^{}(-1)^{\v{T}}w(T)=
\sum _{n=0} ^{\infty}\frac {(-1)^nx^{n}q^{\binom{n+1}2}} 
{(q;q)_n\,(yq;q)_{n}},$$
where
$(\alpha;q)_k$ is the {\em $q$-shifted factorial\/}, given by 
$(\alpha;q)_0:=1$ and
$$(\alpha;q)_k:=(1-\alpha)(1-\alpha q)\cdots(1-\alpha q^{k-1})$$ 
if $k$ is a positive integer. Similary, we obtain
$${\sum _{T}}{}^{\displaystyle\prime} 
(-1)^{\v{T}}w(T)=
-\sum _{n=0} ^{\infty}\frac {(-1)^nx^{n+1}q^{\binom{n+2}2}} 
{(q;q)_n\,(yq;q)_{n+1}},$$
the sum being over all trivial heaps $T$ in $\mathcal T(\Bau,\Rel)$
containing {\it at least one} piece from $\mathcal M$.
Hence, remembering that parallelogram
polyominoes are {\it non-empty} sets of cells, we infer that
\begin{align} \notag
\sum _{P} ^{}x^{b(P)}y^{h(P)}q^{a(P)}&=
y\left(\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)}
-1\right)\\
\label{eq:para} 
&=
y
\frac {\displaystyle\sum _{n=0} ^{\infty}\frac {(-1)^nx^{n+1}q^{\binom{n+2}2}} 
{(q;q)_n\,(yq;q)_{n+1}}} 
{\displaystyle\sum _{n=0} ^{\infty}\frac {(-1)^nx^{n}q^{\binom{n+1}2}} 
{(q;q)_n\,(yq;q)_{n}}},
\end{align}
the sum over $P$ being over all parallogram polyominoes $P$.

\begin{thebibliography}{10}

\bibitem{BeLLAA}
F. Bergeron, G. Labelle and P. Leroux, {\em Combinatorial species and
tree-like structures}, Cambridge University Press, Cambridge, 1998.

\bibitem{BePeAA}
J. B\'etr\'ema and J. G. Penaud, {\em Mod\`eles avec particules 
dures, animaux dirig\'es et s\'eries en variables partiellement 
commutatives},
manuscript, {\tt ar$\chi$iv:math.CO/0106210}.

\bibitem{BousAZ}
M. Bousquet--M\'elou, {\em $q$-\'Enum\'eration de polyominos convexes},
J. Combin.\ Theory Ser.~A {\bf 64} (1993), 265--288.

\bibitem{BousBZ}
M. Bousquet--M\'elou, {\em Polyominoes and polygons}, in: 
Jerusalem Combinatorics '93, pp.~55--70, 
Contemp.\ Math., 178, Amer. Math. Soc., Providence, RI, 1994.

\bibitem{BoReAA}
M.    Bousquet--M\'elou and A. Rechnitzer, {\em Animals and 
heaps of dimers}, Discrete Math.\ {\bf 258} (2002), 235--274.

\bibitem{BoViAA}
M.    Bousquet--M\'elou and X. Viennot, {\em Empilements de segments et 
$q$-\'enum\'eration de polyominos convexes dirig\'es},
J. Combin.\ Theory Ser.~A {\bf 60} (1992), 196--224.

\bibitem{CaFoAA}
P. Cartier and D. Foata,
{\em Probl\`emes combinatoires de commutation et r\'earrangements}, 
Lecture Notes in Mathematics, No.~85,
Springer--Verlag, Berlin, New York, 1969;
republished in the ``books" section of the S\'eminaire
Lotharingien de Combinatoire.

\bibitem{CoDGAA}
S. Corteel, A. Denise and D. Gouyou-Beauchamps, {\em Bijections for
directed animals on infinite families of lattices},
Ann.\ Comb.\ {\bf 4} (2000), 269--284.

\bibitem{FedoAA}
J.-M. F\'edou, {\em Sur les fonctions de Bessel}, Discrete Math.\ 
{\bf 139} (1995), 473--480.

\bibitem{FedoAB}
J.-M. F\'edou, {\em Combinatorial objects enumerated by $q$-Bessel 
functions}, Rep.\ Math.\ Phys.\ {\bf 34} (1994), 57--70.

\bibitem{FlSeAA}
P.    Flajolet and R. Sedgewick,
{\em Analytic Combinatorics},
book project, available at {\tt 
http://algo.inria.fr/flajolet/Publications/books.html}.

\bibitem{DiGuAA}
P. Di Francesco and E. Guitter, {\em Integrability of graph combinatorics 
via random walks and heaps of dimers}, 
J. Stat.\ Mech.\ Theory Exp.\ 2005,  no. 9, P09001, 34 pp.

\bibitem{GarsAF}
A. M. Garsia, {\em Heaps, continued fractions and orthogonal
polynomials}, Lecture Notes for a course given at the University of
California at San Diego, 1993.

\bibitem{GreRAD}
R. M. Green, {\em Acyclic heaps of pieces, I}, J. Algebraic Combin.\
{\bf 19} (2004), 173--196.

\bibitem{GreRAE}
R. M. Green, {\em Acyclic heaps of pieces, II}, Glasgow Math.\ J. 
{\bf 46} (2004), 459--476.

\bibitem{GreRAF}
R. M. Green, {\em On rank functions for heaps}, 
J. Combin.\ Theory Ser.~A {\bf 102} (2003), 411--424. 

\bibitem{GreRAG}
R. M. Green, {\em Full heaps and representations of affine Kac--Moody algebras}, 
preprint, {\tt ar$\chi$iv:math.CO/0605768}.

\bibitem{LaloAA}
P. Lalonde, {\em Lyndon heaps: an analogue of Lyndon words in 
free partially commutative monoids}, Discrete Math.\ {\bf 145} 
(1995), 171--189.

\bibitem{StanBI} R.~P.~Stanley, 
{\em Enumerative Combinatorics}, vol.~2,
Cambridge University Press, Cambridge, 1999. 

\bibitem{StemAS}
J. R. Stembridge, {\em On the fully commutative elements of Coxeter groups}, J. Alg.\ Combin.\ {\bf 5} (1996), 353--385.

\bibitem{StemAT}
J. R. Stembridge, {\em Minuscule elements of Weyl groups},
J. Algebra {\bf 235} (2001), 722--743.

\bibitem{VienAF}
X. G. Viennot,
{\em Heaps of pieces. I. Basic definitions and combinatorial lemmas},
Lecture Notes in Math., 1234, Springer, Berlin, 1986, pp.~ 321--350.

\bibitem{VienAZ}
X. G. Viennot, {\em Bijections for the Rogers-Ramanujan reciprocal},
J. Indian Math.\ Soc.\ (N.S.) {\bf 52} (1987), 171--183.

\bibitem{ViJaAA}
X. Viennot and W. James,
{\em Heaps of segments, $q$-Bessel functions in square lattice
enumeration and applications in quantum gravity},  
preprint.

\end{thebibliography}



\end{document}


