ENUMERATION OF LOZENGE TILINGS OF

HEXAGONS WITH CUT OFF CORNERS

Mihai Ciucu and Christian Krattenthaler

Georgia Institute of Technology School of Mathematics Atlanta, GA 30332, USA

and

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

Abstract. Motivated by the enumeration of a class of plane partitions studied by Proctor and by considerations about symmetry classes of plane partitions, we consider the problem of enumerating lozenge tilings of a hexagon with “maximal staircases” removed from some of its vertices. The case of one vertex corresponds to Proctor’s problem. For two vertices there are several cases to consider, and most of them lead to nice enumeration formulas. For three or more vertices there do not seem to exist nice product formulas in general, but in one special situation a lot of factorization occurs, and we pose the problem of finding a formula for the number of tilings in this case.

1. Introduction and statement of results

The study of lozenge tilings is warranted by the many useful insights they bring in the subject of plane partitions. Some important instances of these are presented in [23] and [7]. In this paper we present some more such connections.

A plane partition is a rectangular array of nonnegative integers with the property that all rows and columns are weakly decreasing. A plane partition contained in an a × b rectangle and with entries at most c can be identified with its three dimensional diagram — a stack of unit cubes contained in an a × b × c box — , which in turn can be regarded as a lozenge

1991 Mathematics Subject Classification. Primary 05A15, 05A17, 05B45. Secondary 11P81, 52C20. Key words and phrases. Plane partitions, symmetry classes, determinant evaluations, lozenge tilings,

non-intersecting lattice paths, tiling enumeration, perfect matchings.

The first author was partially supported by NSF grant DMS-9802390. The second author was partially supported by the Austrian Science Foundation FWF, grant P13190-

MAT.

Figure 1.1. Figure 1.2.

tiling of a hexagon H(a, b, c) with side lengths a, b, c, a, b, c (in cyclic order) and angles of 120^{∘} (see Figure 1.1 and [9] or [29]; a lozenge tiling of a region on the triangular lattice is a tiling by unit rhombi with angles of 60^{∘} and 120^{∘}, referred to as lozenges). This simple bijection is the crucial link between the theory of lozenge tilings and that of plane partitions. For example, the number of tilings of H(a, b, c) follows to be equal to the number of plane partitions that fit in an a × b × c box, which is, by a result due to MacMahon [25], ∏_{i=1}^{a} ∏_{j=1}^{b} ∏_{k=1}^{c}(i + j + k − 1)/(i + j + k − 2).

As a variation of this, Proctor [28] considered the problem of enumerating those plane partitions π contained in an a×b×c box for which the projection of π on one of the coordinate planes, say on Oxy, fits in the “maximal staircase” λ = (b, b − 1, …, b − a + 1) (when λ is viewed as the corresponding Ferrers diagram) contained in the a × b basis rectangle (we are assuming here, without loss of generality, that a ≤ b; see Figure 1.1 for an example of such a plane partition with a = 5, b = 8, c = 3). Proctor [28] found that this number is given by the simple product

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

By the above bijection, it is easily seen that Proctor’s problem is equivalent to counting the lozenge tilings of H(a, b, c) with a maximal “staircase of lozenges” removed from a corner at which edges of lengths a and b meet (simply view Figure 1.1 as being two dimensional; there, a maximal staircase of lozenges was removed from the southeastern corner).

What if we require that the projection of π on two of the coordinate planes be contained in the corresponding staircases? The above bijection shows that the question is equivalent to counting the number of tilings of H(a, b, c) with two maximal staircases removed, from vertices that are non-adjacent and non-opposite (this is illustrated in Figure 1.2; there, maximal staircases were removed from the southeastern and the western corner; the plane partition is the same as in Figure 1.1). There are six cases to consider, corresponding to the six relative orderings of a, b and c. These are shown in Figures 1.3(a)–(f). (At this point, the special marks in form of ellipses should be ignored.) Mirror reflection pairs up these six cases in three pairs — the rows of Figure 1.3.

Figure 1.3(a). H_{d}(8, 3, 5). Figure 1.3(b). H_{d}(8, 5, 3).

Figure 1.3(c). H_{d}(5, 3, 8). Figure 1.3(d). H_{d}(5, 8, 3).

We draw all the hexagons H(a, b, c) and the regions obtained from them by cutting corners so that the horizontal edges have length b, and the other two pairs of parallel edges, as we move counterclockwise, have lengths a and c. Let H_{d}(a, b, c) be the region obtained from H(a, b, c) by removing maximal staircases from the northwestern and eastern corners (the subscript stands for the “diagonal” position of the cut off corners).

For a region R on the triangular lattice, denote by L(R) the number of its lozenge tilings. In the special case when R is obtained from a hexagon H(a, b, c) by removing staircases from two of its corners, we define three more weighted tiling enumerators for R as follows. Consider the tile positions that fit in the indentations of the zig-zag cut that removed a staircase of lozenges (the possible such positions are marked by ellipses in Figure 1.3(c)). By weighting these tile positions by 1/2, one creates a new, weighted count of the tilings

Figure 1.3(e). H_{d}(3, 5, 8). Figure 1.3(f). H_{d}(3, 8, 5).

of R: each tiling T gets weight 1/2^{k}, where k is the number of lozenges of T occupying positions weighted by 1/2, and the sum of weights of all tilings T of R gives the weighted tiling enumeration^{1}. Clearly, one can choose to weight by 1/2 only the tile positions along the cut that removed the northwestern corner of H(a, b, c), or, furthermore, to weight by 1/2 only the tile positions along the cut that removed the eastern corner. These three possibilities define our three weighted enumerators. We denote them by L_{∗}^{∗}, L^{∗}, and L_{∗}, where a superscript (respectively, subscript) indicates weighting along the cut from the northwestern (respectively, eastern) corner.

If b < c < a (see Figure 1.3(a)) — or, by mirror reflection, c < b < a (see Figure 1.3(b)),

— neither L(H_{d}(a, b, c)), nor the weighted enumerators L^{∗}(H_{d}(a, b, c)), L_{∗}(H_{d}(a, b, c)), and L_{∗}^{∗}(H_{d}(a, b, c)) seem to be given by simple product formulas. The other two cases lead to the following results.

Theorem 1.1. If b ≤ a ≤ c (see Figure 1.3(c) for an example), we have

L(H_{d}(a, b, c)) = (−1)^{b(b+1)/2}P_{b}(a − 2b − 1, b + c + 1),  (1.2)

where P_{n}(x, y) denotes the product on the right hand side of (1.8).

Note. All the factors in P_{b}(a − 2b − 1, b + c + 1) are positive except for the factors in the shifted factorial (a − 3b − c + 2j − 1)_{j}, which are all negative since for the largest factor in this product we have

a − 3b − c + 3j − 2 ≤ a − c − 2 ≤ −2,

as a ≤ c in the case addressed by Theorem 1.1. Therefore, for a, b and c as in Theorem 1.1, the sign of P_{b}(a − 2b − 1, b + c + 1) is (−1)^{b(b+1)/2}, which checks that the right hand side of (1.2) is non-negative.

Still keeping the relative order b ≤ a ≤ c of the parameters, the weighted enumerators L^{∗}(H_{d}(a, b, c)) and L_{∗}(H_{d}(a, b, c)) do not seem to be given by simple product formulas. But there is one for L_{∗}^{∗}(H_{d}(a, b, c)).

1The motivation to consider such weightings comes from the fact that weightings of that kind arise whenever the Factorization Theorem from [3] is applied to a (symmetric) region on the triangular lattice.

See [3, Sec. 6][4][5][6][7][10][12] and the proof of Theorem 1.4 in Section 2 for examples.

Theorem 1.2. If b ≤ a ≤ c (see Figure 1.3(c) for an example), we have

L_{∗}^{∗}(H_{d}(a, b, c))

= 2^{−a−b} ∏_{j=1}^{b} \frac{(j − 1)! (a + c − b + 2j − 1)! (c − a + 3j − 1)_{b−j} (a + 2c + 3j − 1)_{b−j+1}}{(b + c + j − 1)! (a − b + 2j − 1)!} , (1.3)

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

For a ≤ b ≤ c, plain enumeration of the tilings of H_{d}(a, b, c) does not seem to be given by a simple product formula. There is, however, a simple formula for L^{∗}(H_{d}(a, b, c)). As we are going to show in Section 2, the following result follows easily from a determinant evaluation of the second author [20, (5.3)].

Proposition 1.3. If a ≤ b ≤ c (see Figure 1.3(e) for an example), we have

L^{∗}(H_{d}(a, b, c)) = \frac{1}{2^{a}} ∏_{j=1}^{a} \frac{(j − 1)! (b + 2c − 3a + 3j) (b + c − 2a + j)!}{(c − a + 2j − 1)!}

· \frac{(b + 2c − 3a + 2j + 1)_{j−1} (2b + c − 3a + 2j + 1)_{j−1}}{(b − a + 2j − 1)!} .

Note. The special cases when c = a − 1 or when b = a − 1 form the subject of [7, Proposition 2.2].

The weighted enumerator L^{∗} clearly makes sense also for the region H_{1}(a, b, c) obtained from H(a, b, c) by cutting off just the northwestern corner. We have the following counterpart of Proctor’s formula (1.1). (This result was also independently discovered by Owczarek, Essam and Brak [26, Eq. (4.45)] in an equivalent form.^{2} Our proof is however completely different.)

Theorem 1.4. For a ≤ b, we have

L^{∗}(H_{1}(a, b, c)) = \frac{1}{2^{a}} ∏_{i=1}^{a} [∏_{j=1}^{b−a} \frac{c + i + j − 1}{i + j − 1} ∏_{j=b−a+i}^{b} \frac{2c + i + j − 1}{i + j − 1}] .  (1.4)

What if we require that the projection of π on all three coordinate planes be contained in the corresponding staircases? An example illustrating this, using the same plane partition as in Figures 1.1 and 1.2, is shown in Figure 1.4. Clearly, by the bijection between plane

2The combinatorial objects that are studied in [26] are “watermelon configurations” above a surface, or, equivalently, nonintersecting lattice paths confined to one side of a given diagonal line. There is a standard bijection between such families of non-intersecting lattice paths and tilings, which we explain in Section 2, see Figures 2.1, 2.2, 2.3(a). Under this bijection, the weight for lozenge tilings used in our definition of L^{∗} becomes the contact weight for watermelon configurations of [26], up to a multiplicative constant.

Figure 1.4. Figure 1.5. T_{5}.

partitions and lozenge tilings, plane partitions satisfying these conditions are identified with tilings of the region H_{3}(a, b, c) obtained from H(a, b, c) by removing maximal staircases from three alternating vertices. No matter what the relative ordering of the side lengths a, b and c is, there are always two staircases that “interfere” — i.e., there is no portion of an edge of the hexagon H(a, b, c) separating them. Data suggests that there are no simple product formulas in general. (Note that, among the cases with two removed staircases, the relative orders of a, b, c not covered by Theorems 1.1, 1.2 and Proposition 1.3 are precisely those in which the staircases interfere.)

However, the special case a = b = c presents significant factorization. Indeed, letting T_{a} stand for the triangular region H_{3}(a, a, a) (the case a = 5 is shown in Figure 1.5), the number of tilings of T_{a} factors as follows for a ≤ 7:

L(T_{1}) = 2
L(T_{2}) = 3^{2}
L(T_{3}) = 2^{3} · 13
L(T_{4}) = 2^{2} · 5^{2} · 31
L(T_{5}) = 2 · 3^{2} · 19^{2} · 37
L(T_{6}) = 2 · 7^{3} · 13 · 43 · 127
L(T_{7}) = 2^{7} · 3^{5} · 5^{3} · 7 · 13 · 73.

The amount of factorization is remarkable (also for larger a; we have computed and factored L(T_{a}) up to a = 30) and comparable, say, to that of the numbers enumerating domino tilings of squares (see [17]). Based on this, we pose the following problem.

Problem 1.5. Find a formula for the number of lozenge tilings of T_{a}, that explains the large amount of prime factorization of these numbers.

Let us now go back to the case of plane partitions with the property that their projection on two coordinate planes is contained in the corresponding staircases. As we saw, in terms of tilings this amounts to counting the tilings of a hexagon with maximal staircases removed

Figure 1.6. H_{a}(3, 8, 5).

from two non-adjacent and non-opposite vertices. What if we remove them from adjacent vertices? This leads to the region H_{a}(a, b, c) (illustrated in Figure 1.6; evidently, the subscript stands for “adjacent”), obtained from H(a, b, c) by removing maximal staircases from the top two corners (we assume that these two staircases do not interfere — otherwise the leftover region has no lozenge tilings; non-interference amounts to b ≥ a + c − 1).

The H_{a}(a, b, c)’s form a family of regions that resemble the case b ≤ a ≤ c of the H_{d}(a, b, c)’s (compare Figures 1.6 and 1.3(c)). Even though they are different, it turns out that the enumeration of tilings of both families of regions reduces to the evaluation of the same determinant, the one in Theorem 1.10. We have the following result.

Theorem 1.6. For b ≥ a + c − 1, we have

L(H_{a}(a, b, c)) = P_{a}(b − a, c),

where P_{n}(x, y) is the product on the right hand side of (1.8).

Also here, let us consider weighted enumerators. As before, let us denote by L_{∗}^{∗}, L^{∗}, and L_{∗} the weighted tiling enumerators where a superscript (respectively, subscript) indicates that the tiles along the northwestern zig-zag line (respectively, northeastern) are weighted by 1/2. While L^{∗}(H_{a}(a, b, c)) and L_{∗}(H_{a}(a, b, c)) do not seem to be given by simple product formulas, this is the case for L_{∗}^{∗}(H_{a}(a, b, c)).

Theorem 1.7. For b ≥ a + c − 1, we have

L_{∗}^{∗}(H_{a}(a, b, c)) = 2^{−c−a} \frac{(b + 2c − a + 2)_{a}}{(a + b − c + 2)_{a}}

× ∏_{j=1}^{a} \frac{(j − 1)! (b + c − a + 2j − 1)! (b − a − c + 2j + 2)_{j} (b + 2c − a + 3j + 2)_{a−j}}{(b + 2j − 1)! (c + a − j)!} .

In view of the previously made observation that in the case that b < a+c−1 the maximal staircases interfere and their removal results in a region which is not tilable, it may seem absurd to insist on having “analogues” of Theorems 1.6 an 1.7 for b < a + c − 1. But why, instead of removing maximal staircases, not remove partial staircases? To be precise, if a + b + c ≡ 0 mod 2, then let us remove the partial staircase (a − 1, a − 2, …, (a − b + c)/2)

Figure 1.7(a). Figure 1.7(b). H_{n}(6, 5, 7)

a b c  (a + b − c)/2  (c + b − a)/2 a b c{  { {  } {

from the top-left vertex of the hexagon, and the partial staircase (c−1, c−2, …, (c−b+a)/2) from the top-right vertex. (See Figure 1.7(a), in which the removed staircases are indicated by the white regions. The shades should be ignored at this point.) We obtain a region that looks like a pentagon with an “artificial” peak glued on top. Any lozenge tiling of this region is uniquely determined in the rhombus that is composed out of the triangular peak and its upside-down mirror image. (In Figure 1.7(a) this rhombus is shaded, and the unique way to tile this rhombus is shown.) Hence, we may equally well remove this rhombus. The leftover region now has the form of a pentagon with a notch (see Figure 1.7(b); at this point the ellipses are without relevance). Let us denote this region by H_{n}(a, b, c). Remarkably, extensive computer calculations suggest that the number of lozenge tilings of H_{n}(a, b, c) is given by a “simple” product formula. We state it as Conjecture A.1 in the Appendix. The fact that the result, even though given in terms of a completely explicit product, is unusually complex^{3} may indicate that proving the conjecture may be a formidable task.

Moreover, it seems that the region H_{n}(a, b, c) also allows a weighted enumeration which is given by a simple product formula. Let us, as before, denote by L_{∗}^{∗}, L^{∗}, and L_{∗} the weighted tiling enumerators where a superscript (respectively, subscript) indicates that the tiles along the northwestern zig-zag line (respectively, northeastern) are weighted by 1/2. (In Figure 1.7(b) these tiles are marked by ellipses.) While L^{∗}(H_{n}(a, b, c)) and L_{∗}(H_{n}(a, b, c)) do not seem to be given by simple product formulas, this seems to be the case for L_{∗}^{∗}(H_{n}(a, b, c)). We state it as Conjecture A.2 in the Appendix. Again, the result is unusually complex, which may indicate that a proof may be a considerable undertaking.

There is one more possibility for choosing two corners of the hexagon from which to

3No nontrivial simplifications seem to be possible. We are not aware of any other “nice” result which is similarly involved.

Figure 1.8. H_{o}(4, 6, 4).

Figure 1.9. Figure 1.10.

remove maximal staircases — two opposite corners. Data suggests that in general this does not lead to simple product formulas. There is one exception, when the sides supporting the removed staircases are equal (see Figure 1.8 for an example), but this is a “semi-frozen” situation — each tiling decomposes in tilings of parallel strips of width two (see the proof of Proposition 1.8 in Section 2).

Let H_{o}(a, b, c) be the region obtained from H(a, b, c) by removing maximal staircases from the western and eastern corners. (Not unexpectedly, here, the subscript stands for “opposite.”)

Proposition 1.8. L(H_{o}(a, b, a)) = (b + 1)^{a}.

A different viewpoint that can naturally lead one to consider the regions introduced above (hexagons with corners cut off) is based on symmetry classes of plane partitions. (It was in fact this viewpoint that provided the original motivation to study these regions.) Consider the regular hexagon H_{2n} := H(2n, 2n, 2n). The ten symmetry classes of plane partitions contained in a cube of side 2n (see [30] for their definition) are identified with the ten symmetry classes of tilings of H_{2n} (see [23]). Define a ray of tiles to be a sequence of n tiles extending from the center of H_{2n} to the nearest point of one of its edges. The six rays of tiles of H_{2n} are shown, for n = 3, in Figure 1.9. It is easy to see that the tilings of H_{2n} that have CSTC symmetry (i.e., cyclically symmetric, transposed complementary tilings) contain the tiles of all six rays, and the restriction of such a tiling to one of the six congruent regions left by removing the rays determines the whole tiling uniquely (see Figure 1.9). The regions H_{d}(a, b, c), b ≤ a ≤ c, form a two parameter generalization of this (compare Figures 1.9 and 1.3(c)).

Similarly, TC (i.e., transposed complementary) symmetry forces inclusion of two opposite rays in the tiling, and reduces to enumerating tilings of one of the two pieces left over after removing the two opposite rays of tiles (see Figure 1.10). The regions corresponding to the plane partitions considered by Proctor (hexagons with one corner cut off) form a one parameter generalization of this (compare Figures 1.10 and 1.1).

We are thus naturally led to consider the regions generated by removing three alternating rays, as shown in Figure 1.11. This region does not correspond to a symmetry class of plane partitions, but it is nevertheless quite compelling to consider in this context. The regions H_{a}(a, b, c) form a two parameter generalization of it (compare Figures 1.11 and 1.6). The two parameters were essential in conjecturing a formula for the number of tilings of these regions, based on data: polynomials fully factored into linear factors contain much more information than just integers factored into small primes.

To finish this analysis, we mention that removing one ray (see Figure 1.12) leads to a region whose number of tilings has a simple product expression, as it easily follows from the Factorization Theorem of [3] and the results of [5].

To rephrase the above statements, if one regards the regions formed by removing rays as being built up of 60^{∘} sectors, the tilings of the regions consisting of 1, 2, 3 or 6 sectors are enumerated by simple product formulas. Data suggests that this is not the case for 4 or 5 sectors.

We prove our results in Section 2 by employing a standard bijection between lozenge tilings and non-intersecting lattice paths, thus, due to the Lindström–Gessel–Viennot theorem [24][14], obtaining a determinant for the number (respectively weighted count) of tilings that we are interested in, and, finally, by evaluating the resulting determinants. In most of the cases, we obtain special cases of the two determinant evaluations that we state in Theorems 1.9 and 1.10 below. Theorem 1.9 is due to the second author [20, (5.3)] (see [1] for a simple proof, which is reproduced in [7]). The determinant evaluation in Theorem 1.10 does not seem to have appeared previously in the literature. The paper [8] contains our original proof, which is rather involved, but has its own appeal as it contains a nonautomatic (!) application of Gosper’s algorithm [15] (see also [16, Sec. 5.7][27, Sec. II.5]). Later we discovered that, in fact, there is a combinatorial argument which transforms the determinant in Theorem 1.10 into an instance of the determinant in Theorem 1.9, so that these two determinant evaluations are actually equivalent. It is this argument that we give in Section 2.

Theorem 1.9. Let x, y and n be nonnegative integers with x + y > 0. Let K_{n}(x, y) be the matrix

K_{n}(x, y) := (\frac{(x + y + i + j − 1)!}{(x + 2i − j)! (y + 2j − i)!})_{1≤i,j≤n}
= (\frac{1}{x + 2i − j} \binom{x + y + i + j − 1}{y + 2j − i})_{1≤i,j≤n} .  (1.5)

Then

det(K_{n}(x, y)) = ∏_{j=1}^{n} \frac{(j − 1)! (x + y + j)! (2x + y + 2j + 1)_{j−1} (x + 2y + 2j + 1)_{j−1}}{(x + 2j − 1)! (y + 2j − 1)!} . (1.6)

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

Theorem 1.10. Let n be a positive integer, and let x and y be nonnegative integers. Let A_{n}(x, y) be the matrix

A_{n}(x, y) := (\binom{x + y + j}{x − i + 2j} − \binom{x + y + j}{x + i + 2j})_{1≤i,j≤n} .  (1.7)

Then

det A_{n}(x, y) = ∏_{j=1}^{n} \frac{(j − 1)! (x + y + 2j)! (x − y + 2j + 1)_{j} (x + 2y + 3j + 1)_{n−j}}{(x + n + 2j)! (y + n − j)!} . (1.8)

Note. Theorems 1.9 and 1.10 are only formulated for nonnegative integral x and y. But in fact, with a generalized definition of factorials and binomials (cf. [16, §5.5, (5.96), (5.100)], both theorems would also make sense and be true for complex x and y.

Remark 1.11. (1) The approach we use for the regions H_{d} can be used also to enumerate tilings of the regions with just one corner cut off, which correspond to the result of Proctor mentioned earlier in the Introduction. This has been worked out in [22, proof of Theorem 6].

(2) A further question that one is immediately tempted to ask is the question of whether or not there exist q-analogues of our results. For example, are there plane partition style q-versions of our results, i.e., closed formulas for the generating function ∑_{P} q^{|P |}, where the sum is over all plane partitions in one of the sets of plane partitions that we consider in our paper, with |P | denoting the number of boxes of the plane partition P? However, this particular q-weight does not lead to “nice” formulas (i.e., simple product formulas), already in the case of Proctor’s problem. For, if we just consider the case a = b, c = 1 in Proctor’s problem (see Figure 1.1), then what we are asking for is a nice expression for q^{\binom{a+1}{2}}C_{a+1}(q^{−1}), where C_{n}(q) is the q-Catalan number introduced by Carlitz and Riordan [2], for which it is known that no closed product formula exists (only nice generating function expansions, see e.g. [13]). A similar statement can be made for the general case.

On the other hand, Proctor does in fact give a q-analogue of his result (in unpublished work; cf. [18, Theorems 8 and 9]^{4}). In this result, the q-weight is given in terms of certain alternating trace weights for the plane partitions under consideration. However, analysis of small cases suggests that this weight, or variations thereof, does not lead to nice q-analogues of our enumeration formulas for lozenge tilings of other regions.

We also note that for the determinant evaluation of Theorem 1.9, which is at the heart of most of our results, there exists in fact a q-analogue [19, Theorem 1]. However, again, we were not able to use it to obtain q-analogues of our enumeration results.

2. Proofs of the results

As already mentioned at the end of the Introduction, we employ in our proofs a standard bijection that maps each lozenge tiling T of a region R on the triangular lattice to a family of non-intersecting lattice paths taking steps east or north on the grid lattice Z^{2}. This bijection works as follows. Choose a lattice line direction d — without loss of generality, the horizontal direction — , and mark with a dot the unit segments parallel to d on the boundary of R (see Figure 2.1). Each marked segment is either on top or at the bottom of the region R. Label from right to left the ones at the bottom of R by u_{1}, u_{2}, …, u_{m} and the ones on top of R by v_{1}, v_{2}, …, v_{n}.

Consider now the tile t_{1} of T resting on u_{i}, for some fixed 1 ≤ i ≤ m (see Figure 2.2 for an example of a tiling T of the region from Figure 2.1). Let t_{2} be the other tile of T containing the side of t_{1} opposite u_{i}. Continue the sequence of selected tiles by choosing t_{3} to be the tile of T sharing with t_{2} the side of t_{2} opposite the one common to t_{2} and t_{1}. This procedure leads to a path of rhombic tiles growing upward, which clearly must end on one of the v_{j}’s. This path of rhombi can be identified with a (linear) path that starts at the midpoint of u_{i} and ends at the midpoint of v_{j}, see Figure 2.2. (There, the resulting linear paths are indicated by dotted segments.) After normalizing the oblique coordinate system and rotating it in standard position, we obtain a lattice path on Z^{2} that starts at the midpoint of u_{i} (actually, its image after these normalizations), ends at the midpoint of v_{j} (again, actually its image after these normalizations) and takes unit steps east or north. (See Figure 2.3(a) for the resulting lattice paths in our example.) One obtains this way a family P of m lattice paths, one for each 1 ≤ i ≤ m, and they cannot touch each other since Figure 2.1. Figure 2.2. u_{3} u_{2} u_{1}

4These theorems are in fact about generating functions for shifted plane partitions of a trapezoidal shape with a fixed first entry in each row. If one chooses these first entries to be all equal to c, say, then in any such shifted plane partition all the entries in the left-hand triangle must be equal to c. Therefore we may simply disregard that triangle. If we remove it then what is left is ordinary plane partitions of shape (b, b − 1, b − 2, …, b − a + 1), for some a and b, with entries bounded by c. These are exactly the plane partitions which correspond to the lozenge tilings of H_{1}(a, b, c), see Figure 1.1.

v_{1}
v_{2}
v_{3}

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; y = x − 2; u_{1}; u_{2}; u_{3}; v_{1}; v_{2}; v_{3}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; y = x − 2]

Figure 2.3(a). Figure 2.3(b).

the corresponding paths of tiles are disjoint. We obtain in particular that m ≤ n, and hence by symmetry m = n. It is easy to see that the correspondence T ↦ P is a bijection between the set of tilings T of R and the families P of non-intersecting lattice paths starting at the midpoints of u_{1}, u_{2}, …, u_{n}, ending at the midpoints of v_{1}, v_{2}, …, v_{n} and contained within R.

Lemma 2.1. For b ≤ a ≤ c, we have L(H_{d}(a, b, c)) = (−1)^{b(b+1)/2} det A_{b}(a−2b−1, b+c+1).

Proof. Label the horizontal unit segments on the boundary of H_{d}(a, b, c) as described above. Choose an oblique coordinate system with the origin at the midpoint of u_{1} and coordinate axes parallel to the non-horizontal lattice lines of the triangular lattice (see Figure 2.1). Applying the procedure described above to H_{d}(a, b, c) one obtains that L(H_{d}(a, b, c)) is equal to the number of families of non-intersecting lattice paths with starting points u_{i} = (−i + 1, i − 1), i = 1, 2, …, b, ending points v_{j} = (a − 2j + 2, c + j − 1), j = 1, 2, …, b, and with the additional requirement that they do not touch the line y = x − 2. (This requirement ensures that the corresponding paths of rhombi stay within our region H_{d}(a, b, c); see Figure 2.3(a). Note that by abuse of notation we denote the midpoints of the u_{i}’s and v_{j}’s by the same symbols we use for the segments.)

By the Lindström-Gessel-Viennot theorem [24, Lemma 1][14][31, Theorem 1.2], the number of such families of non-intersecting lattice paths is given by the determinant of the b × b matrix whose (i, j)-entry is the number of lattice paths from u_{i} to v_{j} that are strictly above the line y = x − 2. By André’s Reflection Principle [11], this number is

\binom{a + c − j + 1}{a − 2j + i + 1} − \binom{a + c − j + 1}{a − 2j − i + 1}.

Therefore, the Lindström-Gessel-Viennot theorem implies that

L(H_{d}(a, b, c)) = det (\binom{a + c − j + 1}{a − 2j + i + 1} − \binom{a + c − j + 1}{a − 2j − i + 1})_{1≤i,j≤b} .  (2.1)

Reversing columns (i.e., replacing j by b + 1 − j) in (2.1) the right hand side becomes

(−1)^{b(b−1)/2} det (\binom{a + c + j − b}{a + 2j + i − 2b − 1} − \binom{a + c + j − b}{a + 2j − i − 2b − 1})_{1≤i,j≤b} .  (2.2)

The entries of the matrix in (2.2) are readily seen to be precisely the negatives of the entries of A_{b}(a − 2b − 1, b + c + 1). This implies the statement of the Lemma. □

Proof of Theorem 1.10. The preceding proof of Lemma 2.1 shows (by renumbering the lattice paths from left to right) that (−1)^{n(n+1)/2}A_{n}(x, y) counts the number of families P of n non-intersecting lattice paths, with starting points (−n + i, n − i), i = 1, 2, …, n, and end points (x + 2j + 1, y − j − 1), j = 1, 2, …, n, with the additional requirement that they do not touch the line y = x − 2 (see Figure 2.3(a) for an example). Now, for each such family, we prepend (2n − 2i + 1) vertical steps to the i-th path. Thus we obtain families P′ of n non-intersecting lattice paths, with starting points (−n + i, −n + i − 1), i = 1, 2, …, n, and end points (x + 2j + 1, y − j − 1), j = 1, 2, …, n, with the additional requirement that they do not touch the line y = x − 2. (See Figure 2.3(b) for the resulting path family in our example.) In fact, this is a bijection between the former and latter path families, because the prepended path portions are in fact forced by the boundary y = x − 2. Therefore (−1)^{n(n+1)/2}A_{n}(x, y) is also equal to the number of the latter path families.

Again we may apply the Lindström-Gessel-Viennot theorem. Since the Reflection Principle yields that the number of paths from (−n + i, −n + i − 1) to (x + 2j + 1, y − j − 1) which do not touch the line y = x − 2 is given by

\binom{x + y + j + 2n − 2i + 1}{x + 2j + n − i + 1} − \binom{x + y + j + 2n − 2i + 1}{x + 2j + n − i}

= \frac{(y − x − 3j) (x + y + j + 2n − 2i + 1)!}{(x + 2j + n − i + 1)! (y + n − j − i + 1)!},

we infer that (−1)^{n(n+1)/2}A_{n}(x, y) is equal to

det (\frac{(y − x − 3j) (x + y + j + 2n − 2i + 1)!}{(x + 2j + n − i + 1)! (y + n − j − i + 1)!})_{1≤i,j≤n}

= ∏_{j=1}^{n}(y − x − 3j) · det (\frac{1}{y + n − j − i + 1}\binom{x + y + j + 2n − 2i + 1}{x + 2j + n − i + 1})_{1≤i,j≤n}

= ∏_{j=1}^{n}(y − x − 3j) · det (\frac{(−1)^{x+2j+n−i+1}}{y + n − j − i + 1}\binom{−y − n + j + i − 1}{x + 2j + n − i + 1})_{1≤i,j≤n}

= ∏_{j=1}^{n} ((−1)^{x+n−j}(y − x − 3j))

× det (\frac{1}{−y − x − 2n + 2i − j − 2}\binom{−y − n + j + i − 2}{x + 2j + n − i + 1})_{1≤i,j≤n} .

(At the second to last equality we used that \binom{n}{k} = (−1)^{k}\binom{−n+k−1}{k}.) This latter determinant is the determinant det K_{n}(−y − x − 2n − 2, x + n + 1), with K_{n}(x, y) defined in (1.5). In view of Theorem 1.9, this proves (1.8), after some manipulation. □

Proof of Theorem 1.1. This follows directly from Lemma 2.1 and Theorem 1.10. □

Proof of Theorem 1.2. As in the proof of Lemma 2.1, we map the tilings to families P of non-intersecting lattice paths, with starting points u_{i} = (−i+1, i−1), i = 1, 2, …, b, ending points v_{j} = (a−2j+2, c+j−1), j = 1, 2, …, b, and with the additional requirement that they do not touch the line y = x−2 (see again Figure 2.3(a)). Following the proof of Theorem 1.10, we prepend 2i−1 vertical steps to the i-th path (because here we kept the numbering of the paths from right to left), so that we obtain families P′ of non-intersecting lattice paths, with starting points u_{i} = (−i + 1, −i), i = 1, 2, …, b, ending points v_{j} = (a − 2j + 2, c + j − 1), j = 1, 2, …, b, and with the additional requirement that they do not touch the line y = x−2 (see again Figure 2.3(b)). However, unlike in the proofs of Lemma 2.1 and Theorem 1.10, here each family has a certain weight, given by the ℓ-th power of 1/2, where ℓ is the number of lozenges that are weighted by 1/2 in the corresponding tiling (compare Figures 1.3(c), 2.1 and 2.3(b)).

To realize this weight, we give each horizontal step from (a − 2k + 1, c + k − 1) to (a − 2k + 2, c + k − 1), for some k, the weight 1/2. This takes care of the fact that the lozenges along the northwestern zig-zag line are weighted by 1/2. To also take into account that the lozenges along the eastern zig-zag line are weighted by 1/2, we assign a weight of 2 (sic!) to each horizontal step from (k, k) to (k + 1, k), for some k (i.e., to each horizontal step which terminates directly at the line y = x − 1 the paths are not allowed to cross). This generates our weight, up to a multiplicative constant of 2^{a}. Indeed, for each marked lozenge position along the eastern boundary, a tiling T has a lozenge in that position if and only if the corresponding unit segment weighted by 2 is not a step on some lattice path of the family corresponding to T, thereby giving rise to a missing weight of 1/2 in comparison to path families where some path does contain that step. To give an explicit example, the tiling in Figure 2.2 contains two tiles weighted by 1/2 along the eastern boundary, the third and the fifth from the bottom. These are the ones which are completely white, as there is no lattice path running through them. Hence, in the corresponding path family shown in Figure 2.3(b), the step from (2, 2) to (3, 2) and the step from (4, 4) to (5, 4) (both weighted by 2) are not contained by any of the paths.

Now we want to write down the Lindström–Gessel–Viennot determinant for our weighted count (as defined just above). In order to do so, we need the weighted count of paths from (−i + 1, −i) to (a − 2j + 2, c + j − 1) which do not touch y = x − 2. We claim that the weighted count of these latter paths is the same as the weighted count of all paths from (−i + 1, −i) to (a − 2j + 2, c + j − 1), in which the last step of the path has weight 1/2 if it is a horizontal step. (It should be noted that in this weighted count there are no steps with weight 2 anymore.) This is seen as follows: suppose we are given a path from (−i + 1, −i) to (a − 2j + 2, c + j − 1) which does not touch the line y = x − 2, and which has exactly ℓ touching points on the line y = x − 1. These ℓ touching points on y = x − 1 must be reached by horizontal steps from (k, k) to (k + 1, k), each of which contribute a weight of 2. Thus, in total, this gives contribution of 2^{ℓ} to the weight. Now we map such a path to 2^{ℓ} paths from (−i + 1, −i) to (a − 2j + 2, c + j − 1) (without restriction), by focussing on the path portions between two consecutive touching points, including the portion between (−i + 1, −i) and the first touching point, and keeping any of them either fixed or reflecting it in the line y = x − 1. This proves the assertion.

By distinguishing between the cases where the last step of a path is vertical respectively horizontal, the new weighted count of the paths from (−i + 1, −i) to (a − 2j + 2, c + j − 1) then is seen to be

\binom{a + c + 2i − j − 1}{a − 2j + i + 1} + \frac{1}{2}\binom{a + c + 2i − j − 1}{a − 2j + i} = \frac{1}{2} \frac{(a + 2c + 3i − 1) (a + c + 2i − j − 1)!}{(a − 2j + i + 1)! (c + i + j − 1)!}.

Therefore the Lindström–Gessel–Viennot determinant is seen, by manipulations similar to those in the proof of Theorem 1.10, to be

det (\frac{1}{2} \frac{(a + 2c + 3i − 1) (a + c + 2i − j − 1)!}{(a − 2j + i + 1)! (c + i + j − 1)!})_{1≤i,j≤b}

= 2^{−b} ∏_{i=1}^{b} ((−1)^{a+i}(a + 2c + 3i − 1)) det (\frac{1}{−a − c + j − 2i}\binom{−c − i − j}{a − 2j + i + 1})_{1≤i,j≤b} .

Figure 2.4.

After reversing the order of rows and columns (i.e., after replacing i by b + 1 − i and j by b + 1 − j), it is seen that this determinant is the determinant det K_{b}(−a − c − b − 1, a − b). Application of Theorem 1.9, division of the resulting expression by 2^{a}, and some rearrangement finish the proof of the theorem. □

Proof of Proposition 1.3. Consider the region H_{d}(a, b, c) and choose the direction d in the bijection between tilings and lattice paths to be the direction of the lattice lines going from southwest to northeast (see Figure 2.4). Consider the unit segments parallel to d on the boundary, and label the midpoints of those on the eastern boundary, from top to bottom, by u_{1}, u_{2}, …, u_{a}, and the midpoints of those on the northwestern boundary by v_{1}, v_{2}, …, v_{a}. Choose an oblique coordinate system centered \sqrt{3} units above u_{1} (see Figure 2.4) and with axes along the northwestern and western lattice line directions.

By the bijection between tilings and lattice paths, each tiling T of H_{d}(a, b, c) is identified with a family P of non-intersecting lattice paths with starting points (−2i, i), i = 1, 2, …, a, and ending points (c − a − j, b − a + 2j), j = 1, 2, …, a. (Unlike in the proof of Lemma 2.1, no additional requirements on the paths are needed).

The weighted enumerator L^{∗} assumes that the northwesternmost a tile positions are weighted by 1/2 (these positions are marked in Figure 2.4). Correspondingly, the paths of P whose last step is a vertical step have weight 1/2 (as before, the weight of a lattice path is the product of the weights of its steps). The weight of the family P is the product of the weights of its members, and by construction it matches the weight of the tiling T. By the Lindström-Gessel-Viennot theorem, the total weight of those families P that are non-intersecting — and hence L^{∗}(H_{d}(a, b, c)) — is given by the determinant of the a × a matrix whose (i, j)-entry equals the total weight of the paths from u_{i} to v_{j}. Splitting the latter family in two according to the type of the last step, one obtains that its total weight

Figure 2.5. R(5, 10, (7, 6, 4, 2, −1)).

is

\binom{b + c − 2a + i + j − 1}{c − a + 2i − j − 1} + \frac{1}{2}\binom{b + c − 2a + i + j − 1}{c − a + 2i − j}

= \frac{b + 2c − 3a + 3i}{2} \frac{(b + c − 2a + i + j − 1) !}{(c − a + 2i − j) ! (b − a + 2j − i) !}.

When computing the determinant of the above matrix, the j-free factors can be factored out along rows, and the leftover matrix is precisely the one in (1.5) with n = a, x = c − a, and y = b − a. Using (1.6) and substituting the values of x and y one obtains the formula in the statement of Proposition 1.3. □

Now we turn our attention to the proof of Theorem 1.4. We deduce (1.4) from a wellknown determinant evaluation (see the proof of Lemma 2.2) and Proctor’s formula (1.1), using the Factorization Theorem for perfect matchings of [3].

Let m and n be nonnegative integers, and let l = (l_{1}, l_{2}, …, l_{n}), 0 ≤ l_{1} ≤ m, l_{1} > ⋯ > l_{n} be a list of integers (some of which may be negative). We define the regions R(n, m, l) as follows. Consider an oblique coordinate system on the triangular lattice, centered at the midpoint of a lattice segment facing northeast and having the x-axis horizontal and the y-axis parallel to the lattice lines going from southwest to northeast (see Figure 2.5). Consider, on the one hand, the points (−i + 1, i − 1), i = 1, 2, …, n, and on the other hand the points (l_{j}, m − l_{j}), j = 1, 2, …, n. We construct R(n, m, l) so that its tilings are in bijection with the families of non-intersecting lattice paths with these starting and ending points. It is easy to see that this determines R(n, m, l) to be the hexagon with side lengths n, l_{1}, m − l_{1}, l_{1} − l_{n} + 1, l_{n} + n − 1, m − l_{n} − n + 1 (in anticlockwise order, starting with the southwestern side), and having triangular dents along the northeastern side at the lattice segments with midpoints not among (l_{j}, m − l_{j}), j = 1, 2, …, n. (R(5, 10, (7, 6, 4, 2, −1)) is shown in Figure 2.5.)

Lemma 2.2.

L(R(n, m, l)) = \frac{∏_{1≤i<j≤n}(l_{i} − l_{j}) ∏_{i=1}^{n}(m + i − 1)!}{∏_{i=1}^{n}(l_{i} + n − 1)! ∏_{i=1}^{n}(m − l_{i})!}.

Proof. By construction and by the Lindström-Gessel-Viennot theorem, we have that

L(R(n, m, l)) = det (\binom{m}{l_{j} + i − 1})_{1≤i,j≤n} .  (2.3)

This determinant can be evaluated, e.g., by means of [21, (3.12)] with A = m − 1 and L_{i} = l_{i} − 1, i = 1, 2, …, n, and one obtains the formula in the statement of the Lemma. □

Proof of Theorem 1.4. Consider the region H_{1}(a, b, c) and weight by 1/2 the a tile positions required to be weighted so by L^{∗} (these are marked in Figure 2.6). Draw a line l through the centers of the marked lozenges, and reflect H_{1}(a, b, c) across l. The union U of H_{1}(a, b, c) with its mirror image is precisely the region R(2c, a, l), where l = (b, b − 1, …, b − c + 1, a − c, a − c − 1, …, a − 2c + 1). Applying Lemma 2.2 one obtains, after some manipulations, that

L(U) = ∏_{i=1}^{a} [∏_{j=1}^{b−a} (\frac{c + i + j − 1}{i + j − 1})^{2} ∏_{j=b−a+1}^{b} \frac{2c + i + j − 1}{i + j − 1}] .  (2.4)

The region U is symmetric about l, so we can apply to it the Factorization Theorem of [3] (see [6] for a phrasing of it in terms of lozenge tilings). Following the prescriptions in the statement of this theorem, cut U along the zig-zag line following lattice segments just above l (this is shown as a thick line in Figure 2.6), and denote the pieces above and below the cut by U^{+} and U^{−}, respectively. In U^{−}, weight the tile positions just below the cut by 1/2. Since l cuts through 2a unit triangles, the Factorization Theorem yields

L(U) = 2^{a}L(U^{+})L^{∗}(U^{−}).  (2.5)

However, U^{−} is by construction just H_{1}(a, b, c). Moreover, in U^{+} there is a row of forced tiles (shaded in Figure 2.6), and the region left upon their removal is congruent to H_{1}(a, b−1, c). Solving for L^{∗}(U^{−}) in (2.5) and using formulas (2.4) and (1.1), one obtains for L^{∗}(H_{1}(a, b, c)) the product expression (1.4). □

Even though the region H_{a}(a, b, c) looks different from the case b ≤ a ≤ c of H_{d}(a, b, c), it turns out that their tiling enumerations amount to evaluating the same determinant.

Lemma 2.3. For b ≥ a + c − 1 we have L(H_{a}(a, b, c)) = det A_{a}(b − a, c).

Proof. Rotate the region H_{a}(a, b, c) clockwise by 60^{∘}, so that it is positioned as in Figure 2.7. By the bijection between tilings and lattice paths, each tiling is identified with a family of non-intersecting lattice paths with starting points (−i + 1, i − 1), ending points (c − j + 1, b − a + 2j − 1), i, j = 1, 2, …, a, and such that all lattice paths stay strictly above the line y = x−2. Just as in the proof of Theorem 1.1, the Lindström-Gessel-Viennot theorem implies that

L(H_{a}(a, b, c)) = det (\binom{b + c − a + j}{b − a + 2j − i} − \binom{b + c − a + j}{b − a + 2j + i})_{1≤i,j≤a} .

The above determinant is readily recognized as A_{a}(b − a, c). □

Figure 2.8.

Proof of Theorem 1.6. This follows directly from Lemma 2.3 and Theorem 1.10. □

Proof of Theorem 1.7. We use the bijection between tilings and families of non-intersect-ing lattice paths from the proof of Lemma 2.3. In addition, we prepend (2i−1) vertical steps to the i-th path. Thus we obtain families P′ of non-intersecting lattice paths, with starting points (−i + 1, −i), i = 1, 2, …, a, ending points (c − j + 1, b − a + 2j − 1), j = 1, 2, …, a, and such that all lattice paths stay strictly above the line y = x − 2. For the rest of the proof one follows the arguments in the proof of Theorem 1.2, which have to be adjusted only insignificantly. □

Proof of Proposition 1.8. Let T be a tiling of H_{o}(a, b, a). Consider the b tiles containing the lattice segments on the bottom part of its boundary. Because of forcing, there is precisely one dent in the upper boundary of the union of these tiles (see Figure 2.8). This dent has to be covered by some other tile t (shaded dark in Figure 2.8), which in turn forces b more tiles in place. Thus, a subregion congruent to H(1, b, 1) at the bottom of H_{o}(a, b, a) ends up being tiled by the restriction of the tiling T. Since there are b + 1 tilings of H(1, b, 1) (corresponding to the b + 1 possible positions of t), this implies

L(H_{o}(a, b, a)) = (b + 1) L(H_{o}(a − 1, b, a − 1)).

Repeated application of this gives the statement of the Proposition. □

Appendix

Conjecture A.1. The number of lozenge tilings of the region H_{n}(x, m + y, x + m − y) (see Figure 1.7(b) for an example) is equal to

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

× 2^{\binom{m}{2}+\binom{y}{2}} ∏_{i=1}^{m−1} i! ∏_{i=1}^{y−1} i! ∏_{i≥0}(x + i + \frac{3}{2})_{m−2i−1} ∏_{i≥0}(x − y + \frac{5}{2} + 3i)_{⌊\frac{3y}{2} − \frac{9i}{2}⌋−2}

× ∏_{i≥0}(x + \frac{3m}{2} − y + ⌈\frac{3i}{2}⌉ + \frac{3}{2})_{3⌈\frac{y}{2} ⌉−⌈\frac{9i}{2}⌉−2} ∏_{i≥0}(x + \frac{3m}{2} − y + ⌊\frac{3i}{2}⌋ + 2)_{3⌊\frac{y}{2} ⌋−⌊\frac{9i}{2}⌋−1}

× ∏_{i≥0}(x + m − ⌊\frac{y}{2} ⌋ + i + 1)_{2⌊\frac{y}{2} ⌋−m−2i} ∏_{i≥0}(x + ⌊\frac{y}{2} ⌋ + i + 2)_{m−2⌊\frac{y}{2} ⌋−2i−2}

× \frac{∏_{i=0}^{y}(x − y + 3i + 1)_{m+2y−4i} ∏_{i=0}^{⌈\frac{y}{2} ⌉−1}(x + m − y + i + 1)_{3y−m−4i}}{∏_{i≥0}(x + \frac{m}{2} − \frac{y}{2} + i + 1)_{y−2i} (x + \frac{m}{2} − \frac{y}{2} + i + \frac{3}{2})_{y−2i−1}}

× \frac{∏_{i=0}^{y}(x + i + 2)_{2m−2i−1}}{(x + y + 2)_{m−y−1} (m + x − y + 1)_{m+y}} . (A.1)

Here, shifted factorials occur with positive as well as with negative indices. The convention with respect to which these have to be interpreted is

(α)_{k} := \{ \begin{matrix}α(α + 1) ⋯ (α + k − 1) & if k > 0, \\ 1 & if k = 0, \\ 1/(α − 1)(α − 2) ⋯ (α + k) & if k < 0. \end{matrix}

All products ∏_{i≥0}(f(i))_{g(i)} in (A.1) have to interpreted as the products over all i ≥ 0 for which g(i) ≥ 0.

For a proof one could try to proceed as follows: first we introduce nonintersecting lattice paths, with starting points along the bottom, and end points along the northeastern and northwestern zig-zag lines. On introducing a suitable coordinate system, the starting points can be represented as A_{i} = (−i, i), i = 1, 2, …, m+y, and the end points as E_{i} = (x−i, 2i), i = 1, 2, …, m, E_{i} = (m + y − 2i + 1, m + x − y + i), i = m + 1, m + 2, …, m + y. The corresponding Lindström–Gessel–Viennot determinant is

det_{1≤i,j≤m+y} (\{ \begin{matrix}\binom{x+i}{x−i+j} & i = 1, …, m \\ \binom{x+2m−i+1}{m+y−2i+j+1} & i = m + 1, …, m + y \end{matrix} \}) .  (A.2)

The task is to evaluate this determinant. In principle, after having taken suitable factors out of the determinant (so that the new determinant is a polynomial in x), the “identification of factors” method, as described in Section 2.4 of [21], should be capable of accomplishing the determinant evaluation.

Conjecture A.2. The weighted count of lozenge tilings of the region H_{n}(x, m+y, x+m−y), where the lozenges along the two zig-zag lines are weighted by 1/2 (see Figure 1.7(b) for an example; the lozenges that are weighted by 1/2 are marked by ellipses), is equal to

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

× 2^{\binom{m}{2}+\binom{y}{2}} ∏_{i=1}^{m−1} i! ∏_{i=1}^{y−1} i! ∏_{i≥0}(x + i + \frac{3}{2})_{m−2i−1} ∏_{i≥0}(x − y + 3i + \frac{7}{2})_{⌈\frac{3y}{2} − \frac{9i}{2}⌉−4}

× ∏_{i≥0}(x + \frac{3m}{2} − y + ⌊\frac{3i}{2}⌋ + \frac{3}{2})_{3⌈\frac{y}{2} ⌉−⌊\frac{9i}{2}⌋−1} ∏_{i≥0}(x + \frac{3m}{2} − y + ⌈\frac{3i}{2}⌉ + 1)_{3⌊\frac{y}{2} ⌋−⌈\frac{9i}{2}⌉+1}

× ∏_{i≥0}(x + m − ⌊\frac{y}{2} ⌋ + i + 1)_{2⌊\frac{y}{2} ⌋−m−2i} ∏_{i≥0}(x + ⌊\frac{y}{2} ⌋ + i + 2)_{m−2⌊\frac{y}{2} ⌋−2i−2}

× \frac{(x − y + \frac{1}{2})_{⌊_{\frac{m}{2}}⌋+2y}(x + m − y)_{y+1} ∏_{i=0}^{y}(x + i + 1)_{2m−2i}}{(x + \frac{m}{2} − \frac{y}{2} + \frac{1}{2})⌊_{\frac{3y}{2}} ⌋(x + \frac{3m}{2} − \frac{y}{2} + 1)_{y+1}(x + \frac{m}{2} + \frac{y}{2} + 1)⌈_{\frac{y−2}{2}}⌉}

× \frac{∏_{i=0}^{y}(x − y + 3i + 1)_{m+2y−4i} ∏_{i=0}^{⌈\frac{y}{2} ⌉−1}(x + m − y + i + 1)_{3y−m−4i}}{(m + x − y)_{m+y+1} (x + y + ⌈\frac{m}{2}⌉)_{⌊_{\frac{m}{2}}⌋−y+1} ∏_{i=0}^{⌈y/2⌉−1}(x − y + 1 + 3i)}

× \frac{1}{∏_{i≥0}(x + \frac{m}{2} − \frac{y}{2} + i + 1)_{y−2i}(x + \frac{m}{2} − \frac{y}{2} + i + \frac{3}{2})_{y−2i−1}} , (A.3)

with the same conventions as in the previous conjecture.

For a proof, one could again introduce nonintersecting lattice paths, with starting points and end points as before. The corresponding Lindström–Gessel–Viennot determinant is

det_{1≤i,j≤m+y} (\{ \begin{matrix}\frac{(x+i−1)! (x+j/2)}{(x−i+j)! (2i−j)!} & i = 1, …, m \\ \frac{(x+2m−i)! (3m/2+x−y/2−j/2+1/2)}{(m+y−2i+j+1)! (m+x−y+i−j)!} & i = m + 1, …, m + y \end{matrix} \}) .  (A.4)

The remarks after (A.2) apply also here.

References

[1] T. Amdeberhan, Lewis strikes again!, electronic manuscript dated 1997. (available at http://www.math.temple.edu/∼tewodros/programs/kradet.html).

[2] L. Carlitz and J. Riordan, Two element lattice path permutation numbers and their q-generalization, Duke J. Math. 31 (1964), 371–388.

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

[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 (available at http://www.math.gatech.edu/∼ciucu/pp1.ps).

[6] M. Ciucu and C. Krattenthaler, The number of centered lozenge tilings of a symmetric hexagon, J. Combin. Theory Ser. A 86 (1999), 103-126.

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

[8] M. Ciucu and C. Krattenthaler, A non-automatic (!) application of Gosper’s algorithm evaluates a determinant from tiling enumeration, Rocky Mountain J. Math.

(to appear), math/0011047.

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

[10] T. Eisenkölbl, Rhombus tilings of a hexagon with two triangles missing on the symmetry axis, Electron. J. Combin. 6 (1) (1999) #R30, 19 pp.

[11] W. Feller, “An introduction to probability theory and its applications,” Vol. I, John Wiley & Sons, 1968.

[12] M. Fulmek and C. Krattenthaler, The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis, I, Ann. Combin. 2 (1998), 19–40.

[13] J. Fürlinger and J. Hofbauer, q-Catalan numbers, J. Combin. Theory A 40 (1985), 248–264.

[14] I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

[15] R. W. Gosper, Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75 (1978), 40–42.

[16] R. L. Graham, D. E. Knuth and O. Patashnik, “Concrete Mathematics,” Addison-Wesley, Reading, Massachusetts, 1989.

[17] P. W. Kasteleyn, The statistics of dimers on a lattice, I: the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209–1225.

[18] C. Krattenthaler, Generating functions for shifted plane partitions, J. Statist. Plann. Inference 34 (1993), 197–208.

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

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

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

[22] C. Krattenthaler, A. J. Guttmann and X. G. Viennot, Vicious walkers, friendly walkers and Young tableaux II: with a wall, J. Phys. A: Math. Gen. 33 (2000), 8835–8866.

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

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

[25] P. A. MacMahon, Memoir on the theory of the partition of numbers — Part V. Partitions in two-dimensional space, Phil. Trans. R. S., 1911, A.

[26] A. L. Owczarek, J. W. Essam and R. Brak, Scaling analysis for the adsorption transition in a watermelon network of n directed non-intersecting walks, J. Statist. Phys. 102 (2001), 997–1017.

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

[28] R. A. Proctor, Odd symplectic groups, Invent. Math. 92 (1988), 307–332.

[29] D. P. Robbins, The story of 1, 2, 7, 42, 429, 7436, …, Math. Intelligencer 13 (1991), No. 2, 12–19.

[30] R. P. Stanley, Symmetries of plane partitions, J. Combin. Theory Ser. A 43 (1986), 103–113.

[31] J. R. Stembridge, Nonintersecting paths, Pfaffians and plane partitions, Adv. in Math. 83 (1990), 96–131.