\documentclass[12pt,reqno]{amsart} \textwidth15.6cm \textheight22.8cm \hoffset-2truecm \voffset-.5truecm \font\Page=cmbx12 \addtocounter{page}{62} \def\thepage{\Page\arabic{page}} \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\al{\alpha} \def\be{\beta} \def\ga{\gamma} \def\de{\delta} \def\ep{\varepsilon} \def\ze{\zeta} \def\et{\eta} \def\th{\theta} \def\vt{\vartheta} \def\io{\iota} \def\ka{\kappa} \def\la{\lambda} \def\rh{\rho} \def\si{\sigma} \def\ta{\tau} \def\ph{\varphi} \def\ch{\chi} \def\ps{\psi} \def\om{\omega} \def\Ga{\Gamma} \def\De{\Delta} \def\Th{\Theta} \def\La{\Lambda} \def\Si{\Sigma} \def\Ph{\Phi} \def\Ps{\Psi} \def\Om{\Omega} \def\P{{\mathbb P}} \def\R{{\mathbb R}} \def\X{{\Cal X}} \def\C{{\mathbb C}} \def\Mf{{\Cal Mf}} \def\FM{{\Cal F\Cal M}} \def\F{{\Cal F}} \def\G{{\Cal G}} \def\V{{\Cal V}} \def\T{{\Cal T}} \def\A{{\Cal A}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\Q{{\mathbb Q}} \def\ddt{\left.\tfrac \partial{\partial t}\right\vert_0} \def\dd#1{\tfrac \partial{\partial #1}} \def\today{\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\day, \number\year} \def\nmb#1#2{#2} %zum Nummerieren \def\iprod#1#2{\langle#1,#2\rangle} \def\pder#1#2{\frac{\partial #1}{\partial #2}} \def\iint{\int\!\!\int} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\supp{\operatorname{supp}} \def\Df{\operatorname{Df}} \def\dom{\operatorname{dom}} \def\Ker{\operatorname{Ker}} \def\Tr{\operatorname{Tr}} \def\Res{\operatorname{Res}} \def\Aut{\operatorname{Aut}} \def\kgV{\operatorname{kgV}} \def\ggT{\operatorname{ggT}} \def\diam{\operatorname{diam}} \def\Im{\operatorname{Im}} \def\Re{\operatorname{Re}} \def\ord{\operatorname{ord}} \def\rang{\operatorname{rang}} \def\rng{\operatorname{rng}} \def\grd{\operatorname{grd}} \def\inv{\operatorname{inv}} \def\maj{\operatorname{maj}} \def\des{\operatorname{des}} \def\varmaj{\operatorname{\overline{maj}}} \def\vardes{\operatorname{\overline{des}}} \def\pvarmaj{\operatorname{\overline{maj}'}} \def\pmaj{\operatorname{maj'}} \def\ln{\operatorname{ln}} \def\der{\operatorname{der}} \def\Hom{\operatorname{Hom}} \def\tr{\operatorname{tr}} \def\Span{\operatorname{Span}} \def\grad{\operatorname{grad}} \def\div{\operatorname{div}} \def\rot{\operatorname{rot}} \def\Sp{\operatorname{Sp}} \def\sgn{\operatorname{sgn}} \def\liml{\lim\limits} \def\supl{\sup\limits} \def\bigcupl{\bigcup\limits} \def\bigcapl{\bigcap\limits} \def\limsupl{\limsup\limits} \def\liminfl{\liminf\limits} \def\intl{\int\limits} \def\suml{\sum\limits} \def\maxl{\max\limits} \def\minl{\min\limits} \def\prodl{\prod\limits} \def\tg{\operatorname{tan}} \def\ctg{\operatorname{cot}} \def\arctg{\operatorname{arctan}} \def\arccot{\operatorname{arccot}} \def\arcctg{\operatorname{arccot}} \def\tgh{\operatorname{tanh}} \def\ctgh{\operatorname{coth}} \def\arcsinh{\operatorname{arcsinh}} \def\arccosh{\operatorname{arccosh}} \def\arctgh{\operatorname{arctanh}} \def\arcctgh{\operatorname{arccoth}} \def\3{\ss} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Input-Datei zum Erzeugen von Gitterpunktwegen.% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %LaTeX-Version% %%%%%%%%%%%%%%% %entering a path: % \Pfad(x-coordinate of starting point,y-coordinate of starting point),path % as 1-2-3-4-5-6-7-8-word\endPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step) %(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step) % %entering a dotted path: % \SPfad(x-coordinate of starting point,y-coordinate of starting point),path % as 1-2-3-4-5-6-7-8-word\endSPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step) %(5=step in negative x-direction, 6=step in negative y-direction, 7=downward left diagonal step, 8=upward left diagonal step) % %coordinate-axes: % \Koordinatenachsen(length of positive x-axes, length of positive y-axes)(length of negative x-axes, length of negative y-axes) %The length of negative axes are entered as negative numbers. % %lattice: % \Gitter(number of points in positive x-direction, number of points in positive y-direction)(number of points in negative x-direction, number of points in negative y-direction) % %diagonal lines: % \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes % %antidiagonal lines: % \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes % %labelling of points: % \Label[location?]{[label]}(x-coordinate,y-coordinate) %where: % [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u %and l=left, r=right, u=bottom, o=top. %In addition, if by \Einheit?cm the basic unit is changed, there exist %\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu. % %The basic unit can be changed by entering % \Einheit=?cm %The default is \Einheit=0.5cm. % %The thickness of the paths can be changed by entering % \PfadDicke{?cm} %The default is \PfadDicke=1pt. % %The following point sizes are available: %\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax: % \DickPunkt(x-coordinate,y-coordinate), etc. % %Besides, a circle is available by \Kreis. Syntax: % \Kreis(x-coordinate,y-coordinate) % \catcode`\@=11 \font\tenln = line10 \font\tenlnw = linew10 \thinlines \newskip\Einheit \Einheit=0.6cm \newcount\xcoord \newcount\ycoord \newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke \PfadD@cke1pt \Pfadd@cke0.5pt \def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2} \long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE} \def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next} \let\REPEAT=\fi \def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss\scriptsize$\bullet$\hss}}} \def\DuennPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-2.5pt\hbox to0pt{\hss\normalsize$\bullet$\hss}\hss}} \def\NormalPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}} \def\DickPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}} \def\Kreis(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}} \def\Diagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){#3}\hss}} \def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax %\advance\xcoord by -0.05\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){#3}\hss}} \def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines} \def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax \else\let\next\ZeichnePfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){1}\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){1}\hss} \advance\xcoord by 1 \advance\ycoord by -1 \else\ifnum#1=5 \advance\xcoord by -1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}% \else\ifnum#1=6 \advance\ycoord by -1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-\PfadD@cke\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}% \else\ifnum#1=7 \advance\xcoord by -1 \advance\ycoord by -1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){1}\hss} \else\ifnum#1=8 \advance\xcoord by -1 \advance\ycoord by +1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){1}\hss} \fi\fi\fi\fi \fi\fi\fi\fi \fi\next} \def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit} \def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt \hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}} \def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad} \def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax \else\let\next\ZeichneSPfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hSSchritt\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-2pt \vSSchritt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \DSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \dSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by -1 \else\ifnum#1=5 \advance\xcoord by -1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hSSchritt\hss}% \else\ifnum#1=6 \advance\ycoord by -1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-2pt \vSSchritt}\hss}% \else\ifnum#1=7 \advance\xcoord by -1 \advance\ycoord by -1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \DSSchritt\hss} \else\ifnum#1=8 \advance\xcoord by -1 \advance\ycoord by 1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \dSSchritt\hss} \fi\fi\fi\fi \fi\fi\fi\fi \fi\next} \def\Koordinatenachsen(#1,#2){\unskip \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}% \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Koordinatenachsen(#1,#2)(#3,#4){\unskip \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1 \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}% \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord0 \advance\ycoord by1 \REPEAT} \def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord#3 \advance\ycoord by1 \REPEAT} \def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}% \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}% \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}% \def\o{\advance\ydim by.25cm}% \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}% \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}% \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}% \def\l{\advance\xdim by-.30cm}% \def\r{\advance\xdim by.30cm}% \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}% \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}% \def\u{\advance\ydim by-.30cm}% \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}% \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}% #1\raise\ydim\hbox to0pt{\hskip\xdim \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}% } \catcode`\@=12 \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 \thispagestyle{empty} \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_11$, $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