RHOMBUS TILINGS OF A HEXAGON WITH THREE FIXED BORDER TILES

THERESIA EISENKÖLBL^{1}

Abstract. We compute the number of rhombus tilings of a hexagon with sides a, b, c, a, b, c with three fixed tiles touching the border. The particular case a = b = c solves a problem posed by Propp. Our result can also be viewed as the enumeration of plane partitions having a rows and b columns, with largest entry ≤ c, with a given number of entries equal to c in the first row, a given number of entries equal to 0 in the last column and a given bottom-left entry.

1. Introduction

The interest in rhombus tilings has emerged from the enumeration of plane partitions in a given box (which was first carried out by MacMahon [6]). The connection comes from representing each entry by a stack of cubes and projecting the picture to the plane. Then the box becomes a hexagon, where opposite sides are equal, and the cubes turn into a rhombus tiling of the hexagon where the rhombi consist of two equilateral triangles (cf. [2]). The number of plane partitions contained in an a × b × c–box was first computed by MacMahon [6] and equals

\begin{matrix}∏ & {a−1 \atop k=0} & k! & ∏ & {b−1 \atop k=0} & k! & ∏ & {c−1 \atop k=0} & k! & ∏ & {a+b+c−1 \atop k=0} & k! \\ ∏ & {a+b−1 \atop k=0} & k! & ∏ & {b+c−1 \atop k=0} & k! & ∏ & {a+c−1 \atop k=0} & k! \end{matrix}.

In [8], Propp proposed several problems regarding ”incomplete” hexagons, i.e., hexagons, where certain triangles are missing. In particular, Problem 3 of [8] asks for a formula for the number of rhombus tilings of a hexagon with sides 2n, 2n + 3, 2n, 2n + 3, 2n, 2n + 3 and angles 120^{∘}, where the middle triangle is missing on each of the longer borders. This turns out to be a special case of the following result (see Corollary 2):

Theorem 1. Let a, b, c be nonnegative integers. The number of rhombus tilings of a hexagon with sides a+2, c+2, b+2, a+2, c+2, b+2, with fixed tiles in positions r, s, t touching the borders a+2, b+2, c+2 respectively (see Figure 1a for the exact meaning of the parameters r, s, t) equals

(r + 1)_{b}(s + 1)_{c}(t + 1)_{a}(c + 3 − t)_{b}(a + 3 − r)_{c}(b + 3 − s)_{a} \begin{matrix}∏ & {a \atop k=0} & k! & ∏ & {b \atop k=0} & k! & ∏ & {c \atop k=0} & k! & ∏ & {a+b+c+2 \atop k=0} & k! \\ ∏ & {b+c+2 \atop k=0} & k! & ∏ & {a+c+2 \atop k=0} & k! & ∏ & {a+b+2 \atop k=0} & k! \end{matrix}

× ((a + 1)(b + 1)(c + 1)(a + 2 − r)(b + 2 − s)(c + 2 − t) + (a + 1)(b + 1)(c + 1)rst

− (a + 2 − r)(b + 2 − s)(c + 2 − t)rst + (a + 1)(c + 1)(b + 2 − s)(c + 2 − t)rs

+ (b + 1)(a + 1)(c + 2 − t)(a + 2 − r)st + (c + 1)(b + 1)(a + 2 − r)(b + 2 − s)tr),

where (a)_{n} = a(a + 1) ⋯ (a + n − 1).

As shown in Figure 2, the fixed tiles determine the tiling along the borders they touch. Thus, we can remove three strips of triangles and end up with a hexagon with sidelengths a, c+3, b, a+3, c, b+3 and missing border triangles in positions r, s, t (see Figure 3). The special case a = b = c = 2n and r = s = t = n + 1 solves Problem 3 of [8]. This is stated in the following corollary.

1 EMAIL:TEISENKO@RADON.MAT.UNIVIE.AC.AT

b + 2  } c + 2 { { t {  }  } r  s a + 2 a. A hexagon with fixed tiles on three borders.  b. A rhombus tiling of the hexagon corres- ponding to the plane partition from (2). c + 2 {  {  } b + 2  a + 2

Figure 1.

t {  }  } r  s

A hexagon with fixed tiles on three borders. The tiling of the dotted area is determined by the fixed tiles.

Figure 2.

Corollary 2. The number of rhombus tilings of a hexagon with sides 2n, 2n + 3, 2n, 2n + 3, 2n, 2n + 3, where the middle triangle is missing on each of the longer borders, equals

((n + 2)_{2n})^{6} \begin{matrix}(∏_{k=0}^{2n} k!) & 3 & ∏ & {6n+2 \atop k=0} & k! \\ (∏_{k=0}^{4n+2} k!) & 3 \end{matrix}(n + 1)^{3}(3n + 1)(3n + 2)^{2}.  (1)

Theorem 1 has also an interpretation in terms of plane partitions. Here it is convenient to view the plane partitions as planar arrays of nonnegative integers with nonincreasing rows and columns. For

} c {  } { t{  } a b  r  s

A hexagon with sides a, c + 3, b, a + 3, c, b + 3, with triangles in positions r, s, t missing, where a = 2, b = 1, c = 1, r = 2, s = 2, t = 1.

Figure 3.

example, the plane partition of Figure 1b is represented by the array

\begin{matrix}3 & 2 & 2 \\ 3 & 2 & 2 \\ 2 & 2 & 0 \\ 2 & 1 & 0. \end{matrix}  (2)

It is easy to see that a plane partition contained in an (a + 2) × (b + 2) × (c + 2)–box is represented by an array of integers ≤ c + 2 having a + 2 rows and b + 2 columns. Furthermore, the fixed tiles of Theorem 1 correspond to the conditions that b + 2 − s entries in the first row of the plane partition are equal to c + 2, r entries in the last column are equal to 0 and the bottom-left entry is c + 2 − t (cf. Figure 1). So Theorem 1 has the following corollary.

Corollary 3. The number of plane partitions contained in an (a + 2) × (b + 2) × (c + 2)–box having b + 2 − s entries equal to c + 2 in the first row, r entries equal to 0 in the last column and c + 2 − t as the bottom-left entry equals

(r + 1)_{b}(s + 1)_{c}(t + 1)_{a}(c + 3 − t)_{b}(a + 3 − r)_{c}(b + 3 − s)_{a} \begin{matrix}∏ & {a \atop k=0} & k! & ∏ & {b \atop k=0} & k! & ∏ & {c \atop k=0} & k! & ∏ & {a+b+c+2 \atop k=0} & k! \\ ∏ & {b+c+2 \atop k=0} & k! & ∏ & {a+c+2 \atop k=0} & k! & ∏ & {a+b+2 \atop k=0} & k! \end{matrix}

× ((a + 1)(b + 1)(c + 1)(a + 2 − r)(b + 2 − s)(c + 2 − t) + (a + 1)(b + 1)(c + 1)rst

− (a + 2 − r)(b + 2 − s)(c + 2 − t)rst + (a + 1)(c + 1)(b + 2 − s)(c + 2 − t)rs

+ (b + 1)(a + 1)(c + 2 − t)(a + 2 − r)st + (c + 1)(b + 1)(a + 2 − r)(b + 2 − s)tr).

For the proof of Theorem 1, which we provide in Section 2, we proceed as follows. First, we use the fact mentioned immediately after Theorem 1, that it suffices to enumerate the rhombus tilings of a hexagon with sides a, c + 3, b, a + 3, c, b + 3 and missing border triangles in positions r, s, t as shown in Figure 3. This can be expressed as a determinant by using the main theorem of nonintersecting lattice paths [3, Cor.2] (see also [9, Theorem 1.2]). The determinant is then evaluated by induction, using a determinant lemma from [5] (see Lemma 4) and equation (4), a determinant formula published by Jacobi in 1841 (see [4]) but first proved in 1819 by P. Desnanot according to [7]. The formula is also closely related to C. L. Dodgson’s condensation method.

Remark. There is an analogy between Theorem 1 and the refined 2-enumeration of alternating sign matrices given in Theorem 6.1 of [1]. Alternating sign matrices are quadratic arrays containing only 0, ±1 and having exactly one 1 in each boundary row and column. Choosing the position of two 1’s leads to the refined enumeration mentioned above. The result is close to a simple product, but contains a nonlinear factor. Our theorem has a similar structure and comes from fixing rhombi on three of six borders.

2. Proof of Theorem 1

By the paragraph following Theorem 1 it is enough to show that the theorem holds for the number of rhombus tilings of a hexagon with sides a, c + 3, b, a + 3, c, b + 3 and missing border triangles in positions r, s, t (see Figure 3).

We start the proof by setting up a correspondence between these rhombus tilings and certain families of nonintersecting lattice paths, where nonintersecting means that no two paths have a common vertex. The reader should consult Figure 4 while reading the following passage. Given a rhombus tiling of the region described above, the lattice paths start on the centers of upper left diagonal edges (the edges on the side of length a) and the two extra edges parallel to it on the two neighbouring sides. They end on the lower right edges (the edges on the side of length a + 3). The paths are generated connecting the center of the respective edge with the center of the edge lying opposite in the rhombus. This process is iterated using the new edge and the second rhombus it bounds and terminates on the lower right boundary edges. It is clear that paths starting at different points have no common vertices and that an arbitrary family of nonintersecting paths from the set of the upper left edges to the set of the lower right edges lies completely inside the hexagon and can be converted back to a tiling (see Figure 4b).

Then we transform the picture to orthogonal paths with positive horizontal and negative vertical steps of unit length (see Figure 4c,d). Let the starting points of the paths be denoted by P_{0}, P_{1}, …, P_{a+1} and the endpoints by Q_{0}, Q_{1}, …, Q_{a+1}. Now we can easily write down the coordinates of the starting points and the endpoints:

P_{0} = (0, c + 2 − t),
P_{i} = (i − 1, c + 2 + i),  for i = 1, …, a,
P_{a+1} = (a + b + 2 − s, a + c + 2),
Q_{j} = (b + j + χ(j ≥ r), j + χ(j ≥ r)), for j = 0, …, a + 1.

Here, the symbol χ(j ≥ r) equals 1 for j ≥ r and 0 otherwise. It ensures that the missing edge on the side of length a + 3 is skipped.

Next we apply the main result for nonintersecting lattice paths [3, Cor.2] (see also [9, Theorem 1.2]). This theorem says that the number of families of nonintersecting lattice paths with path i leading from P_{i} to Q_{i} is the determinant of the matrix with (i, j)-entry the number of lattice paths leading from P_{i} to Q_{j}, provided that every two paths P_{i} → Q_{j}, P_{k} → Q_{l} have a common vertex, if i < j and k > l. It is easily checked that our sets of starting and endpoints meet the required conditions.

Since the number of lattice paths with positive horizontal and negative vertical steps from (a, b) to (c, d) equals \binom{c−a+b−d}{b−d}, we can find the number of families of nonintersecting lattice paths (equivalently, the number of rhombus tilings of our hexagon) by evaluating the determinant of the matrix M(a, b, c, r, s, t) = M = (M[i, j])_{i,j=0}^{a+1}, where

M[i, j] = \{ \begin{matrix}\binom{b + c − t + 2}{c + 2 − t − j − χ(j ≥ r)} & i = 0, \\ \binom{b + c + 3}{b + j + χ(j ≥ r) − i + 1} & i = 1, …, a, \\ \binom{c + s}{j + χ(j ≥ r) − a − 2 + s} & i = a + 1. \end{matrix}  (3)

We will do this using a determinant formula due to Desnanot (see [7]). Given a matrix A = (A[i, j])_{i,j=0}^{n}, this formula states that

(det A)(det A_{0,n}^{0,n}) = (det A_{0}^{0})(det A_{n}^{n}) − (det A_{0}^{n})(det A_{n}^{0}),  (4)

where A_{j}^{i} denotes the matrix A with row i and column j deleted, and A_{0,n}^{0,n} denotes the matrix A with rows 0 and n and columns 0 and n deleted. (In general, given sequences of nonnegative integers U

a. A rhombus tiling of the hexagon of Figure 3. a b  b + 3 a + 3  } c {  } { c + 3{  }  { t{  } r  s b. The corresponding family of paths.

c. The path family without the rhombi.  d. The orthogonal version of the path family.

•  _{•}  _{•}  _{•}  _{•}  _{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•} ∘  ∘ ∘ ∘ ∘  ∘ ∘  ∘^{P_{0}}^{P_{1}}  ^{P_{2}}  ^{P_{3}}_{Q_{0}}  ^{Q_{1}}  ^{Q_{2}}  ^{Q_{3}}

Figure 4.

and V, we will use the symbol A_{V}^{U} to denote the matrix A with all row indices from U and all column indices from V deleted.)

If we use (4) for A = M and n = a + 1, we get

(det M)(det M_{0,a+1}^{0,a+1}) = (det M_{0}^{0})(det M_{a+1}^{a+1}) − (det M_{0}^{a+1})(det M_{a+1}^{0}).  (5)

In order to use (5) for the computation of det M, we need to know the determinants of M_{0,a+1}^{0,a+1}, M_{0}^{0}, M_{a+1}^{a+1}, M_{0}^{a+1} and M_{a+1}^{0}. We start with the evaluation of det M_{0,a+1}^{0,a+1}. We will employ the following determinant lemma from [5, Lemma 2.2]:

Lemma 4.

det_{1≤i,j≤n} ((X_{j} + A_{n})(X_{j} + A_{n−1}) ⋯ (X_{j} + A_{i+1})(X_{j} + B_{i})(X_{j} + B_{i−1}) … (X_{j} + B_{2})) =

= ∏_{1≤i<j≤n} (X_{i} − X_{j}) ∏_{2≤i≤j≤n} (B_{i} − A_{j}).

Lemma 5. Let 1 ≤ r ≤ a + 1. Then

det M_{0,a+1}^{0,a+1} = \frac{((b + c + 3)!)^{a}(a + c + 2 − r)!(b + r)! ∏_{1≤i<j≤a+1} (j − i) ∏_{k=0}^{a−2} (b + c + k + 4)^{a−1−k}}{(a + 1 − r)!(r − 1)! ∏_{j=1}^{a+1} ((b + j)!(a + c + 2 − j)!)} .

Proof. We start by pulling out appropriate factors from columns and rows and get

det M_{0,a+1}^{0,a+1} = det_{1≤i,j≤a} (\binom{b + c + 3}{b + j + χ(j ≥ r) − i + 1})

= (−1)^{∑{a \atop i=1} (a−i)} ∏_{j=1}^{a} \frac{(b + c + 3)!}{(b + j + χ(j ≥ r))!(c − j − χ(j ≥ r) + 2 + a)!}

× det_{1≤i,j≤a} ((b + j + χ(j ≥ r) − i + 2)_{i−1}(j + χ(j ≥ r) − c − a − 2)_{a−i}) .

Applying Lemma 4 with X_{j} = b + j + χ(j ≥ r), A_{k} = −b − c − k − 2, B_{k} = −k + 2 and simplifying yields the desired result.

The cases r = 0 and r ≥ a + 2 can be reduced to the previous lemma by observing that r occurs only in terms of the form χ(j ≥ r). Since χ(j ≥ 0) = χ(j ≥ 1) for j ≥ 1 and χ(j ≥ a + 1) = χ(j ≥ r) for r ≥ a + 2, j ≤ a we have

det M_{0,a+1}^{0,a+1}(a, b, c, 0, s, t) = det M_{0,a+1}^{0,a+1}(a, b, c, 1, s, t)  (6)
det M_{0,a+1}^{0,a+1}(a, b, c, r, s, t) = det M_{0,a+1}^{0,a+1}(a, b, c, a + 1, s, t) for r ≥ a + 2.  (7)

Now we express all remaining determinants in equation (5) in terms of the determinant of M_{0}^{0}. Whenever a matrix does not depend on some parameter because of a deleted row, we will use a star in place of the parameter. It is easily checked that by appropriate relabelling of rows and columns

det M_{a+1}^{0}(a, b, c, r, s, ∗) = det M_{0}^{0}(a, b − 1, c + 1, r + 1, s − 1, ∗),  (8)
det M_{a+1}^{a+1}(a, b, c, r, ∗, t) = det M_{0}^{0}(a, c, b, a + 2 − r, c + 2 − t, ∗),  (9)
det M_{0}^{a+1}(a, b, c, r, ∗, t) = det M_{0}^{0}(a, c − 1, b + 1, a + 3 − r, c + 1 − t, ∗).  (10)

The remaining task is to evaluate det M_{0}^{0}. We state the result for det M_{0}^{0} in the following lemma.

Lemma 6. Let 1 ≤ r ≤ a + 2. Then

det M_{0}^{0} = ∏_{i=1}^{a} (\frac{(b + i + 3)_{c+1−i}}{(c + i + 2)!} )\frac{(s + 1)_{c}}{(a + c + 2)!} \frac{∏_{i=1}^{a} i!}{(r − 1)!(a + 2 − r)!}

× (c + 2)_{a+1−r}(b + 3)_{r−2}(c + 1)_{a+2}(c + 3)_{a}(b + 3 − s)_{a}

× ∏_{k=4}^{a+2} ((b + c + k)^{a+3−k}) ((b + 2)(a + 1) − (r − 1)(b + 2 − s)) .

Proof. Using the argumentation preceding equations (6) and (7) we get

det M_{0}^{0}(a, b, c, 0, s, t) = det M_{0}^{0}(a, b, c, 1, s, t)  (11)
det M_{0}^{0}(a, b, c, a + 3, s, t) = det M_{0}^{0}(a, b, c, a + 2, s, t).  (12)

Now we can prove the claimed expression for det M_{0}^{0} by induction on a. It is easily checked that the statement of Lemma 6 holds for a = 1. Equation (4) with A = M_{0}^{0} gives

(det M_{0}^{0})(det M_{0,1,a+1}^{0,1,a+1}) = (det M_{0,1}^{0,1})(det M_{0,a+1}^{0,a+1}) − (det M_{0,1}^{0,a+1})(det M_{0,a+1}^{0,1}).  (13)

We will express the occurring determinants in terms of the determinants of M_{0}^{0} and M_{0,n}^{0,n} to be able to carry out the induction. We do this by relabelling rows and columns and get:

det M_{0,1,a+1}^{0,1,a+1}(a, b, c, r, ∗, ∗) = det M_{0,a}^{0,a}(a − 1, b, c, r − 1, ∗, ∗),  (14)
det M_{0,1}^{0,1}(a, b, c, r, s, ∗) = det M_{0}^{0}(a − 1, b, c, r − 1, s, ∗),  (15)
det M_{0,a+1}^{0,1}(a, b, c, r, s, ∗) = det M_{0}^{0}(a − 1, b − 1, c + 1, r, s − 1, ∗),  (16)
det M_{0,1}^{0,a+1}(a, b, c, r, ∗, ∗) = det M_{0,a+1}^{0,a+1}(a, b + 1, c − 1, r − 1, ∗, ∗).  (17)

The matrices of the form M_{0}^{0} occurring in the above equations (14)–(17) have parameter (a−1) instead of a, so we can carry out the induction step by using the values for det M_{0,n}^{0,n} derived in Lemma 5 and the induction hypothesis for det M_{0}^{0}. If r ≥ 2, cancellation of common factors in the two sides of (13) yields the identity

((b + 2)(a + 1) − (r − 1)(b + 2 − s))(a + b + 2 − s)

= ((b + 2)a − (r − 2)(b + 2 − s))(a + b + 2) − ((b + 1)a − (r − 1)(b + 2 − s))s,

which is easily seen to be valid. The case r = 1 can be done analogously using equations (6) and (11).

Proof of Theorem 1. Now we know all terms of equation (5) and can evaluate det M. It is indeed the expression of Theorem 1. For, by plugging into equation (5) the claimed formula for det M and the expressions derived in equations (8)–(10) and in Lemma 6, we get an equation that can be simplified by cancelling common factors. If 1 ≤ r ≤ a + 1 the remaining identity is

(b + 1)(c + 1)((b + 2)(a + 1) − (r − 1)(b + 2 − s))((c + 2)(a + 1) − (a + 1 − r)t)
− s(c + 2 − t)((a + 1)(c + 1) − (a + 2 − r)t)((a + 1)(b + 1) − r(b + 2 − s))
=(a + 1)(b + 1)(c + 1)(a + 2 − r)(b + 2 − s)(c + 2 − t) + (a + 1)(b + 1)(c + 1)rst
− (a + 2 − r)(b + 2 − s)(c + 2 − t)rst + (a + 1)(c + 1)(b + 2 − s)(c + 2 − t)rs

+ (b + 1)(a + 1)(c + 2 − t)(a + 2 − r)st + (c + 1)(b + 1)(a + 2 − r)(b + 2 − s)tr,

which is easily verified. The cases r = 0 and r = a + 2 can be done analogously using equations (6), (7), (11) and (12). Thus the proof of Theorem 1 is complete.

Acknowledgement. The author would like to thank the referee for pointing out Cor. 3, and for valuable comments which helped to improve the presentation of the results.

References

[1] M. Ciucu, A complementation theorem for perfect matchings of graphs having a cellular completion, J. Combin. Theory Ser. A, 81 (1998), 34–68.

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

[3] I.M. Gessel and X. Viennot, Determinant, paths and plane partitions, preprint, (1989).

[4] C.G.J. Jacobi, De formatione et proprietatibus Determinantium, in: Gesammelte Werke, vol. 3, Georg Reimer, Berlin (1884), 355–392; first published in Journal für Reine und Angewandte Mathematik 22 (1841), 285–318.

[5] C. Krattenthaler, A determinant evaluation and some enumeration results for plane partitions, in: Number-Theoretic Analysis, E. Hlawka, R. F. Tichy, eds., Lect. Notes in Math. 1452, Springer-Verlag, Berlin, (1990).

[6] P.A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, (1916); reprinted by Chelsea, New York, (1960).

[7] T. Muir, The theory of determinants, 2nd edition, vol. 1, MacMillan, London, (1906).

[8] J. Propp, Twenty open problems on enumeration of matchings, manuscript, (1996).

[9] J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990) 96—131.