THE THEORY OF HEAPS AND THE CARTIER–FOATA MONOID

C. Krattenthaler

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

                      WWW: http://www.mat.univie.ac.at/~kratt

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élou and Viennot.

1. Introduction

The purpose of this note is to present an alternative, geometric point of view of the “monoïde partiellement commutatif” of Cartier and Foata [7], now known as the Cartier–Foata monoid. This alternative point of view is due to Viennot [22], who introduced a combinatorial theory which he coined the theory of “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 3, why this is equivalent to the monoid of Cartier and Foata. The two main theorems (generalising results from [7]) are stated and proved in Section 4, while a beautiful application to parallelogram polyominoes, due to Bousquet–Mélou and Viennot [6], is recalled in Section 5. 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 [3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24]. The reader is also referred to the survey [2].

2. Heaps of pieces

Informally, a heap is what we would imagine. We take a collection of “pieces,” say b_{1}, b_{2}, …, and put them one on top of the other, sometimes also sideways, to form a “heap,” see Figure 1.

We imagine that pieces can only move vertically (so that the heap in Figure 1 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 1 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 1, 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).

[figure: b_{2}; b_{7}; b_{6}; b_{4}; b_{5}; b_{3}; b_{2}; b_{1}]

A heap of pieces

Figure 1

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 1 is shown in Figure 2. (There, we have labelled each vertex by the name of the corresponding piece.) Mathematically, a skeleton is a labelled partially ordered set or poset.

[figure: •; •; •; •; •; •; •; •; b_{2}; b_{4}; b_{5}; b_{3}; b_{2}; b_{1}; b_{7}; b_{6}]

The skeleton of the heap in Figure 1

Figure 2

Definition 2.1. A partially ordered set (poset) is a pair (P, ⪯), where P is a set, and where ⪯ is a binary relation defined on P which is

(1) reflexive, i.e., x ⪯ x for all x in P,

(2) antisymmetric, i.e., if x ⪯ y and y ⪯ x, then x = y for all x, y in P,

(3) transitive, i.e., if x ⪯ y and y ⪯ z then x ⪯ z for all x, y, z in P.

Posets are usually shown graphically in the form of 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 ⪯ y and there is no z different from x and y with x ⪯ z ⪯ y. Moreover, in the diagram, x is shown at a lower level than y. Clearly, the diagram in Figure 2 is the Hasse diagram of a poset, with vertices labelled by pieces.

Now we can rigorously define what a heap is.

Definition 2.2. Let B be a set (of pieces) with a symmetric and reflexive binary relation R. A heap is a triple (P, ⪯, ℓ), where (P, ⪯) is a poset, and where ℓ is a labelling of the elements of P by elements of B, such that:

(1) If x, y ∈ P and ℓ(x)Rℓ(y), then either x ⪯ y or y ⪯ x.

(2) The relation ⪯ is the transitive closure of the relations from (1).

Remark 2.3. The meaning of the relation R is that it expresses which pieces cannot be moved past each other. That is, a relation xRy 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 ⪯ x, or x must be below y, symbolised by x ⪯ y.

We illustrate this concept with the heap in Figure 1. The pieces are B = {b_{1}, b_{2}, …, b_{7}}. The relations are (not mentioning the relations of the form b_{i}Rb_{i}; if a relation b_{i}Rb_{j} holds then also b_{j}Rb_{i})

b_{1}Rb_{2}, b_{1}Rb_{3}, b_{1}Rb_{4}, b_{2}Rb_{4}, b_{3}Rb_{4}, b_{2}Rb_{5}, b_{6}Rb_{7}.  (2.1)

According to Remark 2.3, these relations mean that if b_{i}Rb_{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 ⪯ v or v ⪯ u. In our running example we have b_{2}Rb_{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 1.

A class of heaps which is of great importance for studying animals, polyominoes, Motzkin paths and orthogonal polynomials (cf. [2, 3, 4, 5, 12, 13, 24]), is the class of heaps of monomers and dimers, which we now introduce. (A more general class of heaps will be relevant in our sample application in Section 5.)

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  ^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘^{m_{0}} ^{m_{1}} ^{m_{2}} ^{m_{3}} ^{m_{4}} ^{m_{5}} ^{m_{6}} ^{m_{7}} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘^{d_{1}}  ^{d_{2}}  ^{d_{3}}  ^{d_{4}}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7}

Monomers and dimers

Figure 3

Example 2.4. Let B = M ∪ D, where M = {m_{0}, m_{1}, … } is the set of monomers and D = {d_{1}, d_{2}, … } 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 3. 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 3.

We impose the relations m_{i}Rm_{i}, m_{i}Rd_{i}, m_{i}Rd_{i+1}, i = 0, 1, …, d_{i}Rd_{j}, i − 1 ≤ j ≤ i, and extend R to a symmetric relation. Figure 4 shows two heaps of momomers and dimers.

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘

Two heaps of monomers and dimers

Figure 4

Next we make heaps into a monoid by introducing a 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} ∘ H_{2}, is the heap which results by putting H_{2} on top of H_{1}. The rigorous definition is the following.

Definition 2.5. Let H_{1} and H_{2} be heaps, H_{1} = (P_{1}, ⪯_{1}, ℓ_{1}), H_{2} = (P_{2}, ⪯_{2}, ℓ_{2}). Then the composition of H_{1} and H_{2}, H_{1} ∘ H_{2}, is the heap (H_{3}, ⪯_{3}, ℓ_{3}) with

(1) P_{3} = P_{1} ∪ P_{2}.

(2) The partial order ⪯_{3} on P_{3} is the transitive closure of (a) v_{1} ⪯_{3} v_{2} if v_{1} ⪯_{1} v_{2},

(b) v_{1} ⪯_{3} v_{2} if v_{1} ⪯_{2} v_{2},

(c) v_{1} ⪯_{3} v_{2} if v_{1} ∈ P_{1}, v_{2} ∈ P_{2} and ℓ_{1}(v_{1})Rℓ_{2}(v_{2}).

The composition of the two heaps in Figure 4 is shown in Figure 5.

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘

The composition of the heaps in Figure 4

Figure 5

Given pieces B with relation R, let H(B, R) be the set of all heaps consisting of pieces from B, including the empty heap, denoted by ∅. It is easy to see that Definition 2.5 makes (H(B, R), ∘) into a monoid with unit ∅.

3. Equivalence with the Cartier–Foata monoid

The monoid which we have just defined in the previous section can be seen to be equivalent to the Cartier–Foata monoid [7]. In order to explain this equivalence, we first observe that heaps could also be encoded by words with letters from B, i.e., by sequences of pieces. To obtain a word from a heap H = (P, ⪯, ℓ), one considers a linear extension of the poset P (i.e., a linear ordering ≤ of the elements of P in which x ≤ y whenever x ⪯ y), and then reads the labels ℓ(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 1 (see Figure 2 for the corresponding poset), possible such readings are

b_{2}b_{7}b_{4}b_{5}b_{6}b_{3}b_{2}b_{1} and b_{2}b_{5}b_{4}b_{2}b_{3}b_{1}b_{7}b_{6}.  (3.1)

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 ∼ w, if w arises from u by a squence of interchanges of two adjacent letters x and y for which xR̸y. For example, given the relation R as in (2.1), the words in (3.1) arise from each other by the following sequence of interchanges:

b_{2}b_{7}b_{4}b_{5}b_{6}b_{3}b_{2}b_{1} ∼ b_{2}b_{7}b_{5}b_{4}b_{6}b_{3}b_{2}b_{1} ∼ b_{2}b_{5}b_{7}b_{4}b_{6}b_{3}b_{2}b_{1} ∼ b_{2}b_{5}b_{4}b_{7}b_{6}b_{3}b_{2}b_{1} ∼ b_{2}b_{5}b_{4}b_{7}b_{6}b_{2}b_{3}b_{1} ∼ b_{2}b_{5}b_{4}b_{7}b_{2}b_{6}b_{3}b_{1}

∼ b_{2}b_{5}b_{4}b_{2}b_{7}b_{6}b_{3}b_{1} ∼ b_{2}b_{5}b_{4}b_{2}b_{7}b_{3}b_{6}b_{1} ∼ b_{2}b_{5}b_{4}b_{2}b_{3}b_{7}b_{6}b_{1}

∼ b_{2}b_{5}b_{4}b_{2}b_{3}b_{7}b_{1}b_{6} ∼ b_{2}b_{5}b_{4}b_{2}b_{3}b_{1}b_{7}b_{6}.

Thus, heaps in H(B, R) correspond to equivalence classes of words modulo ∼. 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.

4. The main theorems

For the statement of the main theorems in the theory of heaps, we need two more terms. A trivial heap is a heap consisting of pieces all of which are pairwise unrelated, i.e., xR̸y for all pieces x, y in H. Figure 6.a shows a trivial heap consisting of monomers and dimers. A pyramid is a heap with exactly one maximal element (in the corresponding poset). Figure 6.a shows a pyramid consisting of monomers and dimers. Finally, if H is a heap, then we write |H| for the number of pieces in H.

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}_{0} _{1} _{2} _{3} _{4} _{5} _{6} _{7} ∘ ∘ ∘ ∘ ∘ ∘  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}_{0} _{1} _{2} _{3} _{4} _{5} _{6} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘

a. A trivial heap b. A pyramid

Figure 6

The following theorem is Proposition 5.3 from [22].

Theorem 4.1. Let M be a subset of the pieces B. Then, in the monoid H(B, R), 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 M is given by

∑_{H∈H(B,R)} maximal pieces ⊆M H = ( ∑_{T ∈T (B,R)}(−1)^{|T |}T )^{−1}( ∑_{T ∈T (B\M,R)}(−1)^{|T |}T ),  (4.1)

where T (B, R) denotes the set of all trivial heaps with pieces from B, and similarly for T (B\M, R). In particular, the sum of all heaps if given by

∑_{H∈H(B,R)}H = ( ∑_{T ∈T (B,R)}(−1)^{|T |}T )^{−1}.  (4.2)

Remark 4.2. The inverse of the series which appears on the right-hand sides of (4.1) and (4.2) exists because it has the form (1 − X)^{−1} = ∑_{j≥0} X^{j}.

Remark 4.3. Equation (4.1) generalises Eq. (1) from [7, Introduction, Part A], the latter being equivalent to (4.2).

Proof. Formula (4.2) is the special case of (4.1) in which M = B. Therefore it suffices to establish (4.1). By multiplication at the left by ∑_{T ∈T (B,R)}(−1)^{|T |}T, the latter is equivalent to

∑_{H∈H(B,R), T ∈T (B,R)} maximal pieces of H ⊆M(−1)^{|T |}T ∘ H = ( ∑_{T ∈T (B\M,R)}(−1)^{|T |}T ).  (4.3)

We show that most of the terms on the left-hand side of (4.3) cancel each other pairwise. In order to do this, we first fix an arbitrary linear order on the set of pieces B. Now, let (H, T) be a pair of a heap H in H(B, R) with maximal pieces contained in M and a trivial heap T. Consider the minimal pieces in T ∘ H (again, this means the labels of the minimal elements in the poset corresponding to T ∘ H) which are below some maximal piece in T ∘ H that belongs to M. Let b be the first such minimal piece in the linear order of pieces. Then we form a new pair (H′, T′) by:

• If b ∈ T, then H′ = b ∘ H and T′ = T \b.

• If b ∉ T, then H′ = H\b and T′ = T ∘ b.

In particular, nothing changes in the composed heap, i.e., we have T′ ∘ H′ = T ∘ H. Hence, we have (−1)^{|T′|}T′ ∘ H′ = −(−1)^{|T |}T ∘ 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 (4.3) 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 ∘ H does not contain any maximal piece in M. This forces H (which “sits” on top of T in T ∘ H) to be the empty heap, and T to consist of pieces in B\M only (all the pieces in a trivial heap are maximal). Thus, (4.3) is established. □

The second main theorem, Proposition 5.10 from [22], concerns the set of pyramids in H(B, R), which, for convenience, we denote by P(B, R). In contrast to Theorem 4.1, in the result we must give up non-commutativity.

Theorem 4.4. For the following (formal) sum indexed by pyramids in H(B, R), we have

∑_{P ∈P(B,R)} \frac{1}{|P |}P =_{comm} − log ( ∑_{T ∈T (B,R)}(−1)^{|T |}T ),  (4.4)

where =_{comm} means that the identity holds in the commutative extension of H(B, R), that is, in the commutative monoid which arises from H(B, R) by letting all pieces in B commute.

Proof. We make heaps into labelled objects. More precisely, a labelled heap is a heap from H(B, R) 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 H̃(B, R) denote the set of all labelled heaps, and let P̃(B, R) denote the set of all labelled pyramids in H̃(B, R) with the above special property. Then, by the exponential principle for labelled combinatorial objects (cf. [1, Eqs. (20), (70)], [11, Sec. II.2.1], or [19, Cor. 5.1.6]), we have immediately

∑_{H∈H̃(B,R)} \frac{1}{|H|!}H =_{comm} exp ( ∑_{P ∈P̃(B,R)} \frac{1}{|P |!}P ) .

However, for any (unlabelled) heap in H(B, R) with N pieces there are exactly N! ways to label the pieces to obtain a labelled heap in H̃(B, R), while for any (unlabelled) pyramid from H(B, R) with N pieces there a exactly (N − 1)! ways to label the pieces to obtain a labelled pyramid in P̃(B, R). (The reader should recall that the maximal element of the pyramid must get the smallest label.) Hence,

∑_{H∈H(B,R)}H =_{comm} exp ( ∑_{P ∈P(B,R)} \frac{1}{|P |}P ) ,

which, in view of (4.2), is equivalent to (4.4). □

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 B, 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 4.1 and 4.4 immediately imply the following corollary on the corresponding generating function of heaps.

Corollary 4.5. Let M be a subset of the pieces B. Then, the generating function for all heaps with maximal pieces contained in M is given by

∑_{H∈H(B,R)} maximal pieces ⊆M w(H) = \frac{∑_{T ∈T (B\M,R)}(−1)^{|T |}w(T)}{∑_{T ∈T (B,R)}(−1)^{|T |}w(T)},  (4.5)

where again T (B, R) denotes the set of all trivial heaps with pieces from B. In particular, the generating function for all heaps is given by

∑_{H∈H(B,R)}w(H) = \frac{1}{∑_{T ∈T (B,R)}(−1)^{|T |}w(T)}.  (4.6)

Furthermore,

∑_{P ∈P(B,R)} \frac{1}{|P |}w(P) = − log ( ∑_{T ∈T (B,R)}(−1)^{|T |}w(T)),  (4.7)

where again P(B, R) denotes the set of all pyramids in H(B, R).

5. A sample application

As an illustration, we show how to use the results from Section 4 in order to obtain a formula for a multivariate generating function for parallelogram polyominoes. This beautiful application of heaps is due to Bousquet–Mélou and Viennot [6].

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

A parallogram polyomino

Figure 7

The area a(P) of a parallelogram polyomino P is the number of cells of P. The width b(P) of a parallelogram polyomino P is the number of columns of cells of P. The height h(P) of a parallelogram polyomino P is the number of rows of cells of P. For our parallogram polyomino in Figure 7, 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

∑_{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 ≤ a ≤ 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 8 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].)

. . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}  . . . . .^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .}^{. . . . .} ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ^{S_{8}}  ^{S_{5}}^{S_{7}}^{S_{6}}  ^{S_{4}}^{S_{3}}  ^{S_{2}}^{S_{1}}_{1} _{2} _{3} _{4} _{5} _{6} _{7} _{8}

A heap of segments

Figure 8

Given a parallelogram polyomino P consisting of n columns, we obtain a heap of segments in the following way: Let (c_{1}, c_{2}, …, c_{n}) be the sequence of column lengths of P (considering the columns from left to right). In our example in Figure 7, these are (3, 4, 3, 4, 4, 2, 2, 2). Furthermore, define (a_{1}, a_{2}, …, 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 7, 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, …, 1, on each other, that is, we form the heap

[a_{n}, c_{n}] ∘ [a_{n−1}, c_{n−1}] ∘ ⋯ ∘ [a_{1}, c_{1}].

It can be checked that the heap in Figure 8 corresponds to the parallelogram polyomino in Figure 7 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,

(1) b(P) is the number of pieces of H;

(2) h(P) is one more than the sum of all the lengths of pieces of H;

(3) a(P) is the sum of the right abscissae of the pieces of H (i.e., the sum of the c_{i}’s).

For details, we refer the reader to [6].

Now we apply Corollary 4.5 with H(B, R) being our heaps of segments, M being the set of all pieces of the form [1, c], and with the weight w being defined as

w(H) = x^{|H|}y^{∑(lengths of pieces of H)}q^{∑(right abscissae of pieces of H)}.

In order to do so, first of all, we must compute the sum

∑_{T ∈T (B,R)}(−1)^{|T |}w(T).

Now, a trivial heap consisting of n pieces has the form

[a_{1}, c_{1}] ∘ [a_{2}, c_{2}] ∘ ⋯ ∘ [a_{n}, c_{n}],

where 1 ≤ a_{1} ≤ c_{1} < a_{2} ≤ c_{2} < ⋯ < a_{n} ≤ c_{n}. Therefore,

∑_{T ∈T (B,R)}(−1)^{|T |}w(T) = ∑_{n=0}^{∞}(−1)^{n}x^{n} ∑_{1≤a_{1}≤c_{1}<a_{2}≤c_{2}<···<a_{n}≤c_{n}} y^{∑_{i=1}^{n}(c_{i}−a_{i})}q^{∑_{i=1}^{n} c_{i}}.

Now the sums over c_{n}, a_{n}, c_{n−1}, a_{n−1}, …, c_{1}, a_{1} can be evaluated, in this order, all of them being geometric sums. The result is

∑_{T ∈T (B,R)}(−1)^{|T |}w(T) = ∑_{n=0}^{∞} \frac{(−1)^{n}x^{n}q^{\binom{n+1}{2}}}{(q; q)_{n} (yq; q)_{n}} ,

where (α; q)_{k} is the q-shifted factorial, given by (α; q)_{0} := 1 and

(α; q)_{k} := (1 − α)(1 − αq) ⋯ (1 − αq^{k−1})

if k is a positive integer. Similary, we obtain

∑_{T}′(−1)^{|T |}w(T) = − ∑_{n=0}^{∞} \frac{(−1)^{n}x^{n+1}q^{\binom{n+2}{2}}}{(q; q)_{n} (yq; q)_{n+1}} ,

the sum being over all trivial heaps T in T (B, R) containing at least one piece from M. Hence, remembering that parallelogram polyominoes are non-empty sets of cells, we infer that

∑_{P} x^{b(P)}y^{h(P)}q^{a(P)} = y (\frac{∑_{T ∈T (B\M,R)}(−1)^{|T |}w(T)}{∑_{T ∈T (B,R)}(−1)^{|T |}w(T)} − 1)

= y \begin{matrix}∑_{n=0}^{∞} & \frac{(−1)^{n}x^{n+1}q^{\binom{n+2}{2}}}{(q; q)_{n} (yq; q)_{n+1}} \\ ∑_{n=0}^{∞} & \frac{(−1)^{n}x^{n}q^{\binom{n+1}{2}}}{(q; q)_{n} (yq; q)_{n}} \end{matrix} ,  (5.1)

the sum over P being over all parallogram polyominoes P.

References

[1] F. Bergeron, G. Labelle and P. Leroux, Combinatorial species and tree-like structures, Cambridge University Press, Cambridge, 1998.

[2] J. Bétréma and J. G. Penaud, Modèles avec particules dures, animaux dirigés et séries en variables partiellement commutatives, manuscript, arχiv:math.CO/0106210.

[3] M. Bousquet–Mélou, q-Énumération de polyominos convexes, J. Combin. Theory Ser. A 64 (1993), 265–288.

[4] M. Bousquet–Mélou, Polyominoes and polygons, in: Jerusalem Combinatorics ’93, pp. 55–70, Contemp. Math., 178, Amer. Math. Soc., Providence, RI, 1994.

[5] M. Bousquet–Mélou and A. Rechnitzer, Animals and heaps of dimers, Discrete Math. 258 (2002), 235–274.

[6] M. Bousquet–Mélou and X. Viennot, Empilements de segments et q-énumération de polyominos convexes dirigés, J. Combin. Theory Ser. A 60 (1992), 196–224.

[7] P. Cartier and D. Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, No. 85, Springer–Verlag, Berlin, New York, 1969; republished in the “books” section of the Séminaire Lotharingien de Combinatoire.

[8] S. Corteel, A. Denise and D. Gouyou-Beauchamps, Bijections for directed animals on infinite families of lattices, Ann. Comb. 4 (2000), 269–284.

[9] J.-M. Fédou, Sur les fonctions de Bessel, Discrete Math. 139 (1995), 473–480.

[10] J.-M. Fédou, Combinatorial objects enumerated by q-Bessel functions, Rep. Math. Phys. 34 (1994), 57–70.

[11] P. Flajolet and R. Sedgewick, Analytic Combinatorics, book project, available at

http://algo.inria.fr/flajolet/Publications/books.html.

[12] P. Di Francesco and E. Guitter, Integrability of graph combinatorics via random walks and heaps of dimers, J. Stat. Mech. Theory Exp. 2005, no. 9, P09001, 34 pp.

[13] A. M. Garsia, Heaps, continued fractions and orthogonal polynomials, Lecture Notes for a course given at the University of California at San Diego, 1993.

[14] R. M. Green, Acyclic heaps of pieces, I, J. Algebraic Combin. 19 (2004), 173–196.

[15] R. M. Green, Acyclic heaps of pieces, II, Glasgow Math. J. 46 (2004), 459–476.

[16] R. M. Green, On rank functions for heaps, J. Combin. Theory Ser. A 102 (2003), 411–424.

[17] R. M. Green, Full heaps and representations of affine Kac–Moody algebras, preprint,

arχiv:math.CO/0605768.

[18] P. Lalonde, Lyndon heaps: an analogue of Lyndon words in free partially commutative monoids, Discrete Math. 145 (1995), 171–189.

[19] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[20] J. R. Stembridge, On the fully commutative elements of Coxeter groups, J. Alg. Combin. 5 (1996), 353–385.

[21] J. R. Stembridge, Minuscule elements of Weyl groups, J. Algebra 235 (2001), 722–743.

[22] X. G. Viennot, Heaps of pieces. I. Basic definitions and combinatorial lemmas, Lecture Notes in Math., 1234, Springer, Berlin, 1986, pp. 321–350.

[23] X. G. Viennot, Bijections for the Rogers-Ramanujan reciprocal, J. Indian Math. Soc. (N.S.) 52 (1987), 171–183.

[24] X. Viennot and W. James, Heaps of segments, q-Bessel functions in square lattice enumeration and applications in quantum gravity, preprint.

Fakultät für Mathematik, Universität Wien, Nordbergstrasze 15, A-1090 Vienna,

Austria. WWW: http://www.mat.univie.ac.at/~kratt