Descending plane partitions and rhombus

tilings of a hexagon with triangular hole

C. Krattenthaler^{†}

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France.

                WWW: http://igd.univ-lyon1.fr/~kratt

Abstract. It is shown that the descending plane partitions of Andrews can be geometrically realized as cyclically symmetric rhombus tilings of a certain hexagon of which a centrally located equilateral triangle of side length 2 has been removed. Thus, the lattice structure for descending plane partitions, as introduced by Mills, Robbins and Rumsey, allows for an elegant visualization.

1. Introduction. Descending plane partitions were introduced by Andrews [1] in his attempt to prove Macdonald’s conjecture on the q-enumeration of cyclically symmetric plane partitions. (In [1], Andrews only succeeded to prove the q = 1 case of the conjecture; the full conjecture was later proved by Mills, Robbins and Rumsey [7].) It came as a big surprise, when Mills, Robbins and Rumsey discovered in [8] that there are, apparently, also close connections of descending plane partitions to alternating sign matrices. However, the corresponding conjectures of [8] still remain mysteries.

In the recent paper [6], Lalonde showed that descending plane partitions can be nicely encoded in terms of families of non-intersecting lattice paths. In this encoding, the natural lattice structure of descending plane partitions, that had been introduced in [8], has a rather straight-forward realization. In particular, the unique antiautomorphism of the lattice, which in [8] has a rather complicated definition, can be defined in very simple terms.

The purpose of this note is to point out that there is an even more striking realization of descending plane partitions, in terms of rhombus tilings of a hexagon of which a centrally located equilateral triangle of side length 2 has been removed. In this picture, the lattice structure, and particularly the antiautomorphism, become even more transparent. In addition, this interpretation extends effortlessly to the more general d-descending plane partitions of Andrews (the case d = 0 corresponding to descending plane partitions), thus implying analogous results for these more general objects.

2000 Mathematics Subject Classification. Primary 05A15.

Key words and phrases. descending plane partitions, rhombus tilings of a hexagon.

†Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe,” and by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

2. Descending plane partitions. A descending plane partition is an array π of positive integers of the form

\begin{matrix}π_{1,1} & π_{1,2} & . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . & π_{1,λ_{1}} \\ π_{2,2} & . . . . . . . . . . . . . . . . . . . . . . . . . . . & π_{2,λ_{2}} \\ ... & ... \\ π_{k,k} & … & π_{k,λ_{k}} \end{matrix}  (2.1)

such that (1) λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} ≥ k,

(2) the entries along rows are weakly decreasing,

(3) the entries along columns are strictly decreasing,

(4) the first entry in each row does not exceed the number of entries in the preceding row but is greater than the number of entries in its own row.

A typical example is the array

6 6 6 4 2 5 3 2 1 2 .  (2.2)

(This is, in fact, the running example D_{0} in [6].) Andrews [1, Theorem 10] has shown that the number of descending plane partitions with entries ≤ n is equal to

∏_{i=1}^{n} ∏_{j=1}^{n} \frac{n + i + j − 1}{2i + j − 1}.

Mills, Robbins and Rumsey also defined certain statistics on descending plane partitions. (The enumeration with respect to these statistics is conjecturally identical with the enumeration of alternating sign matrices with respect to certain other statistics, see [8, Conj. 3].) Let us call an entry π_{i,j} of a descending plane partition special, if π_{i,j} ≤ j − i. Thus, the special entries in the descending plane partition in (2.2) are the 2 in the first row and the 2 and 1 in the second row. For a given descending plane partition π with entries ≤ n, the statistics introduced in [8] are

• the number of entries of π which equal to n, denoted by r(π);

• the number of special entries of π, denoted by s(π);

• the total number of entries of π, denoted by i(π). For the example in (2.2), we have r(D_{0}) = 3, s(D_{0}) = 3, and i(D_{0}) = 10. The lattice structure on descending plane partitions with entries ≤ n is given by

the following partial order: given two descending plane partitions π and σ, we define π ≤ σ if, for all i and j, whenever π_{i,j} exists then σ_{i,j} also exists and, in addition, π_{i,j} ≤ σ_{i,j}. We shall not recall the definition of the antiautomorphism τ given in [8] here. For our purposes, it will suffice to note that it is shown in [8] that it is unique, and that, for any descending plane partition π with entries ≤ n it satisfies the following properties:

r(π) + r(τ(π)) = n − 1,  (2.3)
s(τ(π)) = s(π),  (2.4)
i(π) + i(τ(π)) = \binom{n}{2} + s(π).  (2.5)

3. Rhombus tilings and descending plane partitions. In this section we show that descending plane partitions with entries ≤ n are in bijection with cyclically symmetric rhombus tilings of a hexagon with side lengths n−1, n+1, n−1, n+1, n− 1, n + 1 of which a centrally located equilateral triangle with side length 2 has been removed. (In the hexagon, we assume that the angles between sides are 120^{∘}. See Figure 1 for the case that n = 6.) By a rhombus we always mean a rhombus with side lengths 1 and angles of 60^{∘} and 120^{∘}. Finally, a rhombus tiling is called cyclically symmetric, if it is invariant under rotation by 120^{∘}. A cyclically symmetric rhombus tiling of the hexagon with triangular hole in the case n = 6 is shown in Figure 2. (At this point, all shadings, as well as the thick and dotted lines should be ignored.)

Figure 1

Figure 2

To construct the announced bijection, given a rhombus tiling, we restrict the tiling to a fundamental region (see the region cut out by the thick lines in Figure 2), and we read off a family (P_{1}, P_{2}, …, P_{k}) (for some k) of non-intersecting lattice paths (the notion “non-intersecting” will be explained in a moment) consisting of horizontal unit steps in the positive direction and vertical unit steps in the negative direction, where P_{i} runs from (0, x_{i} + 2) to (x_{i}, 0), 0 ≤ x_{1} < x_{2} < ⋯ < x_{k}, in a way which is now standard (see e.g. [3, 4]). That is, we mark the rhombi of the tiling that are cut in two by the borders of the fundamental region (these are the shaded rhombi in Figure 2), and subsequently we connect the latter rhombi which are located along the left border with those rhombi which are located along the bottom border by paths. The paths result by connecting, for each horizontally oriented rhombus and for each rhombus oriented south-west/north-east, the midpoints of the two edges of the rhombus pointing from south-west to north-east. (In Figure 2, the paths are indicated by dotted lines.) These paths are finally deformed so that they become proper orthogonal lattice paths, see Figure 3. (The labels should be ignored at this point.) Since they come from a tiling, they are non-intersecting, meaning that any two paths have no point in common.

To extract the descending plane partition corresponding to the rhombus tiling, we read the heights of the horizontal steps along each path, including the height of the starting point of the path, but ignoring heights of 0 (in Figure 3, the heights to be read are the numbers in the figure), each path contributing one row of the corresponding descending plane partition. It is easy to verify that, in that manner, we do indeed obtain a descending plane partition, as well as that this correspondence is a bijection. In particular, as can be seen from a comparison of (2.2) and Figure 3, the descending

•  _{•}  _{•}  _{•}  _{•}  _{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•} • • • •  • •^{6} ^{6} ^{4} ^{2}^{3} ^{2} ^{1}^{6}^{5}^{2} Figure 3

plane partition corresponding to the rhombus tiling of Figure 2 is the array (2.2). (It can now be realized that the path picture is identical with the path figure in Figure 1 in [6], except that the first vertical strip of the grid there has been removed here, the latter being not necessary anyway, as it is forced).

It is easy to see that the number r(π) of entries of size n is the number of horizontally oriented rhombi in the upper-most strip of the fundamental region (should it be contained in the tiling, the horizontally oriented rhombus situated in the top-most position of the hexagon also counts; in the tiling in Figure 2 there are 3 horizontally oriented rhombi in the upper-most strip of the fundamental region), that the number s(π) of special entries is the number of horizontally oriented rhombi in the wedge cut off by the rays which emanate from the midpoint of one side of the triangle (see Figure 4; the rhombi corresponding to special entries are the three dark ones), and that the total number of entries i(π) is the number of horizontally oriented rhombi in the fundamental region except for rhombi which touch the lower border of the fundamental region (but including horizontally oriented rhombi cut in two by the border of the fundamental region; in the tiling in Figure 2 there are 10 such horizontally oriented rhombi in the fundamental region). We have to exclude the rhombi touching the lower border of the fundamental region because, under the translation between rhombus tilings and descending plane partitions via non-intersecting lattice paths, they would correspond to horizontal steps of height 0, which are ignored in the construction.

The partial order on descending plane partitions is also easily described on the corresponding rhombus tilings: a tiling T_{2} covers another tiling T_{1} if it results from T_{1} by a local replacement

⟶

in the fundamental region, or from the “special” replacement

⟶

in the neighbourhood of the removed triangle. The former does also include the replacement

⟶

along the left border of the fundamental region.

There is a canonical antiautomorphism on the rhombus tilings: the reflection of the tiling in the horizontal symmetry axis of the hexagon with triangular hole. (In fact, because of the cyclic symmetry of the tilings, the reflection in any of the 3 symmetry axes of the tiled region would yield the same result.) Since Mills, Robbins and Rumsey have shown in [8, Sec. 3] that there is a unique antiautomorphism on the lattice of descending plane partitions with entries ≤ n, denoted τ in [8], and since we have shown that this lattice is isomorphic to the lattice on rhombus tilings with the covering relations defined as described above, this reflection must correspond under this isomorphism to the antiautomorphism τ of [8].

The properties (2.3)–(2.5) can now rather easily been read off the geometric picture in terms of rhombus tilings. While going through the arguments below, the reader should always have an eye on Figures 2 and 4.

We begin with (2.3). We have seen that the statistics r(π) corresponds to the number of horizontally oriented rhombi in the upper-most strip of the fundamental region. In this upper-most strip, there are always exactly n−1 rhombi which touch the upper-right border of the hexagon along an edge, of which the first few are horizontally oriented, and the others are oriented downwards (to the right). Say, that there are k which are horizontally oriented. We now apply the reflection with respect to the horizontal symmetry axis. Thereby, these k rhombi are sent to the bottom-right border. By the cyclic symmetry, they correspond to k rhombi in the upper-most strip of the fundamental region which touch the upper-right border of the hexagon along an edge and which are oriented downwards. Consequently, there must be n − 1 − k horizontally oriented rhombi in the reflected tiling. The relation (2.3) follows.

Next we address (2.4). We have seen that the statistics s(π) corresponds to the number of horizontally oriented rhombi in the wedge cut off by the rays which emanate from the midpoint of one side of the triangle. If we apply the reflection with respect to the horizontal symmetry axis, then these rhombi stay in the wedge, and they are still horizontally oriented. This establishes the relation (2.4).

Finally, we come to the most subtle statistics (in terms of rhombus tilings), i(π). We have seen that i(π) corresponds to the number of horizontally oriented rhombi in the fundamental region except for rhombi which touch the lower border of the fundamental region. We now imagine that we superimpose the fundamental region, with the bottom-most strip excluded, and its mirror image with respect to the horizontal symmetry axis. Clearly, the union of the two is the region to the right of the vertical line which connects the top-most and the bottom-most point of the hexagon. For convenience, let us denote this region by R. We claim that, in R, the number of horizontally oriented rhombi (in this count we also include horizontally rhombi which are cut in two by the border of the fundamental region) is always the same, namely \binom{n}{2}. This is best seen by observing that this is the case for the special tiling in which all the horizontally oriented rhombi sit in the equilateral triangle with side length n − 1 on the top of R, and that all other tilings can be obtained from this special tiling by applying the local replacements explained just before, which do not change the number of horizontally oriented rhombi in R. Thus, i(π) + i(τ(π)) is equal to \binom{n}{2} plus the number of horizontally oriented rhombi in the intersection of the fundamental region (with bottom strip excluded) with its mirror image, because the latter rhombi are counted twice in i(π) + i(τ(π)). However, this intersection is exactly the previously described wedge, and the number of horizontally oriented rhombi in the wedge is s(π). This explains the relation (2.5).

Remark. The correspondence which is described in this section is, in some sense, “implicit in the literature.” It could be extracted (with some effort) by a very attentive reading and comparison of Andrews’ original papers [1, 2], David and Tomei’s observation [5] of the equivalence of plane partitions and rhombus tilings, and observations from [3, Figure 3.2 and Proof of Lemma 3.1] and [4, Figures 6 and 7 and Proof of Theorem 7].

4. d-Descending plane partitions. In the original papers [1, 2], Andrews did in fact also consider more general objects, which we shall call here d-descending plane partitions. (Andrews did not give them a name. The objects of which we are talking, are the objects in the sets De(d; m, n) in [1, 2].) For d ≤ 1, we define a d-descending plane partition to be an array π of positive integers of the form (2.1), such that

(1) λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} ≥ k,

(2) the entries along rows are weakly decreasing,

(3) the entries along columns are strictly decreasing,

(4) the first entry in each row does not exceed the number of entries in the preceding row less d but is greater than the number of entries in its own row less d.

Clearly, descending plane partitions are the special case d = 0.^{1} As in the case of descending plane partitions, there is a closed form product formula for the number of all d-descending plane partitions with entries ≤ n, see [1], [2, Theorem 8].

In the same way as in the preceding section, it can be seen that d-descending plane partitions with entries ≤ n are in bijection with cyclically symmetric rhombus tilings of a hexagon with side lengths n + d − 1, n + 1, n + d − 1, n + 1, n + d − 1, n + 1 of which a centrally located equilateral triangle with side length 2 − d has been removed, see Figure 5 for an example with n = 4 and d = −1.

A lattice structure can be introduced on d-descending plane partitions in the same way as in the preceding section. It is obvious that, again, the reflection in the horizontal symmetry axis of the hexagon with triangular hole is an antiautomorphism of this lattice. Since it can be shown in the same manner as in [8, Sec. 3] that for the lattice of d-descending plane partitions with entries ≤ n there is a unique antiautomorphism, the antiautomorphism defined by the above reflection generates this unique antiautomorphism of the lattice of d-descending plane partitions.

Acknowledgement. I am indebted to the anonymous referee for pointing out an oversight in the original interpretation of the statistics i(π).

1In [1, 2], the value d = 2 is also allowed. The corresponding objects should be in bijection with the cyclically symmetric plane partitions, which are at the beginning of the whole story. However, there is a slight inaccuracy there. In order to make the bijection with cyclically symmetric plane partitions work, and in order to make the claimed enumeration formulae in [1, 2] true, the definition of d-descending plane partitions has to be modified in case d = 2: first of all, one must also allow 0 as a possible entry, and, second, one must require that, in each row, the first entry is equal to the number of entries in its row less d−1. We could also adopt this definition for arbitrary d, because the new objects would be in bijection with the objects as defined originally by Andrews by appending an appropriate number of 0s to each row of the latter objects. In any case, under this modification, the assertions of this section apply also for d = 2.

References

1. G. E. Andrews, Plane partitions (III): The weak Macdonald conjecture, Inventiones Math. 53 (1979), 193–225.

2. G. E. Andrews, Macdonald’s conjecture and descending plane partitions, Combinatorics, representation theory and statistical methods in groups, Young Day Proceedings (T. V. Narayana, R. M. Mathsen, J. G. Williams, eds.), Lecture Notes in Pure Math., vol. 57, Marcel Dekker, New York, Basel, 1980, pp. 91–106.

3. M. Ciucu and C. Krattenthaler, Plane partitions II: 5 \frac{1}{2} symmetry classes, Combinatorial Methods in Representation Theory (M. Kashiwara, K. Koike, S. Okada, I. Terada, H. Yamada, eds.), Advanced Studies in Pure Mathematics, vol. 28, RIMS, Kyoto, 2000, pp. 83–103.

4. M. Ciucu, T. Eisenkölbl, C. Krattenthaler and D. Zare, Enumeration of lozenge tilings of hexagons with a central triangular hole, J. Combin. Theory Ser. A 95 (2001), 251–334.

5. G. David and C. Tomei, The problem of the calissons, Amer. Math. Monthly 96 (1989), 429–431.

6. P. Lalonde, Lattice paths and the antiautomorphism of the poset of descending plane partitions, Discrete Math. 271 (2003), 311-319.

7. W. H. Mills, D. H. Robbins and H. Rumsey, Proof of the Macdonald conjecture, Inventiones Math. 66 (1982), 73–87.

8. W. H. Mills, D. H. Robbins and H. Rumsey, Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (1983), 340–359.

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France.