THE NUMBER OF RHOMBUS TILINGS OF A SYMMETRIC HEXAGON WHICH CONTAIN A FIXED RHOMBUS ON THE SYMMETRY AXIS, I

M. FULMEK AND C. KRATTENTHALER

Abstract. We compute the number of rhombus tilings of a hexagon with sides N, M, N, N, M, N, which contain a fixed rhombus on the symmetry axis that cuts through the sides of length M.

1. Introduction

Let a, b and c be positive integers, and consider a hexagon with sides a, b, c, a, b, c whose angles are 120^{∘} (see Figure 1.a). The subject of our interest is tilings of this hexagon by rhombi of unit edge-length and angles of 60^{∘} and 120^{∘} (see Figure 1.b). (From now on, by a rhombus we always mean such a rhombus with side lengths 1 and angles of 60^{∘} and 120^{∘}.) By a well-known bijection [4], the total number of rhombus tilings of this hexagon is equal to the number of all plane partitions contained in an a × b × c box. The latter enumeration was solved long ago by MacMahon [15, Sec. 429, q → 1; proof in Sec. 494]. Therefore:

The number of all rhombus tilings of a hexagon with sides a, b, c, a, b, c equals

∏_{i=1}^{a} ∏_{j=1}^{b} ∏_{k=1}^{c} \frac{i + j + k − 1}{i + j + k − 2}.  (1.1)

(The form of the expression is due to Macdonald.)

A natural question to be asked is what the distribution of the rhombi in a random tiling is. On an asymptotic level, this question was answered by Cohn, Larsen and Propp [3]. On the exact (enumerative) level, Ciucu and Krattenthaler [2] and, independently, Helfgott and Gessel [7] computed the number of all rhombus tilings of a hexagon with sides N, M, N, N, M, N which contain the central rhombus. (They were motivated by a problem posed by Propp [16, Problem 1].)

In this paper we solve an even more general problem, namely the enumeration of all rhombus tilings of a hexagon with side lengths N, M, N, N, M, N which contain an arbitrary fixed rhombus on the symmetry axis which cuts through the sides of length M (see Figure 2 for illustration, the fixed rhombus is shaded). Our results are the following.

Theorem 1. Let m be a nonnegative integer and N be a positive integer. The number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N, which contain the l-th

Date: March 12, 1998.

a. A hexagon with sides a, b, c, a, b, c, where a = 3, b = 4, c = 5  b. A rhombus tiling of a hexagon with sides a, b, c, a, b, c }c } } c{  }  } a  b a b

Figure 1

A hexagon with sides N, M, N, N, M, N and fixed rhombus l, where N = 3, M = 2, l = 1. The thick horizontal line indicates the symmetry axis.  A hexagon with sides N, M, N, N, M, N and fixed rhombus l, where N = 3, M = 3, l = 2. The thick horizontal line indicates the symmetry axis. N  N M  N  N M

Figure 2 rhombus on the symmetry axis which cuts through the sides of length 2m, equals

\frac{m\binom{m+N}{m}\binom{m+N−1}{m}}{\binom{2m+2N−1}{2m}} (∑_{e=0}^{l−1}(−1)^{e}\binom{N}{e}\frac{(N − 2e)(\frac{1}{2})_{e}}{(m + e)(m + N − e)(\frac{1}{2} − N)_{e}} )

× ∏_{i=1}^{N} ∏_{j=1}^{N} ∏_{k=1}^{2m} \frac{i + j + k − 1}{i + j + k − 2}, (1.2)

where the shifted factorial (a)_{k} is defined by (a)_{k} := a(a+1) ⋯ (a+k−1), k ≥ 1, (a)_{0} := 1.

Theorem 2. Let m and N be positive integers. The number of rhombus tilings of a hexagon with sides N + 1, 2m − 1, N + 1, N + 1, 2m − 1, N + 1, which contain the l-th rhombus on the symmetry axis which cuts through the sides of length 2m − 1, equals

\frac{m\binom{m+N}{m}\binom{m+N−1}{m}}{\binom{2m+2N−1}{2m}} (∑_{e=0}^{l−1}(−1)^{e}\binom{N}{e}\frac{(N − 2e)(\frac{1}{2})_{e}}{(m + e)(m + N − e)(\frac{1}{2} − N)_{e}} )

× ∏_{i=1}^{N+1} ∏_{j=1}^{N+1} ∏_{k=1}^{2m−1} \frac{i + j + k − 1}{i + j + k − 2}. (1.3)

In general, the sum in (1.2) and (1.3) (note that it is indeed exactly the same sum) does not simplify. (The only case where the sum is known to simplify is for N = 2n − 1, m = l = n, see [2, Corollary 3] and [7, Theorem 12, Lemma 13].) Given that this is the case, a natural “next” question is to ask what the quantities in (1.2) and (1.3) are “roughly”, or, more precisely, what the proportion of rhombus tilings, which contain the fixed rhombus, in the total number of rhombus tilings is asymptotically as the hexagon becomes large. Indeed, from Theorems 1 and 2, we are able to derive an “arcsine law” for this kind of enumeration.

Theorem 3. Let a be any nonnegative real number, let b be a real number with 0 < b < 1. For m ∼ aN and l ∼ bN, the proportion of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N or N + 1, 2m − 1, N + 1, N + 1, 2m − 1, N + 1, which contain the l-th rhombus on the symmetry axis which cuts through the sides of length 2m, respectively 2m − 1, in the total number of rhombus tilings is asymptotically

\frac{2}{π} arcsin (\begin{matrix}√ & \overline{b(1 − b)} \\ √ & \overline{(a + b)(a − b + 1)} \end{matrix})  (1.4)

as N tends to infinity.

This result is in accordance with Conjecture 1 in [3], to which it adds evidence in special instances. The latter conjecture predicts that in the case of an arbitrary (semiregular) hexagon and an arbitrary fixed rhombus the asymptotics for the same kind of enumeration equals P_{a,b,c}(x, y). Here, P_{a,b,c} is a certain function (defined in [3, Theorem 1]), which depends on the sides a, b, c of the hexagon. This function is evaluated at (x, y), which, roughly speaking, is the location of the fixed rhombus in the “normalized” hexagon. Indeed, the value P_{N,2m,N}(0, \sqrt{3} (−N/2 + l)) for m = aN and l = bN equals

\frac{1}{π} arccot (\frac{a(1 + a) − b(1 − b)}{2\sqrt{a(1 + a)b(1 − b)}}) ,

which, in view of the formula

2 arcsin x = arccot (\frac{1 − 2x^{2}}{2x\sqrt{1 − x^{2}}} ) ,

is exactly equal to (1.4).

In the next section we describe proofs of Theorems 1, 2 and 3. For the proofs of Theorems 1 and 2 we build on the approach of [2]. The basic ingredients are an application of Ciucu’s Matchings Factorization Theorem [1, Theorem 1.2], the standard correspondence between rhombus tilings and nonintersecting lattice paths, and evaluations of the determinants which result from the nonintersecting lattice paths. As opposed to [2], here we have to take care of a few subtleties, which do not arise in [2] when the fixed rhombus is the central rhombus. Besides, we offer a few simplifications compared to [2]. The proof of a crucial auxiliary lemma is deferred to Section 3. Finally, in Section 4, we point to further directions in this research, and list a few open problems and conjectures.

2. The proofs

Proof of Theorems 1 and 2. The proofs of both Theorems are very similar. We will mainly concentrate on the proof of Theorem 1.

There are four basic steps.

Step 1. Application of the Matchings Factorization Theorem. First, rhombus tilings of the hexagon with sides N, 2m, N, N, 2m, N can be interpreted as perfect matchings of the dual graph of the triangulated hexagon, i.e., the (bipartite) graph G(V, E), where the set of vertices V consists of the triangles of the hexagon’s triangulation, and where two vertices are connected by an edge if the corresponding triangles are adjacent. Enumerating only those rhombus tilings which contain a fixed rhombus, under this translation amounts to enumerating only those perfect matchings which contain the edge corresponding to this rhombus, or, equivalently, we may consider just perfect matchings of the graph which results from G(V, E) by removing this edge. Clearly, since the fixed rhombus was located on the symmetry axis, this graph is symmetric. Hence, we may apply Ciucu’s Matchings Factorization Theorem [1, Theorem 1.2]. In general, this theorem says that the number of perfect matchings of a symmetric graph G equals a certain power of 2 times the number of perfect matchings of a graph G^{+} (which is, roughly speaking, the “upper half” of G) times a weighted count of perfect matchings of a graph G^{−} (which is, roughly speaking, the “lower half” of G), in which the edges on the symmetry axis count with weight 1/2 only. Applied to our case, and retranslated into rhombus tilings, the Matchings Factorization Theorem implies the following:

The number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N which contain the l-th rhombus on the symmetry axis which cuts through the sides of length 2m, equals

2^{N−1}R(S′(N, m))R̃(C(N, m, l)),  (2.1)

where S′(N, m) denotes the “upper half” of our hexagon with the fixed rhombus removed (see the left half of Figure 3), where R(S′(m, n)) denotes the number of rhombus tilings of S′(m, n), where C(N, m, l) denotes the “lower half” (again, see the left half of Figure 3), and where R̃(C(N, m, l)) denotes the weighted count of rhombus tilings of C(N, m, l) in which each of the top-most (horizontal) rhombi counts with weight 1/2. (Both, S′(N, m) and C(N, m, l) are roughly pentagonal. The notations S′(N, m) and C(N, m, l) stand for

^{S′(3,1)} _{S(2,1)} _{C(3,1,1)}  ^{S(3,1)} ^{C′(3,2,2)} _{C(2,2,2)} The hexagons from Figure 2 cut along the symmetry axis, according to the Matchings Factorization Theorem. In the shaded regions, the “forced” (uniquely determined) rhombi are shown with thick lines.

Figure 3. Hexagons, cut in two

“simple part” and “complicated part”, respectively, as it will turn out that the count R(S′(N, m)) will be rather straight-forward, while the count R̃(C(N, m, l)) will turn out be considerably harder.)

It is immediately obvious, that along the left-most and right-most vertical strip of S′(N, m), the rhombi are uniquely determined. Hence, we may safely remove these strips (see the left half of Figure 3, the strips are shaded). Let us denote the resulting region by S(N − 1, m). From (2.1) we obtain that the number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N, which contain the l-th rhombus on the symmetry axis which cuts through the sides of length 2m, equals

2^{N−1}R(S(N − 1, m))R̃(C(N, m, l)).  (2.2)

Similarly, for the case of Theorem 2, we obtain that the number of rhombus tilings of a hexagon with sides N, 2m − 1, N, N, 2m − 1, N, which contain the l-th rhombus on the symmetry axis which cuts through the sides of length 2m − 1, equals

2^{N−1}R(S(N, m − 1))R̃(C(N − 1, m, l)).  (2.3)

(See the right half of Figure 3. Note that in the case of Theorem 2, an application of the Matchings Factorization Theorem would directly give us 2^{N−1}R(S(N, m − 1))R̃(C′(N, m, l)), with C′(N, m, l) the region as indicated in Figure 3. However, similarly to before, any rhombus tiling of the “complicated part” C′(N, m, l) is uniquely

Tilings for the “complicated parts” from Figure 3, interpreted as lattice paths.

Figure 4. Lattice path interpretation

determined in the left-most and right-most vertical strip of C′(N, m, l). Removing these strips then yields C(N − 1, m, l).)

Step 2. From rhombus tilings to nonintersecting lattice paths. There is a standard translation from rhombus tilings to nonintersecting lattice paths. We apply it to our regions S(N, m) and C(N, m, l). Figure 4 illustrates this translation for the (“complicated”) lower parts in Figure 3.

For the “simple” pentagonal part S(N, m) we obtain the following: The number R(S(N, m)) of rhombus tilings of S(N, m) equals the number of families (P_{1}, P_{2}, …, P_{N}) of nonintersecting lattice paths consisting of horizontal unit steps in the positive direction and vertical unit steps in the negative direction, where P_{i} runs from (i, i) to (2i, i − m), i = 1, 2, …, N.

Similarly, for the “complicated” pentagonal part C(N, m, l) we obtain: The weighted count R̃(C(N, m, l)) of rhombus tilings of C(N, m, l) equals the weighted count of families (P_{1}, P_{2}, …, P_{N}) of nonintersecting lattice paths consisting of horizontal unit steps in the positive direction and vertical unit steps in the negative direction, where P_{i} runs from (2i − N − 1, i + m) to (i, i) if i ≠ l, while P_{l} runs from (2l − N, l + m) to (l, l), with the additional twist that for i ≠ l path P_{i} has weight 1/2 if it starts with a horizontal step.

Step 3. From nonintersecting lattice paths to determinants. Now, by using the main theorem on nonintersecting lattice paths [6, Corollary 2] (see also [19, Theorem 1.2]), we may write R(S(N, m)) and R̃(C(N, m, l)) as determinants. Namely, we have

R(S(N, m)) = det_{1≤i,j≤N} (\binom{m + i}{m − i + j}) ,  (2.4)

and

R̃(C(N, m, l)) = det_{1≤i,j≤N} (\begin{cases}\frac{(N+m−i)!}{(m+i−j)! (N+j−2i+1)!}(m + \frac{N−j+1}{2}) & if i ≠ l \\ \frac{(N+m−i)!}{(m+i−j)! (N+j−2i)!} & if i = l \end{cases}) . (2.5)

Step 4. Determinant evaluations. Clearly, once we are able to evaluate the determinants in (2.4) and (2.5), Theorems 1 and 2 will immediately follow from (2.2) and (2.3), respectively, upon routine simplification. Indeed, for the determinant in (2.4) we have the following.

Lemma 4.

det_{1≤i,j≤N} (\binom{m + i}{m − i + j}) = ∏_{i=1}^{N} \frac{(N + m − i + 1)! (i − 1)! (2m + i + 1)_{i−1}}{(m + i − 1)! (2N − 2i + 1)!} . (2.6)

Proof. This determinant evaluation follows without difficulty from a determinant lemma in [8, Lemma 2.2]. The corresponding computation is contained in the proof of Lemma 9 in [2] (our determinant becomes the same as in [2] when the order of rows and columns is reversed), and also in the proof of Theorem 5 in [9] (set r = N, λ_{s} = m, B = 2, a + α − b = 2m there, and then reverse the order of rows and columns).

On the other hand, the determinant in (2.5) evaluates as follows.

Lemma 5.

det_{1≤i,j≤N} (\begin{cases}\frac{(N+m−i)!}{(m+i−j)! (N+j−2i+1)!}(m + \frac{N−j+1}{2}) & if i ≠ l \\ \frac{(N+m−i)!}{(m+i−j)! (N+j−2i)!} & if i = l \end{cases})

= ∏_{i=1}^{N} \frac{(N + m − i)!}{(m + i − 1)! (2N − 2i + 1)!} ∏_{i=1}^{⌊N/2⌋} ((m + i)_{N−2i+1} (m + i + \frac{1}{2})_{N−2i})

× 2^{\frac{(N−1)(N−2)}{2}} \frac{(m)_{N+1} ∏_{j=1}^{N}(2j − 1)!}{N! ∏⌊\frac{N}{2} ⌋_{i=1}(2i)_{2N−4i+1}} ∑_{e=0}^{l−1}(−1)^{e}\binom{N}{e}\frac{(N − 2e) (\frac{1}{2})_{e}}{(m + e) (m + N − e) (\frac{1}{2} − N)_{e}} . (2.7)

This determinant evaluation is much more complex than the determinant evaluation of Lemma 4, and, as such, is the most difficult part in our derivation of Theorems 1 and 2. We defer the proof of Lemma 4 to the next section.

Altogether, Steps 1–4 establish Theorems 1 and 2.

Proof of Theorem 3. From MacMahon’s formula (1.1) for the total number of rhombus tilings together with Theorems 1 and 2 we deduce immediately that the proportion is indeed the same for both cases N, 2m, N, N, 2m, N and N + 1, 2m − 1, N + 1, N + 1, 2m − 1, N + 1, and that it is given by

\frac{m\binom{m+N}{m}\binom{m+N−1}{m}}{\binom{2m+2N−1}{2m}} ∑_{e=0}^{l−1}(−1)^{e}\binom{N}{e}\frac{(N − 2e) (\frac{1}{2})_{e}}{(m + e) (m + N − e) (\frac{1}{2} − N)_{e}} .  (2.8)

We write the sum in (2.8) in a hypergeometric fashion, to get

\frac{(2N − 1)! ((m + 1)_{N−1})^{2}}{(N − 1)!^{2} (2m + 1)_{2N−1}} ∑_{e=0}^{l−1} \frac{(−N)_{e} (1 − \frac{N}{2} )_{e} (m)_{e} (−m − N)_{e} (\frac{1}{2})_{e}}{(−\frac{N}{2} )_{e} (1 − m − N)_{e} (1 + m)_{e} (\frac{1}{2} − N)_{e} e!}. (2.9)

Next we shall apply Whipple’s transformation (see [18, (2.4.1.1)]), which reads

7F_{6}[\begin{matrix}a, 1 + \frac{a}{2}, b, c, d, e, −n \\ \frac{a}{2}, 1 + a − b, 1 + a − c, 1 + a − d, 1 + a − e, 1 + a + n \end{matrix}; 1]

= \frac{(a + 1)_{n}(a − d − e + 1)_{n}}{(a − d + 1)_{n}(a − e + 1)_{n}} _{4}F_{3}[\begin{matrix}a − b − c + 1, d, e, −n \\ a − b + 1, a − c + 1, −a + d + e − n \end{matrix}; 1] . (2.10)

Here, we used the standard hypergeometric notation

rF_{s}[\begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix}; z] = ∑_{k=0}^{∞} \frac{(a_{1})_{k} ⋯ (a_{r})_{k}}{k!(b_{1})_{k} ⋯ (b_{s})_{k}} z^{k}.  (2.11)

By setting a = −N, b = m, c = −m − N, d = \frac{1}{2}, e = −N + l, n = l − 1 in (2.10), we obtain as a limit case the following transformation:

∑_{e=0}^{l−1} \frac{(−N)_{e} (1 − \frac{N}{2} )_{e} (m)_{e} (−m − N)_{e} (\frac{1}{2})_{e}}{(−\frac{N}{2} )_{e} (1 − m − N)_{e} (1 + m)_{e} (\frac{1}{2} − N)_{e} e!}

= \frac{(−N + 1)_{l−1}(−l + \frac{1}{2})_{l−1}}{(−N + \frac{1}{2})_{l−1}(−l + 1)_{l−1}} _{4}F_{3}[\begin{matrix}1, \frac{1}{2}, l − N, 1 − l \\ 1 + m, 1 − m − N, \frac{3}{2} \end{matrix}; 1] . (2.12)

Thus, expression (2.9) turns into

\frac{(2N − 1)! ((m + 1)_{N−1})^{2}}{(N − 1)!^{2} (2m + 1)_{2N−1}} \frac{(−N + 1)_{l−1} (−l + \frac{1}{2})_{l−1}}{(−N + \frac{1}{2})_{l−1} (−l + 1)_{l−1}} _{4}F_{3}[\begin{matrix}1, \frac{1}{2}, l − N, 1 − l \\ 1 + m, 1 − m − N, \frac{3}{2} \end{matrix}; 1] .

Next we apply Bailey’s transformation (see [18, (4.3.5.1)]) between two balanced _{4}F_{3}- series,

4F_{3}[\begin{matrix}a, b, c, −n \\ e, f, 1 + a + b + c − e − f − n \end{matrix}; 1] = \frac{(e − a)_{n}(f − a)_{n}}{(e)_{n}(f)_{n}} ×

4F_{3}[\begin{matrix}−n, a, a + c − e − f − n + 1, a + b − e − f − n + 1 \\ a + b + c − e − f − n + 1, a − e − n + 1, a − f − n + 1 \end{matrix}; 1] . (2.13)

with a = 1, b = 1/2, c = l − N, e = m + 1, f = −m − N + 1, n = l − 1. This gives

\frac{(2l)! (2m)! (m + N − 1)! (m + N)! (2N − 2l + 2)!}{4(l + m − 1)(m + N − l + 1)(l − 1)! l! (m − 1)!}

× \frac{1}{m! (N − l)! (N − l + 1)! (2m + 2N − 1)!} _{4}F_{3}[\begin{matrix}1 − l, 1, 1, \frac{3}{2} − l + N \\ \frac{3}{2}, 2 − l − m, 2 − l + m + N \end{matrix}; 1] (2.14)

for the ratio (2.8). Now we substitute m ∼ aN and l ∼ bN and perform the limit N → ∞. With Stirling’s formula we determine the limit for the quotient of factorials in front of the _{4}F_{3}-series in (2.14) as 2\sqrt{a(a + 1)}\sqrt{b(1 − b)}/(π(a − b + 1)(a + b)). For the _{4}F_{3}-series itself, we may exchange limit and summation by uniform convergence:

lim_{N→∞}_{4}F_{3}[\begin{matrix}1 − l, 1, 1, \frac{3}{2} − l + N \\ \frac{3}{2}, 2 − l − m, 2 − l + m + N \end{matrix}; 1] = _{2}F_{1}[1, 1_{\frac{3}{2}}; \frac{(1 − b)b}{(a − b + 1)(a + b)}] .

A combination of these results and use of the identity (see [17, p. 463, (133)])

2F_{1}[1, 1_{\frac{3}{2}}; z] = \begin{matrix}arcsin & \sqrt{z} \\ √ & \overline{z(1 − z)} \end{matrix}

finish the proof.

3. Proof of Lemma 5

The method that we use for this proof is also applied successfully in [13, 2, 10, 11, 12, 14] (see in particular the tutorial description in [12, Sec. 2]).

First of all, we take appropriate factors out of the determinant in (2.7). To be precise, we take

\frac{(N + m − i)!}{(m + i − 1)! (2N − 2i + 1)!}

out of the i-th row of the determinant, i = 1, 2, …, N. Thus we obtain

∏_{i=1}^{N} \frac{(N + m − i)!}{(m + i − 1)! (2N − 2i + 1)!}

× det_{1≤i,j≤N} (\begin{cases}(m + i − j + 1)_{j−1}(N + j − 2i + 2)_{N−j} \frac{N+2m−j+1}{2} & if i ≠ l \\ (m + i − j + 1)_{j−1}(N + j − 2i + 1)_{N−j+1} & if i = l \end{cases}) (3.1)

for the determinant in (2.7). Let us denote by D(m; N, l) the N × N-matrix underlying the determinant in (3.1), i.e., the (i, j)-entry of D(m; N, l) is given by

D(m; N, l)_{i,j} := \begin{cases}(m + i − j + 1)_{j−1}(N + j − 2i + 2)_{N−j} \frac{N+2m−j+1}{2} & if i ≠ l, \\ (m + i − j + 1)_{j−1}(N + j − 2i + 1)_{N−j+1} & if i = l. \end{cases} (3.2)

Comparison of (2.7) and (3.1) yields that (2.7) will be proved once we are able to establish the determinant evaluation

det (D(m; N, l)) = ∏_{i=1}^{⌊N/2⌋} ((m + i)_{N−2i+1}(m + i + \frac{1}{2})_{N−2i})

× 2^{\frac{(N−1)(N−2)}{2}} \frac{(m)_{N+1} ∏_{j=1}^{N}(2j − 1)!}{N! ∏⌊\frac{N}{2} ⌋_{i=1}(2i)_{2N−4i+1}} ∑_{e=0}^{l−1}(−1)^{e}\binom{N}{e}\frac{(N − 2e)(\frac{1}{2})_{e}}{(m + e)(m + N − e)(\frac{1}{2} − N)_{e}} . (3.3)

For the proof of (3.3) we proceed in several steps (see below). An outline is as follows. In the first step we show that ∏_{i=1}^{⌊N/2⌋}(m + i)_{N−2i+1} is a factor of det (D(m; N, l)) as a polynomial in m. In the second step we show that ∏_{i=1}^{⌊N/2⌋}(m + i + \frac{1}{2})_{N−2i} is a factor of det (D(m; N, l)). In the third step we determine the maximal degree of det (D(m; N, l)) as a polynomial in m, which turns out to be \binom{N+1}{2}−1. From a combination of these three steps we are forced to conclude that

det (D(m; N, l)) = ∏_{i=1}^{⌊N/2⌋} ((m + i)_{N−2i+1}(m + i + \frac{1}{2})_{N−2i}) P (m; N, l),  (3.4)

where P (m; N, l) is a polynomial in m of degree at most N −1. Finally, in the fourth step, we evaluate P (m; N, l) at m = 0, −1, …, −N. Namely, we show that P (m; N, l) = 0 if m = − min{N + 1 − l, l}, …, − ⌊N/2⌋ + 1, − ⌊N/2⌋, and for m = 0, −1, …, − min{N + 1 − l, l} + 1 we show that

P (m; N, l) = (−1)^{mN+(m^{2}−m)/2}2^{(m^{2}+m)/2−N+1}(m)_{m}

× \frac{∏_{j=1}^{N−m}(2j − 1)! ∏_{k=1}^{m}(k − 1)!^{2}(N + k − 2m − 1)!(\frac{m−k+1}{2})_{k−1}(k − N)_{N−m}}{∏_{i=1}^{m}(N − m − i)!(m − i)! ∏_{i=m+1}^{⌊N/2⌋}(i − m)_{N−2i+1} ∏_{i=1}^{⌊N/2⌋}(i − m + \frac{1}{2})_{N−2i}} . (3.5)

Moreover, we show that P (m; N, l) = (−1)^{N−1}P (−N − m; N, l), which in combination with (3.5) gives the evaluation of P (m; N, l) at m = − ⌊N/2⌋−1, …, −N+1, −N. Clearly, this determines a polynomial of maximal degree N − 1 uniquely. In fact, an explicit expression for P (m; N, l) can immediately be written down using Lagrange interpolation. As it turns out, the resulting expression for P (m; N, l) is exactly the second line of (3.3). In view of (3.4), this would establish (3.3) and, hence, finish the proof of the Lemma.

Before going into details of these steps, however, it is useful to record two auxiliary facts. The reader may, at this point, directly jump to Steps 1–4, and come back to the auxiliary facts when they are needed there.

Auxiliary Fact I. There holds the symmetry

det (D(m; N, l)) = det (D(m; N, N + 1 − l)) .  (3.6)

This symmetry follows immediately from the combinatorial “origin” of the determinant. For, trivially, the number of rhombus tilings which contain the l-th rhombus on the symmetry axis is the same as the number of rhombus tilings which contain the (N +1−l)- th rhombus. The manipulations that finally lead to the determinant det (D(m; N, l)) do not affect this symmetry, therefore det (D(m; N, l)) inherits the symmetry.

This symmetry is very useful for our considerations, because for any claim that we want to prove (and which also obeys this symmetry) we may freely assume 1 ≤ l ≤ ⌊\frac{N+1}{2}⌋ or ⌊\frac{N+1}{2}⌋ ≤ l ≤ N, whatever is more convenient.

Auxiliary Fact II. There holds the symmetry

det (D(−N − m; N, l)) = (−1)^{\binom{N+1}{2}−1} det (D(m; N, l)) .  (3.7)

In order to establish (3.7), we claim that D(m; N, l) · ((−1)^{j}\binom{j−1}{i−1})_{1≤i,j≤N} equals D(−N − m; N, l), except that all the entries in row l have opposite sign. Let us write R(N) for the matrix ((−1)^{j}\binom{j−1}{i−1})_{1≤i,j≤N}. Since det (R(N)) = (−1)^{\binom{N+1}{2}}, this would establish (3.7).

In order to establish this claim, we have to compute the (i, j)-entry in D(m; N, l)·R(N). For i ≠ l, we have to show

(−1)^{j} ∑_{k=1}^{j} \binom{j − 1}{k − 1}(m + i − k + 1)_{k−1}(N + k − 2i + 2)_{N−k} \frac{(N+2m−k+1)}{2}

= (−N − m + i − j + 1)_{j−1}(N + j − 2i + 2)_{N−j} \frac{(−2m−N−j+1)}{2}, (3.8)

and for i = l we have to show

(−1)^{j} ∑_{k=1}^{j} \binom{j − 1}{k − 1}(m + i − k + 1)_{k−1}(N + k − 2i + 1)_{N−k+1}

= −(−N − m + i − j + 1)_{j−1}(N − 2i + j + 1)_{N−j+1}. (3.9)

Note that for j = 1, equation (3.8) collapses to

−(N − 2i + 3)_{N−1} \frac{(2m+N)}{2} = (N − 2i + 3)_{N−1} \frac{(−2m−N)}{2},

which is of course true, so we may assume j > 1 in the following.

We convert the left-hand side of (3.8) into hypergeometric form, to obtain

(−1)^{j−1} \frac{1}{2}(−2m − N)(N − 2i + 3)_{N−1} _{3}F_{2}[\begin{matrix}−2m − N + 1, 1 − j, 1 − i − m \\ −2m − N, 3 − 2i + N \end{matrix}; 1] .(3.10)

Next we apply the contiguous relation

3F_{2}[\begin{matrix}a, A_{1}, A_{2} \\ B_{1}, B_{2} \end{matrix}; z] = _{3}F_{2}[\begin{matrix}a − 1, A_{1}, A_{2} \\ B_{1}, B_{2} \end{matrix}; z] + z \frac{A_{1}A_{2}}{B_{1}B_{2}} _{3}F_{2}[\begin{matrix}a, A_{1} + 1, A_{2} + 1 \\ B_{1} + 1, B_{2} + 1 \end{matrix}; z] (3.11)

to the _{3}F_{2}-series in (3.10). We want to apply the case where a = −2m − N + 1 and B_{1} = −2m−N. By inspection, in this case parameters cancel inside the two _{3}F_{2}-series on the right-hand side of the contiguous relation, thus leaving two _{2}F_{1}-series. So we obtain

2F_{1}[\begin{matrix}1 − i − m, 1 − j \\ 3 − 2i + N \end{matrix}; 1] + \frac{(j − 1)(1 − i − m)}{(−2m − N)(N − 2i + 3)} _{2}F_{1}[\begin{matrix}2 − i − m, 2 − j \\ 4 − 2i + N \end{matrix}; 1] .(3.12)

Each of the two_{2}F_{1}-series can be evaluated by means of the Chu–Vandermonde-summation (see [18, (1.7.7), Appendix (III.4)]),

2F_{1}[\begin{matrix}a, −n \\ c \end{matrix}; 1] = \frac{(c − a)_{n}}{(c)_{n}} ,  (3.13)

where n is a nonnegative integer. We have to apply the case where n = j − 1 and n = j − 2, respectively. Since j > 1 in our case, the nonnegativity-condition is satisfied, and we obtain

3F_{2}[\begin{matrix}1 − 2m − N, 1 − j, 1 − i − m \\ −2m − N, 3 − 2i + N \end{matrix}; 1]

= \frac{(−N + i − m − 1)(N + j + 2m − 1)(N − i + m + 2)_{j−2}}{(−2m − N)(N − 2i + 3)_{j−1}} . (3.14)

Inserting this into (3.10) shows that (3.8) is true.

In order to show (3.9), we convert the left-hand side into hypergeometric form, to obtain

(−1)^{j}(N − 2i + 2)_{N} _{2}F_{1}[\begin{matrix}1 − i − m, 1 − j \\ 2 − 2i + N \end{matrix}; 1] .  (3.15)

Again, we can evaluate this _{2}F_{1}-series by means of Chu–Vandermonde summation (3.13). This proves (3.9).

Now we are ready for heading into the details of Steps 1–4.

Step 1. ∏_{i=1}^{⌊N/2⌋}(m + i)_{N−2i+1} is a factor of det (D(m; N, l)). Here, for the first time, we make use of the symmetry (3.6). It implies, that we may restrict ourselves to 1 ≤ l ≤ ⌊\frac{N+1}{2}⌋.

For i between 1 and ⌊N/2⌋ let us consider row N − i + 1 of the matrix D(m; N, l). We see that the j-th entry in this row has the form

(m + N − i − j + 2)_{j−1} (−N + 2i + j)_{N−j} \frac{N+2m−j+1}{2}.

Since (−N+2i+j)_{N−j} = 0 for j = 1, 2, …, N−2i, the first N−2i entries in this row vanish. Therefore (m + i)_{N−2i+1} is a factor of each entry in row N − i + 1, i = 1, 2, …, ⌊N/2⌋. Hence, the complete product ∏_{i=1}^{⌊N/2⌋}(m + i)_{N−2i+1} divides det (D(m; N, l)).

Step 2. ∏_{i=1}^{⌊N/2⌋}(m + i + \frac{1}{2})_{N−2i} is a factor of D(m; N, l). Again we make use of the symmetry (3.6), which allows us to restrict ourselves to 1 ≤ l ≤ ⌊\frac{N+1}{2}⌋.

We observe that the product can be rewritten as

∏_{i=1}^{⌊N/2⌋}(m + i + \frac{1}{2})_{N−2i} = ∏_{e=1}^{N−2}(m + e + \frac{1}{2})^{min\{e,N−e−1\}}.

Therefore, because of the other symmetry (3.7), it suffices to prove that (m + e + 1/2)^{e} divides D(m; N, l) for e = 1, 2, …, ⌊N/2⌋ − 1. In order to do so, we claim that for each such e there are e linear combinations of the columns, which are themselves linearly independent, that vanish for m = −e − 1/2. More precisely, we claim that for k = 1, 2, …, e there holds

∑_{j=1}^{k} \binom{k}{j} · (column (N − 2e + k + j) of D(−e − 1/2; N, l))

− \frac{(N − e − l + \frac{1}{2})_{k}}{(−4)^{k}(N − e − l + 1)_{k}} · (column (N − 2e) of D(−e − 1/2; N, l)) = 0. (3.16)

(Note that this operation is really feasible for these values of e and k.) As is not very difficult to see (cf. [12, Sec. 2]) this would imply that (m + e + 1/2)^{e} divides D(m; N, l).

Obviously, in order to prove (3.16) we have to show

∑_{j=0}^{k} \binom{k}{j}(e + i − j − k − \frac{1}{2} − N)_{N−2e+j+k} ×

(2N + 3 − 2e − 2i + j + k)_{2e−j−k−1} \frac{(−j−k−1)}{2} = 0 (3.17)

which is (3.16) restricted to the i-th row, i ≠ l, and

∑_{j=0}^{k} \binom{k}{j}(e + 1 + l − j − k − \frac{1}{2} − N)_{N−2e−1+j+k}(2N − 2e − 2l + j + k + 1)_{2e+1−j−k} −

\frac{(N − e − l − \frac{1}{2})_{k}}{(−4)^{k}(N − e − l + 1)_{k}}

× (e + 1 + l − j − \frac{1}{2} − N)_{N−2e−1+j}(2N − 2e − 2l + j + 1)_{2e+1−j} = 0 (3.18)

which is (3.16) restricted to the l-th row.

Both equations (3.17) and (3.18) can be shown by the same kind of “hypergeometrics” (contiguous relation and Chu-Vandermonde) as was used for establishing (3.7).

Step 3. det (D(m; N, l)) is a polynomial in m of maximal degree \binom{N+1}{2} − 1. Clearly, the degree in m of the (i, j)-entry in the determinant D(m; N, l) is j for i ≠ l, while it is j − 1 for i = l. Hence, in the defining expansion of the determinant, each term has degree (∑_{j=1}^{N} j) − 1 = \binom{N+1}{2} − 1.

Step 4. Evaluation of P (m; N, l) at m = 0, −1, …, −N. Again, we make use of the symmetry (3.6), and this time restrict ourselves to ⌊\frac{N+1}{2}⌋ ≤ l ≤ N. On the other hand, by the symmetry (3.7) and by the definition (3.4) of P (m; N, l), we have P (m; N, l) = P (−N − m; N, l). Therefore, it suffices to compute the evaluation of P (m; N, l) at m = 0, −1, …, − ⌊N/2⌋.

What we would like to do is, for any e with 0 ≤ e ≤ ⌊N/2⌋, to set m = −e in (3.4), compute det (D(−e; N, l)), and then express P (−e; N, l) as the ratio of det (D(−e; N, l)) and the right-hand side product evaluated at m = −e. Unfortunately, this is typically a ratio 0/0 and, hence, undetermined. So, we have to first divide both sides of (3.4) by the appropriate power of (m + e), and only then set m = −e.

Let e, 0 ≤ e ≤ ⌊N/2⌋, be fixed. For k = 0, 1, …, e − 1 we add

∑_{i=1}^{k} \binom{k}{i} · (column (N + 1 − 2e + k + i) of D(m; N, l))  (3.19)

to column N + 1 − 2e + k of D(m; N, l). The effect is that then (m + e) is a factor of each entry in column N + 1 − 2e + k. This can be proven by exactly the same “hypergeometrics” as we used for the proofs of Auxiliary Fact II and Step 2. So, we take (m + e) out of each entry of column N + 1 − 2e + k, k = 0, 1, …, e − 1 and denote the resulting matrix by D_{1}(m; N, l, e). We obtain

D_{1}(m; N, l, e)_{i,j} := \begin{cases}(m + i − j + 1)_{j−1}(N + j − 2i + 2)_{N−j} \frac{N+2m−j+1}{2} & if i ≠ l \\ (m + i − j + 1)_{j−1}(N + j − 2i + 1)_{N−j+1} & if i = l \end{cases}(3.20)

if j ≤ N − 2e or j > N − e, and

D_{1}(m; N, l, e)_{i,j}

:= \begin{cases}(2e + i − k + m − N)_{N−2e+k}(N − i + m + 1)_{k}× \\ (2N − 2e − 2i + 2k + 3)_{2e−2k−1} & if i ≠ l \\ (2N − 2e − 2i + 2k + 2)_{2e−2k}(2e + i − k + m − N)_{N−e−i+k}× \\ (m + e + 1)_{i−e−1}(1 − i + m + N)_{k} & if i = l \end{cases} (3.21)

if N − 2e + 1 ≤ j ≤ N − e.

From what we did so far, it is straight-forward that we must have

D(m; N, l) = (m + e)^{e}D_{1}(m; N, l, e).

A combination with (3.4) gives that

P (m; N, l)

= det (D_{1}(m; N, l, e)) ∏_{i=1}^{⌊N/2⌋} ((m + i)_{e−i}(m + e + 1)_{N−i−e}(m + i + \frac{1}{2})_{N−2i})^{−1} . (3.22)

Now, in this equation, we are able to set m = −e. Hence, in order to determine the evaluation of P (m; N, l) at m = −e, we need the evaluation of det (D_{1}(m; N, l, e)) at m = −e.

Assuming l ≥ \frac{N+1}{2}, we claim that the following is true: If e ≥ N + 1 − l, then we have

det (D_{1}(−e; N, l, e)) = 0,  (3.23)

[figure: 0; 0; 0; 0; ∗; ∗; M; Q_{2}; Q_{1}; 1; N + 1 − 2e; N + 1 − e; N − 2e; N − e; N; 1; e + 1; N + 1 − e; e; N − e; N] Figure 5

otherwise we have

det (D_{1}(−e; N, l, e)) = (−1)^{e·N}2^{\frac{2+e+e^{2}−2N}{2}} (e)_{e} ∏_{j=1}^{N−e}(2j − 1)! ×

∏_{j=1}^{e}(k − 1)!^{2}(N + k − 2e − 1)!(\frac{k+e−1}{2})_{k−1}(k − N)_{N−e}. (3.24)

In order to establish this we observe that D_{1}(−e; N, l, e) has a block form which is sketched in Figure 5. The figure has to be read according to the following convention: If a block is bounded from above by a horizontal line numbered r_{1} at the left margin, is bounded from below by a horizontal line numbered r_{2} at the right margin, is bounded from the left by a vertical line numbered c_{1} at the bottom margin, and is bounded from the right by a vertical line numbered c_{2} at the top margin, then the block consists of the entries from rows i = r_{1}, …, r_{2} and columns j = c_{1}, …, c_{2}. This block form is easily established by routine verification directly from the definitions (3.20) and (3.21).

Hence the determinant D_{1}(−e; N, l, e) factors as follows,

det (D_{1}(−e; N, l, e)) = (−1)^{e(N−e)} det(Q_{2}) det(Q_{1}) det(M).  (3.25)

Since Q_{1} and Q_{2} are upper and lower triangular matrices, respectively, it is easy to evaluate det(Q_{1}) and det(Q_{2}). We simply have to multiply all the entries on the main diagonal. We obtain

det(Q_{1}) = \begin{cases}(−1)^{\frac{e(e−1)}{2}} ∏_{k=0}^{e−1} k!(2e − 2k − 1)!(N + k − 2e)! & if l < N + 1 − e, \\ 0 & if l ≥ N + 1 − e. \end{cases}(3.26)

Note that (3.23) follows immediately from (3.25) and (3.26).

By assumption we have l ≥ \frac{N+1}{2} > e, by assertion (3.23) (which is already proved) we may assume l ≤ N − e, so we are sure to encounter row l in Q_{2}. Multiplying the entries on the main diagonal gives

det(Q_{2}) = (\frac{1}{2})^{N−2e+1} ∏_{j=1}^{N−2e}(j − 1)!(N − 2e − j + 1)_{N−j+1}.  (3.27)

(Note that for e = 0, Q_{2} is the whole, unmodified matrix D(0; N, l).)

For the evaluation of det(M) we employ Krattenthaler’s Lemma (see [8, Lemma 2.2]),

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

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

where X_{1}, …, X_{n}, A_{2}, …, A_{n}, and B_{2}, … B_{n} are arbitrary indeterminates.

The (i, j)-entry of matrix M is the (i, N − e + j)-entry of matrix D(−e; N, l). By assumption we have l ≥ \frac{N+1}{2} > e, so we do not encounter row l in M. Hence, we must evaluate

det_{1≤i,j≤e} (\frac{(−j−e+1)}{2}(N + i − j + 1)_{N−e+j−1}(2N − e − 2i + j + 2)_{e−j}) .  (3.29)

By taking out (i − N)_{N−e} from the i-th row and (−2)^{e−j} \frac{1−e−j}{2} from the j-th column, we get

det_{1≤i,j≤e}((i + (−1 − N + \frac{1}{2})) ⋯ (i + (−N − 1 + \frac{e−j}{2} )) ×

(i + (−N − j + 1)) ⋯ (i + (−N − 1))), (3.30)

which is precisely of the form required for (3.28) (set n = e, X_{i} = i, A_{j} = −1 − N + \frac{e−j+1}{2} and B_{j} = −j − N + 1). So we obtain

∏_{j=2}^{e}(j − 1)!(\frac{e−j+1}{2})_{j−1}  (3.31)

for the (e × e)-determinant in (3.30). Multiplying this with the factors pulled out previously, we have

det(M) = (−2)^{\frac{e(e−1)}{2} −e}(e)_{e} ∏_{i=1}^{e}(i − 1)!(\frac{e−i+1}{2})_{i−1}(i − N)_{N−e}.  (3.32)

By inserting (3.26), (3.27) and (3.32) into (3.25) and simplifying the expression, we obtain (3.24). Thanks to (3.22), this establishes (3.5).

The symmetry (3.7) implies P (m; N, l) = (−1)^{N−1}P (−N − m; N, l), whence we may write down P (m; N, l) using Lagrange-interpolation:

P (m; N, l) = ∑_{e=0}^{N−l} P (−e; N, l)(−1)^{e} \frac{(m)_{e}(m + e + 1)_{N−e} − (m)_{N−e}(N + m − e + 1)_{e}}{e!(N − e)!} ,

with P (−e; N, l) as given by (3.5). So far we proved this only for l ≥ ⌊\frac{N+1}{2}⌋. By the symmetry (3.6), however, we see that the same formula is valid in general if we sum up to min{N − l, l − 1}.

Further simplifications then lead to the sum in (3.3). To be more specific, a close look at the summands shows that they change sign if e is replaced by N − e, so in fact we may simply sum up to l − 1.

This finishes Step 4.

The proof of Lemma 5 is now complete.

4. Open problems and conjectures

In this paper, we computed the number of rhombus tilings of a hexagon with sides N, M, N, N, M, N, which contain a fixed rhombus on the symmetry axis. There are two questions which suggest themselves:

Question 1: What is the number of rhombus tilings of a hexagon with arbitrary side

lengths a, b, c, a, b, c which contain an arbitrary fixed rhombus? Question 2: What is the number of rhombus tilings of a hexagon with side lengths

a, b, c, a, b, c which contain several fixed rhombi?

Whereas it is too much to expect “nice” answers to these questions in general, there is indeed hope for further nice results in special cases. We should mention that Conjecture 1 in [3] predicts an asymptotic answer to Question 1.

Regarding Question 1: Clearly, the approach that we used in this paper is not good enough for any generalizations in these directions. For, the use of the Matchings Factorization Theorem at the very beginning requires a reflective symmetry of the region that we are considering. So, under this approach we need to have a hexagon with sides N, M, N, N, M, N with the fixed rhombus on the symmetry axis which cuts through the sides of length M. (The reader should observe that the Matchings Factorization Theorem cannot be used with respect to the “other” symmetry axis, i.e., the symmetry axis which runs in parallel to the sides of length M. For, this symmetry axis does not have the required property that it “separates” the dual graph, cf. the statement of [1, Theorem 1.2].)

However, it seems that the approach taken by Helfgott and Gessel [7] does allow to obtain further results in this direction. (Recall that they also obtained Theorems 1 and 2 for the cases where the fixed rhombus is the central rhombus.) In fact, a further result, using the approach by Helfgott and Gessel, has already been obtained by the authors and will be subject of a forthcoming article [5]. There, we compute the number of rhombus tilings of a hexagon with sides N, M, N, N, M, N, the parameters N and M being of the same parity, which contain a rhombus which is “next to the center of the region”. (Note, that, since N and M have the same parity, there is no central rhombus.)

Regarding Question 2, there are strong indications that, at least, there are “nice” results analogous to those of Theorems 1 and 2 if we consider rhombus tilings of a hexagon with sides N, M, N, N, M, N which contain a given set of rhombi on the symmetry axis which cuts through the sides of length M.

Suppose that we fix rhombi l_{1}, l_{2}, …, l_{r} on the symmetry axis, and let L = {l_{1}, l_{2}, …, l_{r}}. If we want to know the number of all rhombus tilings which contain these rhombi, then we can use the same approach as we used for proving Theorems 1 and 2.

That is (see Section 2), we apply first the Matchings Factorization Theorem. It implies that the number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N which contain the rhombi from the set L equals

2^{N−r}R(S(N − 1, m))R̃(C(N, m, L)),  (4.1)

where S(N − 1, m) is the same “reduced” “upper region” as in Section 2, and where C(N, m, L) denotes the resulting “lower half”, i.e., a region similar to C(N, m, l) (which appeared in Figure 3), however, where along the “upper border” of the region the rhombi from the set L are removed. As in Section 2, the symbol R̃(C(N, m, L)) denotes the weighted count of rhombus tilings of C(N, m, L) in which each of the top-most (horizontal) rhombi counts with weight 1/2. A similar result (generalizing (2.3)) holds for the case of a hexagon with sides N, 2m − 1, N, N, 2m − 1, N.

Clearly, since R(S(N −1, m)) is already known (see (2.4) and (2.6)), “all” we need is the weighted count R̃(C(N, m, L)). Again, the tiling problem can be translated into nonintersecting lattice paths, and from the lattice path interpretation we obtain a determinant for R̃(C(N, m, L)). To be precise, we have

R̃(C(N, m, L)) = det_{1≤i,j≤N} (\begin{cases}\frac{(N+m−i)!}{(m+i−j)! (N+j−2i+1)!}(m + \frac{N−j+1}{2}) & if i ∉ L \\ \frac{(N+m−i)!}{(m+i−j)! (N+j−2i)!} & if i ∈ L \end{cases}) . (4.2)

The reader should compare this determinant with the one in (2.5). Now we do not have just one “exceptional” row, now we have r = |L| “exceptional” rows. In fact, this determinant can be regarded as the determinant of a “mixture” of two matrices,

A = (\frac{(N + m − i)!}{(m + i − j)! (N + j − 2i + 1)!}(m + \frac{N−j+1}{2}))_{1≤i,j≤N}

and

B = (\frac{(N + m − i)!}{(m + i − j)! (N + j − 2i)!})_{1≤i,j≤N} .

Now, to perform the task of evaluating the determinant, we would try to follow the proof of Lemma 5 in Section 3. Indeed, Auxiliary Facts I and II, and Steps 1–3 carry over, when suitably modified. In particular, the analogue of (3.4) reads:

The determinant in (4.2) equals

∏_{i=1}^{⌊N/2⌋}(m + i)_{N−2i+1} ∏_{i=r}^{⌊N/2⌋}(m + i + \frac{1}{2})_{N−2i} · P (m; N, L),  (4.3)

where P (m; N, L) is a polynomial in m of degree at most r(N − r).

The reader should compare with (3.4) and observe the differences: First, the second product in (4.3) is “smaller” than the corresponding product in (3.4). Second, and unfortunately, the degree of P (m; N, L) is in general considerably larger than the degree of P (m; N, l).

It is here where the problems start. Now it comes to carry over Step 4. At present, we do not know how to accomplish that. In order to determine P (m; N, L) we would need r(N − r) + 1 evaluations of P (m; N, L). What we are able to do is to follow Step 4 in Section 3 and determine the value of P (m; N, L) at m = 0, −1, …, −N. Unfortunately, for r > 1, this is not good enough.

Still, we do believe that a reasonable formula for P (m; N, L) can be found. In fact, it appears that, quite often, P (m; N, L) does indeed factor further. At this point, we want to direct the reader’s attention to the fact that this is also the case for P (m; N, l), the polynomial that was defined in (3.4) and which equals the second line of (3.3). For, from the expression given by the second line of (3.3), it is immediately obvious that (m+l)_{N−2l+1} divides P (m; N, l). In particular, if l = 1 then P (m; N, l) factors completely into linear factors.

A similar phenomenon seems to hold for P (m; N, L) in general. Namely, for L = {1, 2, …, r} it appears that P (m; N, L) factors completely into linear factors (see Conjecture 1 below). And, whenever we move a rhombus by 1 to the right then the degree of P (m; N, L) in m increases by 2 (at least for large N; compare Conjectures 1–3 below).

We have worked out a few conjectures corresponding to “small” L, meaning that the numbers in L are small, which means that the fixed rhombi are far left in the hexagon.

Conjecture 1. Let m be a nonnegative integer and N and r be positive integers with N ≥ r. The number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N, which contain rhombi 1, 2, …, r on the symmetry axis which cuts through the sides of length 2m, equals

2^{\frac{1}{2} (r−1)(r−2N)} \begin{matrix}\binom{m+N−1}{m} & 2 \\ ( & {2m+2N−1 \atop 2m} & ) \end{matrix} ∏_{i=N−r}^{N−2} \frac{1}{i!} ∏_{i=1}^{r−1} \frac{(2i)!! (2N − 2i − 1)!! (m + i + 1)_{N−2i−1}}{(2i − 1)!! (m + i + 1/2)_{N−2i}}

× ∏_{i=1}^{N} ∏_{j=1}^{N} ∏_{k=1}^{2m} \frac{i + j + k − 1}{i + j + k − 2}. (4.4)

The number of rhombus tilings of a hexagon with sides N + 1, 2m − 1, N + 1, N + 1, 2m − 1, N + 1, which contain rhombi 1, 2, …, r on the symmetry axis which cuts through the sides of length 2m − 1, equals

2^{\frac{1}{2} (r−1)(r−2N)} \begin{matrix}\binom{m+N−1}{m} & 2 \\ ( & {2m+2N−1 \atop 2m} & ) \end{matrix} ∏_{i=N−r}^{N−2} \frac{1}{i!} ∏_{i=1}^{r−1} \frac{(2i)!! (2N − 2i − 1)!! (m + i + 1)_{N−2i−1}}{(2i − 1)!! (m + i + 1/2)_{N−2i}}

× ∏_{i=1}^{N+1} ∏_{j=1}^{N+1} ∏_{k=1}^{2m−1} \frac{i + j + k − 1}{i + j + k − 2}, (4.5)

Conjecture 2. Let m be a nonnegative integer and N and r be positive integers with N ≥ r + 1. The number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N, which contain rhombi 1, 2, …, r − 1, r + 1 on the symmetry axis which cuts through the sides of length 2m, equals

2^{\frac{1}{2} (r−1)(r−2N)} \frac{3r(N − r)}{(2r − 1)(2N − 2r + 1)(m + r)(m + N − r)}

× (m^{2} + Nm + \frac{(2r−1)(2N−2r+1)}{3}) \begin{matrix}\binom{m+N−1}{m} & 2 \\ ( & {2m+2N−1 \atop 2m} & ) \end{matrix} ∏_{i=N−r}^{N−2} \frac{1}{i!}

× ∏_{i=1}^{r−1} \frac{(2i)!! (2N − 2i − 1)!! (m + i + 1)_{N−2i−1}}{(2i − 1)!! (m + i + 1/2)_{N−2i}} ∏_{i=1}^{N} ∏_{j=1}^{N} ∏_{k=1}^{2m} \frac{i + j + k − 1}{i + j + k − 2}. (4.6)

The number of rhombus tilings of a hexagon with sides N + 1, 2m − 1, N + 1, N + 1, 2m − 1, N + 1, which contain rhombi 1, 2, …, r − 1, r + 1 on the symmetry axis which cuts through the sides of length 2m − 1, equals

2^{\frac{1}{2} (r−1)(r−2N)} \frac{3r(N − r)}{(2r − 1)(2N − 2r + 1)(m + r)(m + N − r)}

× (m^{2} + Nm + \frac{(2r−1)(2N−2r+1)}{3}) \begin{matrix}\binom{m+N−1}{m} & 2 \\ ( & {2m+2N−1 \atop 2m} & ) \end{matrix} ∏_{i=N−r}^{N−2} \frac{1}{i!}

× ∏_{i=1}^{r−1} \frac{(2i)!! (2N − 2i − 1)!! (m + i + 1)_{N−2i−1}}{(2i − 1)!! (m + i + 1/2)_{N−2i}} ∏_{i=1}^{N+1} ∏_{j=1}^{N+1} ∏_{k=1}^{2m−1} \frac{i + j + k − 1}{i + j + k − 2}, (4.7)

Conjecture 3. Let m be a nonnegative integer and N and r be positive integers with N ≥ r + 2. The number of rhombus tilings of a hexagon with sides N, 2m, N, N, 2m, N, which contain rhombi 1, 2, …, r − 1, r + 2 on the symmetry axis which cuts through the sides of length 2m, equals

2^{\frac{1}{2} (r−1)(r−2N)} \frac{45}{64} \frac{(r)_{2} (N − r − 1)_{2}}{(r − 1/2)_{2} (N − r − 1/2)_{2} (m + r)_{2} (m + N − r − 1)_{2}}

(m^{4} + 2Nm^{3} + (N^{2} + \frac{(20r+1)N}{9} − \frac{20r^{2}+2r+5}{9}) m^{2}

+\frac{((20r+1)N−20r^{2}−2r−5)}{9}Nm + \frac{4}{45}(2r − 1)(2r + 1)(2N − 2r − 1)(2N − 2r + 1))

× \begin{matrix}\binom{m+N−1}{m} & 2 \\ ( & {2m+2N−1 \atop 2m} & ) \end{matrix} ∏_{i=N−r}^{N−2} \frac{1}{i!} ∏_{i=1}^{r−1} \frac{(2i)!! (2N − 2i − 1)!! (m + i + 1)_{N−2i−1}}{(2i − 1)!! (m + i + 1/2)_{N−2i}}

× ∏_{i=1}^{N} ∏_{j=1}^{N} ∏_{k=1}^{2m} \frac{i + j + k − 1}{i + j + k − 2}. (4.8)

The number of rhombus tilings of a hexagon with sides N + 1, 2m − 1, N + 1, N + 1, 2m − 1, N + 1, which contain rhombi 1, 2, …, r − 1, r + 2 on the symmetry axis which cuts through the sides of length 2m − 1, equals

2^{\frac{1}{2} (r−1)(r−2N)} \frac{45}{64} \frac{(r)_{2} (N − r − 1)_{2}}{(r − 1/2)_{2} (N − r − 1/2)_{2} (m + r)_{2} (m + N − r − 1)_{2}}

(m^{4} + 2Nm^{3} + (N^{2} + \frac{(20r+1)N}{9} − \frac{20r^{2}+2r+5}{9}) m^{2}

+\frac{((20r+1)N−20r^{2}−2r−5)}{9}Nm + \frac{4}{45}(2r − 1)(2r + 1)(2N − 2r − 1)(2N − 2r + 1))

× \begin{matrix}\binom{m+N−1}{m} & 2 \\ ( & {2m+2N−1 \atop 2m} & ) \end{matrix} ∏_{i=N−r}^{N−2} \frac{1}{i!} ∏_{i=1}^{r−1} \frac{(2i)!! (2N − 2i − 1)!! (m + i + 1)_{N−2i−1}}{(2i − 1)!! (m + i + 1/2)_{N−2i}}

× ∏_{i=1}^{N+1} ∏_{j=1}^{N+1} ∏_{k=1}^{2m−1} \frac{i + j + k − 1}{i + j + k − 2}, (4.9)

Without difficulty we could move on and work out further conjectures. Already these three conjectures do contain so many similarities, so that the “next” formula, the formula for fixing rhombi 1, 2, …, r − 1, r + 4, can, almost, be guessed right away. Still, these guesses do not seem to help for the determinant evaluations that would be needed to prove these enumerations. So we content ourselves with these three conjectures, and hope that they give enough evidence that in this area there are a lot of further beautiful results waiting to be unearthed, and proved, of course.

References

[1] M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), 67-97.

[2] M. Ciucu and C. Krattenthaler, The number of centered lozenge tilings of a symmetric hexagon, preprint.

[3] H. Cohn, M. Larsen and J. Propp, The shape of a typical boxed plane partition, preprint.

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

[5] M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, II, in preparation.

[6] I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint, 1989.

[7] H. Helfgott and I. M. Gessel, Exact enumeration of certain tilings of diamonds and hexagons with defects, preprint.

[8] C. Krattenthaler, Generating functions for plane partitions of a given shape, Manuscripta Math. 69, (1990), 173–202.

[9] 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-Ver-lag, Berlin, 1990.

[10] C. Krattenthaler, Some q-analogues of determinant identities which arose in plane partition enumeration, Séminaire Lotharingien Combin. 36, (1996), paper B36e, 23 pp.

[11] C. Krattenthaler, A new proof of the M–R–R conjecture — including a generalization, preprint.

[12] C. Krattenthaler, An alternative evaluation of the Andrews–Burge determinant, to appear in the “Rotafestschrift”.

[13] C. Krattenthaler, Determinant identities and a generalization of the number of totally symmetric self-complementary plane partitions, Electron. J. Combin. 4(1) (1997), #R27, 62 pp.

[14] C. Krattenthaler and D. Zeilberger, Proof of a determinant evaluation conjectured by Bombieri, Hunt and van der Poorten, New York J. Math., 3 (1997), 54–102.

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

[16] J. Propp, Twenty open problems on enumeration of matchings, manuscript, 1996.

[17] A.P. Prudnikov, Yu.A. Brychkov, O.I. Marichev, Integrals and Series, vol. 3: More Special Functions, Gordon and Breach, New York, London, 1989.

[18] L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

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

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria, e-mail: Mfulmek@Mat.Univie.Ac.At, Kratt@Pap.Univie.Ac.At