321-avoiding affine permutations, heaps, andperiodic parallelogram polyominoes
Riccardo Biagioli a,1 , Frédéric Jouhet a,2 , Philippe Nadeau a,3a Univ. Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut

Camille Jordan, 43 blvd. du 11 novembre 1918, F-69622 Villeurbanne cedex,
FranceAbstract
We give exact formulas for the bivariate generating series of 321-avoiding affine
permutations with respect to rank and Coxeter length. We use two different combinatorial approaches, both based on the theory of heaps of pieces.
Keywords: Affine permutations, heaps, polyominoes, generating functions.

1

Introduction

A permutation is said to be 321-avoiding if it avoids the pattern 321. In[5], Billey-Jockusch-Stanley showed that a permutation is 321-avoiding if andonly if it is fully commutative (FC), which means that any two of its reduced
decompositions are related by a series of transpositions of adjacent commuting
generators. It is well-known that the number of 321-avoiding permutations in
Coxeter group of type An−1 is given by the nth Catalan number. An analogous
result of Green [7] shows that fully commutative elements in the affine Coxeter
group of type Ãn−1 , once interpreted as infinite permutations, are exactly the
321-avoiding affine permutations (see Section 3). There is an infinite numberof such affine permutations, nevertheless it makes sense to compute how manyof them have a fixed Coxeter length. For any infinite family of Coxeter groups,
1

Email: biagioli@math.univ-lyon1.fr
Email: jouhet@math.univ-lyon1.fr
3
Email: nadeau@math.univ-lyon1.fr
2

it is interesting to compute the series
XXq `(w) ,W (x, q) =WnF C (q)xn , where WnF C (q) =nw∈WnF Cand WnF C denotes the set of FC elements in the Coxeter group of type W andrank n. In the case of the affine group of type Ãn−1 , Hanusa and Jones [8]showed that the series WnF C (q) is a rational function in q, with ultimately periodic coefficients, and provided an expression for the generating series W (x, q),
although rather complicated.
The goal of this extended abstract is to provide some closed form expressions for the series W (x, q) for Coxeter groups of type A and Ã, and for theirsubsets of involutions. In type A, we recover a result of Barcucci et al. [1]. We
use two different approaches and provide two different combinatorial proofs,
both based on the work of Viennot on heaps of pieces [10]. More precisely, thefirst one uses the theory of heaps of cycles, and the second one generalizes atechnique introduced by Bousquet-Mélou and Viennot [6] to enumerate parallelogram polyominoes, and uses heaps of segments. Analytic proofs of such
results can be found in [2].
We now state our results. For n ≥ 0, we denote the q-Pochhammer symbolby(x)n := (1 − x)(1 − xq) · · · (1 − xq n−1 ),where q is the length variable. This is extended to n = ∞.
Theorem 1.1 Let A(x, q) ≡ A and Ã(x, q) ≡ Ã be the generating functionsof fully commutative elements of type A and Ã, respectively defined by
X
X
C
A :=
AFn C (q)xn
and
Ã :=
ÃFn−1(q)xn .
n≥0

n≥1

Then
A=

1 J(xq)1 − xq J(x)andÃ = −xJ 0 (x) X xn q n−,J(x) n≥1 1 − q nwhere J(x) is the following series:
J(x) :=X (−x)n q (n2 )(q)n (xq)nn≥0.

The counterpart of this result for involutions reads as follows.

(1)

Theorem 1.2 With the above notation, the generating functions of fully commutative involutions of type A and Ã are respectively:A=

U(xq) + xqU(xq 2 )U(x) − xU(xq)

and

with
U(x) :=U 0 (x) − xqU 0 (xq) − U(xq),
U(x) − xU(xq)X (−x2 )n q n(2n−1)n≥02Ã = −x(q 2 ; q 2 )n.

(2)

Heaps of pieces

Definition 2.1 Let P be a set (of basic pieces) with a symmetric and reflexive
binary relation C, called the concurrency relation. A heap is a triple (H, , ),
where (H, ) is a finite poset, and  : H → P is a labeling map such that:(i) if x, y ∈ H and (x)C(y), then either x  y or y  x;(ii) the relation  is the transitive closure of the relation from (i).
The elements of H are called pieces. When x  y we will say that thepiece y is above the piece x. Note that P is not necessarily finite. The set of
all heaps with pieces in P and concurrency relation C is denoted by H(P, C).
Let H be a heap. A piece is said to be maximal (resp. minimal) if it is
not concurrent with any piece above (resp. below) it. We denote by max(H)(resp. min(H)) the set of maximal (resp. minimal) pieces of H. A pyramid isa heap with exactly one maximal element. A trivial heap is either the empty
heap, or a heap consisting of pieces which are pairwise unrelated, namely they
are minimal and maximal. We denote with T (P, C) the set of trivial heaps.
We denote with |H| the number of pieces in the heap H.
In this paper we will be mostly interested in a particular family of heaps,
namely that of heaps of segments. The set P of pieces is the set of segments ofthe form [a, b], where a, b ∈ N, a ≤ b. Two pieces p and p0 of P are concurrent if
their intersection is nonempty. There is a well-known operation of compositionof heaps. Intuitively, given two heaps H1 and H2 , the composition H1 ∗ H2
is the heap that results by putting H2 on top of H1 (for a rigorous definition
we refer to [10]). In Figure 1 two heaps of segments and their composition
are depicted: H2 is a heap of monomers and dimers, which means that all its
pieces are either points, or segments of the form [a, a + 1].
The following fundamental result is due to Viennot [10], and it is usuallycalled the Inversion Lemma. It allows to enumerate some families of heaps

∗

=

H1

H2

H1 ∗ H 2

Fig. 1.

with respect to a certain valuation on their pieces. This means that each basic
piece p of H has a weight v(p), and that the weight of H, denoted by v(H), is
defined as the product of the weights of all the pieces of H. For us the weights
will always be elements of some commutative ring with unity.
Lemma 2.2 (Inversion Lemma) Let M be a subset of pieces of P. Thenthe generating function for heaps with all maximal pieces in M is given by
X(−1)|T | v(T )X
T ∈T (P\M,C)
X,
v(H) =(−1)|T | v(T )H∈H(P,C)
max(H)⊆M

T ∈T (P,C)

where T (P, C) denotes the set of all trivial heaps with pieces from P. In
particular, the generating series for all heaps in H(P, C) is given byX

1v(H) =X

H∈H(P,C)(−1)|T | v(T ).

T ∈T (P,C)

3

321-avoiding affine permutations

The Dynkin diagram of the affine Coxeter group of type Ãn−1 is given by
s0

s1

en−1
A

sn−1

There is a well-known combinatorial characterization of Ãn−1 as a group of
infinite permutations. More precisely, consider the set of bijective transformations σ : Z → Z such that σ(i + n) = σ(i) + n for all i ∈ Z, as well asPP
the normalization condition ni=1 σ(i) = ni=1 i. They form a group Sen undercomposition, called the group of affine permutations. It is well-known (see[9]) that Sen is isomorphic to the Coxeter system of type Ãn−1 , via the only
morphism extending si 7→ ((i, i + 1)) for i = 0, 1, . . . , n − 1, where ((i, i + 1))
is the affine permutation exchanging i + kn and i + 1 + kn for all k ∈ Z.
An affine permutation σ is 321-avoiding if there are no i < j < k in Z
satisfying σ(i) > σ(j) > σ(k). Green showed in [7] that an affine permutation
is fully commutative if and only if it is 321-avoiding. We have the following
characterization [7],[4].
Proposition 3.1 An element w of type Ãn−1 is 321-avoiding if and only if,
in any reduced decomposition of w, the occurrences of si and si+1 alternate forall i ∈ {0, . . . , n − 1}, where we set sn = s0 .
Thanks to this characterization, there is a convenient way to represent FC
elements by particular diagrams, called FC-heaps in [4]. They are actually
heaps in the sense of Definition 2.1, but we do not need this characterizationin this note, so we prefer to call them just alternating diagrams. Without
entering into the details of the formal definition, we show how to construct
an alternating diagram through an example. Consider σ = [6, −3, −1, 8] ∈Ã3 . Note that in complete notation it looks like σ = . . . | 2, −7, −5, 4 |6, −3, −1, 8 | 10, 1, 3, 12 | . . .. In Figure 2, it is depicted how to obtain thealternating diagram of σ (right) starting from its line diagram (left).
0

−3

−3

−1

1

2

3

4

6

6

7

1

8

2

3

4

s0 s1 s2 s3 s0

Fig. 2. The element σ = [6, −3, −1, 8] = s1 s3 s0 s2 s1 s3 s0 s2 s1 .

The alternating diagram of a 321-avoiding affine permutation σ ∈ Ãn−1
has several important features. For example, the alternating diagram of σ hasin column i as many points as the number of occurrences of the generator siin any reduced expression of σ. The last column is a copy of the first one andrecords the occurrences of s0 . The points between two consecutive columns i
and i + 1 alternate exactly as the corresponding occurrences of si and si+1 doin the reduced decomposition of σ (from bottom to top).
Alternating diagrams can be encoded by lattice paths as follows. Givenan alternating diagram H of type Ãn−1 , denote by |Hsi | the number of points
in column i. For i = 0, . . . , n − 1, draw a step from Pi = (i, |Hsi |) to Pi+1 =(i + 1, |Hsi+1 |) as follows. If |Hsi | = |Hsi+1 | > 0, we label the corresponding
step by L (resp. R) if the lowest element of the chain H{si ,si+1 } has label si+1
(resp. si ). If |Hsi+1 | = |Hsi | = 0, we label the ith step by L. Following [4]we define ϕ0 (H) to be the walk (P0 , P1 , . . . , Pn ) with its labels; here we set
sn = s0 . This forms a path ϕ0 (H) of length n, with both P0 and Pn at heightC, we set ϕ0 (w) := ϕ0 (H(w)), where H(w) is the alternating|Hs0 |. If w ∈ ÃFn−1
diagram associated to w.

L R
R'0 (H)

HL
s0 s1 s2

s11 s00nFig. 3. The path ϕ0 (H) associated to the heap H.

Define On as the set of paths having n steps in the set {(1, 1), (1, −1), (1, 0)}such that all horizontal steps (1, 0) are labeled either by L or by R, and whose
starting and ending points are at the same height. A walk is said to satisfy
condition (∗) if all horizontal steps of the form (i, 0) → (i + 1, 0) (i.e. at height0) have label L. The
subset of walks satisfying condition (∗) is denoted On∗ .
P
Define also h0 (P ) = n−1i=0 h(Pi ), which corresponds to the area under the walkP , (here h(Pi ) denotes the height of the point Pi ). Finally, denote by En ⊆ On∗
the set of walks with all vertices at the same positive height, and all n steps
with the same label (either L or R). For a proof of the following theorem werefer to [4].
C
Theorem 3.2 The map ϕ0 : ÃFn−1→ On∗ \ En is a bijection such that `(w) =00h (ϕ (w)).
C
The alternating diagram of an involution in ÃFn−1
is horizontally symmetric(see [3]). This means that two consecutive nonempty columns always differ
by exactly one point. Hence the restriction of the map ϕ0 to the subset of
involutions gives paths in On∗ having horizontal steps only at height 0.
It is clear that FC elements of type An−1 are in bijection with FC elementsof type Ãn−1 whose reduced expressions have no occurrence of s0 . Therefore,by Theorem 3.2, FC elements of type An−1 are in bijection with lattice paths
with starting and ending points at height 0 and satisfying condition (∗). Onceagain, the subset of involutions will be in bijection with the subset of suchpaths having horizontal steps only at height 0.

4

Solutions via lattice paths and heaps of monomers anddimersIn this section we give proofs of Theorems 1.1 and 1.2, based on the Inversion
Lemma applied to heaps of monomer and dimers.

4.1

Heaps of cycles

Starting with the path encoding defined in the previous section, we use a
specialization of a bijection due to Viennot [10] in the general theory of heapsof cycles, to encode our lattice paths, and thus affine FC permutations, byheaps of monomers and dimers.
Due to space limitation, we only illustrate such a bijection with an example.
First consider a path in On∗ , where the last point has been marked, and rotate
it clockwise by 90 degrees. Then transform each vertical step into a monomer(with its label), and form a set of dimers by matching pairs of down-up or
up-down steps, precisely by attaching the top one to the first below it thatstarts and ends in the same columns. Finally, drop the resulting dimers andmonomers from top to bottom. An example is shown in Figure 4.
The result of such transformations is a heap of monomer and dimers, wheremonomers might have two labels L and R, except at abscissa 0, where they
have only label L (this is the translation on heaps of the (∗)-condition). Moreover, such heaps have a unique maximal marked element. Hence they aremarked pyramids. By Viennot’s theory, this map is a bijection.
To summarize, there is a bijection between the set of affine FC permutations and pyramids of monomers and dimers marked in their maximal piece,
where the monomers have two labels L or R, except in column 0, where they
have label L. Let us denote this set by Π̇. When we restrict this map toaffine FC involutions the image is the set of marked pyramids of monomers
and dimers, where the monomers can only occur at column 0, with label L.
Once again, when we consider FC permutations (resp. their subset of
involutions), the image is the set of half-pyramids (resp. the maximal piece is[0,1]) of monomers and dimers, where the monomers have two labels L or R,
except in column 0, where they have label L (resp. the monomers can occur
only at column 0, with label L).

R
L
L
R

R

L

Fig. 4. The bijection between paths in O∗ and marked pyramids.

4.2

Fully commutative elements in type A

We will prove the first result of Theorem 1.1, under the following equivalent
form:
j(xq)
A=
,
j(x)

where j(x) :=X (−x)n q (n2 ) (xq n+1 )∞
n≥0

(q)n

= (xq)∞ J(x).

(3)

It will be convenient to introduce two more series H and h, closely related to
J and j:H(x) :=X (−x)n q (n2 )(q)n (x)nn≥0andh(x) := (x)∞ H(x) =X (−x)n q (n2 ) (xq n )∞
n≥0

(q)n
(4)

It is not difficult to give a combinatorial proof of the following lemma.
Lemma 4.1 The series j(x) given by (3) is the signed generating function oftrivial heaps of monomers and dimers satisfying (*). The series h(x) definedby (4) is the signed generating function of trivial heaps of monomers anddimers.
Let us now consider FC elements of type An . As explained after Theorem 3.2, they can be encoded by paths with n + 1 steps satisfying Condition(∗). The length of the FC element is equal to the total height of the associated path. Moreover, as discussed in Section 4.1, these paths are themselvesin bijection with half-pyramids of monomers and dimers. The monomers havea label L or R, except those at abscissa 0 that are all labeled by L. By giving a weight xq i per monomer located at abscissa i, and a weight x2 q 2i+1 per
dimer at abscissa [i, i + 1], we have that an FC element w in An is bijectively
encoded by a half-pyramid of weight xn q `(w) . The above bijection between
FC elements and heaps of monomers and dimers, combined with the Inversion.

Lemma, gives:
h0 (x)
− 1,
(5)
j(x)
where j(x) is defined as in Lemma 4.1, and h0 (x) is the signed generating
function of trivial heaps that have no monomer or dimer at abscissa 0. Sincesuch heaps are obtained by translating one step to the right any trivial heap,
we have h0 (x) = h(xq). One concludes the proof of (3) (left) by combining (5)and the identity j(x) + xj(xq) = h(xq), which can be derived directly by thedefinitions of these series.
Let us now restrict our attention to involutions. They correspond to halfpyramids in which the only monomers lie at abscissa 0 (and then come in only
one colour). By the Inversion Lemma,
xA =

xA =

h(xq)
−1
j(x)

where j(x) is the signed generating function of trivial heaps having no monomerat positive abscissa, and h(x) counts trivial heaps of dimers. It is easy to seethath(x) = U(x)andj(x) = U(x) − xU(xq),(6)
where U(x) is defined by (2). Plugging these values of h and j in the expressionof xA, we obtain the first identity of Theorem 1.2.
4.3

Fully commutative elements in type Ã

Recall that Π̇ denotes the set of P
pyramids whose monomers at column 0 havelabel L. Let us define Π̇(x) := H∈Π̇ v(H), where as before the weight of amonomer located at abscissa i is xq i , and the weight of a dimer at abscissa[i, i + 1] is x2 q 2i+1 . By the arguments of the previous section and Theorem 3.2
we obtain
X xn q n.
(7)Ã = Π̇(x) − 2
n
1
−
q
n≥1
Consider a heap satisfying (∗), with one piece marked.
  By the Inversion
0

0

j (x)
1
Lemma, the associated generating function is x j(x)= −x j(x)2 , where
derivatives are taken with respect to x. By pushing the marked piece downwards, this marked heap factors into a marked pyramid and an arbitrary heap,
both satisfying (∗) (Figure 5). This gives−x

j 0 (x)
Π̇(x)
=
,
2
j(x)
j(x)

0

(x)
. Returnso that the generating function of marked pyramids is Π̇(x) = −x jj(x)ing to (7), this gives the second result of Theorem 1.1 since j(x) = (xq)∞ J(x).

!

Fig. 5. Factorisation of a marked heap.

We now restrict our attention to FC affine involutions. Again, this meansthat the only monomers lie at abscissa 0. Note that this automatically rules
out pyramids consisting of monomers lying at positive abscissa. Using thesame argument as before, we obtainÃ = −xj0 (x).
j(x)Since j(x) = U(x) − xU(xq), this gives the second result of Theorem 1.2.

5

Periodic parallelogram polyominoes and heaps of segments

Here we introduce and enumerate periodic parallelogram polyominoes using
heaps of segments, which extends the theory in [6] for usual parallelogram
polyominoes. We then apply this to the q-enumeration of FC elements ine therefore exhibiting an alternative proof of our enumerative
affine type A,
results in this type.
5.1

Some special heaps of segments

In this section we let H be the set of heaps where the pieces are segments [a, b]
and 1 ≤ a ≤ b are integers. Let S be the set of finite sequences of pairs of
positive integers (ai , bi ), 1 ≤ i ≤ n, satisfying ai ≤ bi for all i and ai ≤ bi−1
for i > 1, i.e.
a1 ≤ b1 ≥ a2 ≤ b2 ≥ · · · ≤ bn−1 ≥ an ≤ bn .
Following [6, Section III], to a sequence (ai , bi )1≤i≤n ∈ S, we associate anelement of H by stacking the segments [an , bn ], [an−1 , bn−1 ], . . . , finishing by[a1 , b1 ]. More precisely, for P ∈ S defined as above, we considerf (P ) := En ∗ · · · ∗ E1 ,where Ei := [ai , bi ], for i = 1, . . . , n, and the composition ∗ is defined as in
Section 2. An illustration is given in Figure 6 (right).
Lemma 5.1 The map f is a bijection between S and H. Moreover [an , bn ](resp. [a1 , b1 ]) is the leftmost minimal (resp. rightmost maximal) segment inf (P ).
In [6, Lemma 3.3(i)], it is already shown that [an , bn ] is the leftmost minimal
segment in the image by f of the previous sequence. Then the inverse imageof any heap of segments is uniquely determined by successively removing theleftmost minimal segments in a heap of H and naming the first one [an , bn ], thesecond one [an−1 , bn−1 ], and so on until the last one, which is denoted [a1 , b1 ].
A parallelogram polyomino is a polyomino such that the intersection withevery line perpendicular to the main diagonal is a segment. In [6], the set ofparallelogram polyominoes is encoded by the subset of sequences (ai , bi )1≤i≤n ∈S with the restriction a1 = 1. Here bi is the length of the ith column and ai
is the number of common rows between the (i − 1)th and ith columns. In [6,Proposition 3.4(i)], it is shown that f induces a bijection between parallelogram polyominoes and half-pyramids, the heaps in H having a unique maximal
segment of the form [1, b]. This is now a consequence of Lemma 5.1.
So the elements of S can be encoded by parallelogram polyominoes which
are marked on their first column at a height a, where a is an integer between
1 and the height of the first column.
Definition 5.2 [Periodic parallelogram polyominoes] A periodic parallelogram
polyomino of width n ≥ 1 is a parallelogram polyomino marked on its firstcolumn in a, where a is an integer between 1 and the height of the last column.
These naturally correspond to sequences (ai , bi )1≤i≤n ∈ S such that a1 ≤ bn .
An example of such a polyomino is represented in Figure 6, together with
its induced image under f (here the dashed columns highlight the periodic
structure). Now, consider the following condition on a nonempty heap H ∈ H.
Definition 5.3 [Condition (I)] If [a, b] is the rightmost maximal segment of
H and [a0 , b0 ] is its leftmost minimal segment, then a ≤ b0 .
Equivalently, condition (I) means that there is no minimal segment of
H which occurs strictly left of a maximal one. Let HI be the set of heaps
satisfying (I). We obtain immediately
Proposition 5.4 The bijection f induces a bijection between the set of periodic parallelogram polyominoes and HI .

width1height

2

3

4

5

6

7

Fig. 6. A periodic parallelogram polyomino P of width n = 5, height 9, and its
image f (P ), with (a1 , . . . , an ) = (5, 7, 2, 1, 2) and (b1 , . . . , bn ) = (7, 7, 4, 2, 6).

Finally, in the correspondence of Proposition 5.4, the width of the periodic
parallelogram polyomino P is equal to the number of segments in f (P ), theheight of P to the sum of the lengths of the segments minus the number ofsegments in f (P ) (here [a, b] has length b − a + 1, which differs from [6]), andthe area of P to the sum of the right abscissas of the segments in f (P ). Herethe height of a periodic parallelogram polyomino is defined as the numbersof rows between the bottom of the first column and the bottom of the first
repeated column.
5.2Counting heaps in HI

Following [6], we want to count heaps H ∈ HI with respect to the following
weight (note that for practical reasons due to the above choice for the lengthof a segment, we adopt here a slightly different, though equivalent, definitionof weight from the one in [6]):v(H) := y |H| x`(H) q e(H) ,where |H| is the number of segments in H, `(H) is the sum of the lengths ofall segments and e(H) is the sum of all right endpoints of segments.
Denote by T ⊂ H the set of trivial heaps. Given any E ∈ H and T ∈ T ,defineφ(E, T ) := (T ∗ E, T ).
The function φ is clearly injective. We wish to determine the image of
HI × T by φ, and to this purpose we need the following definitions for a heapF ∈ HI \ T :•SF = [aF , bF ] is the rightmost segment in max(F ) \ min(F );•YF is the set of segments [a, b] in max(F ) ∩ min(F ) satisfying a > bF ;•XF is the set of segments [a, b] ∈ min(F ) satisfying b < aF ;•U1 (F ) is the union XF ∪ YF ;•if F \ min(F ) ∈/ HI and there exists S0 = S0 (F ) ∈ min(F ) such thatF \(min(F ) \ {S0 }) ∈ HI , then we define U2 (F ) as min(F )\{S0 }, otherwise
we simply set U2 (F ) := min(F ).

Note that if S0 (F ) = [a0 , b0 ], then there exists [a, b] such that a ≤ a0 ≤ b <aF ≤ b0 . From this we deduce that S0 is unique if it exists, so that U2 (F ) is
well-defined.
Lemma 5.5 The pair (F, U ) belongs to φ(HI × T ) if and only if U ⊆ min(F )and one of the following cases occurs:(i) F ∈ T and |F \ U | = 1,(ii) F 6∈ T , F \ U1 (F ) ∈ HI and U1 (F ) ⊆ U ⊆ U2 (F ).
Thus by Lemma 5.5 we obtain!
!
XX(−1)|T | v(T )v(E) =
T ∈T

E∈HI

X

v(F )(−1)|U |(F,U )∈φ(HI ×T )


=

X
F ∈T

|F |(−1)|F |−1 v(F ) +X
F,F \U1 (F )∈HIXv(F ) X (−xy)n q (n+1
2 )
n≥0

(8)

U1 (F )⊆U ⊆U2 (F )Recall that the generating function N ≡ N (x, y, q) :=was computed in [6]; its expression isN (x, y, q) =(−1)|U |  .

(q)n (xq)n|T |T ∈T (−1) v(T )P.

It is easy to see that the first sum in (8) is equal to −y∂y N . It is clearthat the terms in the second sum vanish when U1 6= U2 . It turns out thatthe remaining sum with U1 = U2 also vanishes, which can be proved by acomplicated involution that we skip due to space constraints. Therefore weare left with the equality
X
N×v(E) = −y∂y N,
(9)
E∈HI

from which we obtain that the generating function for HI is given by −y ∂yNN .
Finally we get the following general result.
Proposition 5.6 The generating function for periodic parallelogram polyominoes weighted withx#rows+#columns y #columns q area
is given by −y ∂yNN .
5.3

eBack to FC heaps in affine type A

Let P be a periodic parallelogram polyomino, associated with the sequence(ai , bi )1≤i≤n ; we first remove the bottom box of each of its columns, thereby
possibly obtaining columns of height zero. We then fill every box by a point,
and rotate
P the polyomino by 45 degrees clockwise. Points are now distributedon N = i (bi − ai + 1) vertical lines (repeated periodically), which we want toeN −1 . By picking an integer in the interval
match with generators in the type A[a1 , b1 ], we can determine unambiguously which vertical line corresponds to
the generator s0 , and obtain an alternating diagram of type ÃN −1 .
This construction (due to Viennot) transforms a pair (P, i), where P isa periodic parallelogram polyomino and i is an integer between a1 and b1 ,in an alternating diagram. It is defined except when all columns of P haveequal length, are aligned, and i is equal to the commun length of the columns.
Moreover, it is bijective onto the disjoint union of alternating diagrams ofeN −1 over all N .
Ae as for the periodic
From this we obtain an enumeration formula for A
parallelogram polyominoes if we take into account a little shift due to then boxes removed, a derivative with respect to x instead of y because of theinteger i ∈ [a1 , b1 ], and a corrective term due to the forbidden polyominoes.
More precisely we first get through Proposition 5.4:
e=
A

X
H∈HI∗

x`(H) q e(H)−|H| −X xn q n
1 − qn
n≥1

,

(10)

Fig. 7. From a periodic parallelogram polyomino to an alternating diagram.

where HI∗ is the set of heaps H ∈ HI such that the rightmost maximal segment
is marked on one of its points (recall that by Lemma 5.1 this segment is[a1 , b1 ]). To handle the first sum in this expression, one needs to consider amarked version of Lemma 5.5.
Lemma 5.7 We have:X

y |H| x`(H) q e(H) = −x

H∈HI∗

∂x N
.
N

To prove this result, we examine the image φ(H, T ) = (F, T ) where H ∈ HI∗
and T ∈ T , as in Lemma 5.5, where the marked segment in H naturally
becomes a marked segment in F . Each step in the argument of Section 5.2
is still valid by replacing HI by HI∗ , noting that, when F is trivial, any of its
segments can be marked. When F is not trivial, we also obtain in this case asum that vanishes. Therefore we get

!
X
X
X
(−1)|T | v(T ) 
v(E) =`(F )(−1)|F |−1 v(F ),
(11)
T ∈T

E∈HI∗

F ∈T

from which we derive the result. Summarizing, Lemma 5.7 and (10) togetheryield
X xn q n
J 0 (x) X xn q ne = −x ∂x N (x, 1/q, q) −
=
−x
−
.
A
N (x, 1/q, q)
1 − qnJ(x) n≥1 1 − q nn≥1

Acknowledgements
We would like to thank Mireille Bousquet-Mélou for suggesting the problem tous and for many valuable suggestions given in the earlier stage of this paper.

References[1] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. Some permutations withforbidden subsequences and their inversion number. Discrete Math., 234(1-3):1–
15, 2001.
[2] R. Biagioli, M. Bousquet-Mélou, F. Jouhet, and P. Nadeau.
Lengthenumeration of fully commutative elements in finite and affine Coxeter groups.
arXiv:1612.07591, 2016.
[3] R. Biagioli, F. Jouhet, and P. Nadeau. Combinatorics of fully commutative
involutions in classical Coxeter groups. Discrete Math., 338(12):2242–2259, 2015.
[4] R. Biagioli, F. Jouhet, and P. Nadeau. Fully commutative elements in finite andaffine Coxeter groups. Monatsh. Math., 178(1):1–37, 2015.
[5] S. C. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of
Schubert polynomials. J. Algebraic Combin., 2(4):345–374, 1993.
[6] M. Bousquet-Mélou and X. G. Viennot. Empilements de segments et qénumération de polyominos convexes dirigés. J. Combin. Theory Ser. A,
60(2):196–224, 1992.
[7] R. M. Green. On 321-avoiding permutations in affine Weyl groups. J. Algebraic
Combin., 15(3):241–252, 2002.
[8] C. R. H. Hanusa and B. C. Jones. The enumeration of fully commutative affine
permutations. European J. Combin., 31(5):1342–1359, 2010.
[9] G. Lusztig. Some examples of square integrable representations of semisimple
p-adic groups. Trans. Amer. Math. Soc., 277(2):623–653, 1983.
[10] G. X. Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas.
In Graph theory and its applications: East and West (Jinan, 1986), volume 576
of Ann. New York Acad. Sci., pages 542–570. New York Acad. Sci., New York,1989.