ENUMERATION OF RHOMBUS TILINGS OF A HEXAGON WHICH

CONTAIN A FIXED RHOMBUS ON ITS SYMMETRY AXIS

(EXTENDED ABSTRACT)

M. CIUCU, M. FULMEK AND C. KRATTENTHALER

Summary. 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. A special case solves a problem posed by Jim Propp.

Résumé. Nous considérons ici des pavages à l’aide de losanges. Nous calculons le nombre de tels pavages d’un hexagone de dimension N, M, N, N, M, N, qui contiennent un losange fixé sur un axe de symétrie. Dans un cas particulier, nous obtenons la solution d’un problème posé par Jim Propp.

1. Introduction

In recent years, the enumeration of rhombus tilings of various regions has attracted a lot of interest and was intensively studied, mainly because of the observation (see [14]) that the problem of enumerating all rhombus tilings of a hexagon with sides a, b, c, a, b, c and whose angles are 120^{∘} (see Figure 1; throughout the paper by a rhombus we always mean a rhombus with side lengths 1 and angles of 60^{∘} and 120^{∘}) is another way of stating the problem of counting all plane partitions inside an a × b × c box. The latter problem 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 statistical investigation of which rhombi lie in a random rhombus tiling has been undertaken, on an asymptotic level, by Cohn, Larsen and Propp [3]. On the exact (enumerative) level, Propp [18, Problem 1] observed numerically that apparently exactly one third of the rhombus tilings of a hexagon with side lengths 2n − 1, 2n, 2n − 1, 2n − 1, 2n, 2n − 1 contain the central rhombus.

In this article we present the solution of 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

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 given 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)

The special case of Theorem 1 where the fixed rhombus is the central rhombus was proved by the first and third author [2], and independently by Helfgott and Gessel [6, Theorem 12], using a different method. Building on the approach of [2], the second and third author [4] were able to generalize the enumeration to the above theorems.

The special case N = 2n−1, m = n of Theorem 1 does indeed imply Propp’s conjecture.

Corollary 3. Let n be a positive integer. Exactly one third of the rhombus tilings of a hexagon with sides 2n − 1, 2n, 2n − 1, 2n − 1, 2n, 2n − 1 cover the central rhombus. The same is true for a hexagon with sides 2n, 2n − 1, 2n, 2n, 2n − 1, 2n.

Finally, from Theorems 1 and 2, we derive an “arcsine law” for this kind of enumeration. It complements the asymptotic results by Cohn, Larsen and Propp [3]. In particular, it adds evidence to Conjecture 1 in [3].

Theorem 4. 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.

In the remainder of this article we sketch proofs of these results. In the next section we provide brief outlines of the proofs of Theorems 1, 2, 4 and Corollary 3. The proof (or rather, a sketch of the proof) of a crucial auxiliary lemma is deferred to Section 3.

2. Outline of proofs

Outline of 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 the first author’s Matchings Factorization Theorem [1, Thm. 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 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 Figure 3), and where R̃(C(m, n, l)) denotes the weighted count of rhombus tilings of C(m, n, l) in which each of the topmost (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 “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.)

In the case of Theorem 1 it is immediately obvious, that the rhombi along the leftmost and right-most vertical strip of S′(N, m) must be contained in any rhombus tiling of S′(N, m). Hence, we may safely remove these strips. 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)

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

Figure 3. Hexagons, cut in two

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 (i + m, 2i − N − 1), 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 (i, i) to (i + m, 2i − N − 1) if i ≠ l, while P_{l} runs from (l, l) to (l + m, 2l − N); with the additional twist that path P_{i} (i ≠ l) has weight 1/2 if it ends with a vertical step.

Step 3. From nonintersecting lattice paths to determinants. Now, by using the main theorem on nonintersecting lattice paths [5, Cor. 2] (see also [21, 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{N + m − i + 1}{m + i − j}) ,  (2.4)

Tilings for the “complicated parts” from Figure 3, interpreted as lattice paths: Reflect and rotate the dotted paths to obtain the paths in the lower picture.

Figure 4. Lattice path interpretation

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 5.

det_{1≤i,j≤N} (\binom{N + m − i + 1}{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 [7, Lemma 2.2]. The corresponding computation is contained in the proof of Theorem 5 in [8] (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 6.

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 5, and, as such, is the most difficult part in our derivation of Theorems 1 and 2. We provide a sketch of how to evaluate this determinant in the next section.

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

Proof of Corollary 3. We have to compute the ratio of the expression (1.2), with N = 2n − 1, m = n, by the expression (1.1), with a = b = 2n − 1, c = 2n, respectively the ratio of the expression (1.3), with N = 2n − 1, m = n, by the expression (1.1), with a = b = 2n, c = 2n − 1. Clearly, except for trivial manipulations, we will be done once we are able to evaluate the sum in (1.2) (which is the same as the one in (1.3)) for N = 2n−1, m = n, and l = n.

We claim that

∑_{e=0}^{n−1}(−1)^{e}\binom{2n − 1}{e}\frac{(2n − 2e − 1)(\frac{1}{2})_{e}}{(n + e)(3n − e − 1)(\frac{3}{2} − 2n)_{e}} = 2^{n−1} \frac{n! (n − 1)! (6n − 3)!!}{(3n)! (4n − 3)!!}.

Let us denote the sum by S(n). Then an application of the Gosper–Zeilberger algorithm [17, 22, 23] (we used the Mathematica implementation by Paule and Schorn [16]) yields the relation

2n(2n + 1)(6n − 1)(6n + 1)S(n) − (3n + 1)(3n + 2)(4n − 1)(4n + 1)S(n + 1) = 0, which easily proves the claimed summation by an induction on n.

Outline of proof of Theorem 4. 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 and 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)

Using a special case of Whipple’s transformation (see [20, (2.4.1.1)]), we transform the sum in (2.9) into a _{4}F_{3}-series, thus obtaining

\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]

for the ratio (2.8).

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

\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.10)

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.10) 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 [19, 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. Sketch of proof of Lemma 6

The method that we use for this proof is also applied successfully in [12, 9, 10, 11, 13] (see in particular the tutorial description in [11, 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)

Let us denote the determinant in (3.1) by D(m; N, l). Comparison of (2.7) and (3.1) yields that (2.7) will be proved once we are able to establish the determinant evaluation

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.2)

For the proof of (3.2) we proceed in several steps. 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 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 D(m; N, l). In the third step we determine the maximal degree of 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 conclude that

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.3)

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, assuming l ≥ ⌊\frac{N+1}{2}⌋, we show that P (m; N, l) = 0 for m = −N + l − 1, …, − ⌊N/2⌋, and for m = 0, −1, …, −N + l 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.4)

Moreover, we show that P (m; N, l) = (−1)^{N−1}P (−N − m; N, l), which in combination with (3.4) 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. Since, as we will show, we also have the symmetry P (m; N, l) = P (m; N, N − l), we have in fact determined P (m; N, l) for 1 ≤ l ≤ N. As it turns out, the resulting expression for P (m; N, l) is exactly the second line of (3.2). In view of (3.3), this would establish (3.2) and, hence, finish the proof of the Lemma.

Before going into details of these steps, it is useful to observe the symmetry

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

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 D(m; N, l) do not affect this symmetry, therefore 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.

Another useful symmetry is

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

In order to establish (3.6), we multiply the matrix underlying D(m; N, l) (as defined in (3.1)) by the upper triangular matrix ((−1)^{j}\binom{j−1}{i−1})_{1≤i,j≤N}. Using either the Gosper-Zeilberger algorithm or elementary “hypergeometrics” (a contiguous relation and Vandermonde summation), the result of this multiplication is the original matrix with m replaced by −N − m, except that all the entries in row l have opposite sign. Hence, the equation (3.6) follows immediately.

Now we are ready for giving details of Steps 1–4.

Step 1. ∏_{i=1}^{⌊N/2⌋}(m + i)_{N−2i+1} is a factor of D(m; N, l). Here, for the first time, we make use of the symmetry (3.5). 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 determinant D(m; N, l). Recalling that D(m; N, l) is defined as the determinant in (3.1), 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 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.5), 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.6), 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 + 1 − 2e + k + j) of D(−e − 1/2; N, l))

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

As is not very difficult to see (cf. [11, Sec. 2]) this would imply that (m+e+1/2)^{e} divides D(m; N, l).

Obviously, a proof of (3.7) amounts to proving two hypergeometric identities, one for the restriction of (3.7) to the i-th row, i ≠ l, and another for the restriction of (3.7) to the l-th row itself. Both identities can be easily established by using either the Gosper– Zeilberger algorithm or elementary “hypergeometrics” (again, a contiguous relation and Vandermonde summation).

Step 3. 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. This step is the most technical one, therefore we shall be somewhat brief here.

Again, we make use of the symmetry (3.5), and this time restrict ourselves to ⌊\frac{N+1}{2}⌋ ≤ l ≤ N. On the other hand, by the symmetry (3.6) and by the definition (3.3) 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.3), compute D(−e; N, l), and then express P (−e; N, l) as the ratio of D(−e; N, l) and the right-hand side product evaluated at m = −e. Unfortunately, this is typically a ratio

[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

0/0 and, hence, undetermined. So, we have to first divide both sides of (3.3) 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.8)

to column N + 1 − 2e + k of D(m; N, l). The effect (which is again proved by either the Gosper–Zeilberger algorithm or “hypergeometrics”) is that then (m + e) is a factor of each entry in column N + 1 − 2e + k. So, we take (m + e) out of each entry of column N + 1 − 2e + k, k = 0, 1, …, e − 1.

Let D_{2}(m; N, l, e) denote the resulting determinant. From what we did so far, it is straight-forward that we must have

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

A combination with (3.3) gives that

P (m; N, l) = D_{2}(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.9)

Now, in order to determine the evaluation of P (m; N, l) at m = −e, we set m = −e in (3.9). It turns out that the determinant D_{2}(−e; N, l, e) vanishes for e ≥ N +1−l, whereas for e < N + 1 − l the matrix underlying D_{2}(−e; N, l, e) has a block form as illustrated in Figure 5. Therefore, in the latter case, the determinant D_{2}(−e; N, l, e) equals the product of the determinants of Q_{1}, Q_{2}, and M, each of which can be easily evaluated explicitly. For, Q_{1} and Q_{2} are upper and lower triangular matrices, respectively, and the determinant of M is again easily determined by applying the Determinant Lemma [7, Lemma 2.2]. Then, by combining these computations with (3.9), and performing some simplification, the evaluation (3.4) follows.

This finishes the proof of Lemma 6.

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] M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on its symmetry axis, I , preprint.

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

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

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

[8] 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.

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

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

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

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

[13] 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.

[14] G. Kuperberg, Symmetries of plane partitions and the permanent determinant method, J. Combin. Theory Ser. A 68 (1994), 115–151.

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

[16] P. Paule and M. Schorn, A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities, J. Symbol. Comp. 20 (1995), 673–698.

[17] M. Petkovšek, H. Wilf and D. Zeilberger, A=B, A.K. Peters, Wellesley 1996.

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

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

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

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

[22] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990), 207–211.

[23] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195–204.

School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA, e-mail: ciucu@ias.edu

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