RHOMBIC TILINGS OF POLYGONS
AND CLASSES OF REDUCED WORDS IN COXETER GROUPS
 
Serge Elnitsky

(Note: this paper is based on the author's PhD thesis at the University of Michigan, 1993. Special thanks go to his supervisor, John R. Stembridge.)

	Abstract.  In the standard Coxeter presentation, the symmetric group Sn is generated by the adjacent transpositions (1,2), (2,3), ... , (n-1,n). For any given permutation, we consider all minimal-length factorizations thereof as a product of the generators. Any two transpositions (i,i+1) and (j,j+1) commute if the numbers i and j are not consecutive; thus, in any factorization, their order can be switched to obtain another factorization of the same permutation. Extending this to an equivalence relation, we establish a bijection between the resulting equivalence classes and rhombic tilings of a certain 2n-gon determined by the permutation. We also study the graph structure induced on the set of tilings by the other Coxeter relations. For a special case, we use lattice-path diagrams to prove an enumerative conjecture by G. Kuperberg and J. Propp (counting rhombic tilings of certain octagons), as well as a q‑analogue thereof. Finally, we give similar constructions for two other families of finite Coxeter groups, namely those of types B and D.

	1. Introduction
	This paper has two main goals: 1) establishing a connection between reduced words (or reduced decompositions) and rhombic tilings, and 2) proving an enumerative formula for tilings of a certain kind of octagons. Some definitions and history will help motivate what follows.
	A plane partition is defined as a matrix (mij) with non-negative integer entries and non-increasing rows and columns. It can also be thought of as a subset of (Z+)3, namely 
P = {(i,j,k) : 1 ≤ k ≤ mij};
it is clear that if (a,b,c) Œ P, then P contains the entire a ¥ b ¥ c box 
{(i,j,k) : 1 ≤ i ≤ a, 1 ≤ j ≤ b, 1 ≤ k ≤ c}. 
Several symmetry operations can be defined on plane partitions: reflections in the planes x = y, x = z, y = z; rotations of 120° and 240° around the axis x = y = z; and, if the plane partition is considered to be inside an a ¥ b ¥ c box, complementation, i.e. replacement of P by 
Pc = {(a+1-i, b+1-j, c+1-k) : (i,j,k) œ P}.
Much work has been done (see, for instance, [8], [13], and [14]) to enumerate plane partitions that fit inside given a ¥ b ¥ c boxes and possess given symmetry groups. 
	It is sometimes useful to regard the plane partition as composed not of lattice points, but of unit cubes in R3. In that case, if observed from a point (n,n,n) with n large, a plane partition clearly corresponds to a tiling of a (convex) hexagon by rhombi. (Figure 1; see also [3].) The hexagon has angles of 120° and sides of lengths a, b, c, a, b, c; the rhombi are unions of pairs of equilateral triangles with sides of length 1. All the symmetry properties for plane partitions translate naturally to similar properties for tilings; in particular, as in figure 1, invariance under complementation corresponds to central symmetry. 

    fig. 1

	In [8], Greg Kuperberg used this point of view. After converting a plane partition to a rhombic tiling of a hexagon, he considered that tiling as a break-up of the set of underlying unit equilateral triangles into adjacent pairs, i.e., a perfect matching in a graph whose vertices are the triangles, two vertices being adjacent if the triangles are. He then applied the so-called permanent-determinant and Hafnian-Pfaffian methods to enumerate such perfect matchings.
	The next logical step was to look at tilings of an octagon; in this case, the methods mentioned above do not apply. Kuperberg and James Propp conjectured [9] that for an octagon with angles of 135° and sides of lengths a, b, 1, 1, a, b, 1, 1, the number of possible rhombic tilings was

	We prove this formula, as well as a q-analogue, in sections 4 and 5, and in the process (section 2; see also sections 6 and 7) exhibit another interpretation of rhombic tilings. 
	Another important definition we need to mention is that of a Coxeter group. A Coxeter group is a group W that has the following kind of presentation:
W = < s1, ... , sn : (sisj)m(i,j) = 1 for all i,j >,
where m(i,i) = 1 for all i, and m(i,j) ≥ 2 if i π j. The Coxeter diagram of W is a graph in which the si are the vertices; si and sj are joined by an edge if m(i,j) ≥ 3, and that edge is labeled with m(i,j) if m(i,j) ≥ 4.
	For any w Œ W, the least k such that w can be written as w = si1si2 ... sik is called the length of w, and denoted by l(w). An ordered k-tuple z = (i1, i2, ... , ik), with w = si1si2 ... sik and k = l(w), is called a reduced word for w. 
	Suppose that (sisj)m(i,j) = 1, with i ≠ j, is one of the relations, and that z, a reduced word for w, has a consecutive subword (i, j, i, j, ... ), with a total of m(i,j) i's and j's. Then we can replace that subword by (j, i, j, i, ... ), obtaining a word z'; clearly, z' is also a reduced word for w. We call this procedure applying that relation to z. If C is a subset of the set of relations, two reduced words for w are called C-equivalent if one can be obtained from the other by applying a sequence of relations from C. The resulting equivalence classes are called C‑equivalence classes.
	The following facts, the proofs of which can be found in [1] or [7], will be assumed.
	(1.1) FACT.  If W is a finite Coxeter group and C is the set of relations (sisj)m(i,j) = 1 for all i ≠ j, then for any w Œ W, any two reduced words are C‑equivalent.
	(1.2) FACT.  The symmetric group Sn is a Coxeter group, generated by t1, ... , tn-1 (with ti corresponding to the transposition (i, i+1)), subject to the following 3 sets of relations:
			C0:  ti2 = 1, for all i;
			C1:  titj = tjti, whenever |i-j| > 1;
			C2:  titi+1ti = ti+1titi+1, for all 1 ≤ i ≤ n-1.
	We prove in section 2 that for any permutation s Œ Sn, the set of C1‑equivalence classes of reduced words for s is in a one-to-one correspondence with the set of rhombic tilings of a certain polygon determined by s. (For the special case of the order-reversing permutation w0, discussed in section 3, a related correspondence was given by Günter Ziegler in [16]).
	We can also consider these C1-equivalence classes as vertices of a graph, where two classes are adjacent if a member of one is C2-equivalent to a member of the other. In section 3, we will see that this graph is connected and bipartite. For the special case of w0, this graph (also considered as a ranked poset) has occurred in the study of quantum groups (A. Berenstein and A. Zelevinsky, [2]), as well as that of the higher Bruhat orders (G. Ziegler, [16]; Yu. Manin and V. Schechtman, [10]; and others). 
	Finally, in sections 6 and 7, we give similar constructions for two other families of Coxeter groups, namely those of type B and D.

	2. The bijection between tilings and C1-equivalence classes in Sn
	For any s Œ Sn, let X(s) be a 2n-gon, with all sides having length 1, as follows. Let M be the uppermost vertex; the first n sides counter-clockwise from M, labelled 1, 2, ... , n, form one half of a regular 2n-gon, whereas the first n sides clockwise from M, labelled s(1), s(2), ... , s(n), are arranged so that sides with equal labels are parallel. (See figure 2.)

fig. 2

	(REMARK. The actual values of the side lengths and angles are actually immaterial, and will sometimes be modified for convenience; all we need is for the left-hand side of X(s) to be convex, and for any two identically-labelled sides to be parallel and of same length.)
	We let T(s) denote the set of tilings of X(s) by rhombi with sides of length 1. For a given tiling of X(s), let any path joining M to its antipode M' and consisting of precisely n tile edges be called a border.
	(2.1) LEMMA.  Any border, except the rightmost, has at least one tile which touches it with 2 sides, from the right.
	PROOF.  Let us first suppose that the border has no sides in common with the rightmost one. Draw horizontal lines through M and M’, and consider the sum of all the angles shown in figure 3. On one hand, that sum clearly equals 180n°. But, if no tile touches the border with 2 sides, then there must be n distinct tiles touching it with one side each, and each contributing 180°; also, the very first and very last angles are positive, and do not belong to any tile, thus making the sum greater than 180n°. Hence some tile must touch the border with 2 sides.

  fig. 3

	If some edges of the border are also part of the rightmost one, we can pick a maximal subsequence of consecutive edges that are not, and apply the same argument as above.  n
	In the standard presentation (1.2), let W(s) be the set of reduced words for s; let V(s) be the set, and N(s) the number, of C1-equivalence classes in W(s). 
	(2.2) THEOREM.  There exists a bijection between T(s) and V(s). 

	      fig. 4

	PROOF.  In any specific rhombic tiling of X(s), we may order the tiles as follows: 1) take the leftmost border; 2) assign the number "1" to some tile that touches the border with 2 sides; 3) replace, in the border, those 2 sides with the other 2 sides of the tile; 4) assign the number "2" to some tile that touches the new border with 2 sides, from the right; and so on, until the border equals the rightmost one. (See figure 4.) Let U(s) be the union of the sets of such orderings of tilings of X(s), taken over all the possible tilings.
	Each step in the above procedure corresponds to applying a ti to the border, viewed (if read from top to bottom) as a permutation of [n] = {1, ... , n}. Let zk equal i, where ti is the transposition applied at the k-th step. This gives a word z = (z1, z2, ... , zm), with tz1tz2 ... tzm = s.
	For each pair (i,j) such that i < j but s(i) > s(j), the interchange of i and j must be performed by an (i,j)-tile, that is, a tile with sides labelled i and j. Once i and j have been switched, the (right-hand-side) angle they form becomes greater than 180°, so they clearly can never be switched back by a tile touching the border from the right. Thus m, the total number of tiles, equals inv(s), implying that z is indeed a reduced word; the presence or absence of each kind of tile depends on s only, rather than on the specific tiling used.
	Conversely, any z Œ W(s) can be reinterpreted to give an ordered tiling of X(s). We can simply start with the leftmost border, and then add tiles to it, from the right, according to the entries of z. (Since z is a reduced word, we always have 
l(tz1tz2 ... tzi-1tzi) > l(tz1tz2 ... tzi-1),
so, when the time comes to place the i-th tile, the zi-th edge of the border has a lesser label than the (zi+1)-st one; thus the tile can be placed on the right side of the border.) Thus, we have a bijection between U(s) and W(s).
	Now, if z differs from z' by the interchange of zk and zk+1, with |zk ‑ zk+1| > 1, then the k-th and (k+1)-st tiles of the ordered tiling corresponding to z lie on a common border but have no common sides; their numbers can thus be safely interchanged without affecting anything else. So the ordered tilings corresponding to z and z' differ only by the ordering of the tiles, and hence the same is true for any C1-equivalent z and z'.
	Conversely, we need to show that any two valid orderings (A and B, say) of a tiling correspond to C1-equivalent words. Let m be the number of tiles. If the m-th tile of A (t, say) is the k-th tile of B, with k < m, then look at the (k+1)-st tile of B (t', say). Since t and t' are consecutive in B, they must be on some common border; however, since t came before t' in B and t' came before t in A, they cannot have a common side. Hence, if z is the word corresponding to B, we have |zk - zk+1| > 1; so we can interchange, in B, the labels "k" and "k+1", which will switch zk and zk+1. Repeat this until the m-th tile of A is also the m-th tile of B; induction takes care of the rest.
	Thus, z and z' are C1-equivalent if and only if the ordered tilings corresponding to z and z' are orderings of the same tiling. Hence we have a bijection between V(s) and T(s).  n
	The following recursive formula is due to Victor Reiner [11]. (We will not use it in this paper.)
	For any s Œ Sn, define the descent set D(s) := {i : s(i) > s(i+1)}.
	(2.3) PROPOSITION. If s is the identity permutation, then N(s) = 1; otherwise,

	PROOF.  Let T(i,s) be the set of rhombic tilings of X(s) which have a tile touching the i-th and (i+1)-st edges of the rightmost border. (Of course, T(i,s) is empty if i œ D(s).) Now, for any ∆ ≠ A Õ [n-1],

 is clearly in bijection with 

if A Õ D(s) and |i-j| > 1 for all i, j Œ A, and empty otherwise. Apply the Inclusion-Exclusion Principle.  n

	3. T(s) as a graph and the case s = w0(n) 
	Let us consider T(s) as the set of vertices of a graph, where two tilings are adjacent if one of them can be obtained from the other by "flipping" a sub-hexagon made up of 3 rhombi (see figure 5).
	(3.1) PROPOSITION.  T(s) is connected.
	PROOF.  By (1.1), one can get from any reduced word for s to any other by repeatedly applying relations of type C1 and C2. Applying C1 corresponds to going between different orderings of the same tiling; and it is easy to see that applying C2 corresponds to flipping sub-hexagons. Thus, it is possible, by means of such hexagon-flips, to get from any tiling of X(s) to any other.  n

                        fig. 5

	(3.2) PROPOSITION.  T(s) is bipartite.
	PROOF.  For any reduced word, consider the sum of its entries: it is obviously constant on each C1-equivalence class, but its parity is changed by applying C2.  n
	Let a tiling T of X(s) be given. For each i Œ [n], the tiles which have a side parallel to the i-th side of the left border of X(s) form a strip, joining that i-th side to the side parallel to it on the right border. (See figure 6, i = 3.)

 fig. 6

Define
Inv(s, i) := { j Œ [n] : (i-j)(s(i)-s(j)) < 0 }.
(Note that the strip consists of precisely Inv(s, i) tiles.) For any i Œ [n], let si be the permutation induced by s on [n]\{i}. (We think of permutations as linear orderings; so, if ) 
	(3.3) LEMMA.  Fix i Œ [n]. There is a bijection between T(s) and the set of pairs (T',p), where T' Œ T(si), and p is a path in T', connecting the (i-1)-st vertex counter-clockwise from M and the (s(i)-1)-st vertex clockwise from M, and consisting of |Inv(s, i)| edges.
	PROOF.  For any tiling of X(s) (figure 7a), the strip corresponding to i can be shrunk down to a path (7b, i = 3). We can then bend the angles slightly, so as to make the left-hand side regular; the result is a tiling of X(si), with a path as specified above. Conversely, if we choose such a path in a tiling of X(si), we can thicken it to a strip and thus obtain a tiling of X(s).  n

 fig. 7

	Now, let s = w0(n), the order-reversing permutation in Sn; X(s) is then a regular 2n-gon.
	(3.4) COROLLARY.  The number of tilings of X(w0(n)) equals the sum, over all tilings of X(w0(n‑1)), of the number of borders.
	PROOF.  Let i = n in Lemma (3.3). Then si = sn = w0(n‑1); the path p connects M and M', and consists of n‑1 edges, so it is a border in T' Œ T(w0(n‑1)).  n
	REMARK.  Since it is bipartite, the graph T(w0(n)) may be considered as the Hasse diagram of a ranked poset, the rank of each vertex equaling its distance from some fixed vertex. If that fixed vertex is chosen to be the tiling shown in figure 8 (n = 5), then the poset we obtain is the higher Bruhat order B(n,2), described in [10] and [16].

 fig. 8

	4. N(a1, ... , am) and lattice paths
	Let a1 + ... + am = n be positive integers, and suppose that s Œ Sn performs a permutation w Œ Sm on the m blocks {1, ... , a1}, {a1+1, ... , a1+a2}, ... , {a1+...+am-1+1, ... , n}, while preserving the consecutiveness and the order of the elements within each block. Then s can be thought of as a (special kind of) permutation of a multiset with ai copies of i,  for i = 1, ... , m. Since the different copies of the same i are not permuted among themselves, we can make the edges corresponding to them parallel. Thus X(s) is replaced by a 2m-gon resembling X(w), except that for each i, the i-th side counter-clockwise from M and the w(i)-th side clockwise from M have length ai. (See figure 9; in it, and in some subsequent figures, we will allow the point M to be elsewhere than at the top, for convenience, rather than rotate the entire polygon.)

  fig. 9

	The number of (i,j)-tiles will equal aiaj if the i-th and j-th blocks are switched by s (since each of the ai elements of the i-th has to be switched with each of the aj elements of the j-th), and 0 otherwise.
	If w = w0(m), the order-reversing permutation in Sm, then the 2m-gon X(s) is convex (see figure 10); we denote it by X(a1, ... , am), and the set and number of tilings thereof by T(a1, ... , am) and N(a1, ... , am), respectively. Since the point M can be situated at any vertex of the 2m-gon, it is clear that N(a1, ... , am) = N(ai, ... , am, a1, ... , ai-1) for any i.

   fig. 10

	In this case, the number of (i,j)-tiles will always be aiaj, so the total number of tiles is given by 

	As mentioned in the introduction, many enumerative results about plane partitions translate into results about tilings of convex hexagons. In particular, MacMahon proved that

where H(n) = (n-1)!(n-2)! ... (2)! is the hyperfactorial function. (For a modern proof, see [8].) We will now look at tilings of two special kinds of octagons.
	The following results can easily be generalized (see [5]) to the general case of  T(a,b,c,d). (Note: unlike fig. 1, the pictures below are not intended to be viewed 3-dimensionally.)
	(4.1) LEMMA.  There exists a bijection between T(a,b,1,1) and the set of lattice-path diagrams consisting of an a ¥ b grid with a light-colored path and a dark-colored path, both starting at (0,0) and ending at (a,b), and a distinguished crossing point (or root); at (0,0), the dark-colored path is above the light-colored one (if viewed from (a,0)), whereas at (a,b), the light-colored path is above the dark-colored one. (See fig. 11a,b,c; a = 5, b = 6)
	PROOF.  As in the proof of Lemma 3.3, we can shrink the dark-colored \-strip and light-colored _-strip so that they become paths, with a distinguished point marking the place of the unique (\,_)-tile. Then we bend the figure so as to make the grid into a rectangular one. This procedure can clearly be reversed, so it gives a bijection.  n
	(4.2) LEMMA.  There exists a bijection between T(a,1,c,1) and the set of lattice-path diagrams consisting of an a ¥ c grid with a light-colored path starting at (0,c) and ending at (a,0), a dark-colored path starting at (0,0) and ending at (a,c), and a distinguished crossing point (or root). (See fig. 11d,e; a = 5, c = 3)
	PROOF.  As above, we shrink the dark-colored \-strip and light-colored /-strip so that they become paths, with a distinguished point marking the place of the unique (/, \)-tile. Again, since it is clearly reversible, this procedure gives a bijection.  n

										fig. 11

	It follows immediately from (4.2) that 

	No closed formula is known for this sum. However, the following recurrence relation, first obtained by P. Brock, can be found in [15]:
	(4.3) PROPOSITION. 

	5. A q-analogue of N(a,b,1,1)
	Let us define the q-analogues

			
and so forth. Let T0 be the special tiling of X(a,b,1,1) shown in figure 13, and define N(a,b,1,1; q) to be a polynomial in q, in which the coefficient of qk equals the number of vertices at distance k from T0 in the graph T(a,b,1,1). We can now prove a stronger version of Kuperberg and Propp's conjecture, using the standard non-intersecting-path techniques of Gessel and Viennot [6].

	(5.1) THEOREM.  
	PROOF.  One first observes that under the bijection given in lemma 4.1, each hexagon-flip in a tiling corresponds either to "bending a corner" of one of the paths (figure 12a,b; note that this changes the area under that path by 1) or to moving the root by 1 (figure 12a,c). (The latter, of course, is not always possible; in figure 12a, for instance, the root can be moved only to the left.) We can define the distance between two a ¥ b lattice-path diagrams to be the minimal number of such moves needed to get from one to the other; this, of course, equals the distance between the corresponding tilings.

      fig. 12

	The tiling T0 that we have chosen is the one corresponding to a pair of paths with area 0, the root having coordinates (a,0). (See figure 13; denote this  

   fig. 13
lattice-path diagram by D0.) Thus, if we take any T Œ T(a,b,1,1) and the corresponding lattice-path diagram D, the distance from D to D0 is greater than or equal to the sum of the areas under the paths in D, plus the distance (in a taxi-cab metric) between its root ((i,j), say) and (a,0), namely a-i+j. It is also easy to see that it is, in fact, possible to get from D to D0 in that number of steps; so the distance from D to D0, and hence the distance from T to T0, is exactly equal to the sum of the areas plus a-i+j.
	The pairs of paths described in (4.1) are clearly in a one-to-one correspondence with (unordered) pairs of non-crossing paths from (0,0) to (a,b), together with a choice of root. (Simply interchange the two paths, starting at the root.) Since our pairs are now unordered, we need no longer distinguish the color of the paths. We will denote the set of such pairs by P(a,b).
	Another observation, illustrated in figure 14, is that there exists a bijection between P(a,b) and P'(a,b), the set of pairs of non-crossing paths, one from (0,0) to (a,b+1), the other from (0,0) to (a+1,b). Given an element of P(a,b), we can replace the root by an L-shaped pair of edges to get an element of P'(a,b). Conversely, given an element of P'(a,b), we can follow the paths from (0,0) to their last point of intersection, after which the paths must part company – one's next edge going up, the other one's next edge going to the right; we can

fig. 14

replace this L-shaped pair of edges by a root to get an element of P(a,b). Note that going from an element of P(a,b) to one of P'(a,b) increases the sum of the areas under the paths by precisely a-i+j, where (i,j) was the root; the extra area is shaded.
	Finally, we attach a weight of qk to each horizontal edge at height k, and a weight of 1 to each vertical edge. Thus, for a path p from (0,0) to (m,n), qarea(p) equals the weight of the path, defined as the product of the weights of its edges. It is also well-known (e.g., [12]), that

	Therefore,

(by the last observation)

(translate p' down by 1, and to the left by 1)

(interchange p'' and p''', starting at their first intersection)

(since any such p'' and p''' must intersect)

  n
	(See [5] for some enumerative results about tilings of X(a,b,1,1) and X(a,1,b,1) invariant under the various subgroups of the symmetry groups of the octagons, as well as some examples of the "q = -1" phenomenon, first mentioned in [14]. For instance, 

gives the number of tilings of X(a,b,1,1) which have central symmetry.)

	6.  A similar construction for Bn
	Figure 15 shows the Coxeter diagrams for the three main families of irreducible finite Coxeter groups: Sn (also known as An-1), Bn, and Dn.

    fig. 15

	Let us first consider Bn, the group generated by elements p0, p1, ... , pn-1, subject to the relations
			C0)  pi2 = 1, for all i;
			C1)  pipj = pjpi, whenever |i-j| > 1;
			C2)  pipi+1pi = pi+1pipi+1, for all 1 ≤ i ≤ n-2;
			C3)  p0p1p0p1 = p1p0p1p0.
	One realization of Bn (see [7]) is as the group of signed permutations of [n], where p0 changes the sign of the first object, and the other pi act like the adjacent transpositions ti in Sn. Another is as the subgroup of S2n (where the set of objects being permuted is ±[n] = {-n, ... , -2,-1,1,2, ... ,n}) generated by 
p0 = t0 = (-1,1)
and 
pi = tit-i = (i,i+1)(-i,-i-1)  for  1 ≤ i ≤ n-1.
(Note that second half of this kind of permutation is precisely a signed permutation of [n].) Yet another realization is as a matrix group, generated by

	It is the second realization which will be the most useful to us. For any r Œ Bn, let s be the corresponding permutation in S2n; let X(r) := X(s), and let T(r) be the set of horizontally-symmetric rhombic tilings of X(r). 
	(For instance, if

one possible tiling of the corresponding 12-gon is shown in figure 16.)

fig. 16

	We will, for the rest of this section, use the word tile to mean either a single rhombus situated on the horizontal symmetry axis, or a pair of rhombi symmetric with respect to that axis.
	Let V(r) denote the set, and N(r) the number, of C1-equivalence classes of reduced words z = (z1, ... , zm), such that pz1 ... pzm = r. (For instance, for the r used in the example above, one such word is (0, 2, 1, 0, 1, 2, 1).)
	(6.1) THEOREM.  There exists a bijection between T(r) and V(r).
	PROOF.  As in the proof of Theorem (2.2), we first seek to establish a bijection between reduced words for r and valid horizontally-symmetric ordered tilings of X(r). Let s Œ S2n be the permutation corresponding to r. Given a reduced word z = (z1, ... , zm) for r Œ Bn, we can do the following: take the leftmost border of X(r) = X(s); then, for each zk, perform on the border the transposition, or pair thereof, corresponding to pzk. If we assume for the moment that the border will always move to the right, then, if we label the tile created at step k with the number k, it is clear that we will get an ordered, horizontally-symmetric tiling of X(r). Conversely, any such ordered tiling can be reinterpreted to give a word for r; it will be a reduced word provided that, at each step, the length of the element of Bn recorded by the border increases.
	Thus, all we need to verify is that for any r Œ Bn, l(rpi) > l(r) if and only if the border corresponding to rpi is to the right of the one corresponding to r.
	(6.2) FACT.  The length function on Bn (considered as the group of signed permutations of [n]) is 
l(r) = f(r) + g(r) + h(r), 
where
			f(r) = #( j : j > 0, r(j) < 0),
			g(r) = #( (j, k) : j < k, r(j)+r(k) < 0 ),
			h(r) = #( (j, k) : j < k, -r(j)+r(k) < 0 ).
	(This is a special case of the geometric interpretation of the length function in a reflection group; see [7], section 1.6).
	Armed with (6.2), we can simply check all the cases, shown in figure 17 and Table I; here, a, b Œ [n], a < b. 
	Case 1 (figure 17a). If r(1) = a, then multiplying r by p0 will increase f(r) by 1, while clearly not changing the contribution of pairs (1, k) to the sum g(r)+h(r); as we had hoped, the border moves to the right.
	Case 1' (17a). If r(1) = -a, then multiplying r by p0 will decrease f(r) by 1, while clearly not changing the sum g(r)+h(r); the border moves to the left.
	Case 2 (17b). If r(i) = a and r(i+1) = b, then multiplying r by pi will not change f(r) and g(r), while increasing h(r) by 1; the border moves to the right.
	Case 2' (17b). If r(i) = b and r(i+1) = a, then multiplying r by pi will not change f(r) and g(r), while decreasing h(r) by 1; the border moves to the left.
	The remaining 6 cases (17c,d,e) are similar.

fig. 17

	Gene-	Effect on lower	Fig.	D l(r)	D inv(s)
	rator	half of border	17	

	p0		a	+1	+1
	pi, i >0		b	+1	+2
	pi, i >0		c	+1	+2	
	pi, i >0		d	+1	+2
	pi, i >0		e	+1	+2
						Table I

	Now that we have a bijection between reduced words for s and valid ordered tilings of X(s), we need to show that two words are C1-equivalent if and only if they correspond to different orderings of the same tiling. We can essentially repeat the argument from the proof of Theorem 2.2, replacing "C1" with "C1".
	If z differs from z' by the interchange of zk and zk+1, with |zk ‑ zk+1| > 1, then the k-th and (k+1)-st tiles of the ordered tiling corresponding to z lie on a common border but cannot be adjacent; their numbers can thus be safely interchanged. So the ordered tilings corresponding to z and z' differ only by the ordering of the tiles, and hence the same is true for any C1-equivalent z and z'.
	Conversely, let A and B be two valid orderings of the same tiling consisting of m tiles. If the m-th tile of A (t, say) is the k-th tile of B, with k < m, then look at the (k+1)-st tile of B (t', say). Since t and t' are consecutive in B, they must be on some common border; however, since t came before t' in B and t' came before t in A, they cannot be adjacent. Hence, if z is the word corresponding to B, we have |zk - zk+1| > 1; so we can interchange, in B, the labels "k" and "k+1", which will switch zk and zk+1. Repeat this until the m-th tile of A is also the m-th tile of B; induction takes care of the rest.
	This gives us the desired bijection between V(s) and T(s).  n
	(6.3) COROLLARY (of proof).  The word z = (z1, ... , zm) is a reduced word for r Œ Bn if and only if the word w, obtained from z by inserting -i after each positive entry i, is a reduced word for the corresponding r Œ S2n.  n
	Let the set of horizontally-symmetric tilings of a 4n-gon be considered as a graph, where two tilings are adjacent if they differ by either
	1) a horizontally-symmetric pair of hexagon-flips, or
	2) an octagon-flip (see figure 18), for a sub-octagon centered on the symmetry axis.

    fig. 18

	(6.4) PROPOSITION.  The graph defined above is connected.
	PROOF.  By (1.1), one can get from any reduced word for s to any other by repeatedly applying relations of type C1, C2, and C3. Applying C1 corresponds to going between different orderings of the same tiling; applying C2 corresponds to flipping horizontally-symmetric pairs of sub-hexagons; applying C3 corresponds to  flipping sub-octagons. Thus, it is possible, by means of such hexagon-flips and octagon-flips, to get from any tiling of X(s) to any other.  n
	(6.5) PROPOSITION.  If w0(Bn) is the element of Bn which reverses all the signs, then the number of tilings of X(w0(Bn)) equals the sum, over all tilings of X(w0(Bn‑1)), of the number of pairs of non-crossing paths of length n-1, connecting M to some (common) point on the horizontal symmetry axis.
	PROOF.  For any tiling of X(w0(Bn)), a regular 4n-gon (figure 19a), the two strips corresponding to n and -n (which cross exactly once, on the symmetry axis) can be removed (19b) and the remaining parts joined together (19c). The result is (after a slight bending of the angles) a tiling of X(w0(Bn‑1)) (19d); above the symmetry axis, the pair of paths along which the tiling was joined obviously is as described above. Conversely, if we choose such a pair of paths in a tiling of X(w0(Bn‑1)), we can insert a pair of strips and thus obtain a tiling of X(w0(Bn)).  n
	
fig. 19

	7.  A similar construction for Dn
	Now, we consider Dn, the group generated by elements q0, q1, ... , qn-1, with the relations
			C0)  qi2 = 1, for all i;
			C1)  qiqj = qjqi, if  |i-j| > 1  and  {i,j} ≠ {0,2};
			C2)  qiqi+1qi = qi+1qiqi+1,  if i ≥1;
			C3)  q0q1 = q1q0;
			C4)  q0q2q0 = q2q0q2.
	One realization of Dn (see [7]) is as the subgroup of Bn consisting of those signed permutations that have evenly many minus signs. In this case, q0 changes the signs of the first two objects and also transposes them; the other qi are the same as pi in the realization of Bn. Similarly, there is a realization of Dn as a subgroup of S2n, with

q0 = ,
and the other qi equal to the pi of Bn; and a matrix realization, in which q0 corresponds to 

	We will, once again, use the second realization to construct tilings, just as we did for Bn. We notice, however, that if r Œ Dn corresponds to 
(... -s  -t  t  s ...) Œ S2n 
with s, t Œ ±[n], then rq0 corresponds to 
(... t  s  -s  -t ...) Œ S2n. 
Hence q0 must be represented not by a simple tile or pair of tiles, but by a megatile, a non-convex octagon placed on, and symmetric about, the horizontal symmetry axis. Figure 20 shows the possible shapes of a megatile, for all the possible values of s and t, letting 1 ≤ a < b ≤ n.

 fig. 20

	Furthermore, in the latter cases, the megatile can be self-intersecting (figure 21). This would seem to be disastrous, at least from an aesthetical point of view; fortunately, it can be easily corrected.

 fig. 21

	Without loss of generality, let us take case c) of figure 20. What we need is for the segment KL not to intersect the segment IJ (figure 22a). Let N be the 4th vertex of a parallelogram whose other vertices are J, K, and L, and let l be a line parallel to IJ and passing through N. If K is to the right of l, then clearly KL and IJ will not intersect.
	Since JK has length 1, K is on a circle with centre J and radius 1. Recall that the slopes of JN and l are opposite. So, if the slope of JN is greater than  = tan 60°, the arc that includes K will be to the right of l. (See figure 22b).

fig. 22

	Thus, if the slopes of all the sides of the 4n-gon are greater than  (in absolute value), there is no danger of self-intersection.
	For any r Œ Dn, let s be the corresponding permutation in S2n; let X(r) := X(s). Let T(r) be the set of horizontally-symmetric tilings of X(r) by means of rhombi (which cannot be on the horizontal axis) and megatiles. (For instance, one tiling of X(r), where r is the one used in the example in section 6, is shown in figure 23).

fig. 23

	We will, for the rest of this section, use the word tile to mean either a megatile centred on the horizontal symmetry axis, or a pair of rhombi symmetric with respect to that axis.
	Let V(r) denote the set, and N(r) the number, of C1-equivalence classes of reduced words z = (z1, ... , zm), such that qz1 ... qzm = r. (For instance, in the example above, one such word is (0, 2, 1, 2, 1).)
	(7.1) THEOREM.  There is a bijection between T(r) and V(r).
	PROOF.  As before, we first find a bijection between reduced words for r and valid horizontally-symmetric ordered tilings of X(r). Given a reduced word z = (z1, ... , zm) for r Œ Dn, we can do the following: take the leftmost border of X(r) = X(s); then, for each zk, perform on the border the transformation corresponding to qzk. If we assume for the moment that the border will always move to the right, then, if we label the tile created at step k with the number k, it is clear that we will get an ordered, horizontally-symmetric tiling of X(r). Conversely, any such ordered tiling can be reinterpreted to give a word for r; it will be a reduced word provided that, at each step, the length of the element of Dn recorded by the border increases.
	Thus, all we need to verify is that for any r Œ Dn, l(rqi) > l(r) if and only if the border corresponding to rqi is to the right of the one corresponding to r.
	(7.2) FACT.  The length function on Dn (considered as a group of signed permutations of [n]) is 
l(r) = g(r) + h(r), 
where g(r) and h(r) are as they were defined in section 6.
	(As with (6.2), this is a special case of the geometric interpretation of the length function in a reflection group; see [7], section 1.6).
	The effects of multiplying r by the generators q1, ... , qn-1 are the same as the effects of p1, ... , pn-1 in the case of Bn (since none of them affect f(r)). Thus we only need to look at multiplication by q0. Figure 20 and Table II show all the possibilities for q0, with 1 ≤ a < b ≤ n.
	Case 1 (figure 20a). If r(1) = a and r(2) = b, then multiplying r by p0 will not change the total contribution of pairs (1, k) and (2, k) to the sum g(r)+h(r), nor the contribution of the pair (1, 2) to h(r), while the contribution of the pair (1, 2) to g(r) increases by 1; as we had hoped, the border moves to the right.
	Case 1' (20a). If r(1) = -b and r(2) = -a, then multiplying r by p0 undoes what was done in Case 1; so l(r) decreases by 1, and the border moves to the left.
	The remaining 6 cases (20b,c,d) are similar.

	Effect on lower	Fig. 	D l(r)	D inv(s)	
	half of border	20

		a	+1	+4
		b	+1	+4
		c	+1	+2
		d	+1	+2	     
						Table II
	Now that we have a bijection between reduced words for s and valid ordered tilings of X(s), we need to show that two words are C1-equivalent if and only if they correspond to different orderings of the same tiling. Once again, we use the argument from the proof of Theorem 2.2, mutatis mutandis.
	If z differs from z' by the interchange of zk and zk+1, with |zk ‑ zk+1| > 1 and {zk, zk+1} ≠ {0, 2}, then the k-th and (k+1)-st tiles of the ordered tiling corresponding to z lie on a common border but cannot be adjacent; their numbers can thus be interchanged. So the ordered tilings corresponding to z and z' differ only by the ordering of the tiles, and hence the same is true for any C1‑equivalent z and z'.
	Conversely, let A and B be two valid orderings of the same tiling consisting of m tiles. If the m-th tile of A (t, say) is the k-th tile of B, with k < m, then look at the (k+1)-st tile of B (t', say). Since t and t' are consecutive in B, they must be on some common border; however, since t came before t' in B and t' came before t in A, they cannot be adjacent. Hence, if z is the word corresponding to B, we have |zk - zk+1| > 1, and {zk, zk+1} ≠ {0, 2}; so we can interchange, in B, the labels "k" and "k+1", which will switch zk and zk+1. Repeat this until the m-th tile of A is also the m-th tile of B; induction takes care of the rest.
	This gives us the desired bijection between V(s) and T(s).  n
	Let T(r) be considered as a graph, where two tilings are adjacent if they differ by either a horizontally-symmetric pair of hexagon-flips, or by an operation shown in figure 24a or 24b.

 fig. 24

	(7.3) PROPOSITION.  The graph defined above is connected.
	PROOF.  By (1.1), one can get from any reduced word for s to any other by repeatedly applying relations of type C1, C2, C3, and C4. Applying C1 corresponds to going between different orderings of the same tiling; applying C2 corresponds to flipping horizontally-symmetric pairs of sub-hexagons; C3 and C4 correspond to the operations in figure 24a and 24b, respectively. Thus, it is possible, by means of all of these operations, to get from any tiling of X(s) to any other.  n

BIBLIOGRAPHY

1.  	N. BOURBAKI, “Groupes et Algèbres de Lie,” Chap. 4, 5, 6. Masson, 1981.
2.  	A. BERENSTEIN and A. ZELEVINSKY, String Bases For Quantum Groups of Type Ar, preprint.
3.  	G. DAVID and C. TOMEI, The Problem of the Calissons, Amer. Math. Monthly 96 (1989), 429-434.
4.  	P. H. EDELMAN, Lexicographically First Reduced Words, preprint.
5.  	S. ELNITSKY, “Rhombic Tilings of Polygons and Classes of Reduced Words in Coxeter Groups,” PhD dissertation, University of Michigan, 1993.
6.  	I. M. GESSEL and G. VIENNOT, Determinants, Paths, and Plane Partitions, preprint.
7.  	J. E. HUMPHREYS, “Reflection Groups and Coxeter Groups,” Cambridge University Press, 1990.
8.  	G. KUPERBERG, Symmetries of Plane Partitions and the Permanent-Determinant Method, preprint.
9.  	G. KUPERBERG, Private communication.
10.	YU. I. MANIN and V. V. SCHECHTMAN, Higher Bruhat Orders, Related to the Symmetric Group, Funct. Anal. Appl. 20 (1986), 148-150.
11.	V. REINER, Private communication.
12. 	R. P. STANLEY, “Enumerative Combinatorics, vol. I,” Wadsworth & Brooks/Cole, 1986.
13. 	R. P. STANLEY, Symmetries of Plane Partitions, J. Combin. Theory, Ser. A, 43 (1986).
14. 	J. R. STEMBRIDGE, Some Hidden Relations Involving the Ten Symmetry Classes of Plane Partitions, J. Combin. Theory, Ser. A, to appear.
15.	V. STREHL, Combinatorics of Special Functions: Facets of Brock's Identity, in “Séries formelles et combinatoire algébrique,” ed. by P. Leroux and C. Reutenauer, UQAM, 1992.
16. 	G. M. ZIEGLER, Higher Bruhat Orders and Cyclic Hyperplane Arrangements, Topology 32 (1993), 259-279.