ENUMERATION OF LOZENGE TILINGS OF HEXAGONS WITH A CENTRAL TRIANGULAR HOLE

M. CIUCU^{†}, T. EISENKÖLBL, C. KRATTENTHALER^{‡}, D. ZARE

Department of Mathematics, Georgia Institute of Technology Atlanta, GA 30332-0160

Institut für Mathematik der Universität Wien Strudlhofgasse 4, A-1090 Wien, Austria

Department of Mathematics, Columbia University New York, NY 10027

Abstract. We deal with unweighted and weighted enumerations of lozenge tilings of a hexagon with side lengths a, b + m, c, a + m, b, c + m, where an equilateral triangle of side length m has been removed from the center. We give closed formulas for the plain enumeration and for a certain (−1)-enumeration of these lozenge tilings. In the case that a = b = c, we also provide closed formulas for certain weighted enumerations of those lozenge tilings that are cyclically symmetric. For m = 0, the latter formulas specialize to statements about weighted enumerations of cyclically symmetric plane partitions. One such specialization gives a proof of a conjecture of Stembridge on a certain weighted count of cyclically symmetric plane partitions. The tools employed in our proofs are nonstandard applications of the theory of nonintersecting lattice paths and determinant evaluations. In particular, we evaluate the determinants det_{0≤i,j≤n−1} (ωδ_{ij} + \binom{m+i+j}{j}), where ω is any 6th root of unity. These determinant evaluations are variations of a famous result due to Andrews (Invent. Math. 53 (1979), 193–225), which corresponds to ω = 1.

1. Introduction

Let a, b and c be positive integers, and consider a hexagon with side lengths a, b, c, a, b, c (in cyclic order) and angles of 120^{∘}. It is well-known that the total number of lozenge^{1}

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A17 05A19 05B45 33C20 52C20.

Key words and phrases. lozenge tilings, rhombus tilings, plane partitions, determinants, nonintersecting lattice paths.

† Research partially supported by a membership at the Institute for Advanced Study and by NSF grant DMS 9802390.

‡ Research partially supported by the Austrian Science Foundation FWF, grant P12094-MAT and P13190-MAT.

1 Here and in the following, by a lozenge we mean a rhombus with side lengths 1 and angles of 60^{∘} and 120^{∘}.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001 by Academic Press

tilings of such a hexagon equals

\frac{H(a) H(b) H(c) H(a + b + c)}{H(a + b) H(b + c) H(c + a)},  (1.1)

where H(n) stands for the “hyperfactorial” ∏_{k=0}^{n−1} k!. This follows from a bijection (cf. [7]) between such lozenge tilings and plane partitions contained in an a × b × c box, and from MacMahon’s enumeration [26, Sec. 429, q → 1; proof in Sec. 494] of the latter.

In [33] (see also [34]), Propp posed several problems regarding “incomplete” hexagons. For example, Problem 2 in [33] (and [34]) asks for the number of lozenge tilings of a hexagon with side lengths n, n+1, n, n+1, n, n+1 with the central unit triangle removed. This problem was solved in [4, Theorem 1], [15, Theorem 20] and [32, Theorem 1] (the most general result, for a hexagon with side lengths a, b + 1, c, a + 1, b, c + 1, being contained in [32]). In [5], the first author considers the case when a larger triangle (in fact, possibly several) is removed. However, in contrast to [32], the results in [5] assume that the hexagon has a reflective symmetry, i.e., that b = c.

Continuing this line of research, in this paper we address the general case, when no symmetry axis is required. We consider hexagons of sides a, b + m, c, a + m, b, c + m (in clockwise order) with an equilateral triangle of side m removed from the center (see Figures 1 and 2 for examples). We call this triangle the core, and the leftover region, denoted C_{a,b,c}(m), a cored hexagon.

To define C_{a,b,c}(m) precisely, we need to specify what position of the core is the “central” one. Let s be a side of the core, and let u and v be the sides of the hexagon parallel to it. The most natural definition (and the one that we are going to adopt) would require that the distance between s and u is the same as the distance between v and the vertex of the core opposite s, for all three choices of s.

However, since the sides of the core have to be along lines of the underlying triangular lattice, it is easy to see that this can be achieved only if a, b and c have the same parity (Figure 1 illustrates such a case); in that case, we define this to be the position of the core. On the other hand, if for instance a has parity different from that of b and c, the triangle satisfying the above requirements would only have one side along a lattice line, while each of the remaining two extends midway between two consecutive lattice lines (this can be seen from Figure 2). To resolve this, we translate this central triangle half a unit towards the side of the hexagon of length b, in a direction parallel to the side of length a, and define this to be the position of the core in this case.

Note that, when translating the central triangle, there is no “natural” reason to do it in the sense we chose: we could have just as well chosen the opposite sense, obtaining an alternative (and not less central) definition of the core. However, it is easy to see that the alternative definition does not lead to new regions: it generates the same region that we obtain by swapping b and c in our definition. (In fact, this ambiguity in choosing the center will be used effectively in Section 12, see Theorem 29 and the paragraph preceding it.)

Our main results, given in Theorems 1 and 2 below, provide explicit formulas for the total number of lozenge tilings of such a cored hexagon (see Figures 3 and 8.a for examples of such tilings). Remarkably, the results can be expressed in closed form, more precisely, as quotients of products of hyperfactorials (completely analogous to formula (1.1)), thus providing an infinite family of enumerations which contains MacMahon’s

a  b + m  } c c + m {  b  a + m } m  } {  } {

Figure 1. Position of the core when a, b and c have the same parity: C_{3,5,1}(2)

a  b + m  } c c + m {  b  a + m } m  } {  } {

Figure 2. Position of the core when a, b and c have mixed parities: C_{2,5,1}(2)

“box formula” (1.1) as a special case. For the statement of the theorems, it is convenient to extend the definition of hyperfactorials to half-integers (i.e., odd integers divided by 2):

H(n) := \begin{cases}∏_{k=0}^{n−1} Γ(k + 1) & for n an integer, \\ ∏_{k=0}^{n− \frac{1}{2}} Γ(k + \frac{1}{2}) & for n a half-integer. \end{cases}

Now we are able to state our theorems. The first result addresses the case that a, b and c have the same parity. Let L(R) stand for the number of lozenge tilings of the region R. Theorem 1. Let a, b, c, m be nonnegative integers, a, b, c having the same parity. The number of lozenge tilings of a hexagon with sides a, b + m, c, a + m, b, c + m, with an equilateral triangle of side m removed from its center (see Figure 1 for an example) is given by

L(C_{a,b,c}(m)) =

\frac{H(a + m) H(b + m) H(c + m) H(a + b + c + m)}{H(a + b + m) H(a + c + m) H(b + c + m)} \frac{H(m + ⌈\frac{a+b+c}{2}⌉) H(m + ⌊\frac{a+b+c}{2}⌋)}{H(\frac{a+b}{2} + m) H(\frac{a+c}{2} + m) H(\frac{b+c}{2} + m)}

× \frac{H(⌈\frac{a}{2}⌉) H(⌈\frac{b}{2}⌉) H(⌈\frac{c}{2}⌉) H(⌊\frac{a}{2}⌋) H(⌊\frac{b}{2}⌋) H(⌊\frac{c}{2}⌋)}{H(\frac{m}{2} + ⌈\frac{a}{2}⌉) H(\frac{m}{2} + ⌈\frac{b}{2}⌉) H(\frac{m}{2} + ⌈\frac{c}{2}⌉) H(\frac{m}{2} + ⌊\frac{a}{2}⌋) H(\frac{m}{2} + ⌊\frac{b}{2}⌋) H(\frac{m}{2} + ⌊\frac{c}{2}⌋)}

× \frac{H(\frac{m}{2})^{2} H(\frac{a+b+m}{2})^{2} H(\frac{a+c+m}{2})^{2} H(\frac{b+c+m}{2})^{2}}{H(\frac{m}{2} + ⌈\frac{a+b+c}{2}⌉) H(\frac{m}{2} + ⌊\frac{a+b+c}{2}⌋) H(\frac{a+b}{2}) H(\frac{a+c}{2}) H(\frac{b+c}{2})}. (1.2)

Clearly, formula (1.2) reduces to (1.1) for m = 0 (as it should). The special case m = 1 has been obtained earlier in [32, Theorem 1].

The corresponding result for the case when a, b and c do not have the same parity reads as follows.

Theorem 2. Let a, b, c, m be nonnegative integers, with a of parity different from the parity of b and c. The number of lozenge tilings of a hexagon with sides a, b + m, c, a + m, b, c + m, with the “central” (in the sense described above) triangle of side m removed (see Figure 2 for an example) is given by

L(C_{a,b,c}(m)) =

H (a + m) H (b + m) H (c + m) H (a + b + c + m) H (m + ⌈\frac{a+b+c}{2}⌉) H (m + ⌊\frac{a+b+c}{2}⌋) ; H (a + b + m) H (a + c + m) H (b + c + m) H (⌊\frac{a+c}{2}⌋ + m) H (\frac{b+c}{2} + m) H (⌈\frac{a+b}{2}⌉ + m)

× H (\frac{m}{2})^{2} H (⌈\frac{a}{2}⌉) H (⌈\frac{b}{2}⌉) H (⌈\frac{c}{2}⌉) H (⌊\frac{a}{2}⌋) H (⌊\frac{b}{2}⌋) H (⌊\frac{c}{2}⌋) ; H (\frac{m}{2} + ⌈\frac{a}{2}⌉) H (\frac{m}{2} + ⌈\frac{b}{2}⌉) H (\frac{m}{2} + ⌈\frac{c}{2}⌉) H (\frac{m}{2} + ⌊\frac{a}{2}⌋) H (\frac{m}{2} + ⌊\frac{b}{2}⌋) H (\frac{m}{2} + ⌊\frac{c}{2}⌋)

× H (⌈\frac{a+b}{2}⌉ + \frac{m}{2}) H (⌊\frac{a+b}{2}⌋ + \frac{m}{2}) H (⌊\frac{a+c}{2}⌋ + \frac{m}{2}) H (⌈\frac{a+c}{2}⌉ + \frac{m}{2}) H (\frac{b+c}{2} + \frac{m}{2})^{2} ; H (\frac{m}{2} + ⌈\frac{a+b+c}{2}⌉) H (\frac{m}{2} + ⌊\frac{a+b+c}{2}⌋) H (⌊\frac{a+b}{2}⌋) H (⌈\frac{a+c}{2}⌉) H (\frac{b+c}{2}) . (1.3)

Again, formula (1.3) reduces to (1.1) for m = 0. The special case m = 1 has been obtained earlier in [32, Theorem 4].

Given the explicit results in Theorems 1 and 2, it is routine to determine, using the Euler–MacLaurin summation formula, the asymptotic behavior of the number of lozenge tilings of a cored hexagon. For instance, when a, b and c have the same parity we obtain the following result.

Corollary 3. Let a, b, c, m, n be nonnegative integers, a, b, c having the same parity. The number of lozenge tilings of a hexagon with sides an, (b+m)n, cn, (a+m)n, bn, (c+m)n, with an equilateral triangle of side mn removed from its center, is asymptotically given by

L(C_{an,bn,cn}(mn)) ∼ e^{kn^{2}}, n → ∞,

where

k = \frac{(a+m)^{2}}{2} log(a + m) + \frac{(b+m)^{2}}{2} log(b + m) + \frac{(c+m)^{2}}{2} log(c + m)

+ \frac{(a+b+c+m)^{2}}{2} log(a + b + c + m) + 2(m + \frac{a+b+c}{2})^{2} log(m + \frac{a+b+c}{2})
+ 2(\frac{b}{2})^{2} log(\frac{b}{2}) + 2(\frac{c}{2})^{2} log(\frac{c}{2}) + 2(\frac{a}{2})^{2} log(\frac{a}{2}) + (\frac{m}{2})^{2} log(m)
− (\frac{3}{4}(a + b + m)^{2} log(a + b + m) + \frac{3}{4}(a + c + m)^{2} log(a + c + m)
+ \frac{3}{4}(b + c + m)^{2} log(b + c + m)

+ (\frac{a+b}{2} + m)^{2} log(\frac{a+b}{2} + m) + (\frac{a+c}{2} + m)^{2} log(\frac{a+c}{2} + m) + (\frac{b+c}{2} + m)^{2} log(\frac{b+c}{2} + m)

+(\frac{a+b}{2})^{2} log(a + b) + (\frac{a+c}{2})^{2} log(a + c) + (\frac{b+c}{2})^{2} log(b + c))

+ (m^{2} + a^{2} + b^{2} + c^{2} + \frac{3m(a+b+c)}{2} + ab + bc + ca) log 2. (1.4)

In addition to plain counts, (−1)-enumerations of plane partitions, i.e., enumerations where plane partitions are given a weight of 1 or −1, according to certain rules, have been found to possess remarkable properties (see [39, 40]). Motivated in part by a conjectured (−1)-enumeration on cyclically symmetric plane partitions due to Stembridge [41], in Section 2 we consider a (−1)-enumeration of the lozenge tilings of Theorems 1 and 2. The corresponding results are given in Theorems 4 and 5.

In Section 3, we restrict our attention to cyclically symmetric lozenge tilings (i.e., tilings invariant under rotation by 120^{∘}) of cored hexagons. Clearly, this makes sense only if a = b = c, i.e., for cored hexagons of the form C_{a,a,a}(m). The plain enumeration of such cyclically symmetric lozenge tilings had already been considered in [6, Theorem 3.2 and Corollary 3.3]. We restate the result here as Theorem 6. We provide several additional results. Theorem 7 concerns the (−1)-enumeration of such cyclically symmetric lozenge tilings and some additional weighted enumerations of them, where each lozenge tiling is weighted by some 6th root of unity, according to a certain rule (see the paragraph before Theorem 7 for the precise definition). In the special case m = 0 we obtain results about weighted enumerations of cyclically symmetric plane partitions (see Corollary 8). A particular case of Corollary 8 proves a conjecture of Stembridge [41, Case 9 on p. 6] about a certain (−1)-enumeration of cyclically symmetric plane partitions. (The first proof of this conjecture, by totally different means, is due to Kuperberg [23, last displayed equation on p. 27].) Our results also allow us to prove another conjecture on (−1)-enumeration of cyclically symmetric plane partitions due to Stembridge [41, Case 10 on p. 7]. In fact, we again prove a more general result, namely a result on cyclically symmetric lozenge tilings (see Theorem 9).

The remaining sections, Sections 4–11, are devoted to the proofs of these results. For the proofs of Theorems 1–5, the enumeration results for lozenge tilings without symmetry, we proceed as follows. First, we identify tilings with certain families of nonintersecting lattice paths (see Section 5). Then, a nonstandard application of the main theorem on nonintersecting lattice paths [24, Lemma 1], [13, Theorem 1] (restated here in Lemma 14) provides a determinant for the weighted count of lozenge tilings (see (5.4), respectively (5.5)). To be precise, the determinant gives the correct weighted count either only for even m (m being the side of the core) or only for odd m, depending on whether we are considering plain enumeration or (−1)-enumeration. To cover the other case as well, we prove that the weighted count of lozenge tilings that we are interested in is polynomial in m, so that it suffices to determine this number only for one of the two possibilities, either for even m or for odd m. This is in turn achieved by evaluating the aforementioned determinant (see Lemmas 17–24).

The results on weighted enumerations of cyclically symmetric lozenge tilings in Section 3 can be obtained in a similar way. We phrase the problem in terms of nonintersecting lattice paths, and thus find determinants for these enumerations. The determinants have the form

det_{0≤i,j≤a−1} (ωδ_{ij} + \binom{m + i + j}{j}) ,  (1.5)

where ω is any 6th root of unity. These determinants are remarkable. The case ω = 1 occured first in the work of Andrews on plane partitions. He evaluated the determinant (1.5) in that case [2, Theorem 8] (restated here as Theorem 10) in order to prove the “weak Macdonald conjecture” on counting cyclically symmetric plane partitions. It had already been observed in [6, Sec. 3] that Andrews’ evaluation of (1.5) with ω = 1 gives the number of cyclically symmetric lozenge tilings of the cored hexagon C_{a,a,a}(m). We prove our weighted enumerations of these lozenge tilings by evaluating the determinant (1.5) when ω is any 6th root of unity (see Theorems 11–13).

Our paper is structured as follows. In Section 2 we give the precise definition of our (−1)-enumeration of lozenge tilings, and we state the corresponding results (see Theorems 4 and 5). In Section 3 we define precisely our unusual weightings of cyclically symmetric lozenge tilings. Theorems 6 and 7, Corollary 8 and Theorem 9 state the corresponding results. The subsequent section, Section 4, gives the proofs of our enumeration results in Theorems 1–9, leaving out, however, several details. These details are then worked out in later sections. First of all, in Section 5, it is explained how lozenge tilings correspond, in a one-to-one fashion, to families of nonintersecting lattice paths. We then employ the result of Lemma 14 to obtain, at least for every other value of m, a determinant for the weighted count of lozenge tilings that we are interested in (see Lemmas 15 and 16). It is then argued in Section 6 that this number is in fact polynomial in m, so that the evaluation of the determinant in Lemma 15, respectively Lemma 16, suffices. The precise form of the evaluation of the determinant in Lemma 15 (again, a case-by-case analysis is necessary, depending on the parity of a) is stated and proved in Section 7 (see Lemmas 17–20), while the precise form of the evaluation of the determinant in Lemma 16 is stated and proved in Section 8 (see Lemmas 21–24). Finally, in Section 9 we prove the determinant evaluation of Theorem 11, in Section 10 the one in Theorem 12, and in Section 11 the one in Theorem 13. We conclude the article with some comments concerning connections of this work with multiple hypergeometric series and some open problems. These are the subject of Section 12.

2. (−1)-enumerations of lozenge tilings of cored hexagons

In this section we enumerate lozenge tilings of a cored hexagon with respect to a certain weight that assigns to each lozenge tiling the value 1 or −1. More precisely, fix a lozenge tiling T of the cored hexagon C_{a,b,c}(m) (see Figures 1 and 2 for examples of such regions, and Figure 3 for an example of a tiling; at this point, the thickness of edges is without significance). Consider the side of the core which is parallel to the sides of the hexagon of lengths a and a + m (in the figure this is the bottommost side of the core). Extend this side of the triangle to the right. Let n(T) be the number of edges of

a  b + m  } c c + m { b  a + m } m  } {  } {

Figure 3. A lozenge tiling of a hexagon with sides a = 5, b = 3, c = 1 and removed triangle of side length m = 2.

lozenges of the tiling T contained in the extended side (in Figure 3 there are two such edges, marked as thick segments). The statistic n(T) becomes most transparent in the lattice path interpretation of lozenge tilings that is going to be explained in Section 5, as it counts exactly the number of paths which pass the core on the right. Furthermore, we shall see in Section 3 that in the plane partitions case, i.e., in the case m = 0 (when the core shrinks to a point), the statistic n(T) has a very natural meaning as well (see the remarks after Theorem 7).

In the (−1)-enumeration, which is the subject of the following two theorems, each lozenge tiling T is weighted by (−1)^{n(T)}. Let L^{−1}(R) be the weighted count of lozenge tilings of region R under the above weight. Theorem 4. Let a, b, c, m be nonnegative integers. If all of a, b and c are even, then the weighted count ∑(−1)^{n(T)}, summed over all lozenge tilings T of a hexagon with sides a, b + m, c, a + m, b, c + m, with an equilateral triangle of side length m removed from its center (see Figure 1) is given by

L^{−1}(C_{a,b,c}(m)) =

(−1)^{a/2} \frac{H(a + m) H(b + m) H(c + m) H(a + b + c + m)}{H(a + b + m) H(a + c + m) H(b + c + m)}

× \frac{H(\frac{a}{2})^{2} H(\frac{b}{2})^{2} H(\frac{c}{2})^{2} H(\frac{m−1}{2}) H(\frac{m+1}{2})}{H(\frac{a}{2} + \frac{m−1}{2}) H(\frac{b}{2} + \frac{m−1}{2}) H(\frac{c}{2} + \frac{m−1}{2}) H(\frac{a}{2} + \frac{m+1}{2}) H(\frac{b}{2} + \frac{m+1}{2}) H(\frac{c}{2} + \frac{m+1}{2})}

× \frac{H(\frac{a+b+m−1}{2}) H(\frac{a+b+m+1}{2}) H(\frac{a+c+m−1}{2}) H(\frac{a+c+m+1}{2}) H(\frac{b+c+m−1}{2}) H(\frac{b+c+m+1}{2})}{H(\frac{a+b}{2}) H(\frac{a+c}{2}) H(\frac{b+c}{2}) H(\frac{a+b}{2} + m) H(\frac{a+c}{2} + m) H(\frac{b+c}{2} + m)}

× \frac{H(\frac{a+b+c}{2} + m)^{2}}{H(\frac{a+b+c}{2} + \frac{m−1}{2}) H(\frac{a+b+c}{2} + \frac{m+1}{2})}. (2.1)

For a, b, c all odd, the (−1)-enumeration equals zero.

Figure 4. A cyclically symmetric lozenge tiling of a hexagon with sides 3, 5, 3, 5, 3, 5 and core of size m = 2.

The analogous theorem for the case when a has a parity different from the parity of b and c reads as follows. Theorem 5. Let a, b, c, m be nonnegative integers, a of parity different from the parity of b and c. The weighted count ∑ (−1)^{n(T)}, summed over all lozenge tilings T of a hexagon with sides a, b + m, c, a + m, b, c + m, with an equilateral triangle of side length m removed that is “central” in the sense that was described in the Introduction (see Figure 2), equals

L^{−1}(C_{a,b,c}(m)) =

(−1)^{⌈a/2⌉} \frac{H(a + m) H(b + m) H(c + m) H(a + b + c + m)}{H(a + b + m) H(a + c + m) H(b + c + m)}

× \frac{H(⌊\frac{a+b+c}{2}⌋ + m) H(⌈\frac{a+b+c}{2}⌉ + m)}{H(\frac{a+b+1}{2} + m) H(\frac{a+c−1}{2} + m) H(\frac{b+c}{2} + m)}

× \frac{H(⌊\frac{a}{2}⌋) H(⌈\frac{a}{2}⌉) H(⌊\frac{b}{2})⌋ H(⌈\frac{b}{2}⌉) H(⌊\frac{c}{2}⌋) H(⌈\frac{c}{2}⌉) H(\frac{m−1}{2}) H(\frac{m+1}{2})}{H(\frac{m−1}{2} + ⌊\frac{a+1}{2}⌋) H(\frac{m+1}{2} + ⌈\frac{a−1}{2}⌉) H(\frac{m−1}{2} + ⌊\frac{b+1}{2}⌋) H(\frac{m+1}{2} + ⌈\frac{b−1}{2}⌉) H(\frac{m−1}{2} + ⌊\frac{c+1}{2}⌋)}

×\frac{H(\frac{a+b+m}{2})^{2} H(\frac{a+c+m}{2})^{2} H(\frac{b+c+m−1}{2}) H(\frac{b+c+m+1}{2})}{H(\frac{m+1}{2} + ⌈\frac{c−1}{2}⌉) H(\frac{a+b−1}{2}) H(\frac{a+c+1}{2}) H(\frac{b+c}{2}) H(\frac{m−1}{2} + ⌊\frac{a+b+c+1}{2}⌋) H(\frac{m+1}{2} + ⌈\frac{a+b+c−1}{2}⌉)}. (2.2)

3. Enumeration of cyclically symmetric lozenge tilings

In this section we enumerate cyclically symmetric lozenge tilings of the cored hexagon C_{a}(m) := C_{a,a,a}(m) with respect to certain weights. By a cyclically symmetric lozenge tiling we mean a lozenge tiling which is invariant under rotation by 120^{∘}. See Figure 4 for an example. (At this point, all shadings, thick and dotted lines should be ignored.) The unweighted enumeration of these lozenge tilings was given earlier in [6, Theorem 3.2 and Corollary 3.3]. We restate the result below. Let L_{c}(R) denote the number of cyclically symmetric lozenge tilings of region R.

Theorem 6. Let a be a nonnegative integer. The number L_{c}(C_{a}(m)) of cyclically symmetric lozenge tilings of a hexagon with side lengths a, a+m, a, a+m, a, a+m, with an equilateral triangle of side length m removed from the center, equals the right-hand side in (3.2). □

Let us now associate certain weights to each such lozenge tiling T. These weights depend again on the number n(T) of edges of lozenges of the tiling T which are incident to the extension to the right of the bottommost side of the core. (Since we are now dealing with cyclically symmetric tilings, it does, in fact, not matter which side is considered, and the weighted count is not even affected by the choice of direction.) In the following three theorems, each lozenge tiling T is assigned the weight ω^{n(T)}, where ω is some fixed 6th root of unity. Denote by L_{c}^{ω}(R) the corresponding weighted count of cyclically symmetric lozenge tilings of region R.

Theorem 7. Let a ≥ 0 and m ≥ 0 be integers. Then the weighted count L_{c}^{ω}(C_{a}(m)) := ∑ ω^{n(T)}, summed over all cyclically symmetric lozenge tilings T of a hexagon with side lengths a, a + m, a, a + m, a, a + m, with an equilateral triangle of side length m removed from the center, equals the right-hand side in (3.3) if ω = −1, it equals the right-hand side in (3.4) if ω is a primitive third root of unity, and it equals the right-hand side in (3.5) if ω is a primitive sixth root of unity.

If we specialize these results to m = 0, i.e., to the case where there exists no core, we obtain enumeration results for cyclically symmetric plane partitions. Before we state these, let us briefly recall the relevant notions from plane partition theory (cf. e.g.

[37] or [39, Sec. 1]). There are (at least) three possible equivalent ways to define plane partitions. Out of the three possibilities, in this paper, we choose to define a plane partition π as a subset of the three-dimensional integer lattice ℤ_{+}^{3} (where ℤ_{+} denotes the set of positive integers), with the property that if (i_{1}, j_{1}, k_{1}) is an element of π, then all points (i_{2}, j_{2}, k_{2}) with 1 ≤ i_{2} ≤ i_{1}, 1 ≤ j_{2} ≤ j_{1}, 1 ≤ k_{2} ≤ k_{1} also belong to π. (In the language of partially ordered sets, π is an order ideal of ℤ_{+}^{3}.) A plane partition π is called cyclically symmetric if for every (i, j, k) in π the point (j, k, i) which results by a cyclic permutation of coordinates is in π as well.

Often, a plane partition is viewed as the corresponding pile of unit cubes which results when replacing each point (i, j, k) of the plane partition by the unit cube with center (i, j, k). A three-dimensional picture of a plane partition, viewed as pile of unit cubes, is shown in Figure 5 (in fact, this example is cyclically symmetric). As we already mentioned in the Introduction, plane partitions contained in an a × b × c box (i.e., plane partitions π with the property that every (i, j, k) ∈ π satisfies 1 ≤ i ≤ a, 1 ≤ j ≤ b, 1 ≤ k ≤ c) are in bijection with lozenge tilings of a hexagon with side lengths a, b, c, a, b, c (see [7]). This bijection can be visualised easily on the example in Figure 5. Clearly, under this bijection, cyclically symmetric plane partitions contained in an a × a × a box correspond to cyclically symmetric lozenge tilings of a hexagon with all sides of length a. Thus, Theorem 7 with m = 0 yields results about certain weighted counts of cyclically symmetric plane partitions. We just have to figure out how the weights ω^{n(T)} for lozenge tilings T translate to the plane partition language.

Figure 5. A cyclically symmetric plane partition.

Let π_{T} be the plane partition that corresponds to the lozenge tiling T under this bijection. Denote by m_{1}(π_{T}) the number of elements of the form (i, i, i) in π_{T}. Then there are precisely m_{1}(π_{T}) unit cubes on the main diagonal of the pile of unit cubes representing π_{T}. Let v be the vertex farthest from the origin of the last such unit cube (in the planar rendering of π_{T} — for our example, Figure 5 — v is the center of the hexagon). A ray through v approaching orthogonally any of the coordinate planes will cut through precisely m_{1}(π_{T}) layers of unit thickness. Since each such cut corresponds to a lozenge side contained in the ray, we see that m_{1}(π_{T}) is precisely the statistic n(T). We therefore obtain the following corollary of Theorem 7.

Corollary 8. Let a be a nonnegative integer. Then the weighted count ∑ ω^{m_{1}(π)}, summed over all cyclically symmetric plane partitions π contained in an a × a × a box, equals the right-hand side in (3.3) with m = 0 if ω = −1, it equals the righthand side in (3.4) with m = 0 if ω is a primitive third root of unity, and it equals the right-hand side in (3.5) with m = 0 if ω is a primitive sixth root of unity. □

Weighted enumerations of this sort have been considered earlier. In fact, the result for ω = −1 of Corollary 8 had been conjectured by Stembridge [41, Case 9 on p. 6], and proved for the first time by Kuperberg [23, last displayed equation on p. 27]. Thus, the (−1)-result of Theorem 7 is a generalization of Kuperberg’s result. There are many more conjectures on (−1)-enumerations of cyclically symmetric plane partitions in [41]. One of these, the Conjecture on p. 7 of [41, Case 10], asks for the weighted count ∑(−1)^{m_{6}(π)} of cyclically symmetric plane partitions in which the statistic m_{6}(π) is defined as the number of orbits (under cyclic rotation) {(i, j, k), (j, k, i), (k, i, j)} of elements of π with coordinates that are not all equal.

We prove this conjecture of Stembridge in Theorem 9 below. In fact, in Theorem 9 we prove a result for cyclically symmetric lozenge tilings of cored hexagons. In this result, a cyclically symmetric lozenge tiling T is given a weight (−1)^{n_{6}(T)}, with the statistic

Figure 6. The statistic n_{6} for this tiling is n_{6}(T_{0}) = 3

n_{6}(T) to be described below. It is defined in a way so that in the case when there is no core present (i.e., m = 0) it reduces to m_{6}(π_{T}), where again π_{T} denotes the plane partition corresponding to T.

Let T be a fixed cyclically symmetric lozenge tiling of the cored hexagon C_{a}(m) (see Figure 6 for an example with a = 3 and m = 2; at this point, all thick lines and shadings should be ignored). We consider the horizontal lozenges which are at least partially contained in the top-right fundamental region. (In Figure 6 the top-right fundamental region is framed. The horizontal lozenges which are at least partially contained in that region are the grey and black lozenges.) The statistic n_{6}(T) is by definition the sum of the vertical distances between these horizontal lozenges and the lower border of the fundamental region. (Thus, for the lozenge tiling T_{0} in Figure 6 we have, considering the horizontal lozenges in the order from left to right, n_{6}(T_{0}) = 2 + 1 + 0 + 0 + 0 = 3.)

Suppose now that m = 0, and view the tiling T as a plane partition π_{T}. The fundamental region of T used in our definition of the statistic n_{6} corresponds to a fundamental region of π_{T} with the main diagonal removed. Since the distances we add up in our definition of n_{6}(T) are precisely the heights of the vertical columns of unit cubes in this fundamental region, we obtain that n_{6}(T) is equal to the number of unit cubes contained in it, which is clearly just the number of orbits of cubes off the main diagonal. This verifies our claim that n_{6}(T) = m_{6}(π_{T}).

The weight which is assigned to a tiling T in the theorem below is (−1)^{n_{6}(T)}. An equivalent way to define this weight is to say that it is the product of the weights of all lozenges which are, at least partially, contained in the top-right fundamental region, where the weight of a horizontal lozenge with odd distance from the lower border of the region is −1, the weight of all other lozenges being 1. (In Figure 6 the black lozenge has weight −1, all other lozenges have weight 1.) Yet another way to obtain this weight is through the perfect matchings point of view of lozenge tilings, elaborated for example in [22, 23]. In this setup, the cyclically symmetric lozenge tilings that we consider here correspond bijectively to perfect matchings in a certain hexagonal graph (basically, the dual graph of a fundamental region of the cored hexagon). Assignment of weights to the edges of this graph so that each face has “curvature” −1 (see [23, Sec. II]) generates again (up to a multiplicative constant) the above weight for lozenge tilings.

Denote by L_{o}^{−1}(R) (where the index letter stands for “orbits”) the weighted count of lozenge tilings of region R under the above-defined weight.

Theorem 9. Let a and m be nonnegative integers. Let R_{1}(a, m) denote the right-hand side of (3.2), let R_{2}(a, m) denote the right-hand side of (3.3), and let R_{3}(a, m) denote the right-hand side of (3.5). Then the weighted count ∑(−1)^{n_{6}(T)}, summed over all cyclically symmetric lozenge tilings T of a hexagon with side lengths a, a + m, a, a + m, a, a + m with an equilateral triangle of side length m removed from the center, is given by

L_{o}^{−1}(C_{a}(m)) = \begin{cases}|R_{3}(\frac{a}{2}, \frac{m}{2})|^{2} & if a is even and m is even, \\ R_{1}(\frac{a+1}{2}, \frac{m}{2} − 1)R_{1}(\frac{a−1}{2}, \frac{m}{2} + 1) & if a is odd and m is even, \\ R_{1}(\frac{a}{2}, \frac{m−1}{2})R_{2}(\frac{a}{2}, \frac{m+1}{2}) & if a is even and m is odd, \\ R_{1}(\frac{a+1}{2}, \frac{m−1}{2})R_{2}(\frac{a−1}{2}, \frac{m+1}{2}) & if a is odd and m is odd. \end{cases} (3.1)

As we show in Section 4, all the above results in the current section follow from evaluations of the determinant (1.5) for ω equal to 1, to −1, to a primitive third root of unity, and to a primitive sixth root of unity, respectively. The corresponding evaluations read as follows, the evaluation for ω = 1, given in Theorem 10 below, being due to Andrews [2, Theorem 8].

Theorem 10. For any nonnegative integer a,

det_{0≤i,j≤a−1} (δ_{ij} + \binom{m + i + j}{j})

= \begin{cases}2^{⌈a/2⌉} ∏_{i=1}^{a−2} (\frac{m}{2} + ⌈i/2⌉ + 1)_{⌊(i+3)/4⌋} \\ ×\frac{∏_{i=1}^{a/2} (\frac{m}{2} + \frac{3a}{2} − ⌈\frac{3i}{2}⌉ + \frac{3}{2})_{⌈i/2⌉−1} (\frac{m}{2} + \frac{3a}{2} − ⌈\frac{3i}{2}⌉ + \frac{3}{2})_{⌈i/2⌉}}{∏_{i=1}^{a/2−1}(2i − 1)!! (2i + 1)!!} & if a is even, \\ 2^{⌈a/2⌉} ∏_{i=1}^{a−2} (\frac{m}{2} + ⌈i/2⌉ + 1)_{⌊(i+3)/4⌋} \\ ×\frac{∏_{i=1}^{(a−1)/2} (\frac{m}{2} + \frac{3a}{2} − ⌈\frac{3i−1}{2}⌉ + 1)_{⌈(i−1)/2⌉} (\frac{m}{2} + \frac{3a}{2} − ⌈\frac{3i}{2}⌉)_{⌈i/2⌉}}{∏_{i=1}^{(a−1)/2}(2i − 1)!!^{2}} & if a is odd, \end{cases} (3.2)

where (α)_{k} is the standard notation for shifted factorials, (α)_{k} := α(α+1) ⋯ (α+k−1), k ≥ 1, and (α)_{0} := 1. □

Theorem 11. For nonnegative integers a,

det_{0≤i,j≤a−1} (−δ_{ij} + \binom{m + i + j}{j})

= \begin{cases}0, & if a is odd, \\ (−1)^{a/2} ∏_{i=0}^{a/2−1} \frac{i!^{2} ( \frac{m}{2} +i)!^{2} ( \frac{m}{2} +3i+1)!^{2} (m+3i+1)!^{2}}{(2i)! (2i+1)! ( \frac{m}{2} +2i)!^{2} ( \frac{m}{2} +2i+1)!^{2} (m+2i)! (m+2i+1)!}, & if a is even. \end{cases} (3.3)

The proof of this theorem is given in Section 9. Theorem 12. Let ω be a primitive third root of unity. Then

det_{0≤i,j≤a−1} (ωδ_{ij} + \binom{m + i + j}{j}) = \frac{(1 + ω)^{a} 2^{⌊a/2⌋}}{∏_{i=1}^{⌊a/2⌋} (2i − 1)!! ∏_{i=1}^{⌊(a−1)/2⌋} (2i − 1)!!}

× ∏_{i≥0} (\frac{m}{2} + 3i + 1)_{⌊(a−4i)/2⌋} (\frac{m}{2} + 3i + 3)_{⌊(a−4i−3)/2⌋}

· (\frac{m}{2} + a − i + \frac{1}{2})_{⌊(a−4i−1)/2⌋} (\frac{m}{2} + a − i − \frac{1}{2})_{⌊(a−4i−2)/2⌋} , (3.4)

where, in abuse of notation, by ⌊α⌋ we mean the usual floor function if α ≥ 0, however, if α < 0 then ⌊α⌋ must be read as 0, so that the product over i ≥ 0 is indeed a finite product.

The proof of this theorem is given in Section 10. Theorem 13. Let ω be a primitive sixth root of unity. Then

det_{0≤i,j≤a−1} (ωδ_{ij} + \binom{m + i + j}{j}) = \frac{(1 + ω)^{a} (\frac{2}{3})^{⌊a/2⌋}}{∏_{i=1}^{⌊a/2⌋} (2i − 1)!! ∏_{i=1}^{⌊(a−1)/2⌋} (2i − 1)!!}

× ∏_{i≥0} (\frac{m}{2} + 3i + \frac{3}{2})_{⌊(a−4i−1)/2⌋} (\frac{m}{2} + 3i + \frac{5}{2})_{⌊(a−4i−2)/2⌋}

· (\frac{m}{2} + a − i)_{⌊(a−4i)/2⌋} (\frac{m}{2} + a − i)_{⌊(a−4i−3)/2⌋}, (3.5)

where again, in abuse of notation, by ⌊α⌋ we mean the usual floor function if α ≥ 0, however, if α < 0 then ⌊α⌋ must be read as 0, so that the product over i ≥ 0 is indeed a finite product.

The proof of this theorem is given in Section 11.

4. Outline of the proofs of Theorems 1–9

In this section, we give outlines of the proofs of our enumeration results stated in the Introduction and in Sections 2 and 3. We fill in the details of these proofs in later sections.

Proof of Theorem 1. There is a standard bijection between lozenge tilings and families of nonintersecting lattice paths. This bijection is explained in Section 5 (see in particular Figure 8). Thus, the problem of enumerating lozenge tilings is converted to the problem of counting certain families of nonintersecting lattice paths. By the Lindström–Gessel– Viennot theorem (stated in Lemma 14), the number of such families of paths can be expressed as a determinant (see Lemma 15). Thus, in principle, we would be done once we evaluate this determinant, given in (5.4). However, Lemma 15 applies only if the size m of the core is even. We show, in Section 6, that it suffices to address this case, by proving that the number of lozenge tilings that we are interested in is a polynomial in m. The evaluation of the determinant (5.4) for even m is carried out in Section 7 (see (7.1) and Lemmas 17 and 18). □

Proof of Theorem 4. The first steps are identical with those in the preceding proof: the lozenge tilings are converted into nonintersecting lattice paths, in the way that is described in Section 5. Therefore, Lemma 14 yields a determinant for the (−1)- enumeration that we are interested in. Unlike in the previous proof, this provides a determinant for our weighted count only if the size m of the core is odd (see Lemma 15). Again, the considerations in Section 6 show that this number is a polynomial in m, so it suffices to evaluate the determinant (5.4) for odd m. This is done in Section 7 (see (7.1) and Lemmas 19 and 20). □

Proof of Theorem 2. Again, we use the strategy from the proof of Theorem 1. We convert the lozenge tilings into families of nonintersecting lattice paths as described in Section 5. The starting and ending points are slightly different from the ones used before. They are given in (5.2). Lemma 14 yields a determinant for the number we are interested in for even m (see Lemma 16). The considerations of Section 6 still apply, so the number of lozenge tilings is a polynomial in m and it suffices to evaluate the determinant (5.5) for even m. This is accomplished in Section 8 (see (8.1) and Lemmas 21 and 22). □

Proof of Theorem 5. We proceed analogously to the proof of Theorem 2. The lozenge tilings are converted into nonintersecting lattice paths, in the way that is described in Section 5. Therefore, Lemma 14 yields a determinant for the (−1)-enumeration in the case of odd m (see Lemma 16). Again, the considerations in Section 6 show that this number is a polynomial in m, so that it suffices to evaluate the determinant (5.5) for odd m. This is worked out in Section 8 (see (8.1) and Lemmas 23 and 24). □

Proof of Theorem 7. We follow the arguments of the proof of Theorem 6, as given in [6, Lemma 3.1]. Suppose we are given a cyclically symmetric lozenge tiling T of our cored hexagon C_{a}(m). It is completely determined by its restriction to a fundamental region, the lower-left fundamental region, say. (In the example in Figure 4, the lowerleft fundamental region is framed.) Some of the lozenges are cut in two by the borders of the fundamental region. (In Figure 4 these are the shaded lozenges.) We draw lattice paths which connect these “cut” lozenges, by “following” along the other lozenges, as is indicated in Figure 4 by the dashed lines. To be precise, in each lozenge in the interior of the fundamental region, we connect the midpoints of the sides that run up-diagonal, in case the lozenge possesses such sides. Clearly, these paths are nonintersecting, by which we mean that no two paths have a common vertex. Since they determine completely the cyclically symmetric lozenge tiling, we may as well count all these families of nonintersecting lattice paths, with respect to the corresponding weight. In fact, as is easy to see, because of the cyclic symmetry, the statistic n(T) is exactly equal to a minus the number of paths. If we fix the “cut” lozenges, say in positions i_{1}, i_{2}, …, i_{k} (counted from inside out, beginning with 0; thus, in Figure 4, the “cut” lozenges have positions 0 and 2), then, according to Lemma 14, the number of families of nonintersecting lattice paths connecting the fixed “cut” lozenges is given by

• _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} •  •

Figure 7. The orthogonal path corresponding to Figure 6

the corresponding Lindström–Gessel–Viennot determinant (the left-hand side of (5.3)). This determinant turns out to be the minor of (\binom{m+i+j}{j})_{0≤i,j≤a−1} consisting of rows

and columns with indices i_{1}, i_{2}, …, i_{k}. This number must be multiplied by the common weight ω^{a−k} of these families of nonintersecting lattice paths. Therefore, in order to obtain the total weighted count that we are interested in, we have to sum all these quantities, i.e., take the sum of

((i_{1}, i_{2}, …, i_{k})-principal minor of (\binom{m+i+j}{j})_{0≤i,j≤a−1} ) × ω^{a−k}

over all k = 0, 1, …, a and 0 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ a − 1. Clearly, this sum is exactly equal to det_{0≤i,j≤a−1} (ωδ_{ij} + \binom{m+i+j}{j}), which equals the left-hand side of (3.3) if ω = −1, the left-hand side of (3.4) if ω is a primitive third root of unity, and the left-hand side of (3.5) if ω a primitive sixth root of unity. The respective right-hand sides provide therefore the solution to our enumeration problem. □

Proof of Theorem 9. We adapt the arguments used in the proof of Theorem 7. (Clearly, here we want to count the same objects, but with respect to a different weight.) So, again, we draw paths that connect the lozenges which are cut in two by the borders of the fundamental region. This time, we choose the top-right region as the fundamental region. Figure 6 shows an example. There, the top-right fundamental region is framed. As in Figure 4, paths are indicated by dashed lines. (In the example in Figure 6 there is just one path.) If we slightly distort the underlying lattice, we get orthogonal paths with positive horizontal and negative vertical steps. Figure 7 shows the orthogonal path corresponding to the path in Figure 6. The manner in which we have chosen the coordinate system ensures that possible starting points of paths are the points (0, j), 0 ≤ j ≤ a − 1, and possible ending points are the points (m + i, 0), 0 ≤ i ≤ a − 1.

Now, as before, we fix the positions of the “cut” lozenges. Then a weighted version of the Lindström–Gessel–Viennot theorem (see [24, Lemma 1] or [13, Cor. 2]) can be used to express the weighted count of the corresponding families of nonintersecting lattice paths in form of a determinant. In fact, this weighted version just says that Lemma 14 remains true when the number P(A → E) of paths from A to E is replaced everywhere by the weighted count ∑_{P} w(P) of all paths P from A to E, where w is some weight function on the edges of the square lattice and the weight w(P) of a path is the product of the weights of its steps. Thus, if we repeat the subsequent arguments in the proof of Theorem 7, then we obtain the determinant

det_{0≤i,j≤a−1} (δ_{ij} + ∑_{P:(0,j)→(m+i,0)} w(P))  (4.1)

for the weighted count of our families of nonintersecting lattice paths.

We now choose the weight function w so that the weight of the family of nonintersecting lattice paths corresponding to a tiling T is equal to (−1)^{n_{6}(T)}. To do this, it will be convenient to stick on an extra initial horizontal step at the beginning of each path, so that now it starts on the line x = −1. Weight the vertical steps on this line by 0, all the remaining vertical steps by 1, and weight horizontal steps at height j by (−1)^{j}. Since the height of a horizontal step is equal to the distance of the corresponding horizontal lozenge to our reference line in the tiling, the weight of a family (P_{1}, P_{2}, …) of nonintersecting lattice paths is equal to (−1)^{n_{6}(T)}, where T is the corresponding tiling. On the other hand, it is clearly equal to (−1)^{A(P_{1})+A(P_{2})+···}, where A(P) denotes the area between a path P and the x-axis.

To find an expression for the entries of the Lindström–Gessel–Viennot matrix we use the well-known fact (see [38, Prop. 1.3.19]) that the weighted count ∑ q^{A(P)}, summed over all lattice paths P from (0, c) to (d, 0), is equal to [ \begin{matrix}c+d \\ c \end{matrix}]_{q}, where [ \begin{matrix}n \\ k \end{matrix}]_{q} is the standard q-binomial coefficient,

[\begin{matrix}n \\ k \end{matrix}]_{q} := \frac{(1 − q^{n})(1 − q^{n−1}) ⋯ (1 − q^{n−k+1})}{(1 − q^{k})(1 − q^{k−1}) ⋯ (1 − q)}.

Thus, the determinant (4.1) becomes (see also [41, Lemma 4])

det_{0≤i,j≤a−1} (δ_{ij} + (−1)^{j} [\begin{matrix}m + i + j \\ j \end{matrix}]_{−1}) .  (4.2)

From the q-binomial theorem (see [1, (3.3.6)]),

(1 + z)(1 + qz) ⋯ (1 + q^{n−1}z) = ∑_{k=0}^{n} q^{\binom{k}{2}} [\begin{matrix}n \\ k \end{matrix}]_{q} z^{k},

it is straightforward to extract that

[\begin{matrix}n \\ k \end{matrix}]_{−1} = \begin{cases}0 & if n is even and k is odd, \\ \binom{⌊n/2⌋}{⌊k/2⌋} & otherwise. \end{cases}  (4.3)

We have to compute the determinant (4.2). Let us denote it by D_{0}. We have to distinguish between four cases, depending on the parities of m and a.

First, let m be even. We reorder rows and columns simultaneously, so that the evennumbered rows and columns come before the odd-numbered, respectively. If a is even, then we obtain for D_{0} the block determinant

det (\begin{matrix}I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2}) & −B(\frac{a}{2}, \frac{m}{2}) \\ B(\frac{a}{2}, \frac{m}{2}) & I(\frac{a}{2}) \end{matrix}) ,

where I(N) is the N × N identity matrix and B(N, m) is the N × N matrix (\binom{m+i+j}{j})_{0≤i,j≤N−1}. By a few simple manipulations, this determinant can be factored into a product of two determinants,

D_{0} = det (\begin{matrix}I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2}) & −B(\frac{a}{2}, \frac{m}{2}) \\ B(\frac{a}{2}, \frac{m}{2}) & I(\frac{a}{2}) \end{matrix})

= det (\begin{matrix}I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2}) & −B(\frac{a}{2}, \frac{m}{2}) \\ B(\frac{a}{2}, \frac{m}{2}) & I(\frac{a}{2}) \end{matrix}) det (\begin{matrix}I(\frac{a}{2}) & 0 \\ −B(\frac{a}{2}, \frac{m}{2}) & I(\frac{a}{2}) \end{matrix})

= det (\begin{matrix}I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2}) + B(\frac{a}{2}, \frac{m}{2})^{2} & −B(\frac{a}{2}, \frac{m}{2}) \\ 0 & I(\frac{a}{2}) \end{matrix})

= det (I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2}) + B(\frac{a}{2}, \frac{m}{2})^{2})

= det (ωI(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2})) det (\overline{ω}I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m}{2})) ,

where ω is a primitive sixth root of unity, each of which can be computed by application of Theorem 12. The result is the first expression in (3.1).

On the other hand, if a is odd, then analogous arguments yield

D_{0} = det (I(\frac{a+1}{2}) + B(\frac{a+1}{2}, \frac{m}{2}) + B^{(c)}(\frac{a+1}{2}, \frac{m}{2}) B^{(r)}(\frac{a+1}{2}, \frac{m}{2})) ,  (4.4)

where B^{(c)}(\frac{a+1}{2}, \frac{m}{2}) is the (\frac{a+1}{2}) × (\frac{a−1}{2}) matrix which arises from B(\frac{a+1}{2}, \frac{m}{2}) by deleting its last column, while B^{(r)}(\frac{a+1}{2}, \frac{m}{2}) is the (\frac{a−1}{2}) × (\frac{a+1}{2}) matrix which arises from B by deleting its last row.

It is easy to check that

I(\frac{a+1}{2})+B(\frac{a+1}{2}, \frac{m}{2})+B^{(c)}(\frac{a+1}{2}, \frac{m}{2}) B^{(r)}(\frac{a+1}{2}, \frac{m}{2}) = (I(\frac{a+1}{2})+\overline{B}) (I(\frac{a+1}{2}) + B(\frac{a+1}{2}, \frac{m}{2} − 1)) ,

where \overline{B} is the (\frac{a+1}{2}) × (\frac{a+1}{2})-matrix with (i, j)-entry \binom{\frac{m}{2} +i+j−1}{j−1}, 0 ≤ i, j ≤ (a − 1)/2. (So the first column of \overline{B} is zero). We expand det(I(\frac{a+1}{2}) + \overline{B}) with respect to the first column and get det(I(\frac{a−1}{2}) + B(\frac{a−1}{2}, \frac{m}{2} + 1)).

Therefore, in the case of even m and odd a, we have

D_{0} = det (I(\frac{a+1}{2}) + B(\frac{a+1}{2}, \frac{m}{2} − 1)) det (I(\frac{a−1}{2}) + B(\frac{a−1}{2}, \frac{m}{2} + 1)) .

Both determinants can be evaluated by means of Theorem 10. The result is the second expression in (3.1).

Now let m be odd. We proceed analogously. If a is even, then reordering rows and columns according to the parity of the indices gives

D_{0} = det (\begin{matrix}I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m−1}{2}) & 0 \\ B(\frac{a}{2}, \frac{m+1}{2}) & I(\frac{a}{2}) − B(\frac{a}{2}, \frac{m+1}{2}) \end{matrix})
= det (I(\frac{a}{2}) + B(\frac{a}{2}, \frac{m−1}{2})) det (I(\frac{a}{2}) − B(\frac{a}{2}, \frac{m+1}{2})) .

The first determinant is evaluated by means of Theorem 10, while the second is evaluated by means of Theorem 11. The result is the third expression in (3.1).

Finally, if a is odd we get

D_{0} = det (\begin{matrix}I(\frac{a+1}{2}) + B(\frac{a+1}{2}, \frac{m−1}{2}) & 0 \\ B^{(r)}(\frac{a+1}{2}, \frac{m+1}{2}) & I(\frac{a−1}{2}) − B(\frac{a−1}{2}, \frac{m+1}{2}) \end{matrix})
= det (I(\frac{a+1}{2}) + B(\frac{a+1}{2}, \frac{m−1}{2})) det (I(\frac{a−1}{2}) − B(\frac{a−1}{2}, \frac{m+1}{2})) .

Again, the first determinant is evaluated by means of Theorem 10, while the second is evaluated by means of Theorem 11. The result is the fourth expression in (3.1). □

5. Lozenge tilings, nonintersecting lattice paths, and determinants

The purpose of this section is to derive determinants for the ordinary and (−1)- enumeration of lozenge tilings of cored hexagons (see Lemmas 15 and 16). We find these determinants by first translating the lozenge tilings to nonintersecting lattice paths, and subsequently applying the Lindström–Gessel–Viennot theorem (stated here as Lemma 14).

From lozenge tilings to nonintersecting lattice paths. There is a well-known translation of lozenge tilings to families of nonintersecting lattice paths. We start with a lozenge tiling of the cored hexagon (see Figure 8.a). We mark the midpoints of the edges along the sides of length a and a + m and along the side of the triangle which is parallel to them (see Figure 8.b). Now, in the same way as in the proof of Theorem 7 in the preceding section, we connect these points by paths which “follow” along the lozenges of the tiling, as is illustrated in Figure 8.b. Clearly, the resulting paths are nonintersecting, i.e., no two paths have a common vertex. If we slightly distort the underlying lattice, we get orthogonal paths with positive horizontal and negative vertical steps (see Figure 8.c). In the case that a, b and c have the same parity, we can introduce a coordinate system in a way so that the coordinates of the starting points A_{i} and end points E_{j} are

A_{i} = (i − 1, c + m + i − 1),  i = 1, 2, …, a,  (5.1a)
A_{i} = (\frac{a + b}{2} + i − a − 1, \frac{a + c}{2} + i − a − 1) , i = a + 1, a + 2, …, a + m, (5.1b)
E_{j} = (b + j − 1, j − 1),  j = 1, 2, …, a + m,  (5.1c)

see Figure 8.c.

Suppose now that the parity of a is different from that of b and c, which is the case in Theorems 2 and 5. Since in this case the core is slightly off the “truly central” position (because the triangle in the “truly central” position would not be a lattice triangle; see the definitions in the Introduction), the starting points of the lattice paths originating at boundary points of the core are changed slightly as well. The starting and ending points become

A_{i} = (i − 1, c + m + i − 1),  i = 1, 2, …, a,  (5.2a)
A_{i} = (\frac{a + b − 1}{2} + i − a − 1, \frac{a + c − 1}{2} + i − a − 1) , i = a + 1, a + 2, …, a + m, (5.2b)

E_{j} = (b + j − 1, j − 1),  j = 1, 2, …, a + m. (5.2c)

In either case, the lozenge tiling can be recovered from the path family, so that it suffices to count the families of nonintersecting lattice paths with the above-mentioned starting and end points.

From nonintersecting lattice paths to a determinant. In order to count these families of nonintersecting lattice paths, we make use of a result due to Lindström [24, Lemma 1] and independently to Gessel and Viennot [13, Theorem 1]. In fact, it is the not so wellknown general form of the result which we need here. In order to state this result, we

a. A lozenge tiling of the cored hexagon in Figure 1 a  b + m } c c + m {  b  a + m } m } {  } {  b. The corresponding path family c. The path family made orthogonal

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ∘  ∘^{A_{1}}  _{E_{1}} ∘  ∘^{A_{2}}  ^{E_{4}} ∘  ∘^{A_{3}}  ^{E_{5}} ∘ ∘^{A_{4}}  ^{E_{2}} ∘ ∘^{A_{5}}  ^{E_{3}}

Figure 8

introduce some lattice path notation. We write P(A → E) for the number of paths starting at A and ending at E. Given two sets A = {A_{1}, …, A_{n}} and E = {E_{1}, …, E_{n}} of lattice points and a permutation σ, we write P(A → E_{σ}, nonint.) for the number of families of n nonintersecting paths with the ith path running from A_{i} to E_{σ(i)}, i = 1, 2, …, n.

Now we can state the main result on nonintersecting lattice paths (see [24, Lemma 1] or [13, Theorem 1]).

Lemma 14. Let A_{1}, A_{2}, …, A_{n}, E_{1}, E_{2}, …, E_{n} be points of the planar integer lattice. Then the following identity holds:

det_{1≤i,j≤n} (P(A_{i} → E_{j})) = ∑_{σ∈S_{n}} (sgn σ) · P(A → E_{σ}, nonint.).  (5.3)
□

Remark. The result in [24], respectively [13], is in fact more general, as it is formulated for paths in an arbitrary oriented graph. But then the graph must satisfy an acyclicity condition. We have not mentioned it in the formulation of the above lemma as it is automatically satisfied in our more restricted setting.

Usually, this lemma is applied in the case that the only permutation for which nonintersecting lattice paths exist is the identity permutation, so that the sum on the right-hand side reduces to a single term, which counts all families (P_{1}, P_{2}, …, P_{n}) of nonintersecting lattice paths, the ith path P_{i} running from A_{i} to E_{i}, i = 1, 2, …, n. (The only exceptions that we are aware of, i.e., applications of the above formula in the case where the sum on the right-hand side does not reduce to a single term, can be found in [8], [24], and [42].) This is, however, not exactly the situation that we encounter in our problem. Therefore, it seems that Lemma 14 is not suited for our problem. However, our choice of starting and end points (see Figure 8.c) implies that nonintersecting lattice paths are only possible if m consecutive end points (m being the side length of the equilateral triangle removed from the hexagon) are paired with the starting points from the triangle. So the corresponding permutation σ, which describes in which order the starting points are connected to the end points, differs from the identity permutation by a composition of cycles of length m + 1. Thus, if m is even, we have sgn σ = 1, so that the right-hand side in Lemma 14 counts exactly all nonintersecting lattice path families and, thus, all the lozenge tilings that we are interested in.

On the other hand, if m is odd, then the sign of the permutation σ will not be 1 always. In fact, as is straightforward to see, the sign of σ is 1 if the number of paths which pass the core on the right is even, and is −1 otherwise. If this is translated back to the original lozenge tiling, T say, then it follows that sgn σ is exactly equal to (−1)^{n(T)}, with the statistic n(.) from Section 2. Thus, in the case that m is odd, the determinant in Lemma 14 gives exactly the (−1)-enumeration of our lozenge tilings.

Since the number of paths from (x_{1}, y_{1}) to (x_{2}, y_{2}) with positive horizontal and negative vertical steps equals the binomial coefficient \binom{x_{2}−x_{1}+y_{1}−y_{2}}{x_{2}−x_{1}}, our findings so far can be summarized as follows.

Lemma 15. Let a, b, c, m be nonnegative integers, a, b, c having the same parity. If m is even, then the number of lozenge tilings of a hexagon with sides a, b+m, c, a+m, b, c+m, with an equilateral triangle of side length m removed from its center, equals

det_{1≤i,j≤a+m} (\begin{matrix}\binom{b + c + m}{b − i + j} & 1 ≤ i ≤ a \\ \binom{\frac{b+c}{2}}{\frac{b+a}{2} − i + j} & a + 1 ≤ i ≤ a + m \end{matrix}) .  (5.4)

If m is odd, then the weighted count ∑(−1)^{n(T)}, where T varies through all the above lozenge tilings, is equal to the above determinant.

Lemma 16. Let a, b, c, m be nonnegative integers, a of parity different from the parity of b and c. If m is even, then the number of lozenge tilings of a hexagon with sides a, b + m, c, a + m, b, c + m, with an equilateral triangle of side length m removed that is

a  b + m  } c c + m { b  a + m } m  } {  } {

Figure 9. A lozenge tiling of a hexagon with sides a = 5, b = 3, c = 1 and removed triangle of side length m = 2 and the corresponding paths.

“central” in the sense that was described in the Introduction, equals

det_{1≤i,j≤a+m} (\begin{matrix}\binom{b + c + m}{b − i + j} & 1 ≤ i ≤ a \\ \binom{\frac{b+c}{2}}{\frac{b+a+1}{2} − i + j} & a + 1 ≤ i ≤ a + m \end{matrix}) .  (5.5)

If m is odd, then the weighted count ∑(−1)^{n(T)}, where T varies through all the above lozenge tilings, is equal to the above determinant.

6. Polynomiality of the number of lozenge tilings

The goal of this section is to establish polynomiality in m — the side of the core — of the weighted counts of lozenge tilings considered in Theorems 1, 2, 4, 5, provided a, b, c are fixed. Below we just address the case that a, b and c have the same parity (i.e., the case considered in Theorems 1 and 4), the other case being completely analogous.

We set up a bijection between the lozenge tilings of our cored hexagon and nonintersecting lattice paths in a manner different from the one in the preceding section. We start by extending all sides of the removed triangle to the left (if viewed from the interior of the triangle; see Figure 9, where these extensions are marked as thick segments). These segments partition the cored hexagon into three regions. Furthermore, the segments cut some of the lozenges in two. (In Figure 9 these lozenges are shaded.) In each of the three regions, we mark the midpoints of those edges of the “cut” lozenges and of those edges along the border of the region that are not parallel to the “thick” segments bordering this region (see Figure 9). Now, in each of the three regions, we connect the marked points by “following” along the lozenges of the tiling, in the same way as in Section 4 (in the proof of Theorem 7), and in Section 5 (see Figure 8.b). The lozenge tiling can be recovered from the three nonintersecting path families. Thus this defines indeed a bijection.

Hence, if we fix the lozenges that are cut in two by the segments, the corresponding number of lozenge tilings which contain these fixed “cut” lozenges is easily computed by applying the Lindström–Gessel–Viennot theorem (Lemma 14) to each of the three regions separately. This gives a product of three determinants, one for each region. The total number of lozenge tilings is then obtained as the sum over all possible choices of “cut” lozenges (along the segments) of this product of three determinants.

It is easy to see that each entry in any of the three determinants is a binomial coefficient of the form \binom{m+x}{y}, where x and y are independent of m. So the entries are polynomials in m, and, hence, the determinants as well. The segment which extends the side of the removed triangle that is parallel to a has length min\{\frac{a+b}{2}, \frac{a+c}{2}\}, which is independent of m, similarly for the other lines. The total number of lozenge tilings is thus equal to a sum of polynomials in m, where the range of summation is independent of m. Therefore it is itself a polynomial in m, as was claimed.

Basically, the same arguments hold also for (−1)-enumeration. The only difference is that each product of three determinants is multiplied by a sign, depending (according to the definition of our statistic n) on the parity of the number of lozenge sides contained in the northeastern extension of the bottom side of the core. However, this number equals the length of this extension minus the number of lozenges the extension cuts through, and is therefore again independent of m.

7. Determinant evaluations, I

In this section we evaluate the determinant in Lemma 15. The underlying matrix is a mixture of two matrices. If we would have to compute the determinant of just one of the matrices (i.e., if we consider the case a = 0 or m = 0), then the determinant could be easily evaluated (see (12.5)). However, the mixture is much more difficult to evaluate. As it turns out, we have to distinguish between several cases, depending on the parities of a and m.

It is convenient to take (b + c + m)!/(b + a + m − i)! (c + m + i − 1)! out of the ith row, i = 1, 2, …, a, and (\frac{b+c}{2})!/(\frac{b+3a}{2} + m − i)! (\frac{c−a}{2} + i − 1)! out of the ith row, i = a + 1, a + 2, …, a + m. This gives

det_{1≤i,j≤a+m} (\begin{matrix}\binom{b + c + m}{b − i + j} & 1 ≤ i ≤ a \\ \binom{\frac{b+c}{2}}{\frac{b+a}{2} − i + j} & a + 1 ≤ i ≤ a + m \end{matrix})

= ∏_{i=1}^{a} \frac{(b + c + m)!}{(b + a + m − i)! (c + m + i − 1)!} ∏_{i=a+1}^{a+m} \frac{(\frac{b+c}{2})!}{(\frac{b+3a}{2} + m − i)! (\frac{c−a}{2} + i − 1)!}

× det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a}{2} + i − j + 1)_{j−1} (\frac{b+a}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix}) . (7.1)

Thus it suffices to evaluate the determinant on the right-hand side. The advantage is that this determinant is a polynomial in b and c. This enables us to apply the “identification of factors” method, as proposed in [20, Sec. 2.4]. The four lemmas below address the four different cases, as a and m vary through all possible parities.

Lemma 17. Let a and m be both even nonnegative integers. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a}{2} + i − j + 1)_{j−1} (\frac{b+a}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= \frac{H(a + m) H(\frac{a}{2})^{2} H(\frac{m}{2})^{2}}{H(\frac{a+m}{2})^{2} 2^{m(a+m−1)/2}} ∏_{k=1}^{m/2} (\frac{b}{2} + k)_{a/2}^{2} (\frac{c}{2} + k)_{a/2}^{2} ∏_{k=0}^{a/2−1} (b + c + m + 2k + 1)^{a−2k−1}

× ∏_{k=1}^{a/2−1} (b + c + 2m + 2k)^{a−2k} ∏_{k=m/2+1}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{m/2} (b + c + 2k)^{m−k}. (7.2)

Proof. Let us denote the determinant in (7.2) by D_{1}(b, c).

We proceed in several steps. An outline is as follows. The determinant D_{1}(b, c) is obviously a polynomial in b and c. In Steps 1–5 we show that the right-hand side of (7.2) divides D_{1}(b, c) as a polynomial in b and c. In Step 6 we show that the degree of D_{1}(b, c) as a polynomial in b is at most \binom{a+m}{2}. Of course, the same is true for the degree in c. On the other hand, the degree of the right-hand side of (7.2) as a polynomial in b is exactly \binom{a+m}{2}. It follows that D_{1}(b, c) must equal the right-hand side of (7.2) times a quantity which does not depend on b. This quantity must be polynomial in c. But, in fact, it cannot depend on c as well, because, as we just observed, the degree in c of the right-hand side of (7.2) is already equal to the maximal degree in c of D_{1}(b, c). Thus, this quantity is a constant with respect to b and c. That this constant is equal to 1 is finally shown in Step 7, by evaluating the determinant D_{1}(b, c) for b = c = 0.

Before we begin with the detailed description of the individual steps, we should explain the odd looking occurrences of “e ≡ a mod 2” below (e.g., in Step 1(a)–(d)). Clearly, in the present context this means “e ≡ 0 mod 2”, as a is even by assumption. However, Steps 1–6 will also serve as a model for the proofs of the subsequent Lemmas 18–20. Consequently, formulations are chosen so that they remain valid without change at the corresponding places. In particular, in the context of the proofs of Lemmas 18 and 20, the statement “e ≡ a mod 2” will mean “e ≡ 1 mod 2”.

Step 1. ∏_{k=1}^{m/2} (\frac{b}{2} + k)_{a/2}^{2} (\frac{c}{2} + k)_{a/2}^{2} divides the determinant. The original determinant is symmetric in b and c for combinatorial reasons. The factors which were taken out of the determinant in (7.1) are also symmetric in b and c (this can be seen by reversing all the products involving c). Therefore it suffices to check that the linear factors involving b divide D_{1}(b, c), i.e., that the product ∏_{k=1}^{m/2} (\frac{b}{2} + k)_{a/2}^{2} divides D_{1}(b, c).

We distinguish between four subcases, labeled below as (a), (b), (c), and (d).

(a) (b + e)^{e} divides D_{1}(b, c) for 1 ≤ e ≤ min{a, m}, e ≡ a mod 2: This follows from the easily verified fact that (b + e) is a factor of each entry in the first e columns of D_{1}(b, c).

(b) (b + e)^{m} divides D_{1}(b, c) for m < e < a, e ≡ a mod 2: We prove this by finding m “different” linear combinations of the columns of D_{1}(b, c) which vanish for b = −e. By the term “different” we mean that these linear combinations are themselves linearly independent. (Equivalently, we find m linearly independent vectors in the kernel of the linear operator defined by the matrix underlying D_{1}(−e, c).) See Section 2 of [19], and in particular the Lemma in that section, for a formal justification of this procedure.

To be precise, we claim that the following equation holds for s = 1, 2, …, m,

∑_{j=1}^{e+s−m} \binom{e − m + s − 1}{j − 1}\frac{(c + a − e − s + 2m + 1)_{e+s−j−m}}{(a − e − s + 2m + 1)_{e+s−j−m}} · (column j of D_{1}(−e, c)) = 0.

(7.3)

Since the entries of D_{1}(b, c) have a split definition (see (7.2)), for the proof of the above equation we have to distinguish between two cases. If we restrict (7.3) to the ith row, i ≤ a, then (7.3) becomes

∑_{j=1}^{e+s−m} \binom{e − m + s − 1}{j − 1}\frac{(c + a − e − s + 2m + 1)_{e+s−j−m}}{(a − e − s + 2m + 1)_{e+s−j−m}}

· (c + m + i − j + 1)_{j−1} (−e − i + j + 1)_{a+m−j} = 0, (7.4)

whereas on restriction to the ith row, i > a, equation (7.3) becomes

∑_{j=1}^{e+s−m} \binom{e − m + s − 1}{j − 1}\frac{(c + a − e − s + 2m + 1)_{e+s−j−m}}{(a − e − s + 2m + 1)_{e+s−j−m}}

· (\frac{c−a}{2} + i − j + 1)_{j−1} (\frac{−e+a}{2} − i + j + 1)_{a+m−j} = 0. (7.5)

First, let i ≤ a. Here and in the following, we make use of the usual 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} .  (7.6)

In this notation, the sum on the left-hand side of (7.4) reads

\frac{(2 − e − i)_{−1+a+m} (1 + a + c − e + 2 m − s)_{−1+e−m+s}}{(1 + a − e + 2 m − s)_{−1+e−m+s}}

×_{3}F_{2}[\begin{matrix}1 − c − i − m, 1 − e + m − s, 1 − a − m \\ 1 − a − c − m, 2 − e − i \end{matrix}; 1] .

Next we use a transformation formula due to Thomae [43] (see also [10, (3.1.1)]),

3F_{2}[\begin{matrix}A, B, −n \\ D, E \end{matrix}; 1] = \frac{(E − B)_{n}}{(E)_{n}}_{3}F_{2}[\begin{matrix}−n, B, D − A \\ D, 1 + B − E − n \end{matrix}; 1] ,  (7.7)

where n is a nonnegative integer. This gives

\frac{(1 + a + c − e + 2 m − s)_{e−m+s−1} (1 − i − m + s)_{a+m−1}}{(1 + a − e + 2m − s)_{e−m+s−1}}

×_{3}F_{2}[\begin{matrix}1 − a − m, 1 − e + m − s, −a + i \\ 1 − a − c − m, 1 − a + i − s \end{matrix}; 1] .

The factor (1 − i − m + s)_{a+m−1} vanishes for i ≤ a and the denominator is never zero, so the sum in (7.4) equals zero, as desired.

We proceed similarly in order to prove (7.5) for i > a. The hypergeometric form of the sum in (7.5) is

\frac{(2 + \frac{a}{2} − \frac{e}{2} − i)_{a+m−1} (1 + a + c − e + 2 m − s)_{e−m+s−1}}{(1 + a − e + 2 m − s)_{e−m+s−1}}

×_{3}F_{2}[\begin{matrix}1 + \frac{a}{2} − \frac{c}{2} − i, 1 − a − m, 1 − e + m − s \\ 1 − a − c − m, 2 + \frac{a}{2} − \frac{e}{2} − i \end{matrix}; 1] .

Using the transformation formula (7.7) again, we get

(1 + \frac{a}{2} + \frac{e}{2} − m − i + s)_{a+2m−e−s} (1 + \frac{3a}{2} − \frac{e}{2} − i + m)_{e−m+s−1}

× \frac{(1 + a + c − e + 2 m − s)_{e−m+s−1}}{(1 + a − e + 2 m − s)_{e−m+s−1}}

×_{3}F_{2}[\begin{matrix}1 − e + m − s, 1 − a − m, −\frac{3a}{2} − \frac{c}{2} + i − m \\ 1 − a − c − m, 1 − \frac{3 a}{2} − \frac{e}{2} + i − s \end{matrix}; 1] .

This expression is zero, because the factor (1+\frac{a}{2}+\frac{e}{2}−m−i+s)_{a+2m−e−s} vanishes for i > a (it is here where we need e ≡ a mod 2, because this guarantees that 1+ \frac{a}{2} + \frac{e}{2} −m−i+s is an integer). So the sum in (7.5) equals zero, as desired.

(c) (b + e)^{a} divides D_{1}(b, c) for a < e < m, e ≡ a mod 2: Proceeding in the spirit of case (b), we prove this by finding a linear combinations of the columns of D_{1}(b, c) which vanish for b = −e. To be precise, we claim that the following equation holds for s = 1, 2, …, a:

∑_{j=1}^{\frac{e−a}{2} +s} \binom{\frac{e−a}{2} + s − 1}{j − 1}\begin{matrix}(\frac{c}{2} + m − \frac{e}{2} + a − s + 1) & (e−a)/2+s−j \\ (m + \frac{3a−e}{2} − s + 1) & (e−a)/2+s−j \end{matrix} · (column j of D_{1}(−e, c)) = 0.

(7.8)

In order to prove this equation, we first restrict it to the ith row, i ≤ a. Then, in hypergeometric notation, the left-hand side reads

\frac{(2 − e − i)_{a+m−1} (1 + a + \frac{c}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}}{(1 + \frac{3 a}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}}

×_{3}F_{2}[\begin{matrix}1 − a − m, 1 − c − i − m, 1 + \frac{a}{2} − \frac{e}{2} − s \\ 1 − \frac{a}{2} − \frac{c}{2} − m, 2 − e − i \end{matrix}; 1] .

We apply the transformation formula (7.7) and get

(1 + c − e + m)_{\frac{e}{2} − \frac{a}{2} +s−1} (1 + a + \frac{c}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}

× \frac{(1 − \frac{a}{2} − \frac{e}{2} − i + s)_{\frac{3 a}{2} − \frac{e}{2} +m−s}}{(1 + \frac{3 a}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}} _{3}F_{2}[\begin{matrix}1 + \frac{a}{2} − \frac{e}{2} − s, 1 − c − i − m, \frac{a}{2} − \frac{c}{2} \\ 1 − \frac{a}{2} − \frac{c}{2} − m, 1 + \frac{a}{2} − c + \frac{e}{2} − m − s \end{matrix}; 1] .

This expression is zero because the factor (1 − \frac{a}{2} − \frac{e}{2} − i + s)_{\frac{3a}{2} − \frac{e}{2} +m−s} vanishes.

If instead we restrict the left-hand side of (7.8) to the ith row, i > a, and convert it into hypergeometric form, then we obtain

\frac{(2 + \frac{a}{2} − \frac{e}{2} − i)_{a+m−1} (1 + a + \frac{c}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}}{(1 + \frac{3 a}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}}

×_{3}F_{2}[\begin{matrix}1 + \frac{a}{2} − \frac{c}{2} − i, 1 − a − m, 1 + \frac{a}{2} − \frac{e}{2} − s \\ 1 − \frac{a}{2} − \frac{c}{2} − m, 2 + \frac{a}{2} − \frac{e}{2} − i \end{matrix}; 1] .

We apply again the transformation formula (7.7). This gives

\frac{(1 + a + \frac{c}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s} (1 − i + s)_{−1+a+m}}{(1 + \frac{3a}{2} − \frac{e}{2} + m − s)_{−1− \frac{a}{2} + \frac{e}{2} +s}}

×_{3}F_{2}[\begin{matrix}1 + \frac{a}{2} − \frac{e}{2} − s, 1 − a − m, −a + i − m \\ 1 − \frac{a}{2} − \frac{c}{2} − m, 1 − a + i − m − s \end{matrix}; 1] .

This expression is zero because the factor (1 − i + s)_{−1+a+m} vanishes for a + 1 ≤ i ≤ a + m. So the sum in (7.8) equals zero, as desired.

(d) (b + e)^{a+m−e} divides D_{1}(b, c) for max{a, m} ≤ e ≤ a + m − 1, e ≡ a mod 2: Still proceeding in the spirit of case (b), this time we find a + m − e linear combinations of the rows of D_{1}(b, c) which vanish for b = −e. To be precise, we claim that the following equation holds for s = 1, 2, …, a + m − e:

∑_{i=1}^{s} \binom{s − 1}{i − 1}\frac{(−1)^{i} (\frac{c−e}{2} + 1)_{a+m−s} (\frac{c−e}{2} + m)_{i−1}}{(1 + c − e + m)_{a+m−s+i−1}}
· (row (a + m − e − s + i) of D_{1}(−e, c))

+ (row (m + \frac{3a}{2} − \frac{e}{2} − s + 1) of D_{1}(−e, c)) = 0. (7.9)

In the sum, it is only the first a rows which are involved, whereas the extra term is a row out of the last m rows of the determinant. Therefore, by restriction to the jth column, we see that it is equivalent to

∑_{i=1}^{s} \binom{s − 1}{i − 1}\frac{(−1)^{i} (\frac{c−e}{2} + 1)_{a+m−s} (\frac{c−e}{2} + m)_{i−1}}{(1 + c − e + m)_{a+m−s+i−1}}
· (a + c + 2m − e − s + i − j + 1)_{j−1} (−a − m + s − i + j + 1)_{a+m−j}

+ (\frac{c−e}{2} + a + m − s − j + 2)_{j−1} (−a − m + s + j)_{a+m−j} = 0. (7.10)

We treat the cases j ≤ a + m − s and j > a + m − s separately. For j ≤ a + m − s the factor (−a − m + s − i + j + 1)_{a+m−j}, which appears in the sum, is zero for all the summands, as well is the factor (−a − m + s + j)_{a+m−j}, which appears in the extra term in (7.10).

For j > a + m − s we convert the sum in (7.10) into hypergeometric form and get

\frac{−(1 + \frac{c}{2} − \frac{e}{2})_{a+m−s} (2 + a + c − e − j + 2 m − s)_{−1+j} (−a + j − m + s)_{a−j+m}}{(1 + c − e + m)_{a+m−s}}

×_{2}F_{1}[\begin{matrix}\frac{c}{2} − \frac{e}{2} + m, 1 + a − j + m − s \\ 2 + a + c − e − j + 2 m − s \end{matrix}; 1] .

We can evaluate the _{2}F_{1}-series by the Chu–Vandermonde summation formula (see [36, (1.7.7), Appendix (III.4)]),

2F_{1}[\begin{matrix}A, −n \\ C \end{matrix}; 1] = \frac{(C − A)_{n}}{(C)_{n}} ,  (7.11)

where n is a nonnegative integer. Thus we get

−(2 + a + \frac{c}{2} − \frac{e}{2} − j + m − s)_{j−1} (−a + j − m + s)_{a−j+m}.  (7.12)

It is easily seen that adding the extra term in (7.10) gives zero.

Step 2. ∏_{k=0}^{a/2−1} (b + c + m + 2k + 1)^{a−2k−1} divides the determinant. We find e + 1 linear combinations of the rows of D_{1}(b, c) which vanish for b = −c−a−m+1+e. To be precise, we claim that the following equation holds for 0 ≤ e ≤ a − 2, s = 1, 2, …, e + 1:

∑_{i=1}^{a−e−1} (\frac{(c + m + i)_{a−e−i+s−1}}{(c − e − 1 + i)_{a−e−i+s−1}} \binom{a − e − 2}{i − 1}\frac{(s)_{a−e−1} (−1)^{i}}{(s − i + a − e − 1)(a − e − 2)!}

· (row i of D_{1}(−c − a − m + 1 + e, c)))

+ (−1)^{a−e−1} · (row (a − e − 1 + s) of D_{1}(−c − a − m + 1 + e, c)) = 0. (7.13)

Restricted to the jth column, and converted into hypergeometric notation, the sum in (7.13) reads

− \frac{(1 − a − c + e + j − m)_{a−j+m} (1 + c + m)_{a−e+s−2} (2 + c − j + m)_{j−1} (s)_{a−e−2}}{(1)_{a−e−2} (c − e)_{a−e+s−2}}

×_{3}F_{2}[\begin{matrix}2 − a + e − s, a + c − e − j + m, 2 − a + e \\ 3 − a + e − s, 2 + c − j + m \end{matrix}; 1] .

Here we use the Pfaff–Saalschütz summation formula (see [36, (2.3.1.3), Appendix (III.2)])

3F_{2}[\begin{matrix}A, B, −n \\ C, 1 + A + B − C − n \end{matrix}; 1] = \frac{(C − A)_{n} (C − B)_{n}}{(C)_{n} (C − A − B)_{n}} ,  (7.14)

where n is a nonnegative integer. Thus we get

(−1)^{a−e−1}(1 + c + m)_{a−e+s−2} (2 + c − j + m)_{j−1}

× \frac{(3 − 2 a − c + 2 e + j − m − s)_{a−e−2}}{(c − e)_{a−e+s−2} (1 − c + e)_{−2−e+j−m}} .

It is easily verified that adding the jth coordinate of the extra term in (7.13) gives zero, as desired. For now, we need equation (7.13) only for even e.

Step 3. ∏_{k=1}^{a/2−1} (b + c + 2m + 2k)^{a−2k} divides the determinant. We find e linear combinations of the columns of D_{1}(b, c) which vanish for b = −c − 2m − a + e. To be precise, we claim that the following equation holds for 0 < e ≤ a, e ≡ a mod 2, and s = 1, 2, …, e:

∑_{j=s}^{a+m+s−e} \binom{a + m − e}{j − s} · (column j of D_{1}(−c − 2m − a + e, c)) = 0.  (7.15)

Restricted to the ith row, i ≤ a, and converted into hypergeometric notation, the left-hand side sum in (7.15) reads

(1 + c + i + m − s)_{s−1} (1 − a − c + e − i − 2 m + s)_{a+m−s}

×_{2}F_{1}[\begin{matrix}−c − i − m + s, −a + e − m \\ 1 − a − c + e − i − 2 m + s \end{matrix}; 1] .

This is summable by the Chu–Vandermonde summation formula (7.11). We get

\frac{(1 − a + e − m)_{a−e+m} (1 + c + i + m − s)_{s−1}}{(1 − c + e − i − m)_{s−e}} .

This expression equals zero because the factor (1 − a + e − m)_{a−e+m} vanishes.

On the other hand, if i > a, the left-hand side sum in (7.15), restricted to the ith row and converted into hypergeometric from, reads

(1 − \frac{a}{2} + \frac{c}{2} + i − s)_{s−1} (1 − \frac{c}{2} + \frac{e}{2} − i − m + s)_{a+m−s}

×_{2}F_{1}[\begin{matrix}\frac{a}{2} − \frac{c}{2} − i + s, −a + e − m \\ 1 − \frac{c}{2} + \frac{e}{2} − i − m + s \end{matrix}; 1] .

The Chu–Vandermonde summation formula (7.11) turns this expression into

\frac{(1 − \frac{a}{2} + \frac{e}{2} − m)_{a−e+m} (1 − \frac{a}{2} + \frac{c}{2} + i − s)_{s−1}}{(1 + a − \frac{c}{2} + \frac{e}{2} − i)_{−e+s}} .

This expression is zero because the factor (1 − \frac{a}{2} + \frac{e}{2} − m)_{a−e+m} vanishes for e ≡ a mod 2. So the sum in (7.15) is zero, as desired.

Step 4. ∏_{k=m/2+1}^{m} (b + c + 2k)^{a+m−k} divides the determinant. We find a+m−e linear combinations of the columns of D_{1}(b, c) which vanish for b = −c−2e. To be precise, we claim that the following equation holds for m/2 < e ≤ m and s = 1, 2, …, a + m − e:

∑_{j=s}^{s+e} \binom{e}{j − s} · (column j of D_{1}(−c − 2e, c)) = 0.  (7.16)

Restricted to the ith row, i ≤ a, and converted into hypergeometric notation, the left-hand side sum in (7.16) reads

(1 + c + i + m − s)_{s−1} (1 − c − 2e − i + s)_{a+m−s} _{2}F_{1}[\begin{matrix}−c − i − m + s, −e \\ 1 − c − 2e − i + s \end{matrix}; 1] .

The result after application of the Chu–Vandermonde summation formula (7.11) is

\frac{(1 − 2e + m)_{e} (1 + c + i + m − s)_{s−1}}{(1 + a − c − 2e − i + m)_{−a+e−m+s}} .

This expression equals zero because the factor (1 − 2e + m)_{e} vanishes.

On the other hand, if i > a, the left-hand side sum in (7.16), restricted to the ith row and converted into hypergeometric from, reads

(1 − \frac{a}{2} + \frac{c}{2} + i − s)_{s−1} (1 + \frac{a}{2} − \frac{c}{2} − e − i + s)_{a+m−s} _{2}F_{1}[\begin{matrix}\frac{a}{2} − \frac{c}{2} − i + s, −e \\ 1 + \frac{a}{2} − \frac{c}{2} − e − i + s \end{matrix}; 1] .

Chu-Vandermonde summation (7.11) yields

\frac{(1 − e)_{e} (1 − \frac{a}{2} + \frac{c}{2} + i − s)_{s−1}}{(1 + \frac{3 a}{2} − \frac{c}{2} − e − i + m)_{−a+e−m+s}} .

This expression is zero because the factor (1 − e)_{e} vanishes. So the sum in (7.16) is zero, as desired.

Step 5. ∏_{k=1}^{m/2} (b + c + 2k)^{m−k} divides the determinant. We find e linear combinations of the rows of D_{1}(b, c) which vanish for b = −c − 2m + 2e. To be precise, we claim that the following equation holds for e ≤ m − 1 and s = 1, 2, …, e:

∑_{i=1}^{m−s+1}(−1)^{i}\binom{m − s}{i − 1}\begin{matrix}(\frac{c}{2} + \frac{a}{2} + i) & m−s−i+1 \\ (\frac{c}{2} − \frac{a}{2} − e + i) & m−s−i+1 \end{matrix}

· (row (a + i) of D_{1}(−c − 2m + 2e, c)) = 0. (7.17)

Restricted to the jth row, and converted into hypergeometric notation, the left-hand side sum in (7.17) reads

− \frac{(1 + \frac{a}{2} + \frac{c}{2})_{m−s} (2 + \frac{a}{2} + \frac{c}{2} − j)_{j−1} (−\frac{a}{2} − \frac{c}{2} + e + j − m)_{a−j+m}}{(1 − \frac{a}{2} + \frac{c}{2} − e)_{m−s}}

×_{2}F_{1}[\begin{matrix}1 + \frac{a}{2} + \frac{c}{2} − e − j + m, −m + s \\ 2 + \frac{a}{2} + \frac{c}{2} − j \end{matrix}; 1] .

After applying Chu–Vandermonde summation (7.11) again, we obtain

− (1 + \frac{a}{2} + \frac{c}{2})_{m−s}(1 + e − m)_{m−s}

× \frac{(−\frac{a}{2} − \frac{c}{2} + e + j − m)_{a−j+m}(2 + \frac{a}{2} + \frac{c}{2} − j + m − s)_{j−m+s−1}}{(1 − \frac{a}{2} + \frac{c}{2} − e)_{m−s}} .

This expression equals zero because the factor (1 + e − m)_{m−s} vanishes. So the sum in (7.17) is zero, as desired.

Step 6. Determination of the degree of D_{1}(b, c) as a polynomial in b. Obviously the degree of the (i, j)-entry of D_{1}(b, c) as a polynomial in b is a + m − j. Therefore, if we expand the determinant D_{1}(b, c) according to its definition as a sum over permutations, each term in this expansion has degree \binom{a+m}{2} in b. Hence, D_{1}(b, c) itself has degree at most \binom{a+m}{2} in b.

Step 7. Computation of the multiplicative constant. As we observed at the beginning of this proof, Steps 1–6 show that the determinant D_{1}(b, c) is equal to the right-hand side of (7.2) up to multiplication by a constant. To determine this constant, it suffices to compute D_{1}(b, c) for some particular values of b and c. We choose b = c = 0. The value of D_{1}(0, 0) is most easily determined by going back, via (7.1) and Lemma 15, to the origin of the determinant D_{1}(b, c), which is enumeration of lozenge tilings. Figure 10 shows the typical situation for b = c = 0. As the figure illustrates, there is exactly one lozenge tiling of the region. Hence, by Lemma 15, it follows that the determinant (5.4) must be equal to 1 for b = c = 0. If we substitute this into (7.1), we have evaluated D_{1}(b, c), which is the determinant on the right-hand side of (7.1), for b = c = 0. It is then a routine task to check that the result agrees exactly with the right-hand side of (7.2) for b = c = 0.

} {  } m {  a  m a + m

Figure 10. The unique lozenge tiling for b = c = 0

This completes the proof of the lemma. □

Lemma 18. Let a and m be nonnegative integers, a odd and m even. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a}{2} + i − j + 1)_{j−1} (\frac{b+a}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= \frac{H(a + m) H(\frac{a−1}{2}) H(\frac{a+1}{2}) H(\frac{m}{2})^{2}}{H(\frac{a+m−1}{2}) H(\frac{a+m+1}{2}) 2^{m(a+m−1)/2}}

× ∏_{k=1}^{m/2} (\frac{b−1}{2} + k)_{(a+1)/2} (\frac{b+1}{2} + k)_{(a−1)/2} (\frac{c−1}{2} + k)_{(a+1)/2} (\frac{c+1}{2} + k)_{(a−1)/2}

× ∏_{k=0}^{(a−1)/2−1} (b + c + m + 2k + 1)^{a−2k−1} ∏_{k=1}^{(a−1)/2} (b + c + 2m + 2k)^{a−2k}

× ∏_{k=m/2+1}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{m/2} (b + c + 2k)^{m−k}. (7.18)

Proof. We proceed analogously to the proof of Lemma 17. The only difference is the parity of a, so we have to read through the proof of Lemma 17 and find the places where we used the fact that a is even.

As it turns out, the arguments in Steps 1–5 in the proof of Lemma 17 can be used here, practically without change, to establish that the right-hand side of (7.18) divides the determinant on the left-hand side of (7.18) as a polynomial in b and c. Differences arise only in the products corresponding to each subcase (for example, the arguments in Step 3 of the proof of Lemma 17 prove that ∏_{k=1}^{a/2−1} (b + c + 2m + 2k)^{a−2k} divides the determinant D_{1}(b, c) if a is even, while for odd a they prove that ∏_{k=1}^{(a−1)/2} (b + c + 2m + 2k)^{a−2k} divides D_{1}(b, c)), and in the fact that in Step 2 we are now interested in the factors corresponding to odd values of e, 1 ≤ e ≤ a − 2 (because here the factors with even e are covered by Steps 3 and 4).

} {  } m + 1 {  a  a + m  m + 1 A_{1} A_{2}  A_{3} A^{4} A_{5}

Figure 11. A lozenge tiling and the corresponding path family for b = c = 1, a = 5

Also Step 6, the determination of a degree bound on the determinant, can be used verbatim.

For the determination of the multiplicative constant relating the right-hand and the left-hand side of (7.18), we have to modify however the arguments in Step 7 of the proof of Lemma 17. We determine the constant by computing the determinant for b = c = 1. Again, this value is most conveniently found by going back, via (7.1) and Lemma 15, to the combinatorial root of the determinant, which is enumeration of lozenge tilings.

We claim that the number of lozenge tilings for b = c = 1, a odd and m even, equals

2\binom{m + 1 + \frac{a−1}{2}}{\frac{a−1}{2}}.  (7.19)

This can be read off Figure 11, which shows a typical example of the case b = c = 1: The path starting at A_{\frac{a+1}{2}} (see the labeling in Figure 11; it is derived from the labeling of starting points of paths in Figure 8) must pass either to the right or to the left of the triangle. Since the hexagon is symmetric, we can count those path families where the path passes to the right, and in the end multiply the resulting number by two. For those path families, the paths starting at points to the right of A_{\frac{a+1}{2}} are fixed. The paths to the left have all exactly one South-East step. Suppose that the South-East step of the path which starts in A_{i}, 1 ≤ i ≤ (a − 1)/2, occurs as the h_{i}th step. Then we must have

m + 2 ≥ h_{1} ≥ h_{2} ≥ ⋯ ≥ h_{\frac{a−1}{2}} ≥ 1.

So we just have to count monotonously decreasing sequences of \frac{a−1}{2} numbers between 1 and m + 2. The number is exactly the binomial coefficient in (7.19). It is then a routine task to check that, on substitution in (7.1), the result agrees exactly with the right-hand side of (7.18) for b = c = 1. □

Lemma 19. Let a and m be nonnegative integers, a even and m odd. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a}{2} + i − j + 1)_{j−1} (\frac{b+a}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= (−1)^{a/2} \frac{H(a + m) H(\frac{a}{2})^{2} H(\frac{m−1}{2}) H(\frac{m+1}{2})}{H(\frac{a+m−1}{2}) H(\frac{a+m+1}{2}) 2^{m(a+m−1)/2}}

× (\frac{b}{2} + \frac{1+m}{2})_{\frac{a}{2}} (\frac{c}{2} + \frac{1+m}{2})_{\frac{a}{2}} ∏_{k=1}^{(m−1)/2} (\frac{b}{2} + k)2_{\frac{a}{2}} ∏_{k=1}^{(m−1)/2} (\frac{c}{2} + k)2_{\frac{a}{2}} ∏_{k=1}^{a/2−1} (b + c + 2 k + m)^{a−2 k}

× ∏_{k=1}^{a/2−1} (b + c + 2 k + 2 m)^{a−2 k} ∏_{k=0}^{(m−1)/2} (1 + b + c + 2 k + m)^{a} ∏_{k=1}^{m} (b + c + 2 k)^{m−k}. (7.20)

Proof. We proceed analogously to the proof of Lemma 17. The only difference is the parity of m, so we have to check the places in the proof of Lemma 17 where we used the fact that m is even.

Again, Steps 1–6 can be reused verbatim, except that the products corresponding to the individual subcases are slightly different, and in Step 2 we are now interested in the factors corresponding to odd values of e, 1 ≤ e ≤ a − 2 (because the factors with even e are covered by Steps 3 and 4).

The computation of the multiplicative constant relating the right-hand and the lefthand side of (7.20) is done analogously to Step 7 in the proof of Lemma 17, i.e., we compute the determinant for b = c = 0 by going back, via (7.1) and Lemma 15, to the lozenge tiling interpretation of the determinant. We already concluded in the proof of Lemma 17 that for b = c = 0 there is just one lozenge tiling (see Figure 10). By definition, the statistic n(.) attains the value a/2 on this lozenge tiling, so that its weight is (−1)^{a/2}. It is then not difficult to verify that, on substitution of this in (7.1), the result agrees exactly with the right-hand side of (7.20) for b = c = 0. □

Lemma 20. Let a and m be odd nonnegative integers. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a}{2} + i − j + 1)_{j−1} (\frac{b+a}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix}) = 0. (7.21)

Proof. Analogously to the previous cases, we can show that the product

∏_{i=1}^{(m+1)/2} (\frac{b−1}{2} + i)_{(a+1)/2} ∏_{i=1}^{(m−1)/2} (\frac{b+1}{2} + i)_{(a−1)/2} ∏_{k=1}^{(a−1)/2} (b + c + m + 2k)^{a−2k}

× ∏_{k=1}^{(a−1)/2} (b + c + 2m + 2k)^{a−2k} ∏_{k=(m+1)/2}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{(m−1)/2} (b + c + 2k)^{m−k}

divides the determinant as a polynomial in b and c. Although not completely obvious, this is implied by the linear combinations of Lemma 17, Steps 1–5. The degree in b of this product is \binom{a+m}{2} + 1 which is larger than the maximal degree \binom{a+m}{2} of the determinant viewed as a polynomial in b. So the determinant must be zero. □

8. Determinant Evaluations, II

In this section we evaluate the determinant in Lemma 16. We proceed analogously to Section 7 and start by taking (b + c + m)!/(b + a + m − i)! (c + m + i − 1)! out of the ith row, i = 1, 2, …, a, and (\frac{b+c}{2})!/(\frac{b+3a+1}{2} + m − i)! (\frac{c−a−1}{2} + i − 1)! out of the ith row, i = a + 1, a + 2, …, a + m. This gives

det_{1≤i,j≤a+m} (\begin{matrix}\binom{b + c + m}{b − i + j} & 1 ≤ i ≤ a \\ \binom{\frac{b+c}{2}}{\frac{b+a+1}{2} − i + j} & a + 1 ≤ i ≤ a + m \end{matrix})

= ∏_{i=1}^{a} \frac{(b + c + m)!}{(b + a + m − i)! (c + m + i − 1)!} ∏_{i=a+1}^{a+m} \frac{(\frac{b+c}{2})!}{(\frac{b+3a+1}{2} + m − i)! (\frac{c−a−1}{2} + i − 1)!}

× det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a−1}{2} + i − j + 1)_{j−1} (\frac{b+a+1}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix}) . (8.1)

Thus it suffices to evaluate the determinant on the right-hand side. As in the preceding section, the advantage is that this determinant is a polynomial in b and c. So we can again apply the “identification of factors” method, as proposed in [20, Sec. 2.4]. We note that the first a rows of the matrix are identical to those of (7.1), whereas the other m rows differ only slightly. Hence we can use many arguments from Section 7. The four lemmas below address the four different cases, as a and m vary through all combinations of parities.

Lemma 21. Let a and m be both even nonnegative integers. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a−1}{2} + i − j + 1)_{j−1} (\frac{b+a+1}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= \frac{H(a + m) H(\frac{a}{2})^{2} H(\frac{m}{2})^{2}}{H(\frac{a+m}{2})^{2} 2^{m(a+m−1)/2}} ∏_{k=1}^{m/2} (\frac{b−1}{2} + k)_{a/2} (\frac{b+1}{2} + k)_{a/2}

× ∏_{k=1}^{m/2} (\frac{c−1}{2} + k)_{a/2} (\frac{c+1}{2} + k)_{a/2} ∏_{k=0}^{a/2−1} (b + c + m + 2k + 1)^{a−2k−1}

× ∏_{k=1}^{a/2−1} (b + c + 2m + 2k)^{a−2k} ∏_{k=m/2+1}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{m/2} (b + c + 2k)^{m−k}. (8.2)

Proof of Lemma 21. Let us denote the determinant in (8.2) by D_{2}(b, c). We will again proceed in the spirit of the proof of Lemma 17, i.e., we first show, in Steps 1–5 below, that the right-hand side of (8.2) divides D_{2}(b, c) as a polynomial in b and c. Then, in Step 6, we show that the degree of D_{2}(b, c) as a polynomial in b is at most \binom{a+m}{2}, the same being true for the degree in c. Analogously to the proof of Lemma 17, we conclude that D_{2}(b, c) must equal the right-hand side of (8.2), times a constant with respect to b and c. That this constant is equal to 1 is finally shown in Step 7, by evaluating the determinant D_{2}(b, c) for b = c = 1.

In order to prove (in Steps 1–5) that the right-hand side of (8.2) divides D_{2}(b, c), for each linear factor of (8.2) we exhibit again sufficiently many linear combinations of columns or rows which vanish. These linear combinations are almost identical (sometimes they are even identical) with the corresponding linear combinations in the proof of Lemma 17. Consequently, we will merely state these linear combinations here, but will not bother to supply their verifications, because these parallel the verifications in the proof of Lemma 17.

Step 1. ∏_{k=1}^{m/2} (\frac{b−1}{2} + k)_{a/2} (\frac{b+1}{2} + k)_{a/2} (\frac{c−1}{2} + k)_{a/2} (\frac{c+1}{2} + k)_{a/2} divides the determinant. Unlike in the case of the previous determinant D_{1}(b, c) (see (7.2)), here it is not possible to infer symmetry of D_{2}(b, c) in b and c directly from the definition. Therefore it will be necessary to prove separately that the factors involving b, respectively c, divide the determinant.

Again, we distinguish between four subcases, labeled below as (a), (b), (c), and (d).

(a) (b + e)^{e} (c + e)^{e} divides D_{2}(b, c) for 1 ≤ e ≤ min{a, m}, e ≢ a mod 2: This follows from the easily verified fact that (b + e) is a factor of each entry in the first e columns of D_{2}(b, c), respectively, that (c + e) is a factor of each entry in the last e columns of D_{2}(b, c).

(b) (b + e)^{m} (c + e)^{m} divides D_{2}(b, c) for m < e < a, e ≢ a mod 2: The following equations hold for s = 1, 2, …, m:

∑_{j=1}^{e+s−m} \binom{e − m + s − 1}{j − 1}\frac{(c + a − e − s + 2m + 1)_{e+s−j−m}}{(a − e − s + 2m + 1)_{e+s−j−m}} · (column j of D_{2}(−e, c)) = 0,

(8.3)

and

∑_{j=1}^{e+s−m} \binom{e − m + s − 1}{j − 1}\frac{(b + a − e − s + 2m + 1)_{e+s−j−m}}{(a − e − s + 2m + 1)_{e+s−j−m}}
· (column (a + m + 1 − j) of D_{2}(b, −e)) = 0. (8.4)

(c) (b + e)^{a} divides D_{2}(b, c) for a < e < m, e ≢ a mod 2: The following equations hold for s = 1, 2, …, a:

∑_{j=1}^{\frac{e−a−1}{2} +s} \binom{\frac{e−a−1}{2} + s − 1}{j − 1}\begin{matrix}(\frac{c}{2} + m − \frac{e}{2} + a − s + 1) & (e−a−1)/2+s−j \\ (m + \frac{3a−e}{2} − s + 1) & (e−a−1)/2+s−j \end{matrix}
· (column j of D_{2}(−e, c)) = 0, (8.5)

and

∑_{j=1}^{\frac{e−a−1}{2} +s} \binom{\frac{e−a−1}{2} + s − 1}{j − 1}\begin{matrix}(\frac{b}{2} + m − \frac{e}{2} + a − s + 1) & (e−a−1)/2+s−j \\ (m + \frac{3a−e}{2} − s + 1) & (e−a−1)/2+s−j \end{matrix}
· (column (a + m + 1 − j) of D_{2}(b, −e)) = 0. (8.6)

(d) (b + e)^{a+m−e} divides D_{2}(b, c) for max{a, m} ≤ e ≤ a + m, e ≢ a mod 2: The following equations hold for s = 1, 2, …, a + m − e:

∑_{i=1}^{s} \binom{s − 1}{i − 1}\frac{(−1)^{i} (\frac{c−e}{2} + 1)_{a+m−s} (\frac{c−e}{2} + m)_{i−1}}{(1 + c − e + m)_{a+m−s+i−1}}
· (row (a + m − e − s + i) of D_{2}(−e, c))
+ (row (m + \frac{3a+1}{2} − \frac{e}{2} − s + 1) of D_{2}(−e, c)) = 0, (8.7)

and

∑_{i=1}^{s} \binom{s − 1}{i − 1}\frac{(−1)^{i} (\frac{b−e}{2} + 1)_{a+m−s} (\frac{b−e}{2} + m)_{i−1}}{(1 + b − e + m)_{a+m−s+i−1}}
· (row (e + s − m − i + 1) of D_{2}(b, −e))
+ (row (\frac{a+1}{2} + \frac{e}{2} + s) of D_{2}(b, −e)) = 0. (8.8)

Step 2. ∏_{k=0}^{a/2−1} (b + c + m + 2k + 1)^{a−2k−1} divides the determinant. The following equation holds for 0 ≤ e ≤ a − 2, s = 1, 2, …, e + 1:

∑_{i=1}^{a−e−1} (\frac{(c + m + i)_{a−e−i+s−1}}{(c − e − 1 + i)_{a−e−i+s−1}} \binom{a − e − 2}{i − 1}\frac{(s)_{a−e−1} (−1)^{i}}{(s − i + a − e − 1)(a − e − 2)!}

· (row i of D_{2}(−c − a − m + 1 + e, c)))

+ (−1)^{a−e−1} · (row (a − e − 1 + s) of D_{2}(−c − a − m + 1 + e, c)) = 0. (8.9)

Here, we need equation (8.9) only for even e.

Step 3. ∏_{k=1}^{a/2−1} (b + c + 2m + 2k)^{a−2k} divides the determinant. The following equation holds for 0 < e ≤ a, e ≡ a mod 2, and s = 1, 2, …, e:

∑_{j=s}^{a+m+s−e} \binom{a + m − e}{j − s} · (column j of D_{2}(−c − 2m − a + e, c)) = 0.  (8.10)

Step 4. ∏_{k=m/2+1}^{m} (b + c + 2k)^{a+m−k} divides the determinant. The following equation holds for m/2 < e ≤ m and s = 1, 2, …, a + m − e:

∑_{j=s}^{s+e} \binom{e}{j − s} · (column j of D_{2}(−c − 2e, c)) = 0.  (8.11)

Step 5. ∏_{k=1}^{m/2} (b + c + 2k)^{m−k} divides the determinant. The following equation holds for e ≤ m − 1 and s = 1, 2, …, e:

∑_{i=1}^{m−s+1}(−1)^{i}\binom{m − s}{i − 1}\begin{matrix}(\frac{c}{2} + \frac{a}{2} + i − \frac{1}{2}) & m−s−i+1 \\ (\frac{c}{2} − \frac{a}{2} − e + i − \frac{1}{2}) & m−s−i+1 \end{matrix}

· (row (a + i) of D_{1}(−c − 2m + 2e, c)) = 0. (8.12)

Step 6. Determination of the degree of D_{2}(b, c) as a polynomial in b. This is clearly the same degree as for D_{1}(b, c), that is, \binom{a+m}{2}.

Step 7. Computation of the multiplicative constant. In analogy to the proof of Lemma 18, we evaluate the determinant for b = c = 1. Again, we do this by going back, via (8.1) and Lemma 16, to the combinatorial origin of the determinant, which is enumeration of lozenge tilings. We can still use Figure 11 for our considerations. The number of lozenge tilings is easily seen to be equal to \binom{m+1+ \frac{a}{2}}{\frac{a}{2}} + \binom{m+1+ \frac{a}{2} −1}{\frac{a}{2} −1}. It is then a routine computation to verify that this does indeed give the multiplicative constant as claimed in (8.2). □

Lemma 22. Let a and m be nonnegative integers, a odd and m even. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a−1}{2} + i − j + 1)_{j−1} (\frac{b+a+1}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= \frac{H(a + m) H(\frac{a−1}{2}) H(\frac{a+1}{2}) H(\frac{m}{2})^{2}}{H(\frac{a+m−1}{2}) H(\frac{a+m+1}{2}) 2^{m(a+m−1)/2}}

× ∏_{k=1}^{m/2} (\frac{b}{2} + k)_{(a−1)/2} (\frac{b}{2} + k)_{(a+1)/2} (\frac{c}{2} + k)_{(a−1)/2} (\frac{c}{2} + k)_{(a+1)/2}

× ∏_{k=0}^{(a−3)/2} (b + c + m + 2k + 1)^{a−2k−1} ∏_{k=0}^{(a−1)/2} (b + c + 2m + 2k)^{a−2k}

× ∏_{k=m/2+1}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{m/2} (b + c + 2k)^{m−k}. (8.13)

Proof. We proceed analogously to the proof of Lemma 21. The only difference is the parity of a, so we have to check the places in the proof of Lemma 21 where we used the fact that a is even.

Steps 1, 3–5 can be reused verbatim, but the corresponding products are slightly different.

In Step 2 we are now interested in the factors corresponding to odd values of e (1 ≤ e ≤ a − 2), because the factors with even e are covered by Steps 3 and 4.

Step 6 can be reused verbatim.

The computation of the multiplicative constant is done analogously to Step 7 in the proof of Lemma 17. Again using Figure 10, we see that the number of lozenge tilings, related to our determinant via (8.1) and Lemma 16, for b = c = 0 equals 1. It is then a routine computation to verify that this gives the multiplicative constant as claimed in (8.13). □

Lemma 23. Let a and m be nonnegative integers, a even and m odd. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a−1}{2} + i − j + 1)_{j−1} (\frac{b+a+1}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= (−1)^{a/2} \frac{H(a + m) H(\frac{a}{2})^{2} H(\frac{m−1}{2}) H(\frac{m+1}{2})}{H(\frac{a+m−1}{2}) H(\frac{a+m+1}{2}) 2^{m(a+m−1)/2}} ∏_{k=1}^{(m+1)/2} (\frac{b−1}{2} + k)_{a/2} ∏_{k=1}^{(m−1)/2} (\frac{b+1}{2} + k)_{a/2}

× ∏_{k=1}^{(m+1)/2} (\frac{c−1}{2} + k)_{a/2} ∏_{k=1}^{(m−1)/2} (\frac{c+1}{2} + k)_{a/2} ∏_{k=1}^{a/2−1} (b + c + m + 2k)^{a−2k}

× ∏_{k=1}^{a/2−1} (b + c + 2m + 2k)^{a−2k} ∏_{k=(m+1)/2}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{(m−1)/2} (b + c + 2k)^{m−k}. (8.14)

Proof. We proceed analogously to the proof of Lemma 21. The only difference is the parity of m, so we have to check the places in the proof of Lemma 21 where we used the fact that m is even.

Steps 1, 3–5 can be reused verbatim, but the corresponding products are slightly different.

In Step 2 we are now interested in the factors corresponding to odd values of e (1 ≤ e ≤ a − 3), because the factors with even e are covered by Steps 3 and 4.

Step 6 can be reused verbatim.

The computation of the multiplicative constant is done analogously to Step 7 in the proof of Lemma 21. Using again Figure 11, we see that the (−1)-enumeration of lozenge tilings, related to our determinant via (8.1) and Lemma 16, for b = c = 1 equals (−1)^{a/2}\binom{m+1+ \frac{a}{2}}{\frac{a}{2}} + (−1)^{a/2+1}\binom{m+1+ \frac{a}{2} −1}{\frac{a}{2} −1}. It is then a routine computation to verify that this gives the multiplicative constant as claimed in (8.14). □

Lemma 24. Let a and m be odd nonnegative integers. Then

det_{1≤i,j≤a+m} (\begin{matrix}(c + m + i − j + 1)_{j−1} (b − i + j + 1)_{a+m−j} & 1 ≤ i ≤ a \\ (\frac{c−a−1}{2} + i − j + 1)_{j−1} (\frac{b+a+1}{2} − i + j + 1)_{a+m−j} & a < i ≤ a + m \end{matrix})

= (−1)^{(a+1)/2} \frac{H(a + m) H(\frac{a−1}{2}) H(\frac{a+1}{2}) H(\frac{m−1}{2}) H(\frac{m+1}{2})}{H(\frac{a+m}{2})^{2} 2^{m(a+m−1)/2+1/2}}

× ∏_{k=1}^{(m+1)/2} (\frac{b}{2} + k)_{(a−1)/2} ∏_{k=1}^{(m−1)/2} (\frac{b}{2} + k)_{(a+1)/2}

× ∏_{k=1}^{(m+1)/2} (\frac{c}{2} + k)_{(a−1)/2} ∏_{k=1}^{(m−1)/2} (\frac{c}{2} + k)_{(a+1)/2} ∏_{k=1}^{(a−1)/2} (b + c + m + 2k)^{a−2k}

× ∏_{k=1}^{(a−1)/2} (b + c + 2m + 2k)^{a−2k} ∏_{k=(m+1)/2}^{m} (b + c + 2k)^{a+m−k} ∏_{k=1}^{(m−1)/2} (b + c + 2k)^{m−k}. (8.15)

Proof. We proceed analogously to the proof of Lemma 21. The parameters a and m are odd, so we have to check the places in the proof of Lemma 21 where we used the fact that a or m is even.

Steps 1–6 can be reused verbatim, but the corresponding products are slightly different.

The computation of the multiplicative constant is done analogously to Step 7 in the proof of Lemma 17. Again using Figure 10, we see that the (−1)-enumeration of lozenge tilings, related to our determinant via (8.1) and Lemma 16, for b = c = 0 equals (−1)^{(a+1)/2}. It is then a routine computation to verify that this gives the multiplicative constant as claimed in (8.15). □

9. Proof of Theorem 11

For the proof of Theorem 11, we proceed similarly to [28]. We define determinants Z_{n}(x, μ) by

Z_{n}(x, μ) = det_{0≤i,j≤n−1} (−δ_{ij} + ∑_{t,k=0}^{n−1} \binom{i + μ}{t}\binom{k}{t}\binom{j − k + μ − 1}{j − k}x^{k−t}) .  (9.1)

The only difference to the definition of Z_{n}(x, μ) in [28] is the minus sign in front of δ_{ij}.

Then an analogue of Theorem 5 of [28] is true. Lemma 25. Let n be a nonnegative integer. Then Z_{n}(x, μ) = 0 if n is odd. If n is even, then Z_{n}(x, μ) factors,

Z_{n}(x, μ) = (−1)^{n/2} det_{0≤i,j≤n/2−1} (∑_{t=0}^{n−1} \frac{t + 1}{j + 1}\binom{i + μ}{t − i}\binom{j + 1}{t − j}x^{2j+1−t})

× det_{0≤i,j≤n/2−1} (∑_{t=0}^{n−1} \frac{t + μ + 1}{i + μ + 1}\binom{i + μ + 1}{t − i}\binom{j}{t − j}x^{2j−t}) . (9.2)

Proof. As in the proof of Theorem 5 of [28], define matrices S, M, U,

S = (\binom{i + μ}{t})_{0≤i,t≤n−1} , M = (\binom{k}{t}x^{k−t})_{0≤t,k≤n−1} ,

U = (\binom{j − k + μ − 1}{j − k})_{0≤k,j≤n−1} ,

and J and F (x),

J = ((−1)^{k−i}\binom{μ}{k − i})_{0≤i,k≤n−1} , F (x) = (\binom{j − ⌊j/2⌋}{j − i}(−x)^{j−i})_{0≤i,j≤n−1} . (9.3)

Thus, Z_{n}(x, μ) equals det(−I +SMU). Now, as in [28], multiply Z_{n}(x, μ) on the left by det(F (1)^{t}) and on the right by det(JF (x)). Subsequently do the manipulations given in [28] (which amount to applying the Chu–Vandermonde summation formula several times). The result is that

Z_{n}(x, μ) = det_{0≤i,j≤n−1}(−I + SMU) = det_{0≤i,j≤n−1}(−V (x, μ) + W (x, μ)),

where

V (x, μ)_{2i+r,2j+s} = ∑_{t=0}^{n−1}(−1)^{r+s}\binom{i + r + μ}{t − i}\binom{j + s}{t − j}x^{2j+s−t},  (9.4)

W (x, μ)_{2i+r,2j+s} = ∑_{t=0}^{n−1} \binom{i + μ}{t − i − r}\binom{j}{t − j − s}x^{2j+s−t},  (9.5)

where r and s are restricted to be 0 or 1, as in [28].

It is straightforward to check that V_{2i,2j} = W_{2i,2j}. Hence, each entry of the matrix −V + W in an even-numbered row and even-numbered column is 0. This implies that det(−V + W) must be 0 whenever the size of the matrix, n, is odd. In the case that n is even it implies the factorization

Z_{n}(x, μ) = det(−V (x, μ) + W (x, μ))

= (−1)^{n/2} det_{0≤i,j≤n/2−1}(−V_{2i,2j+1} + W_{2i,2j+1}) det_{0≤i,j≤n/2−1}(−V_{2i+1,2j} + W_{2i+1,2j}).

As is easily verified, this equation is exactly equivalent to (9.2). □

Proof of Theorem 11. Now choose x = 1, μ = m/2, n = a in Lemma 25. Then all the sums appearing in (9.2) can be evaluated by means of the Chu–Vandermonde summation (7.11). The result is

Z_{a}(1, m/2) = det_{0≤i,j≤a−1} (−δ_{ij} + \binom{m + i + j}{j})

= det_{0≤i,j≤a/2−1} ((3i + m + 1)\frac{(i + j + m/2)!}{(2i − j + m/2)! (2j − i + 1)!})

× det_{0≤i,j≤a/2−1} ((3j + m/2 + 1)\frac{(i + j + m/2)!}{(2i − j + m/2 + 1)! (2j − i)!}) .

Both determinants on the right-hand side of this identity can be evaluated by means of Theorem 10 in [18], which reads

det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)!}{(x + 2i − j)! (y + 2j − i)!})

= ∏_{i=0}^{n−1} \frac{i! (x + y + i − 1)! (2x + y + 2i)_{i} (x + 2y + 2i)_{i}}{(x + 2i)! (y + 2i)!} . (9.6)

This completes the proof of the theorem. □

10. Proof of Theorem 12

We prove Theorem 12 by finding a determinant factorization, Eq. (10.1), in which the first determinant represents the number of all lozenge tilings of a hexagon with side lengths a, a + m, a, a + m, a, a + m and removed central triangle of side length m (see the following paragraph), in which the second determinant represents the number of all such tilings which are cyclically symmetric (see e.g. [6, Lemma 3.1]), and in which the third determinant is the one that we want to evaluate. Since the total number of the above lozenge tilings is already known (thanks to Theorem 1), as well as the number of

S_{2}  S_{1}  S_{3}

Figure 12. A lozenge tiling of a hexagon with a = b = c = 3 and core of size m = 2.

all such tilings which are cyclically symmetric (thanks to Theorem 6), we obtain, up to some multiplicative constant that is not difficult to find, an explicit expression for our determinant on the left-hand side of (3.4). The factorization (10.1), interpreted combinatorially in the above way, could be explained in terms of the principle of “factorization through symmetry” as described in [23, Sec. IVB; cf. in particular Sec. VIIA] (with a precursor appearing in [16, Theorem 3’, Sec. 5, although it is not explicitly stated]). We prefer to provide a direct derivation by means of “wrapping lattice paths around the triangular hole,” as it is a very attractive and instructive alternative way to derive this equation.

We already know that the number of all lozenge tilings of a hexagon with side lengths a, a + m, a, a + m, a, a + m and removed central triangle of side length m equals (1.2) with a = b = c. On the other hand, we claim that it equals det(I + B^{3}), where, as before in the proof of Theorem 9 in Section 4, B = B(a, m) is the a × a matrix with entries \binom{m+i+j}{j}, 0 ≤ i, j ≤ a − 1, and I = I(a) is the a × a identity matrix.

To prove this claim, we first note that det(I +B^{3}) is the sum of all principal minors of B^{3}. Next we consider the construction used in Section 6 in order to prove polynomiality in m of the number of lozenge tilings of a cored hexagon, i.e., we extend all sides of the removed triangle to the left (if viewed from the interior of the triangle), as is indicated by the thick segments, labeled as S_{1}, S_{2}, and S_{3}, in Figure 12. These segments cut the cored hexagon into three regions. In particular, they cut some of the lozenges in two. (In Figure 12, these lozenges are shaded.) Subsequently, in each of the three regions, we connect the “cut” lozenges by paths, by “following” along the lozenges of the tiling, as is illustrated in Figure 12 by the dashed lines. (Note the difference between Figures 12 and 9. In our special case a = b = c all the paths form cycles.)

Let us number the possible positions of the “cut” lozenges, from inside to outside, by 0, 1, …, a − 1. Thus, the positions of the “cut” lozenges on the segment S_{1} are 0 and 2, they are 0 and 1 on S_{2}, and they are 1 and 2 on S_{3}. The number of paths in the lower left region which start at position i on S_{1} and end at position j on S_{2} is \binom{m+i+j}{j}, which is the (i, j)-entry of B. The rotational symmetry of the cored hexagon guarantees that an analogous fact is true for the other regions. Thus, the number of paths starting at position i on S_{1}, then running around the removed triangle, and finally ending at position j on S_{1}, equals the (i, j)-entry of B^{3}. If we have a family of paths starting and ending at positions i_{1}, i_{2}, …, i_{k}, the Lindström–Gessel–Viennot theorem (see Lemma 14) implies that the number of these paths is the minor consisting of rows and columns with indices i_{1}, i_{2}, …, i_{k} of the matrix B^{3}. Thus, the number of these families of paths is the sum of all principal minors of B^{3}, which we have already found to be equal to det(I + B^{3}).

Now we use the factorization

I + B^{3} = (I + B)(ωI + B)(\overline{ω}I + B),

where ω is a primitive third root of unity. Thus we have

det(I + B^{3}) = det(I + B) · | det(ωI + B)|^{2}.  (10.1)

The left-hand side equals (1.2) with a = b = c by the above considerations, and the determinant det(I + B) has been computed by Andrews [2, Theorem 8], restated here as Theorem 10.

Thus, a combination of (10.1), Theorem 10 and (1.2) with a = b = c will give det(ωI+ B), the determinant that we want to compute, up to a complex factor of modulus 1. We note that the determinant is a polynomial in m. It is a routine computation to verify that the determinant is the expression claimed in Theorem 12, up to this multiplicative constant.

In order to compute the multiplicative constant, we compute the leading coefficient of the determinant as a polynomial in m/2, and compare the result with the leading coefficient of the right-hand side of (3.4). Unfortunately, the leading coefficient of the determinant cannot be determined straightforwardly by extracting the leading coefficient of each of the entries and computing the corresponding determinant, for the result would be zero. Therefore we have to perform some manipulations of the matrix first to avoid cancellation of leading terms. We use the strategy from [28], which we have already used in the proof of Lemma 25. Instead of the determinant Z_{n}(x, μ), we consider here the slightly different determinant

Z̃_{n}(x, μ) = det_{0≤i,j≤n−1} (ωδ_{ij} + ∑_{t,k=0}^{n−1} \binom{i + μ}{t}\binom{k}{t}\binom{j − k + μ − 1}{j − k}x^{k−t}) ,  (10.2)

where ω is a primitive third root of unity.

Now we proceed analogously to the proof of Lemma 25, i.e., we multiply Z̃_{n}(x, μ) on the left by det(F (1)^{t}) and on the right by det(JF (x)), where the matrices F (x) and J are given in (9.3), and use Chu–Vandermonde summation several times. This yields

Z̃_{n}(x, μ) = det_{0≤i,j≤n−1}(ωV (x, μ) + W (x, μ)),

where V (x, μ) and W (x, μ) are the matrices defined in equation (9.4).

Now let x = 1, μ = m/2, n = a, and V = V (1, m/2), W = W (1, m/2). Again using Chu–Vandermonde summation, we can express the desired determinant in terms of V = (V_{ij})_{0≤i,j≤a−1} and W = (W_{ij})_{0≤i,j≤a−1}:

det(ωI + B) = det(ωV + W),  (10.3)

where

V_{2i+r,2j+s} = (−1)^{r+s}\binom{i + j + r + s + m/2}{s + 2j − i}  (10.4)

and

W_{2i+r,2j+s} = \binom{i + j + m/2}{s + 2j − i − r},  (10.5)

where r and s are restricted to be 0 or 1. Next we extract the leading coefficients of all the entries of ωV + W, viewed as polynomials in m/2, and compute the corresponding determinant. If we should obtain something nonzero, then this must be the leading coefficient of the determinant det(ωV + W), and hence of det(ωI + B), as a polynomial in m/2. Thus, we have to compute the determinant of the matrix L = (L_{ij})_{0≤i,j≤a−1}, where

L_{2i+r,2j+s} = \begin{cases}\frac{(−1)^{s+1}}{(s+2j−i)!}ω & if r = 1, \\ \frac{(−1)^{s}}{(s+2j−i)!}ω + \frac{1}{(s+2j−i)!} & if r = 0. \end{cases}

We add row 1 of L to row 0, row 3 to row 2, etc. In that manner, we obtain the matrix L′ = (L′_{ij})_{o≤i,j≤a−1}, where

L′_{2i+r,2j+s} = \begin{cases}\frac{1}{(s+2j−i)!} & if r = 0, 2i ≠ a − 1, \\ \frac{(−1)^{s+1}}{(s+2j−i)!}ω & if r = 1, \\ \frac{((−1)^{s}ω+1)}{(s+2j−i)!} & if 2i = a − 1. \end{cases}

Clearly, we have det L = det L′, and we can take out ω from all the rows of L′ with odd row index. We get

det L = ω^{⌊^{\frac{a}{2}}⌋} det L′′,

with the matrix L′′ = (L′′_{ij})_{0≤i,j≤a−1} defined by

L′′_{2i+r,2j+s} = \begin{cases}\frac{1}{(s+2j−i)!} & if r = 0, 2i ≠ a − 1, \\ \frac{(−1)^{s+1}}{(s+2j−i)!} & if r = 1, \\ \frac{((−1)^{s}ω+1)}{(s+2j−i)!} & if 2i = a − 1. \end{cases}

Now we add row 0 of L′′ to row 1, row 2 to row 3, etc. We obtain the matrix L′′′ = (L′′′_{ij})_{0≤i,j≤a−1}, where

L′′′_{2i+r,2j+s} = \begin{cases}\frac{1}{(s+2j−i)!} & if r = 0, 2i ≠ a − 1, \\ \frac{2}{(s+2j−i)!} & if r = 1, s = 1, \\ 0 & if r = 1, s = 0, \\ \frac{((−1)^{s}ω+1)}{(s+2j−i)!} & if 2i = a − 1. \end{cases}

We rearrange the rows and columns simultaneously, so that the odd-numbered rows and columns come before the even-numbered, respectively. Now we have obtained a block matrix with one block formed by the rows and columns with odd indices and the other one formed by the rows and columns with even indices. Consequently, we have

det L = ω^{⌊a/2⌋} det_{0≤i,j≤⌊\frac{a−2}{2}⌋} (\frac{2}{(1 + 2j − i)!}) det_{0≤i,j≤⌊\frac{a−1}{2}⌋} ((ω + 1)\frac{1}{(2j−i)!}  i = \frac{a−1}{2}^{\frac{1}{(2j−i)!}  i ≠ \frac{a−1}{2}})

= ω^{⌊a/2⌋}(ω + 1)^{χ(a odd)}2^{⌊a/2⌋} ∏_{j=0}^{⌊(a−2)/2⌋} \frac{1}{(2j + 1)!} ∏_{j=0}^{⌊(a−1)/2⌋} \frac{1}{(2j)!}

× det_{0≤i,j≤⌊(a−2)/2⌋} ((2j − i + 2)_{i}) det_{0≤i,j≤⌊(a−1)/2⌋} ((2j − i + 1)_{i}),

where we used the notation χ(A)=1 if A is true and χ(A)=0 otherwise. The two determinants can be evaluated by special cases of a variant of the Vandermonde determinant evaluation which we state in Lemma 26 below. After application of this lemma and some simplification we get

2^{l^{2}}ω^{l} \frac{H(l)^{2}}{H(2l)}  (10.6)

if a is even, a = 2l, and

2^{l^{2}+l}ω^{l}(ω + 1)\frac{H(l) H(l + 1)}{H(2l + 1)}  (10.7)

if a is odd, a = 2l + 1.

It is routine to check that the leading coefficient of the right-hand side of (3.4), viewed as a polynomial in m/2, is exactly the same.

This finishes the proof of the theorem. □ Lemma 26. Let p_{i} be a monic polynomial of degree i, i = 0, 1, …, n. Then

det_{0≤i,j≤n}(p_{i}(X_{j})) = ∏_{0≤i<j≤n}(X_{j} − X_{i}).

□

11. Proof of Theorem 13

If a is even, a = 2l say, the formula can be derived analogously to Theorem 12. (The derivation of the latter was the subject of the preceding section.) Here, the starting point is to do the (−1)-enumeration (as opposed to “ordinary” enumeration) of all the lozenge tilings of a hexagon with side lengths a, a + m, a, a + m, a, a + m and removed central triangle of side length m in two different ways.

First, the (−1)-enumeration of these lozenge tilings is given by (2.1) with a = b = c. On the other hand, the arguments given at the beginning of the preceding section, suitably modified, show that it also equals det(−I + B^{3}), where B is again the matrix from the preceding section.

Now we use the factorization

det(−I + B^{3}) = det(−I + B) · | det(ωI + B)|^{2},  (11.1)

where ω is a primitive sixth root of unity. (Note that this equation is the analogue of (10.1) in the present context. Again, this factorization of the (−1)-enumeration of all lozenge tilings of the above cored hexagon could have also been derived by means of the principle of “factorization through symmetry” [23, Sec. IVB; cf. in particular Sec. VIIA].) By the above considerations, the left-hand side equals (2.1) with a = b = c, and the determinant det(−I+B) is computed in Theorem 11. This determines det(ωI+ B) up to a multiplicative constant of modulus 1. It is then a routine computation to check that the result agrees with the expression at the right-hand side of (3.5), up to a factor of modulus 1.

In order to determine the multiplicative constant, one proceeds as in the preceding section. In fact, the determination of the leading coefficient of the determinant as a polynomial in m/2 given there can be used here verbatim, because we treated ω like an indeterminate in the respective computations. Thus, the leading coefficient is the expression in (10.6), with ω now a primitive sixth root of unity. It is routine to check that for a = 2l the right-hand side of (3.5) has the same leading coefficient as polynomial in m/2.

Now let us suppose that a is odd, a = 2l + 1 say. Unfortunately, the above strategy of determining the value of det(ωI + B) through equation (11.1) fails miserably here, because det(−I + B^{3}) as well as det(−I + B) are zero in the case of odd a (compare Theorems 4 and 11). Therefore we have to find a different line of attack. We approach the evaluation of det(ωI + B), for odd a, by first transforming the determinant in the way we have already done in the proofs of Lemma 25 and of Theorem 12, and by then applying once again the “identification of factors” method to evaluate the obtained determinant.

In fact, the manipulations explained in the preceding section that proved (10.3) (which are based on multiplying the relevant matrix to the left and right by suitable matrices, as elaborated in the proof of Lemma 25 in Section 9) remain valid in the present context, again, because there ω is treated like an indeterminate. Therefore we have

det(ωI + B) = det(ωV + W),

where the matrices V = (V_{ij})_{0≤i,j≤2l} and W = (W_{ij})_{0≤i,j≤2l} are again the matrices defined by (10.4) and (10.5).

Our goal is now to evaluate the determinant of the matrix ωV + W. We denote this matrix by X(2l +1, m/2). The determinant det X(2l +1, m/2) is a polynomial in m, so we can indeed use the “identification of factors” method to compute this determinant. Again, there are several steps to be performed. In Steps 1–4 below we prove that the right-hand side of (3.5) does indeed divide the determinant as a polynomial in m. In Step 5 we determine the maximal degree of the determinant as a polynomial in m. It turns out to be (a^{2} − 1)/4, which is exactly the degree of the right-hand side of (3.5) (for odd a, of course). Therefore the determinant must be equal to the right-hand side of (3.5), up to a multiplicative constant. This multiplicative constant is finally found to be 1 in Step 6.

Step 1. ∏_{i=0}^{⌊l/2⌋−1}(\frac{m}{2} + 2l − i + 1)_{l−2i−1} divides the determinant det X(2l + 1, m/2). Proceeding in the spirit of Step 1(b) in the proof of Lemma 17, we prove this by finding, for each linear factor of the product, a linear combination of the columns of X(2l + 1, m/2) which vanishes if the factor vanishes. To be precise, we claim that for m/2 = −3l + k + 3d, d ≥ 0 and 1 ≤ k ≤ l − 2d − 1 the following equation holds:

∑_{j=0}^{k−1} \binom{k − 1}{j}(ω · (column (2l − 2d − 2j − 1) of X(2l + 1, −3l + k + 3d))

+ (column (2l − 2d − 2j − 2) of X(2l + 1, −3l + k + 3d))) = 0. (11.2)

If we restrict the left-hand side of this equation to the (2i)th row, and simplify a little bit, it becomes

∑_{j=0}^{k−1} \binom{k − 1}{j} (\binom{i − 2l + 2d − j + k}{2l − 2d − 2j − i − 1} + \binom{i − 2l + 2d − j + k − 1}{2l − 2d − 2j − i − 2}) .  (11.3)

It becomes (ω − 1) times the same expression if we restrict to the (2i + 1)th row.

As is seen by inspection, the expression (11.3) vanishes trivially for k = 1. From now on, let k > 1. In order to establish that (11.3) vanishes in that case as well, we first rewrite the sum (11.3) in hypergeometric notation (7.6):

\frac{(k − 1) (2 + 4d + 2i + k − 4l)_{−2−2d−i+2l}}{(2l − 2d − i − 1)!}

×_{4}F_{3}[\begin{matrix}1 − k, \frac{4}{3} − \frac{k}{3}, 1 + d + \frac{i}{2} − l, \frac{1}{2} + d + \frac{i}{2} − l \\ \frac{1}{3} − \frac{k}{3}, 1 − 2d − i − k + 2l, 2 + 4d + 2i + k − 4l \end{matrix}; 4] . (11.4)

The hypergeometric summation formula which is relevant here, and as well in the subsequent steps, is the following “strange” evaluation of a _{7}F_{6}-series, due to Gessel and Stanton [12, (1.7)] (see also [10, (3.8.14), c = 1, a → q^{A}, etc., q → 1]):

7F_{6}[\begin{matrix}A, 1 + \frac{A}{3}, B, 1 − B, \frac{F}{2} , \frac{1}{2} + A − \frac{F}{2} + n, −n \\ \frac{A}{3}, 1 + \frac{A}{2} − \frac{B}{2} , \frac{1}{2} + \frac{A}{2} + \frac{B}{2} , 1 + A − F, −A + F − 2n, 1 + A + 2n \end{matrix}; 1]

= \frac{(1 + A)_{2n} (1 + \frac{A}{2} − \frac{B}{2} − \frac{F}{2} )_{n} (\frac{1}{2} + \frac{A}{2} + \frac{B}{2} − \frac{F}{2} )_{n}}{(1 + A − F)_{2n} (1 + \frac{A}{2} − \frac{B}{2} )_{n} (\frac{1}{2} + \frac{A}{2} + \frac{B}{2} )_{n}} ,

where n is a nonnegative integer. If in this formula we let B tend to infinity, we obtain

5F_{4}[\begin{matrix}A, 1 + \frac{A}{3}, \frac{F}{2} , \frac{1}{2} + A − \frac{F}{2} + n, −n \\ \frac{A}{3}, 1 + A − F, −A + F − 2n, 1 + A + 2n \end{matrix}; 4] = \frac{(1 + A)_{2n}}{(1 + A − F)_{2n}} .  (11.5)

In particular, this formula allows us to deduce that the left-hand side of (11.5) must be zero whenever A is a negative integer. This is seen as follows: Multiply both sides of (11.5) by

(−A + F − 2n)_{−A} (1 + A + 2n)_{−A}.  (11.6)

Then, for a fixed negative integer A, the left-hand side becomes polynomial in n. The right-hand side is zero for all n larger than −A/2 because of the presence of the term (1 + A)_{2n}. The term (11.6) is nonzero for these values of n, therefore the left-hand side of (11.5) must be zero for these n. Since these are infinitely many n, the left-hand side of (11.5) must be in fact zero for all n. (An alternative way to see that the left-hand side of (11.5) vanishes for all negative A is by setting c = 1 in [11, (5.13)] or [10, (3.8.11)], then replace a by q^{A}, etc., and finally let q → 1 and B → ∞.)

If we use (11.5) with A = 1 − k, F = 2d + i − 2l + 2, n = 2d + i + k − 2l, together with the above remarks, then we get immediately that the _{4}F_{3}-series in (11.4) vanishes for k > 1. (It should be noted that, for this choice of parameters, the _{5}F_{4}-series in (11.5) reduces to the _{4}F_{3}-series in (11.4).) Thus, equation (11.2) is established.

Step 2. ∏_{i=0}^{⌊l/2⌋}(m/2 + 2l − i)_{l−2i} divides the determinant. We claim that for m/2 = −3l + k + 3d − 1, d ≥ 0 and 1 ≤ k ≤ l − 2d the following equation holds:

∑_{j=0}^{k−1} \binom{k − 1}{j}((column (2l − 2d − 2j) of X(2l + 1, −3l + k + 3d − 1))

+ (2ω − 1) · (column (2l − 2d − 2j − 1) of X(2l + 1, −3l + k + 3d − 1))

+ (ω − 1) · (column (2l − 2d − 2j − 2) of X(2l + 1, −3l + k + 3d − 1))) = 0. (11.7)

Restricted to the (2i)th row, the left-hand side of this equation becomes, after a little simplification,

(1 + ω) ∑_{j=0}^{k−1} \binom{k − 1}{j} (\binom{i − 2l + 2d − j + k − 1}{2l − 2d − 2j − i} + \binom{i − 2l + 2d − j + k − 2}{2l − 2d − 2j − i − 1}) .

(11.8)

Clearly, this expression vanishes for k = 1. If k > 1, we write (11.8) in hypergeometric notation, to obtain

(1 + ω)\frac{(k − 1) (4d + 2i + k − 4l)_{−1−2d−i+2l}}{(2l − 2d − i)!}

×_{4}F_{3}[\begin{matrix}1 − k, \frac{4}{3} − \frac{k}{3}, \frac{1}{2} + d + \frac{i}{2} − l, d + \frac{i}{2} − l \\ \frac{1}{3} − \frac{k}{3}, 2 − 2d − i − k + 2l, 4d + 2i + k − 4l \end{matrix}; 4] . (11.9)

This time we use (11.5) with A = 1 − k, F = 2d + i − 2l + 1, n = 2d + i + k − 2l − 1. Together with the remarks accompanying (11.5), this implies immediately that the 4F_{3}-series in (11.9) vanishes for k > 1.

On the other hand, restricted to the (2i + 1)th row, the left-hand side of (11.7) becomes, after a little simplification,

(ω − 1) ∑_{j=0}^{k−1} \binom{k − 1}{j} (\binom{i − 2l + 2d − j + k}{2l − 2d − 2j − i − 1} + \binom{i − 2l + 2d − j + k − 1}{2l − 2d − 2j − i − 2})

− ω ∑_{j=0}^{k−1} \binom{k − 1}{j} (\binom{i − 2l + 2d − j + k − 1}{2l − 2d − 2j − i} + \binom{i − 2l + 2d − j + k − 2}{2l − 2d − 2j − i − 1}) .

That the first sum vanishes was already shown in Step 1 (compare (11.3)), that the second sum vanishes was shown just above (compare (11.8)). Thus, equation (11.7) is established.

A short argument shows that the linear combinations of Step 1 are independent of the linear combinations of Step 2. Let us denote the columns of X(2l + 1, m/2) by C_{0}, C_{1}, …, C_{2l}. In Step 1 we have linear combinations of vectors of the form ωC_{2k+1} + C_{2k}, whereas in Step 2 we have always linear combinations of vectors of the form C_{2k+2} + (2ω − 1)C_{2k+1} + (ω − 1)C_{2k}. If these linear combinations were dependent we could use the identity

(C_{2k+2} + (2ω − 1)C_{2k+1} + (ω − 1)C_{2k}) − (ω + 1)(ωC_{2k+1} + C_{2k}) = C_{2k+2} − 2C_{2k},

and get a linear combination of vectors of the form ωC_{2k+1} + C_{2k} equal to a nonzero real linear combination of the C_{i}’s, which is clearly impossible.

Step 3. ∏_{i=0}^{⌊l/2⌋−1}(m/2 + 3i + 5/2)_{l−2i−1} divides the determinant. We claim that for m/2 = −k − \frac{3}{2}d, d odd, d ≥ 1, and 1 ≤ k ≤ l − d the following equation holds:

∑_{i=0}^{k−1} \binom{k − 1}{i}((row (2i + 2d) of X(2l + 1, −k − \frac{3}{2}d))

+ ω · (row (2i + 2d + 1) of X(2l + 1, −k − \frac{3}{2}d))) = 0. (11.10)

Restricted to the (2j)th column, the left-hand side of this equation becomes, after a little simplification,

∑_{i=0}^{k−1} \binom{k − 1}{i} (\binom{i − d/2 + j − k + 1}{2j − i − d} + \binom{i − d/2 + j − k}{2j − i − d}) .  (11.11)

It becomes (ω − 1) times the same expression if we restrict to the (2j + 1)th column.

Again, the expression (11.11) vanishes trivially for k = 1. In order to establish that (11.11) vanishes for k > 1 as well, we reverse the order of summation, and then write the sum in hypergeometric notation. Thus we obtain

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

(11.12)

By (11.5) with A = 1 − k, F = 1 − d/2 + j − k, n = j − d/2, together with the remarks accompanying (11.5), this implies immediately that the _{4}F_{3}-series in (11.12) vanishes for k > 1. Thus, equation (11.10) is established.

Step 4. ∏_{i=0}^{⌊l/2⌋}(m/2 + 3i + 3/2)_{l−2i} divides the determinant. We claim that for m/2 = −k − \frac{3}{2}d − \frac{1}{2}, d even, d ≥ 0, and 1 ≤ k ≤ l − d the following equation holds:

∑_{i=0}^{k−1} \binom{k − 1}{i}((row (2i + 2d) of X(2l + 1, −k − \frac{3}{2}d − \frac{1}{2}))

+ (2 − ω) · (row (2i + 2d + 1) of X(2l + 1, −k − \frac{3}{2}d − \frac{1}{2}))

− ω · (row (2i + 2d + 2) of X(2l + 1, −k − \frac{3}{2}d − \frac{1}{2}))) = 0. (11.13)

Restricted to the (2j)th column, the left-hand side of this equation becomes, after a little simplification,

(1 − 2ω) ∑_{i=0}^{k−1} \binom{k − 1}{i} (\binom{i − d/2 + j − k + 1/2}{2j − i − d − 1} + \binom{i − d/2 + j − k − 1/2}{2j − i − d − 1}) .

(11.14)

Again, this expression vanishes trivially for k = 1. If k > 1, after reversion of summation, the hypergeometric form of (11.14) is

(−1)^{k} \frac{(1 − k) (1 + d − 2j)_{−1+k}}{(2j − d − 1)! (−\frac{1}{2} − \frac{d}{2} + j)_{1+d−2j+k}}

×_{4}F_{3}[\begin{matrix}1 − k, \frac{4}{3} − \frac{k}{3}, \frac{1}{4} − \frac{d}{4} + \frac{j}{2} − \frac{k}{2}, \frac{3}{4} − \frac{d}{4} + \frac{j}{2} − \frac{k}{2} \\ \frac{1}{3} − \frac{k}{3}, \frac{3}{2} + \frac{d}{2} − j, 1 − d + 2j − k \end{matrix}; 4] . (11.15)

Now we use (11.5) with A = 1 − k, F = 1/2 − d/2 + j − k, n = j − d/2 − 1/2. Together with the remarks accompanying (11.5), this implies immediately that the _{4}F_{3}-series in (11.15) vanishes for k > 1.

On the other hand, restricted to the (2j + 1)th column, the left-hand side of (11.13) becomes, after a little simplification,

(ω − 1) ∑_{i=0}^{k−1} \binom{k − 1}{i} (\binom{i − d/2 + j − k + 1/2}{2j − i − d − 1} + \binom{i − d/2 + j − k − 1/2}{2j − i − d − 1})

+ ∑_{i=0}^{k−1} \binom{k − 1}{i} (\binom{i − d/2 + j − k + 3/2}{2j − i − d + 1} + \binom{i − d/2 + j − k + 1/2}{2j − i − d + 1}) . (11.16)

It was already shown just before that the first sum in (11.16) vanishes (compare (11.14)). The second sum certainly vanishes for k = 1. To see that it vanishes for k > 1 as well, we reverse the order of summation and then convert the sum into hypergeometric notation,

(−1)^{k} \frac{(1 − k) (−1 + d − 2j)_{−1+k}}{(2j − d + 1)! (\frac{1}{2} − \frac{d}{2} + j)_{−1+d−2j+k}}

×_{4}F_{3}[\begin{matrix}1 − k, \frac{4}{3} − \frac{k}{3}, \frac{3}{4} − \frac{d}{4} + \frac{j}{2} − \frac{k}{2}, \frac{5}{4} − \frac{d}{4} + \frac{j}{2} − \frac{k}{2} \\ \frac{1}{3} − \frac{k}{3}, \frac{1}{2} + \frac{d}{2} − j, 3 − d + 2j − k \end{matrix}; 4] . (11.17)

Again, by (11.5), this time with A = 1 − k, F = 3/2 − d/2 + j − k, n = j − d/2 + 1/2, together with the remarks accompanying (11.5), it follows immediately that the _{4}F_{3}- series in (11.17) vanishes for k > 1. Thus, equation (11.13) is established.

The linear combinations of Steps 3 and 4 are independent by the argument used at the end of Step 2.

Step 5. Determination of the degree of det X(2l + 1, m/2) as a polynomial in m. The (i, j)-entry of X(2l + 1, m/2), viewed as polynomial in m, has the degree j − ⌊i/2⌋. Therefore, the determinant of X(2l + 1, m/2) has degree at most

∑_{j=0}^{2l} j − ∑_{i=0}^{2l} ⌊\frac{i}{2}⌋ = l(l + 1) = \frac{a^{2} − 1}{4}

as a polynomial in m.

Step 6. Computation of the multiplicative constant. It suffices to compute the leading coefficient of the determinant det X(2l + 1, m/2) as a polynomial in m/2. This leading coefficient can be computed as the determinant of the leading coefficients of the individual entries. In fact, we already did such a computation at the end of the proof of Theorem 12 in the preceding section, with ω a primitive third root of unity instead of

a  b + m  } c c + m {  b  a + m } m  } {  } {  a  b + m  } c c + m {  b  a + m } m  } {  } { a. Removal of the triangle which is  b. Removal of the triangle which is off-center by one “unit”  off-center by 3/2 “units”

Figure 13

a primitive sixth root of unity. However, since ω was treated there as an indeterminate, everything can be used here as well. Thus we obtain the expression (10.7), with ω a primitive sixth root of unity. It is then routine to check that for a = 2l + 1 the right-hand side of (3.5) has the same leading coefficient as a polynomial in m/2. □

12. Comments and open problems

1) Conjectured further enumeration results. There is overwhelming evidence (through computer supported empirical calculations) that there are also “nice” formulas for the number of lozenge tilings of a cored hexagon for at least two further locations of the core.

First, let a, b and c have the same parity, and consider a hexagon with side lengths a, b+m, c, a+m, b, c+m from which an equilateral triangle of side length m is removed which is off-center by “one unit”. To be more precise, let again s_{a} be the side of the triangle which is parallel to the borders of the hexagon of lengths a and a + m, and similarly for s_{b} and s_{c}. Then the distance of s_{a} to the border of length a + m is the same as the distance of the vertex of the triangle opposite to s_{a} to the border of length a. The distance of s_{b} to the border of length b + m exceeds the distance of the vertex of the triangle opposite to s_{b} to the border of length b by two units. Finally, the distance of s_{c} to the border of length c + m is two units less than the distance of the vertex of the triangle opposite to s_{c} to the border of length c. See Figure 13.a for an example. Then the following seems to be true.

Conjecture 1. Let a, b, c, m be nonnegative integers, a, b, c having the same parity. The number of lozenge tilings of a hexagon with sides a, b + m, c, a + m, b, c + m, with an equilateral triangle of side length m removed from the position that was described above (see Figure 13.a), equals

\frac{1}{4} \frac{H(a + m) H(b + m) H(c + m) H(a + b + c + m)}{H(a + b + m) H(a + c + m) H(b + c + m)}

× \frac{H(m + ⌈\frac{a+b+c}{2}⌉) H(m + ⌊\frac{a+b+c}{2}⌋)}{H(\frac{a+b}{2} + m + 1) H(\frac{a+c}{2} + m − 1) H(\frac{b+c}{2} + m)}

× \frac{H(⌈\frac{a}{2}⌉) H(⌈\frac{b}{2}⌉) H(⌈\frac{c}{2}⌉) H(⌊\frac{a}{2}⌋) H(⌊\frac{b}{2}⌋) H(⌊\frac{c}{2}⌋)}{H(\frac{m}{2} + ⌈\frac{a}{2}⌉) H(\frac{m}{2} + ⌈\frac{b}{2}⌉) H(\frac{m}{2} + ⌈\frac{c}{2}⌉) H(\frac{m}{2} + ⌊\frac{a}{2}⌋) H(\frac{m}{2} + ⌊\frac{b}{2}⌋) H(\frac{m}{2} + ⌊\frac{c}{2}⌋)}

× \frac{H(\frac{m}{2})^{2} H(\frac{a+b+m}{2})^{2} H(\frac{a+c+m}{2})^{2} H(\frac{b+c+m}{2})^{2}}{H(\frac{m}{2} + ⌈\frac{a+b+c}{2}⌉) H(\frac{m}{2} + ⌊\frac{a+b+c}{2}⌋) H(\frac{a+b}{2} − 1) H(\frac{a+c}{2} + 1) H(\frac{b+c}{2})}P_{1}(a, b, c, m), (12.1)

where P_{1}(a, b, c, m) is the polynomial given by

P_{1}(a, b, c, m) = \begin{cases}(a + b)(a + c) + 2am & if a is even, \\ (a + b)(a + c) + 2(a + b + c + m)m & if a is odd. \end{cases}

The reader should notice that the only differences between formulas (12.1) and (1.2) are in some hyperfactorials involving (a + b)/2 and (a + c)/2, in the polynomial P_{1}(a, b, c, m), which does not appear in (1.2), and in the factor 1/4 in front of (12.1).

The second case needs a to have a parity different from b and c. Consider a hexagon with side lengths a, b + m, c, a + m, b, c + m from which an equilateral triangle of side length m is removed which is off-center by “3/2 units”. To be more precise, with s_{a}, s_{b}, s_{c} the sides of the triangle as above, the distance of s_{a} to the border of length a + m is the same as the distance of the vertex of the triangle opposite to s_{a} to the border of length a, the distance of s_{b} to the border of length b + m exceeds the distance of the vertex of the triangle opposite to s_{b} to the border of length b by three units, and the distance of s_{c} to the border of length c + m is three units less than the distance of the vertex of the triangle opposite to s_{c} to the border of length c. See Figure 13.b for an example. Then the following seems to be true. Conjecture 2. Let a, b, c, m be nonnegative integers, a of parity different from the parity of b and c. The number of lozenge tilings of a hexagon with sides a, b+m, c, a+m, b, c+m, with an equilateral triangle of side length m removed from the position that was described above (see Figure 13.b), equals

\frac{1}{16} \begin{matrix}H & (a + m) & H & (b + m) & H & (c + m) & H & (a + b + c + m) \\ H & (a + b + m) & H & (a + c + m) & H & (b + c + m) \end{matrix}

× H (\frac{m}{2})^{2} H (⌈\frac{a}{2}⌉) H (⌈\frac{b}{2}⌉) H (⌈\frac{c}{2}⌉) H (⌊\frac{a}{2}⌋) H (⌊\frac{b}{2}⌋) H (⌊\frac{c}{2}⌋) ; H (\frac{m}{2} + ⌈\frac{a}{2}⌉) H (\frac{m}{2} + ⌈\frac{b}{2}⌉) H (\frac{m}{2} + ⌈\frac{c}{2}⌉) H (\frac{m}{2} + ⌊\frac{a}{2}⌋) H (\frac{m}{2} + ⌊\frac{b}{2}⌋) H (\frac{m}{2} + ⌊\frac{c}{2}⌋)

× H (⌈\frac{a+b}{2}⌉ + \frac{m}{2}) H (⌊\frac{a+b}{2}⌋ + \frac{m}{2}) H (⌊\frac{a+c}{2}⌋ + \frac{m}{2}) H (⌈\frac{a+c}{2}⌉ + \frac{m}{2}) H (\frac{b+c}{2} + \frac{m}{2})^{2} ; H (\frac{m}{2} + ⌈\frac{a+b+c}{2}⌉) H (\frac{m}{2} + ⌊\frac{a+b+c}{2}⌋) H (⌊\frac{a+b}{2}⌋ − 1) H (⌈\frac{a+c}{2}⌉ + 1) H (\frac{b+c}{2})

× \begin{matrix}H & (m + ⌈\frac{a+b+c}{2}⌉) & H & (m + ⌊\frac{a+b+c}{2}⌋) \\ H & (⌊\frac{a+c}{2}⌋ + m − 1) & H & (\frac{b+c}{2} + m) & H & (⌈\frac{a+b}{2}⌉ + m + 1) \end{matrix}P_{2}(a, b, c, m), (12.2)

where the polynomial P_{2}(a, b, c, m) is given by

P_{2}(a, b, c, m) = \begin{cases}((a + b)^{2} − 1)((a + c)^{2} − 1) + 4am(a^{2} + 2ab + b^{2} + 2ac + 3bc + c^{2} \\ +2am + 3bm + 3cm + 2m^{2} − 1) & if a is even, \\ ((a + b)^{2} − 1)((a + c)^{2} − 1) + 4(a + b + c + m)m(a^{2} + bc − 1) \\ if a is odd. \end{cases}

Again, the reader should notice that the only differences between formulas (12.2) and (1.3) are in some hyperfactorials involving (a + b)/2 and (a + c)/2, in the polynomial P_{2}(a, b, c, m), which does not appear in (1.3), and in the factor 1/16 in front of (12.2).

Conjectured results about the (−1)-enumeration of the above two families of lozenge tilings could be easily worked out as well, and would have similar appearance, i.e., the result would be a quotient of products of many “nice” factors times an irreducible polynomial of small degree. However, if one moves the triangle farther away from the center, then, for both ordinary and (−1)-enumeration, the irreducible polynomial factor seems to grow rather quickly in degree, and is therefore difficult to predict in general.

For a proof of Conjectures 1 and 2, one might go through considerations analogous to those in Section 5, i.e., convert the lozenge tilings into families of nonintersecting lattice paths, and, by means of the Lindström–Gessel–Viennot theorem (Lemma 14), obtain a determinant for the number of lozenge tilings. This determinant, which then must be evaluated, is

det_{1≤i,j≤a+m} (\begin{matrix}\binom{b + c + m}{b − i + j} & 1 ≤ i ≤ a \\ \binom{\frac{b+c}{2}}{\frac{b+a}{2} − i + j + ε} & a + 1 ≤ i ≤ a + m \end{matrix}) ,  (12.3)

with ε = 1 and ε = 3/2, respectively. (The determinants in Lemmas 15 and 16 are the respective special cases ε = 0 and ε = 1/2 of (12.3).)

2) A multidimensional analogue of Watson’s _{3}F_{2}-summation, and some variants. There is another possible way to approach the evaluation of the determinants in Lemmas 15 and 16. This approach consists of applying Laplace expansion to these determinants. More precisely, we write an (a + m) × (a + m) determinant (such as the determinant in Lemma 15 or 16) as a (signed) sum of products of a minor formed of elements of the first a rows times the complementary minor formed of elements of the last m rows. That is, given an (a + m) × (a + m) matrix M, we write

det M = ∑_{K}(−1)^{s(K)} (det M^{K}) (det M_{K′}) ,  (12.4)

where the sum is over all a-element subsets K of {1, 2, …, a + m}, where s(K) = ∑_{k∈K} k − \binom{a+1}{2}, M^{K} denotes the submatrix of M determined by the first a rows and the columns with indices in K, K′ denotes the complement of K in {1, 2, …, a + m}, and M_{K′} denotes the submatrix of M determined by the last m rows and the columns with indices in K′.

The gain in applying (12.4) to our determinants in Lemmas 15 and 16 is that the entries of the resulting minors which then appear on the right-hand side of (12.4) have now a uniform definition (in contrast to the original determinants), and can in fact easily be evaluated in closed form, by means of the determinant evaluation

det_{1≤i,j≤n} ((\begin{matrix}A \\ L_{j} − i \end{matrix})) = \frac{∏_{1≤i<j≤n}(L_{j} − L_{i})}{∏_{i=1}^{n}(A − L_{i} + n)!} \frac{∏_{i=1}^{n}(A + i − 1)!}{∏_{i=1}^{n}(L_{i} − 1)!}.  (12.5)

(This determinant evaluation is easily proved, e.g., by means of a general determinant lemma from [17, Lemma 2.2]; see also [20, Sec. 2.2 and (3.12)]). Thus, on the right-hand side of (12.4) we obtain a multiple (hypergeometric) series for our determinants. If an evaluation of this multiple sum would appear in the existing literature, then we would be immediately done. Unfortunately, this does not seem to be the case. On the other hand, we did evaluate the determinants in Sections 7 and 8. Thus, comparison of the results with the right-hand side in (12.4) establishes summation theorems for multiple hypergeometric series. The summation theorem that results, after some replacement of parameters, from the evaluations in Section 7 of the determinant in Lemma 15 is the following. Theorem 27. Let a be a positive integer and M be a nonnegative integer. The multiple series

∑_{0≤k_{1}<k_{2}<···<k_{a}} ∏_{1≤i<j≤a}(k_{i} − k_{j})^{2} ∏_{i=1}^{a} \frac{(−M)_{k_{i}} (C)_{k_{i}} (B)_{k_{i}}}{k_{i}! (\frac{a}{2} − \frac{M}{2} + \frac{C}{2} )_{k_{i}} (2B + a − 1)_{k_{i}}}  (12.6)

equals

(−1)^{a/2}2^{a^{2}−a−aM} \frac{M!^{a} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2}^{a}}

× ∏_{i=1}^{a/2} \frac{(i − 1)!^{2} (\frac{1}{2} + \frac{C}{2} )_{i−1}^{2} (B − \frac{C}{2} + i − 1)_{M/2−a/2+1} (B − \frac{C}{2} + i)_{M/2−a/2}}{(\frac{M}{2} − i)! (\frac{M}{2} − i + 1)! (\frac{a}{2} + B − \frac{1}{2})_{M/2−i+1}^{2} (\frac{a}{2} + B)_{i−1}^{2} (1 + \frac{C}{2} − i + \frac{M}{2} )_{2i−1}} (12.7)

if a and M are even, it equals

(−1)^{a/2}2^{a^{2}−a−aM} \frac{M!^{a} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2+1/2}^{a}} ∏_{i=1}^{a/2} \begin{matrix}(i − 1)! & 2 \\ (\frac{M}{2} − i + \frac{1}{2})! & 2 \end{matrix}

× ∏_{i=1}^{a/2} \begin{matrix}(\frac{C}{2} )i−1 & (\frac{C}{2} )i & (B − \frac{C}{2} + i − \frac{1}{2})_{M/2−a/2+1/2}^{2} \\ (\frac{a}{2} + B − \frac{1}{2}) & M/2−i+1/2 & (\frac{a}{2} + B − \frac{1}{2}) & M/2−i+3/2 & (\frac{a}{2} + B)_{i−1}^{2} & (1 + \frac{C}{2} − i + \frac{M}{2} ) & 2i−1 \end{matrix} (12.8)

if a is even and M is odd, it equals

(−1)^{M/2}2^{a^{2}−a−aM} \frac{M!^{a} (B − \frac{C}{2} + \frac{a}{2})_{M/2−a/2+1/2} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{M}{2} )! (\frac{a}{2} + B)_{M/2} (\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2+1/2}^{a}}

× ∏_{i=1}^{(a−1)/2} \begin{matrix}(i − 1)! & i! & (\frac{C}{2} ){2 \atop i} & (B − \frac{C}{2} + i − \frac{1}{2})_{M/2−a/2+1/2}^{2} \\ (\frac{M}{2} − i)!^{2} & (\frac{a}{2} + B − \frac{1}{2})_{i}^{2} & (\frac{a}{2} + B)_{M/2−i}^{2} & (\frac{1}{2} + \frac{C}{2} − i + \frac{M}{2} ) & 2i \end{matrix} (12.9)

if a is odd and M is even, and it vanishes if both a and M are odd.

There are two interesting features of this summation theorem to be observed. First, if we set a = 1, the theorem reduces to a terminating case of Watson’s _{3}F_{2}-summation (see [36, (2.3.3.13); Appendix (III.23)]),

3F_{2}[\begin{matrix}A, C, B \\ \frac{1+A+C}{2} , 2B \end{matrix}; 1] = \frac{Γ (\frac{1}{2}) Γ (\frac{1}{2} + B) Γ (\frac{1}{2} + \frac{A}{2} + \frac{C}{2} ) Γ (\frac{1}{2} − \frac{A}{2} − \frac{C}{2} + B)}{Γ (\frac{1}{2} + \frac{A}{2}) Γ (\frac{1}{2} + \frac{C}{2} ) Γ (\frac{1}{2} − \frac{A}{2} + B) Γ (\frac{1}{2} − \frac{C}{2} + B)},

which is a summation formula which is not so often met. Second, however, the above theorem is an unusual multidimensional analogue of Watson’s _{3}F_{2}-summation, because of the term ∏_{1≤i<j≤a}(k_{i}−k_{j})^{2} appearing in the summand. Whereas for series containing a term like ∏_{1≤i<j≤a}(k_{i} − k_{j}) (i.e., the same term, but without the square) there is now an extensive theory of summation and transformation formulas (such a series is called a hypergeometric series in U(a) or an A_{a} hypergeometric series), mainly thanks to Milne and Gustafson (see for example [14, 29, 30, 31, 35], and the references contained therein), it is only occasionally that series containing the square ∏_{1≤i<j≤a}(k_{i} − k_{j})^{2} appear. Most of the time, they arise from series featuring Schur functions (see [21, Theorem 6] for such an example). However, our Theorem 27 does not seem to extend to a “Schur function theorem.”

The summation theorem that results from the evaluations in Section 8 of the determinant in Lemma 16 is a variant of the preceding theorem.

Theorem 28. Let a be a positive integer and M be a nonnegative integer. The multiple series

∑_{0≤k_{1}<k_{2}<···<k_{a}} ∏_{1≤i<j≤a}(k_{i} − k_{j})^{2} ∏_{i=1}^{a} \frac{(−M)_{k_{i}} (C)_{k_{i}} (B)_{k_{i}}}{k_{i}! (\frac{a}{2} − \frac{M}{2} + \frac{C}{2} + \frac{1}{2})_{k_{i}} (2B + a − 2)_{k_{i}}}  (12.10)

equals

(−1)^{a/2} 2^{a^{2}−a−aM} \frac{M!^{a} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{1}{2} + \frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2}^{a}}

× ∏_{i=1}^{a/2} \frac{(i − 1)!^{2} (\frac{C}{2} )_{i−1} (\frac{C}{2} )_{i}}{(\frac{M}{2} − i)! (\frac{M}{2} − i + 1)! (\frac{a}{2} + B − 1)_{i−1} (\frac{a}{2} + B − 1)_{i}}

× ∏_{i=1}^{a/2} \begin{matrix}(B − \frac{C}{2} + i − \frac{3}{2}) & M/2−a/2+1 & (B − \frac{C}{2} + i − \frac{1}{2}) & M/2−a/2 \\ (\frac{a}{2} + B − \frac{1}{2}) & M/2−i & (\frac{a}{2} + B − \frac{1}{2}) & M/2−i+1 & (\frac{1}{2} + \frac{C}{2} − i + \frac{M}{2} ) & 2i \end{matrix} (12.11)

if a and M are even, it equals

(−1)^{a/2} 2^{a^{2}−a−aM} \frac{M!^{a} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{1}{2} + \frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2−1/2}^{a}} ∏_{i=1}^{a/2} \begin{matrix}(i − 1)! & 2 \\ (\frac{M}{2} − i + \frac{1}{2})! & 2 \end{matrix}

× ∏_{i=1}^{a/2} \begin{matrix}(\frac{1}{2} + \frac{C}{2} )_{i−1}^{2} & (B − \frac{C}{2} + i − 1)_{M/2−a/2+1/2}^{2} \\ (\frac{a}{2} + B − 1) & i−1 & (\frac{a}{2} + B − 1) & i & (\frac{a}{2} + B − \frac{1}{2})_{M/2−i+1/2}^{2} & (\frac{1}{2} + \frac{C}{2} − i + \frac{M}{2} ) & 2i \end{matrix} (12.12)

if a is even and M is odd, it equals

(−1)^{M/2} 2^{a^{2}−a−aM} \frac{M!^{a} (B − \frac{C}{2} + \frac{a}{2} − \frac{1}{2})_{M/2−a/2+1/2}}{(\frac{C}{2} + \frac{M}{2} ) (\frac{M}{2} )! (\frac{a}{2} + B − 1)_{M/2−a/2+1/2}}

× \frac{∏_{i=1}^{a}(B)_{i−1}}{(\frac{1}{2} + \frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2−1/2}^{a}} ∏_{i=1}^{(a−1)/2} \frac{(i − 1)! i! (\frac{1}{2} + \frac{C}{2} )_{i−1} (\frac{1}{2} + \frac{C}{2} )_{i}}{(\frac{M}{2} − i)!^{2} (\frac{a}{2} + B − 1)_{M/2−i+1}^{2}}

× ∏_{i=1}^{(a−1)/2} \begin{matrix}(B − \frac{C}{2} + i − 1) & {2 \atop M/2−a/2+1/2} \\ (\frac{a}{2} + B − \frac{1}{2}) & i−1 & (\frac{a}{2} + B − \frac{1}{2}) & i & (\frac{C}{2} − i + \frac{M}{2} ) & 2i+1 \end{matrix} (12.13)

if a is odd and M is even, and it equals

(−1)^{M/2−1/2} 2^{a^{2}−a−aM} \frac{M!^{a} (B − \frac{C}{2} − \frac{1}{2})_{M/2−a/2+1}}{(\frac{C}{2} + \frac{M}{2} ) (\frac{M}{2} − \frac{a}{2})! (\frac{a}{2} + B − 1)_{M/2+1/2}}

× \frac{∏_{i=1}^{a}(B)_{i−1}}{(\frac{1}{2} + \frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2}^{a}} ∏_{i=1}^{(a−1)/2} \frac{(i − 1)! i! (\frac{C}{2} )_{i}^{2}}{(\frac{M}{2} − i + \frac{1}{2})!^{2} (\frac{a}{2} + B − 1)_{M/2−i+1/2}^{2}}

× ∏_{i=1}^{(a−1)/2} \begin{matrix}(B − \frac{C}{2} + i − \frac{1}{2}) & M/2−a/2 & (B − \frac{C}{2} + i − \frac{1}{2}) & M/2−a/2+1 \\ (\frac{a}{2} + B − \frac{1}{2}) & i−1 & (\frac{a}{2} + B − \frac{1}{2}) & i & (\frac{C}{2} − i + \frac{M}{2} ) & 2i+1 \end{matrix} (12.14)

if both a and M are odd.

In fact, the evaluations in Section 8 of the determinant in Lemma 16 establish even a further variant of Theorem 27. This variant is obtained as follows. Recall (see the Introduction) that the determinant in Lemma 16 arose from the case when the parity of a was different from that of b and c, so that, in order to have a well-defined enumeration problem, we had to adjust the definition of a “central” triangle of the hexagon. What we did was to shift the really central triangle by half a unit in parallel to the sides of the hexagon of length a and a + m. Now let us suppose that, unlike in that case, it is b that has parity different from that of a and c, so that the “central” triangle in the sense of the Introduction is the really central triangle shifted by half a unit in parallel to the sides of the hexagon of length b and b + m. Clearly, our enumeration results in Theorems 2 and 5 can be still used, we just have to interchange the roles of a and b. On the other hand, if we go through the considerations in Section 5 (without interchange of the roles of a and b, i.e., starting and end points of the lattice paths are chosen on the sides of the hexagon of length a and a + m and on the side of the triangle which is parallel), then we obtain a certain determinant, which differs slightly from the determinants in Lemmas 15 and 16. Comparison of the enumeration results with Laplace expansion (12.4) of the determinant establishes the following summation theorem. Theorem 29. Let a be a positive integer and M be a nonnegative integer. The multiple series

∑_{0≤k_{1}<k_{2}<···<k_{a}} ∏_{1≤i<j≤a}(k_{i} − k_{j})^{2} ∏_{i=1}^{a} \frac{(−M)_{k_{i}} (C)_{k_{i}} (B)_{k_{i}}}{k_{i}! (\frac{a}{2} − \frac{M}{2} + \frac{C}{2} )_{k_{i}} (2B + a − 2)_{k_{i}}}  (12.15)

equals

(−1)^{a/2} 2^{a^{2}−a−aM} \frac{M!^{a} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{a}{2} + B − 1)_{a/2} (\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2}^{a}} ∏_{i=1}^{a/2} \frac{(i − 1)!^{2}}{(\frac{M}{2} − i)! (\frac{M}{2} − i + 1)!}

× ∏_{i=1}^{a/2} \begin{matrix}(\frac{1}{2} + \frac{C}{2} )_{i−1}^{2} & (B − \frac{C}{2} + i − 1) & M/2−a/2 & (B − \frac{C}{2} + i − 1) & M/2−a/2+1 \\ (\frac{a}{2} + B − 1)_{i−1}^{2} & (\frac{a}{2} + B − \frac{1}{2}) & M/2−i & (\frac{a}{2} + B − \frac{1}{2}) & M/2−i+1 & (1 + \frac{C}{2} − i + \frac{M}{2} ) & 2i−1 \end{matrix} (12.16)

if a and M are even, it equals

(−1)^{a/2} 2^{a^{2}−a−aM} \frac{M!^{a} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2+1/2}^{a}} ∏_{i=1}^{a/2} \begin{matrix}(i − 1)! & 2 \\ (\frac{M}{2} − i + \frac{1}{2})! & 2 \end{matrix}

× ∏_{i=1}^{a/2} \begin{matrix}(\frac{C}{2} ) & i−1 & (\frac{C}{2} ) & i & (B − \frac{C}{2} + i − \frac{3}{2}) & M/2−a/2+1/2 & (B − \frac{C}{2} + i − \frac{1}{2}) & M/2−a/2+1/2 \\ (\frac{a}{2} + B − 1) & i−1 & (\frac{a}{2} + B − 1) & i & (\frac{a}{2} + B − \frac{1}{2})_{M/2−i+1/2}^{2} & (1 + \frac{C}{2} − i + \frac{M}{2} ) & 2i−1 \end{matrix} (12.17)

if a is even and M is odd, it equals

(−1)^{M/2} 2^{a^{2}−a−aM} \frac{M!^{a} (B − \frac{C}{2} − \frac{1}{2})_{M/2−a/2+1/2} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{M}{2} )! (\frac{a}{2} + B − 1)_{M/2−a/2+1/2} (\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2+1/2}^{a}}

× ∏_{i=1}^{(a−1)/2} \frac{(i − 1)! i! (\frac{C}{2} )_{i}^{2}}{(\frac{M}{2} − i)!^{2} (\frac{a}{2} + B − 1)_{M/2−i+1}^{2}}

× ∏_{i=1}^{(a−1)/2} \begin{matrix}(B − \frac{C}{2} + i − \frac{1}{2}) & {2 \atop M/2−a/2+1/2} \\ (\frac{a}{2} + B − \frac{1}{2}) & i−1 & (\frac{a}{2} + B − \frac{1}{2}) & i & (\frac{1}{2} + \frac{C}{2} − i + \frac{M}{2} ) & 2i \end{matrix} (12.18)

if a is odd and M is even, and it equals

(−1)^{M/2+1/2} 2^{a^{2}−a−aM} \frac{M!^{a} (B − \frac{C}{2} + \frac{a}{2} − \frac{1}{2})_{M/2−a/2} ∏_{i=1}^{a}(B)_{i−1}}{(\frac{M}{2} − \frac{a}{2})! (\frac{a}{2} + B − 1)_{M/2+1/2} (\frac{a}{2} + \frac{C}{2} − \frac{M}{2} )_{M/2−a/2}^{a}}

× ∏_{i=1}^{(a−1)/2} \frac{(i − 1)! i! (\frac{1}{2} + \frac{C}{2} )_{i−1} (\frac{1}{2} + \frac{C}{2} )_{i}}{(\frac{M}{2} − i + \frac{1}{2})!^{2} (\frac{a}{2} + B − 1)_{M/2−i+1/2}^{2}}

× ∏_{i=1}^{(a−1)/2} \begin{matrix}(B − \frac{C}{2} + i − 1) & M/2−a/2 & (B − \frac{C}{2} + i − 1) & M/2−a/2+1 \\ (\frac{a}{2} + B − \frac{1}{2}) & i−1 & (\frac{a}{2} + B − \frac{1}{2}) & i & (\frac{1}{2} + \frac{C}{2} − i + \frac{M}{2} ) & 2i \end{matrix} (12.19)

if both a and M are odd.

The reader should observe that, by similar considerations, i.e., by applying Laplace expansion (12.4) to (12.3), Conjectures 1 and 2 are equivalent to further variations of Theorem 27. To be precise, Conjectures 1 and 2 could be proved by establishing summation theorems for the multiple series

∑_{0≤k_{1}<k_{2}<···<k_{a}} ∏_{1≤i<j≤a}(k_{i} − k_{j})^{2} ∏_{i=1}^{a} \frac{(−M)_{k_{i}} (C)_{k_{i}} (B)_{k_{i}}}{k_{i}! (\frac{a}{2} − \frac{M}{2} + \frac{C}{2} + ε)_{k_{i}} (2B + a − 1 − 2ε)_{k_{i}}} , (12.20)

with ε = 1 and ε = 3/2, respectively.

3) Are there q-analogues of our results? By “q-analogue”, we mean, as usual, that objects x are counted with respect to a weight q^{w(x)}, where w(x) is some statistic defined on the objects. The question of whether there is a q-analogue, say of Theorems 1 and 2, is motivated by two facts: In the case of m = 0 of Theorems 1 and 2, i.e., if one counts lozenge tilings of a hexagon with no triangle removed, or, equivalently, plane partitions contained in a given box, there is a well-known q-analogue due to MacMahon [26, Sec. 429; proof in Sec. 494], in which every plane partition P is given the weight q^{|P |}, where |P | denotes the number of “boxes” (points, according to our definition of plane partitions in Section 3) of P. The result is the q-analogue of formula (1.1) which is obtained by replacing all factorials in (1.1) by the respective q-factorials. Similarly, in the case m = 1, q-analogues of Theorems 1 and 2 can be gleaned from [32, Theorem 3], by setting x_{i} = q^{i}, i = 1, 2, …, n + 1, respectively x_{i} = q^{i}, i = 1, 2, …, n, x_{n+1} = 0, and using the hook-content formula for the principal specialization of Schur functions (see [25, I, Sec. 3, Ex. 1], [9, Ex. A.30, (ii)]). The question of whether there are q-analogues for arbitrary m remains open. Furthermore, it would be particularly interesting if there were a q-analogue of Theorem 10 that would specialize for m = 0 to the the statement of the Macdonald (ex)conjecture on cyclically symmetric plane partitions (cf. [27]).

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Math. and its Applications, Vol. 2, Addison–Wesley, Reading, 1976.

[2] G. E. Andrews, Plane partitions (III): The weak Macdonald conjecture, Invent. Math. 53 (1979), 193–225.

[3] W. N. Bailey, Generalized hypergeometric series, Cambridge University Press, Cambridge, 1935.

[4] M. Ciucu, Enumeration of lozenge tilings of punctured hexagons, J. Combin. Theory Ser. A 83 (1998), 268–272.

[5] M. Ciucu, Plane partitions I: A generalization of MacMahon’s formula, preprint, math/9808017.

[6] M. Ciucu and C. Krattenthaler, Plane partitions II: 5\frac{1}{2} symmetry classes, in: Combinatorial Methods in Representation Theory, M. Kashiwara, K. Koike, S. Okada, I. Terada, H. Yamada, eds., Advanced Study in Pure Mathematics, RIMS, Kyoto (to appear); math/9808018.

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

[8] I. Fischer, Enumeration of rhombus tilings of a hexagon which contain a fixed rhombus in the centre, preprint, math/9906102.

[9] W. Fulton and J. Harris, Representation Theory, Springer–Verlag, New York, 1991.

[10] G. Gasper and M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, Cambridge, 1990.

[11] G. Gasper and M. Rahman, An indefinite bibasic summation formula and some quadratic, cubic and quartic summation and transformation formulae, Can. J. Math. 42 (1990), 1–27.

[12] I. M. Gessel and D. Stanton, Strange evaluations of hypergeometric series, SIAM J. Math. Anal. 13 (1982), 295–308.

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

[14] R. A. Gustafson, The Macdonald identities for affine root systems of classical type and hypergeometric series very-well-poised on semisimple Lie algebras, Ramanujan International Symposium on Analysis (Dec. 26th to 28th, 1987, Pune, India), N. K. Thakare, ed., 1989, 187–224.

[15] H. Helfgott and I. M. Gessel, Exact enumeration of tilings of diamonds and hexagons with defects, Electron. J. Combin. 6 (1) (1999), #R16, 26 pp.

[16] W. Jockusch, Perfect matchings and perfect squares, J. Combin. Theory Ser. A 67 (1994), 100–115.

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

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

[19] C. Krattenthaler, An alternative evaluation of the Andrews–Burge determinant, in: Mathematical Essays in Honor of Gian-Carlo Rota, B. E. Sagan, R. P. Stanley, eds., Progress in Math., vol. 161, Birkhäuser, Boston, 1998, pp. 263–270.

[20] C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (“The Andrews Festschrift”) (1999), paper B42q, 67 pp.

[21] C. Krattenthaler, Schur function identities and the number of perfect matchings of holey Aztec rectangles, Contemporary Math. (to appear).

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

[23] G. Kuperberg, An exploration of the permanent-determinant method, Electron. J. Combin. 5 (1998), #R46, 34 pp.

[24] B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

[25] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford University Press, New York/London, 1995.

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

[27] W. H. Mills, D. H. Robbins and H. Rumsey, Proof of the Macdonald conjecture, Invent. Math. 66 (1982), 73–87.

[28] W. H. Mills, D. H. Robbins and H. Rumsey, Enumeration of a symmetry class of plane partitions, Discrete Math. 67 (1987), 43–55.

[29] S. C. Milne, q-analog of a Whipple’s transformation for hypergeometric series in U(n), Adv. in Math. 108 (1994), 1–76.

[30] S. C. Milne and G. M. Lilly, Consequences of the A_{l} and C_{l} Bailey transform and Bailey lemma, Discrete Math. 139 (1995), 319–346.

[31] S. C. Milne and J. W. Newcomb, U(n) very-well-poised _{10}ϕ_{9} transformations, J. Comput. Appl. Math. 68 (1996), 239–285.

[32] S. Okada and C. Krattenthaler, The number of rhombus tilings of a “punctured” hexagon and the minor summation formula, Adv. Appl. Math. 21 (1998), 381–404.

[33] J. Propp, Twenty open problems on enumeration of matchings, manuscript, 1996, math/9801060.

[34] J. Propp, Enumeration of matchings: Problems and progress, in: ”New Perspectives in Algebraic Combinatorics,” L. Billera, A. Björner, C. Greene, R. Simion, and R. P. Stanley, eds., Mathematical Sciences Research Institute Publications, vol. 38, Cambridge University Press, Cambridge, 1999, pp. 255–291.

[35] M. Schlosser, Multidimensional matrix inversion and A_{r} and D_{r} basic hypergeometric series, The Ramanujan J. 1 (1997), 243–276.

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

[37] R. P. Stanley, Symmetries of plane partitions, J. Combin. Theory A 43 (1986), 103–113; Erratum: ibd. 44 (1987), 310.

[38] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998.

[39] J. R. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A 68 (1994), 372–409.

[40] J. R. Stembridge, On minuscule representations, plane partitions and involutions in complex Lie groups, Duke Math. J. 73 (1994), 469–490.

[41] J. R. Stembridge, Strange enumerations of CSPP’s and TSPP’s, unpublished manuscript, 1993,

    available at http://www.math.lsa.umich.edu/~jrs/other.html.

[42] R. A. Sulanke, A determinant for q-counting lattice paths, Discrete Math. 81 (1990), 91–96.

[43] J. Thomae, Über die Funktionen, welche durch Reihen von der Form dargestellt werden: …, J. für Math. (Crelle) 87 (1879), 26–73.

Department of Mathematics, Georgia Institute of Technology.

E-mail: ciucu@math.gatech.edu, WWW: http://www.math.gatech.edu/~ciucu

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Aus-

tria. E-mail: teisenko@radon.mat.univie.ac.at, KRATT@Pap.Univie.Ac.At
WWW: http://radon.mat.univie.ac.at/People/kratt

Department of Mathematics, Columbia University, New York, NY 10027.

E-mail: zare@math.columbia.edu, WWW: http://www.math.columbia.edu/~zare