Enumeration of Tilings of Diamonds and Hexagons with Defects

Harald A. Helfgott Department of Mathematics Princeton University Princeton, NJ 08544

                     haraldh@math.princeton.edu

Ira M. Gessel Mathematics Department Brandeis University Waltham, MA 02254-9110

                      gessel@math.brandeis.edu

Submitted: August 1, 1998; Accepted February 23, 1999 Classification 05B40,05C70

Abstract

We show how to count tilings of Aztec diamonds and hexagons with defects using determinants. In several cases these determinants can be evaluated in closed form. In particular, we obtain solutions to open problems 1, 2, and 10 in James Propp’s list of problems on enumeration of matchings [22].

1. Introduction

While studying dimer models, P. W. Kasteleyn [15] noticed that tilings of very simple figures by very simple tiles can be not only plausible physical models, but also starting points for some very interesting enumeration problems. Kasteleyn himself solved the problem of counting tilings of a rectangle by dominoes. He also found a general method (now known as Kasteleyn matrices) for computing the number of tilings of any bipartite planar graph in polynomial time. Kasteleyn’s method has proven very useful for computational-experimental work, but it does not, of itself, provide proofs of closed formulas for specific enumeration problems. We shall see a few examples of problems for which Kasteleyn matrices alone are inadequate.

By an (a, b, c, d, e, f) hexagon we mean a hexagon with sides of lengths a, b, c, d, e, f, and angles of 120 degrees, subdivided into equilateral triangles of unit side by lines parallel to the sides. We draw such a hexagon with the sides of lengths a, b, c, d, e, f in clockwise order, so that the side of length b is at the top and the side of length e is at the bottom. We shall use the term (a, b, c) hexagon for an (a, b, c, a, b, c) hexagon. Thus Figure 2 shows a (3, 4, 3) hexagon.

Figure 1. Aztec diamond of order 3  Figure 2. (3, 4, 3) hexagon

An Aztec diamond of order n is the union of all unit squares with integral vertices contained within the region |x| + |y| ≤ n + 1. Figure 1 shows an Aztec diamond of order 3.

We are interested in tilings of hexagons with lozenges, which are rhombi with unit sides and angles of 120 and 60 degrees, and tilings of Aztec diamonds with dominoes, which are 1 by 2 rectangles. In particular, we shall examine three problems from James Propp’s list of open problems on tilings [22].

Problem 1 (Propp’s Problem 1). Show that in the (2n − 1, 2n, 2n − 1) hexagon, the central vertical lozenge (consisting of the two innermost triangles) is covered by a lozenge in exactly one-third of the tilings.

Problem 2 (Propp’s Problem 2). Enumerate the lozenge-tilings of the region obtained from the (n, n + 1, n, n + 1, n, n + 1) hexagon by removing the central triangle.

Problem 3 (Propp’s Problem 10). Find the number of domino tilings of a (2k − 1) by 2k undented Aztec rectangle with a square adjoining the central square removed, where the a by b undented Aztec rectangle is defined as the union of the squares bounded by x + y ≤ b + 1, x + y ≥ b − 2a − 1, y − x ≤ b + 1, y − x ≥ −(b + 1).

We have solved these three problems, not by using Kasteleyn matrices, but by choosing a new approach, which, while much less general than Kasteleyn matrices, is better suited for problems like these three. We can summarize our approach as follows:

1. Find the number of tilings of half of a hexagon or half of a diamond, with dents at given places. This is not new: see [7] and [8].

2. Express the number of tilings of the figure as a whole as a sum of squares of the expressions obtained in the first step. The sum’s range depends on the “defects” (missing triangles or squares, fixed lozenges or dominos) given in the problem.

3. Express the sum of squares as a Hankel determinant.

4. Evaluate the Hankel determinant using continued fractions or Jacobi’s theorem.

C. Krattenthaler has been working on these problems at the same time as us, together with M. Ciucu [6] and S. Okada [20]. The solution to Problem 1 in [6] is literally orthogonal to ours: Ciucu and Krattenthaler slice the hexagon vertically rather than horizontally. More generally, Fulmek and Krattenthaler [9] have counted tilings of an (n, m, n, n, m, n) hexagon that contain an arbitrary fixed rhombus on the symmetry axis that cuts through the sides of length m. Krattenthaler and Okada’s solution [20] to Problem 2 and Krattenthaler’s solution [17] to Problem 10 are much like ours in steps 1 and 2. Thereafter, they are based on identities for Schur functions, not Hankel determinants. The work of Krattenthaler and his coauthors and our work thus complement each other.

2. From Tilings to Determinants

First we note that a necessary and sufficient condition for an (a, b, c, d, e, f) hexagon to exist is that the parameters be nonnegative integers satisfying a−d = c−f = e−b. The number of upward pointing triangles minus the number of downward pointing triangles in an (a, b, c, d, e, f) hexagon is a − d. Then since every lozenge covers one upward pointing triangle and one downward pointing triangle, an (a, b, c, d, e, f) hexagon can be tiled by lozenges only if a = d, and this implies that that the hexagon is an (a, b, c) hexagon. Moreover, if we remove a − d upward pointing triangles from an (a, b, c, d, e, f) hexagon with a ≥ d, then the remaining figure will have as many upward pointing as downward pointing triangles.

Definition 1. A (k, q, k) upper semi-hexagon is the upper half of a (k, q, k) hexagon having sides k, q, k, q +k, i.e., a symmetric trapezium. A (k, q, k) lower semi-hexagon is defined similarly. A (k, q, k) dented upper semi-hexagon is a (k, q, k) semi-hexagon with k upward pointing triangles removed from the side of length q + k. (Figure 4 shows a (3, 4, 3) dented upper semi-hexagon with dents at positions 1, 4, and 6). It will be convenient to use the term semi-hexagon for an upper semi-hexagon.

Note that a (k, q, k) semi-hexagon is the same as a (k, q, k, 0, q + k, 0) hexagon, so removing k upward pointing triangles leaves a region with as many upward as downward triangles.

Definition 2. An a by b dented Aztec rectangle is the union of the squares bounded by x + y ≤ b + 1, x + y ≥ b − 2a − 1, y − x ≤ b, y − x ≥ −(b + 1), with the squares in positions r_{0} < r_{1} < ⋯ < r_{b−1} removed from the side given by y − x ≤ b (see Figure 3).

Before proceeding with our results on tilings, we first note some facts about the power sums 1^{j} +2^{j} +⋯+m^{j} that we will need later on. We omit the straightforward proofs.

Figure 3. Dented 3 by 2 Aztec rectangle Figure 4. Dented (3, 4, 3) semi-hexagon

For any integer m and any nonnegative integer j we define S_{m}^{j} by

S_{m}^{j} = \begin{cases}1^{j} + ⋯ + m^{j}, & if m > 0; \\ 0, & if m = 0; \\ (−1)^{j+1}(0^{j} + 1^{j} + ⋯ + (−m − 1)^{j}), & if m < 0, \end{cases}

where we interpret 0^{0} as 1.

Lemma 1. The numbers S_{m}^{j} have the following properties:

(1) For any integers p and q, with p ≤ q,

p^{j} + (p + 1)^{j} + ⋯ + q^{j} = S_{q}^{j} − S_{p−1}^{j}.

(2) S_{0}^{j} = 0 for all j and S_{−1}^{j} = 0 for j > 0.

(3) For m > 0, S_{−m}^{j} = (−1)^{j+1}S_{m−1}^{j}.

(4) For m ≥ 0, S_{m}^{j} is given by the exponential generating function

∑_{j=0}^{∞} S_{m}^{j} \frac{x^{j}}{j!} = \frac{e^{x}(e^{mx} − 1)}{e^{x} − 1}

(5) S_{m}^{j} is a polynomial in m of degree j + 1, with leading coefficient 1/(j + 1).

Next we prove two known results. First, we have a closed expression for the number of tilings of semi-hexagons with given dents, first stated in this form in [7]. This is equivalent to a well-known result on the enumeration of Gelfand patterns, as noted in [7], or on column-strict plane partitions. (See Knuth [16, exercise 23, p. 71; solution, p. 593] for a proof similar to ours.)

Lemma 2. The number of tilings of a (k, q, k) semi-hexagon with dents at positions 0 ≤ r_{0} < ⋯ < r_{k−1} < q + k is

T_{k,q,r} = \frac{1}{V_{k−1}} ∏_{0≤i<j<k}(r_{j} − r_{i}),

where V_{n} = 1! 2! ⋯ n! = ∏_{0<i<j≤n}(j − i).

Proof. We proceed by induction on k. For the case k = 1, there is only one tiling, no matter where the solitary dent is. Hence the lemma holds for k = 1.

Let us now assume the lemma holds for k. Suppose we have a tiling of a (k + 1, q, k + 1) semi-hexagon with dents at 0 ≤ r_{0} < ⋯ < r_{k} < q + k + 1. If we remove the bottom layer of lozenges from the dented side, we obtain a tiling of a (k, q, k) semi-hexagon with dents at 0 ≤ t_{0} < ⋯ < t_{k−1} ≤ q + k, r_{i} ≤ t_{i} < r_{i+1}. For every such tiling of a (k, q, k) semi-hexagon with dents at those places, there is exactly one tiling of the dented (k, q, k) semi-hexagon. Hence

T_{k+1,q,r} = ∑_{r_{i}≤t_{i}<r_{i+1}} T_{k,q,t}

= ∑_{r_{i}≤t_{i}<r_{i+1}} \frac{1}{V_{k−1}} ∏_{0≤i<j<k}(t_{j} − t_{i}).

= \frac{1}{V_{k−1}} ∑_{r_{i}≤t_{i}<r_{i+1}} |t_{i}^{j}|_{0}^{k−1}

= \frac{1}{V_{k−1}} |S_{r_{i+1}−1}^{j} − S_{r_{i}−1}^{j}|_{0}^{k−1}

= \frac{1}{V_{k−1}} |S_{r_{i+1}−1}^{j} − S_{r_{0}−1}^{j}|_{0}^{k−1} ,

where S_{m}^{j} = 1^{j} + 2^{j} + ⋯ + m^{j}. In the second line of our calculations we can see that, since ∏_{0≤i<j<k}(t_{j} − t_{i}) depends only on the differences between the t_{i}’s, T_{k+1,q,r} depends only on the differences between the r_{i}’s, not on their actual values. (It is also easy to see this combinatorially.) Hence it is sufficient to prove the formula in the case r_{0} = 0. By Lemma 1, S_{m−1}^{j} − S_{−1}^{j} is a polynomial in m of degree j + 1 with leading coefficient 1/(j + 1) that vanishes at 0. Thus we can reduce the determinant |S_{r_{i+1}−1}^{j} − S_{−1}^{j}|_{0}^{k−1} to |r_{i+1}^{j+1}/(j + 1)|_{0}^{k−1} by elementary column operations. Hence

T_{k+1,q,r} = \frac{1}{V_{k−1}} |\frac{r_{i+1}^{j+1}}{j + 1}|_{0}^{k−1}

= \frac{1}{V_{k}} |r_{i+1}^{j+1}|_{0}^{k−1}

= \frac{r_{1}r_{2} ⋯ r_{k}}{V_{k}} |r_{i+1}^{j}|_{0}^{k−1}

= \frac{r_{1}r_{2} ⋯ r_{k}}{V_{k}} ∏_{1≤i<j<k+1}(r_{j} − r_{i})

= \frac{1}{V_{k}} ∏_{0≤i<j<k+1}(r_{j} − r_{i}),

since we assumed that r_{0} = 0. Then by our observation the formula holds for all values of r_{0}.

3. Tilings of Dented Aztec Rectangles

Definition 3. An a by b dented Aztec rectangle is the union of the squares bounded by x + y ≤ b + 1, x + y ≥ b − 2a − 1, y − x ≤ b, y − x ≥ −(b + 1), with the squares in positions r_{0} < r_{1} < ⋯ < r_{b−1} removed from the side given by y − x ≤ b (see Figure 3). An a by b undented Aztec rectangle is an a by b+1 dented Aztec rectangle with all squares on the side given by y − x ≤ b removed.

Our next result counts tilings of dented Aztec rectangles. Another proof can be found in [8]. Just as tilings of dented hexagons correspond to Gelfand patterns, in [8] it is shown that tilings of dented Aztec rectangles correspond to monotone triangles, and in this context, a proof of the formula can be found in [19].

Lemma 3. The number of tilings of an a by b dented Aztec rectangle with dents at 0 ≤ r_{0} ≤ ⋯ ≤ r_{b−1} ≤ a is

A_{a,b,r} = \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} ∏_{0≤i<j<b}(r_{j} − r_{i}),

where V_{n} = 1! 2! ⋯ n!.

Proof. We proceed by induction on b. First we note that if r_{i} = r_{i+1} for some i, then the lemma asserts that A_{a,b,r} = 0, which is correct. Although of no interest in itself, this case will be necessary for the induction.

If b = 1, there is only one tiling, no matter where the one dent is. (In general, the number of dents has to be equal to b for the dented Aztec rectangle to be tileable.) Hence the lemma holds for b = 1.

Let us now assume the lemma holds for b. Suppose we have a tiling of an a by b+1 Aztec rectangle with dents at 0 ≤ r_{0} < ⋯ < r_{b} ≤ a. If we remove all dominoes with one or two squares on the dented long diagonal and the adjacent short diagonal, we obtain a tiling of an a by b Aztec rectangle with dents at 0 ≤ t_{0} < ⋯ < t_{b−1} ≤ a, where r_{k} ≤ t_{k} ≤ r_{k+1}. For every such tiling of an a by b Aztec rectangle with dents at those places, there are 2^{m} tilings of the a by b + 1 dented Aztec rectangle, where m is the cardinality of {k : r_{k} < t_{k} < r_{k+1}}.

Next we show that this implies

A_{a,b+1,r} = ∑_{l∈{0,1}^{b}} ∑_{r_{k}≤t_{k}−l_{k}<r_{k+1}} A_{a,b,t}  (1)

This follows from the fact that if r_{k} < t_{k} < r_{k+1} then r_{k} ≤ t_{k} −l_{k} < r_{k+1} if l_{k} is either 0 or 1, but if t_{k} = r_{k} then this inequality holds only for l_{k} = 0 and if t_{k} = r_{k+1}, it holds only for l_{k} = 1. Thus the number of different possible values of l corresponding to a given sequence r, is 2^{m}, where m is the cardinality of {k : r_{k} < t_{k} < r_{k+1}}. Moreover, if for some l ∈ {0, 1}^{b}, t satisfies r_{k} ≤ t_{k} − l_{k} < r_{k+1} for all i, then we must have t_{0} ≤ t_{1} ≤ ⋯ ≤ t_{b−1}, so all terms A_{a,b,t} that occur in (1) either have t_{0} < ⋯ < t_{b−1} or are zero; in either case they are covered by the induction hypothesis.

Hence

A_{a,b+1,r} = ∑_{l∈{0,1}^{b}} ∑_{r_{k}≤t_{k}−l_{k}<r_{k+1}} A_{a,b,t}

= \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} ∑_{l∈\{0,1\}^{b}} ∑_{r_{k}+l_{k}≤t_{k}<r_{k+1}+l_{k}} ∏_{0≤i<j<b}(t_{j} − t_{i})  (2)

= \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} ∑_{l∈\{0,1\}^{b}} ∑_{r_{k}+l_{k}≤t_{k}<r_{k+1}+l_{k}} |t_{i}^{j}|_{0}^{b−1}

= \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} ∑_{l∈\{0,1\}^{b}} |S_{r_{i+1}+l_{i}−1}^{j} − S_{r_{i}+l_{i}−1}^{j}|_{0}^{b−1} ,

where S_{m}^{j} = 1^{j} +2^{j} +⋯+m^{j}. Now if u(i, j, k) is any function defined for 0 ≤ i, j < b, 0 ≤ k ≤ 1, then since a determinant is a linear function of its rows, we have

∑_{l∈{0,1}^{b}} |u(i, j, l_{i})|_{0}^{b−1} = |u(i, j, 0) + u(i, j, 1)|_{0}^{b−1} .

Thus

A_{a,b+1,r} = \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} |S_{r_{i+1}−1}^{j} + S_{r_{i+1}}^{j} − (S_{r_{i}−1}^{j} + S_{r_{i}}^{j})|_{0}^{b−1}

= \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} |(S_{r_{i+1}−1}^{j} + S_{r_{i+1}}^{j}) − (S_{r_{0}−1}^{j} + S_{r_{0}}^{j})|_{0}^{b−1} .

By (2), we can see that, since ∏_{0≤i<j<b}(t_{j} − t_{i}) depends only on the differences between the t_{k}’s, A_{a,b+1,r} depends only on the differences between the r_{k}’s, not on their actual values. Hence we may assume that r_{0} = 0. Since S_{m−1}^{j}+S_{m}^{j}−(S_{−1}^{j}+S_{0}^{j}) = S_{m−1}^{j} +S_{m}^{j} −S_{−1}^{j} is a polynomial in m of degree j +1 with leading coefficient 2/(j +1)

that vanishes at 0, we can reduce the determinant |(S_{r_{i+1}−1}^{j} + S_{r_{i+1}}^{j}) − S_{−1}^{j}|_{0}^{b−1} to |2r_{i+1}^{j+1}/(j + 1)|_{0}^{b−1} by elementary column operations. Hence

A_{a,b+1,r} = \frac{2^{\frac{b(b−1)}{2}}}{V_{b−1}} |\frac{2r_{i+1}^{j+1}}{j + 1} |_{0}^{b−1}

= \frac{2^{\frac{(b+1)b}{2}}}{V_{b}} |r_{i+1}^{j+1}|_{0}^{b−1}

= \frac{2^{\frac{(b+1)b}{2}} r_{1}r_{2} ⋯ r_{b}}{V_{b}} |r_{i+1}^{j}|_{0}^{b−1}

= \frac{2^{\frac{(b+1)b}{2}} r_{1}r_{2} ⋯ r_{b}}{V_{b}} ∏_{1≤i<j<b+1}(r_{j} − r_{i})

= \frac{2^{\frac{(b+1)b}{2}}}{V_{b}} ∏_{0≤i<j<b+1}(r_{j} − r_{i}).

4. From hexagons to Determinants

We now compute the number of tilings of a (k, q, k) hexagon with restrictions on where vertical lozenges may cross the horizontal symmetry axis.

Proposition 4. Let L be a subset of {0, 1, …, k+q −1}. Then the number of tilings of a (k, q, k) hexagon in which the set of indices of the vertical lozenges crossing the q + k-long symmetry axis is a subset of L is

\frac{1}{V_{k−1}^{2}} |∑_{l∈L} l^{i+j}|_{0}^{k−1}.

Proof. We first recall that by the Binet-Cauchy theorem [11, p. 9], if M is any k by n matrix and M^{t} is its transpose, then the determinant of MM^{t} is equal to the sum of the squares of the k by k minors of M.

The number of tilings of a (k, q, k) hexagon in which the indices of the vertical lozenges crossing the q + k-long symmetry axis are r_{0} < r_{1} < ⋯ < r_{k−1} is clearly

T_{k,q,r}^{2} = \frac{1}{V_{k−1}^{2}} (|r_{j}^{i}|_{0}^{k−1})^{2}.

Thus the number of tilings to be counted is the sum of T_{k,q,r}^{2} over all r_{0} < r_{1} < ⋯ < r_{k−1} where each r_{j} is in L. Now suppose that the elements of L are l_{0} < l_{1} < ⋯ < l_{n−1} and let M be the k by n matrix (l_{j}^{i})_{0≤i<k, 0≤j<n}. Then by the Binet-Cauchy theorem,

∑_{r} T_{k,q,r}^{2} = \frac{1}{V_{k−1}^{2}} |MM^{t}| = \frac{1}{V_{k−1}^{2}} |∑_{l∈L} l^{i+j}|_{0}^{k−1}.

Note that since the numbers T_{k,q,r} depend only on the differences of the r_{i}, the determinant in Proposition 4 depends only on the differences of the elements of L; thus we may shift all the elements of L by the same amount without changing the determinant. This observation will be useful later on:

Lemma 5. For any finite set L of numbers and any number u,

|∑_{l∈L} l^{i+j}|_{0}^{k−1} = |∑_{l∈L}(l + u)^{i+j}|_{0}^{k−1} .

Proposition 6. The number of tilings of a (k, 2n + 1 − k, k, k + 1, 2n − k, k + 1) hexagon with a triangle removed below the center of the horizontal line dividing the two “hemispheres” is

\frac{1}{V_{k−1}V_{k}} |(1 + (−1)^{i+j})(∑_{l=1}^{n} l^{i+j+1})|_{0}^{k−1}.

Proof. If we cut such a tiled hexagon into two parts by the horizontal segment between the two angles formed by a side of length k and a side of length k + 1, and then remove the lozenges that are bisected by this line, we obtain a tiling of a (k, 2n + 1 − k, k) upper semi-hexagon with dents at points r_{0} < r_{1} < ⋯ < r_{k−1}, and a tiling of a (k + 1, 2n − k, k + 1) lower semi-hexagon with dents at points r_{0} < r_{1} < ⋯ < r_{k−1} and at the center. Since the formula in Lemma 2 depends only on the differences among the r_{i}, we can make zero lie on the center of horizontal line dividing the two “hemispheres” of the hexagon. Thus, we have −n ≤ r_{0} < r_{1} < ⋯ < r_{k−1} ≤ n, r_{i} ≠ 0.

The number of tilings of the upper semi-hexagon is

\frac{1}{V_{k−1}} ∏_{0≤i<j<k}(r_{j} − r_{i}),

and the number of tilings of the lower semi-hexagon is

\frac{1}{V_{k}} ∏_{0≤i<j<k}(r_{j} − r_{i}) ∏_{0≤i<k} |r_{i}|.

Hence the number of tilings of the hexagon for given −n ≤ r_{0} < ⋯ < r_{k−1} ≤ n is

\frac{1}{V_{k−1}V_{k}} (|r_{j}^{i}|_{0}^{k−1})^{2} ∏_{0≤i<k} |r_{i}| = \frac{1}{V_{k−1}V_{k}} (||r_{j}|^{1/2}r_{j}^{i}|_{0}^{k−1})^{2}.

(Note that this vanishes whenever r_{j} = 0 for some j.)

Now let M be the k by 2n + 1 matrix (|j|^{\frac{1}{2}} j^{i})_{0≤i<k,−n≤j≤n}. Then by the Binet-Cauchy theorem, the number of tilings of the hexagon is

∑_{−n≤r_{0}<···<r_{n−1}≤n} \frac{1}{V_{k−1}V_{k}} (||r_{j}|^{1/2}r_{j}^{i}|_{0}^{k−1})^{2} = \frac{1}{V_{k−1}V_{k}} |MM^{t}|

= \frac{1}{V_{k−1}V_{k}} | ∑_{−n≤l≤n} |l|l^{i+j}|_{0}^{k−1}

= \frac{1}{V_{k−1}V_{k}} |(1 + (−1)^{i+j}) ∑_{l=1}^{n} l^{i+j+1}|_{0}^{k−1} .

5. From Aztec rectangles to determinants

For our next result, we use the following lemma, which is analogous to the Binet-Cauchy theorem.

Lemma 7. Let U = (u_{ij}) be a 2k by k matrix, with rows indexed from 0 to 2k − 1 and columns from 0 to k − 1. For each k-subset A of {0, 1, …, 2k − 1}, let U_{A} be the k by k minor of U corresponding to the rows in A and all columns, and let Ā be the complement of A in {0, 1, …, 2k − 1}. Then

∑_{\begin{matrix}A⊆\{0,... ,2k−1\} \\ |A|=k \end{matrix}} U_{A}UĀ = 2^{k} |u_{2i,j}|_{0}^{k−1} |u_{2i+1,j}|_{0}^{k−1} .

Proof. The lemma is a direct consequence of a result of Propp and Stanley [21, Theorem 2]. More precisely, the lemma follows from their result when we sum over all possibilities for A^{∗}. (As noted by Propp and Stanley, their result is a special case of a theorem of Sylvester [25].)

Proposition 8. The number of tilings of an a by b undented Aztec rectangle, where a < b ≤ 2a + 1, and b = 2k + 1, with squares with indices r_{0} < r_{1} < ⋯ < r_{b−a−1} missing from a diagonal of length a + 1 going through the central square, is

\frac{2^{k^{2}+a}}{V_{k}^{2}} ( ∏_{0≤j<i<2k+1−a}(r_{i} − r_{j}) ∏_{\begin{matrix}0≤i<2a−2k \\ 0≤j<2k+1−a \end{matrix}} |t_{i} − r_{j}|) |t_{2i}^{j}|_{0}^{a−k−1} |t_{2i+1}^{j}|_{0}^{a−k−1} ,

where t_{0} < t_{1} < ⋯ < t_{2a−2k−1} are the elements of {0, 1, ⋯ a} − {r_{0}, r_{1}, …, r_{2k−a}}.

Proof. Every tiling of the undented Aztec rectangle with missing squares can be subdivided into a tiling of two a by k + 1 dented Aztec rectangles with sets of dents A and B of the form A = R ∪ P and B = R ∪ (T − P), where R = {r_{0}, r_{1}, …, r_{2k−a}}, T = {0, 1, ⋯ a} − R and P is some subset of T of size a − k. (See figure 5.) Let Figure 5. From missing squares to dents

t_{0} < t_{1} < ⋯ < t_{2a−2k−1} be the elements of T. Then the number of tilings of the undented Aztec rectangle with missing squares is

\frac{2^{k(k+1)}}{V_{k}^{2}} ∏_{0≤j<i<2k+1−a}(r_{i} − r_{j}) ∏_{\begin{matrix}0≤i<2a−2k \\ 0≤j<2k+1−a \end{matrix}} |t_{i} − r_{j}|

× ∑_{\begin{matrix}P ⊆T \\ |P |=a−k \end{matrix}} ∏_{\begin{matrix}t_{0},t_{1}∈P \\ t_{0}<t_{1} \end{matrix}}(t_{1} − t_{0}) ∏_{\begin{matrix}t_{0},t_{1}∈T −P \\ t_{0}<t_{1} \end{matrix}}(t_{1} − t_{0}),

which, written with determinants instead of products, is

\frac{2^{k(k+1)}}{V_{k}^{2}} ( ∏_{0≤j<i<2k+1−a}(r_{i} − r_{j}) ∏_{\begin{matrix}0≤i<2a−2k \\ 0≤j<2k+1−a \end{matrix}} |t_{i} − r_{j}|) ∑_{\begin{matrix}P ⊆T \\ |P |=a−k \end{matrix}} |p_{i}^{j}|_{0}^{a−k−1} |q_{i}^{j}|_{0}^{a−k−1} ,

where p_{0} < p_{1} < ⋯ < p_{a−k−1} are the elements of P and q_{0} < q_{1} < ⋯ < q_{a−k−1} are the elements of T − P. Applying Lemma 7 yields the theorem.

We can prove the following proposition in exactly the same way.

Proposition 9. The number of tilings of an a by b undented Aztec rectangle, a < b ≤ 2a + 1, b = 2k, with squares with indices r_{0} < r_{1} < ⋯ < r_{b−a−1} missing from a diagonal of length a + 1 touching the central square is

\frac{2^{k^{2}−k+a}}{V_{k−1}V_{k}} ( ∏_{0≤j<i<2k+1−a}(r_{i} − r_{j}) ∏_{\begin{matrix}0≤i<2a−2k+1 \\ 0≤j<2k−a \end{matrix}} |t_{i} − r_{j}|) |t_{2i}^{j}|_{0}^{a−k} |t_{2i+1}^{j}|_{0}^{a−k−1} ,

where t_{0} < t_{1} < ⋯ < t_{2a−2k} are the elements of {0, 1, ⋯ a} − {r_{0}, r_{1}, …, r_{2k−a−1}}.

the electronic journal of combinatorics 6 (1999), #R16 12

6. Computing Determinants of Aztec Rectangles: A Special Case We can now solve Problem 3 using Proposition 9 with a = 2k−1, b = 2k, r_{0} = k−1.

The number of tilings is

\frac{2^{k^{2}−k+a}}{V_{k−1}V_{k}} ( ∏_{\begin{matrix}0≤i<2a−2k+1 \\ 0≤j<2k−a \end{matrix}} |t_{i} − r_{j}|) |t_{2i}^{j}|_{0}^{a−k} |t_{2i+1}^{j}|_{0}^{a−k−1}

= \frac{2^{k^{2}+k−1}}{V_{k−1}V_{k}} ( ∏_{0≤i<2k−1} |t_{i} − (k − 1)|) |t_{2i}^{j}|_{0}^{k−1} |t_{2i+1}^{j}|_{0}^{k−2}

= \frac{2^{k^{2}+k−1}}{V_{k−1}V_{k}} (k − 1)! k! |t_{2i}^{j}|_{0}^{k−1} |t_{2i+1}^{j}|_{0}^{k−2}

= \frac{2^{k^{2}+k−1}}{V_{k−2}V_{k−1}} ∏_{0≤j_{0}<j_{1}<k}(t_{2j_{1}} − t_{2j_{0}}) ∏_{0≤j_{0}<j_{1}<k−1}(t_{2j_{1}+1} − t_{2j_{0}+1}).

For k = 2q, we have

∏_{0≤j_{0}<j_{1}<k}(t_{2j_{1}} − t_{2j_{0}})

= ∏_{0≤j_{0}<j_{1}<q}(2j_{1} − 2j_{0}) ∏_{0≤j_{0}<j_{1}<q}((2q + 1 + 2j_{1}) − (2q + 1 + 2j_{0}))

× ∏_{0≤j_{0},j_{1}<q}((2q + 1 + 2j_{1}) − (2j_{0}))

= (2^{q−1}4^{q−2} ⋯ (2q − 2))^{2}

× 3 · 5^{2} ⋯ (2q − 1)^{q−1}(2q + 1)^{q}(2q + 3)^{q−1} ⋯ (4q − 1)

and

∏_{0≤j_{0}<j_{1}<k−1}(t_{2j_{1}+1} − t_{2j_{0}+1})

= ∏_{0≤j_{0}<j_{1}<q−1}((2j_{1} + 1) − (2j_{0} + 1)) ∏_{0≤j_{0}<j_{1}<q}((2q + 2j_{1}) − (2q + 2j_{0}))

× ∏_{\begin{matrix}0≤j_{0}<q−1 \\ 0≤j_{1}<q \end{matrix}}((2q + 2j_{1}) − (2j_{0} + 1))

= (2^{q−2}4^{q−3} ⋯ (2q − 4))(2^{q−1}4^{q−2} ⋯ (2q − 2))

× 3 · 5^{2} ⋯ (2q − 1)^{q−1}(2q + 1)^{q−1} ⋯ (4q − 3).

the electronic journal of combinatorics 6 (1999), #R16 13

For k = 2q + 1, we have

∏_{0≤j_{0}<j_{1}<k}(t_{2j_{1}}−t_{2j_{0}})

= ∏_{0≤j_{0}<j_{1}<q}(2j_{1} − 2j_{0}) ∏_{0≤j_{0}<j_{1}<q+1}((2q + 1 + 2j_{1}) − (2q + 1 + 2j_{0}))

× ∏_{\begin{matrix}0≤j_{0}<q \\ 0≤j_{1}<q+1 \end{matrix}}((2q + 1 + 2j_{1}) − (2j_{0}))

= (2^{q−1}4^{q−2} ⋯ (2q − 2))(2^{q}4^{q−1} ⋯ (2q))

× 3 · 5^{2} ⋯ (2q − 1)^{q−1}(2q + 1)^{q}(2q + 3)^{q} ⋯ (4q + 1)

and

∏_{0≤j_{0}<j_{1}<k−1}(t_{2j_{1}+1} − t_{2j_{0}+1})

= ∏_{0≤j_{0}<j_{1}<q}((2j_{1} + 1) − (2j_{0} + 1)) ∏_{0≤j_{0}<j_{1}<q}((2q + 2 + 2j_{1}) − (2q + 2 + 2j_{0}))

× ∏_{0≤j_{0},j1<q}((2q + 2 + 2j_{1}) − (2j_{0} + 1))

= (2^{q−1}4^{q−2} ⋯ (2q − 2))^{2}

× 3 · 5^{2} ⋯ (2q − 1)^{q−1}(2q + 1)^{q}(2q + 3)^{q−1} ⋯ (4q − 1)

Therefore, for k = 2q the number of tilings is

\frac{2^{(2q)^{2}+2q−1}}{V_{2q−2}V_{2q−1}} 2^{4q−5}4^{4q−9} ⋯ (2q − 2)^{3}

× 3^{2}5^{4} ⋯ (2q − 1)^{2q−2}(2q + 1)^{2q−1}(2q + 3)^{2q−3} ⋯ (4q − 3)^{3}(4q − 1),

and for k = 2q + 1 the number of tilings is

\frac{2^{(2q+1)^{2}+(2q+1)−1}}{V_{2q−1}V_{2q}} 2^{4q−3}4^{4q−7} ⋯ (2q − 2)^{5}(2q)

× 3^{2}5^{4} ⋯ (2q − 1)^{2q−2}(2q + 1)^{2q}(2q + 3)^{2q−1} ⋯ (4q − 1)^{3}(4q + 1).

7. Computing Determinants: Hexagons

In this section we solve Propp’s Problem 1, and more generally, we count tilings of a (2m − 1, 2n, 2m − 1) or (2m, 2n − 1, 2m) hexagon with a vertical lozenge at the center. (A (k, q, k) hexagon has a central vertical lozenge if and only if k + q is odd.)

Lemma 10. The number of tilings of a (2m − 1, 2n, 2m − 1) hexagon with a vertical lozenge in the center is

\frac{1}{V_{2m−2}^{2}} |(1 + (−1)^{i+j})S_{m+n−1}^{i+j}|_{1}^{2m−2} .

The number of tilings of a (2m, 2n − 1, 2m) hexagon with a vertical lozenge in the center is

\frac{1}{V_{2m−1}^{2}} |(1 + (−1)^{i+j})S_{m+n−1}^{i+j}|_{1}^{2m−1} .

Proof. By Proposition 4, the number of tilings of a (2m − 1, 2n, 2m − 1) hexagon is

\frac{1}{V_{2m−2}^{2}} | ∑_{l=0}^{2m+2n−2} l^{i+j}|_{0}^{2m−2}.

By Lemma 5, this determinant is equal to

| ∑_{l=−m−n+1}^{m+n−1} l^{i+j}|_{0}^{2m−2} = |(1 + (−1)^{i+j})S_{m+n−1}^{i+j} + δ_{i+j}|_{0}^{2m−2}

= |(1 + (−1)^{i+j})S_{m+n−1}^{i+j}|_{0}^{2m−2} + |(1 + (−1)^{i+j})S_{m+n−1}^{i+j}|_{1}^{2m−2} ,

where δ_{k} is 1 if k = 0 and is 0 otherwise.

It also follows from Proposition 4 that the number of tilings of a (2m−1, 2n, 2m−1) hexagon that do not have a vertical lozenge in the center is

\frac{1}{V_{2m−2}^{2}} | ∑_{\begin{matrix}0≤l≤2m+2n−2 \\ l≠m+n−1 \end{matrix}} l^{i+j}|_{0}^{2m−2}.

By Lemma 5 this determinant is equal to

| ∑_{\begin{matrix}−m−n+1≤l≤m+n−1 \\ l≠0 \end{matrix}} l^{i+j}|_{0}^{2m−2} = |(1 + (−1)^{i+j})S_{m+n−1}^{i+j}|_{0}^{2m−2} .

We find the number of tilings that do have a vertical lozenge in the center by subtracting from the total number of tilings the number of tilings that do not have a lozenge in the center.

The formula for (2m, 2n − 1, 2m) hexagons is derived similarly.

As a first step in evaluating the determinants in Lemma 10, we evaluate the determinant |S_{p}^{i+j}|_{0}^{k−1}. It is interesting to note that this determinant was evaluated by Zavrotsky [28] in the course of his research on minimum square sums, and we follow his proof.

Lemma 11.

\begin{aligned}|S_{p}^{i+j}|_{0}^{k−1} & = \frac{V_{k−1}^{4}}{V_{2k−1}} (p − k + 1) ⋯ (p − 1)^{k−1}p^{k}(p + 1)^{k−1} ⋯ (p + k − 1) \\ & = \frac{V_{p+k−1}V_{p−k−1}V_{k−1}^{4}}{V_{p−1}^{2}V_{2k−1}} , \end{aligned}

where S_{p}^{i} = 1^{i} + 2^{i} + ⋯ + p^{i} and V_{p} = 1! 2! ⋯ p!.

Proof (Zavrotsky [28]). If p is a positive integer, we can express the matrix (S_{p}^{i+j})_{0}^{k−1} as the product of a k by p matrix and a p by k matrix, as in the proof of Proposition 4. Since the rank of an p by k matrix is at most p, the rank of the matrix (S_{p}^{i+j})_{0}^{k−1} is at most p. Moreover, this holds also for p = 0.

Now let (a_{i,j}(λ))_{0}^{k−1} be a matrix whose entries are polynomials in λ. It is known [10, p. 17] that if, for some value λ_{0} of λ, the matrix (a_{i,j}(λ_{0}))_{0}^{k−1} has rank at most m, where m ≤ k, then |a_{i,j}(λ)|_{0}^{k−1} is divisible by (λ − λ_{0})^{k−m} as a polynomial in λ.

By Lemma 1, there is a polynomial S_{λ}^{i} in λ whose value at λ = p is S_{p}^{i}. Since the

rank of (S_{m}^{i+j})_{0}^{k−1} is at most m, |S_{λ}^{i+j}|_{0}^{k−1} is divisible by (λ − m)^{k−m} for 0 ≤ m ≤ k.

Since S_{−m}^{i} = (−1)^{i+1}S_{m−1}^{i} when i > 0, it follows that the rank of (S_{−m}^{i+j})_{0}^{k−1} is at most one more than the rank of (S_{m−1}^{i+j})_{0}^{k−1}; i.e., at most m. Thus |S_{λ}^{i+j}|_{0}^{k−1} is divisible by (λ + m)^{k−m} for 1 ≤ m ≤ k.

Since S_{λ}^{i} is a polynomial in λ of degree i + 1, |S_{λ}^{i+j}|_{0}^{k−1} is a polynomial in λ of

degree k^{2}. Hence |S_{λ}^{i+j}|_{0}^{k−1} is equal to a constant times

(λ − k + 1) ⋯ (λ − 1)^{k−1}λ^{k}(λ + 1)^{k−1}(λ + 2)^{k−2} ⋯ (λ + k − 1).

Since S_{λ}^{i} has leading coefficient 1/(i + 1), and, by [3, p. 425], the determinant |1/(i + j + 1)|_{0}^{k−1} (a Hilbert determinant) is equal to V_{k−1}^{4}/V_{2k−1}, we may compare leading coefficients and conclude that the constant is V_{k−1}^{4}/V_{2k−1}.

Corollary 12. The number of tilings of a (k, q, k) hexagon is

\frac{V_{2k+q−1}V_{q−1}V_{k−1}^{2}}{V_{k+q−1}^{2}V_{2k−1}} .

In particular, the number of tilings of a (2m − 1, 2n, 2m − 1) hexagon is

\frac{V_{4m+2n−3}V_{2n−1}V_{2m−2}^{2}}{V_{2m+2n−2}^{2}V_{4m−3}}

and the number of tilings of a (2m, 2n − 1, 2m) hexagon is

\frac{V_{4m+2n−2}V_{2n−2}V_{2m−1}^{2}}{V_{2m+2n−2}^{2}V_{4m−1}} .

Proof. By Proposition 4 and Lemma 5, the number of tilings of a (k, q, k) hexagon is

\frac{1}{V_{k−1}^{2}} |S_{k+q}^{i+j}|_{0}^{k−1} .

The result then follows from Lemma 11.

It is also possible, as shown in [7], to derive the formula for the number of tilings of an (a, b, c) hexagon directly from Lemma 2.

Next we prove a general theorem on Hankel determinants that allows us to evaluate the determinants in Lemma 10.

Proposition 13. Let {a_{i}}_{i=0}^{∞} be a sequence, and let

H_{s}(k) = |a_{(i+j+s)/2}|_{0}^{k−1} ,

for k ≥ 1, with H_{s}(0) = 1, where we take a_{i} to be 0 if i is not an integer. Define λ_{k} inductively by

H_{0}(k + 1) = λ_{0}^{k+1}λ_{1}^{k} ⋯ λ_{k},

so that λ_{0} = H_{0}(1) = a_{0} and

λ_{k} = \frac{H_{0}(k − 1)H_{0}(k + 1)}{H_{0}(k)^{2}}

for k ≥ 1. Then

H_{2}(k) = λ_{0}^{−1}H_{0}(k + 1) ∑_{j=0}^{⌊k/2⌋} ∏_{i=1}^{j} \frac{λ_{2i−1}}{λ_{2i}}  (3)

Proof. Define M_{r}(k) by

M_{r}(k) = |a_{i+j+r}|_{0}^{k−1} .

It is easy to see that

H_{2r}(k) = M_{r}(⌈k/2⌉)M_{r+1}(⌊k/2⌋).  (4)

Then

\frac{H_{2}(2m + 1)}{H_{2}(2m)} = \frac{M_{1}(m + 1)}{M_{1}(m)} = \frac{H_{0}(2m + 2)}{H_{0}(2m + 1)}.

Thus it suffices to prove (3) for k = 2m.

Since (3) holds for k = 0, to prove it for even k we need only show that for m ≥ 1,

\frac{H_{2}(2m)}{H_{0}(2m + 1)} − \frac{H_{2}(2m − 2)}{H_{0}(2m − 1)} = λ_{0}^{−1} ∏_{i=1}^{m} \frac{λ_{2i−1}}{λ_{2i}} .

Using (4), we may write the identity to be proved as

\frac{M_{2}(m)}{M_{0}(m + 1)} − \frac{M_{2}(m − 1)}{M_{0}(m)} = \frac{λ_{1}λ_{3} ⋯ λ_{2m−1}}{λ_{0}λ_{2} ⋯ λ_{2m}} .  (5)

To prove (5), we use Jacobi’s identity [12, pp. 594–595],

(M_{1}(m))^{2} − M_{0}(m)M_{2}(m) + M_{0}(m + 1)M_{2}(m − 1) = 0.

Dividing both sides by M_{0}(m)M_{0}(m + 1), we may rewrite Jacobi’s identity as

\frac{M_{2}(m)}{M_{0}(m + 1)} − \frac{M_{2}(m − 1)}{M_{0}(m)} = \frac{M_{1}(m)^{2}}{M_{0}(m)M_{0}(m + 1)}.  (6)

To complete the proof we need to express the right side of (6) in terms of the λ_{i}. We have

\frac{M_{0}(m)}{M_{0}(m − 1)} = \frac{H_{0}(2m − 1)}{H_{0}(2m − 2)} = λ_{2m−2} \frac{H_{0}(2m − 2)}{H_{0}(2m − 3)}

= λ_{2m−2}λ_{2m−3} \frac{H_{0}(2m − 3)}{H_{0}(2m − 4)} = λ_{2m−2}λ_{2m−3} \frac{M_{0}(m − 1)}{M_{0}(m − 2)}.

Since M_{0}(0) = 1 and M_{0}(1) = λ_{0}, this gives

\frac{M_{0}(m)}{M_{0}(m − 1)} = λ_{0}λ_{1} ⋯ λ_{2m−2},

and thus

M_{0}(m) = λ_{0}^{m}(λ_{1}λ_{2})^{m−1} ⋯ (λ_{2m−3}λ_{2m−2})

Similarly, we can show that

M_{1}(m) = (λ_{0}λ_{1})^{m} ⋯ (λ_{2m−4}λ_{2m−3})^{2}(λ_{2m−2}λ_{2m−1}).

Making these substitutions in the right side of (6) yields (5), completing the proof.

Note. There is a simple combinatorial proof of Proposition 13 in which the determinant is interpreted as counting nonintersecting paths; see Viennot [26, Chapter IV].

We now apply Proposition 13 to evaluate the determinant |(1 + (−1)^{i+j})S_{p}^{i+j}|_{1}^{k}.

Proposition 14. The determinant |(1 + (−1)^{i+j})S_{p}^{i+j}|_{1}^{k} is equal to

\frac{1}{2p + 1} \frac{V_{2p+k+1}V_{2p−k−1}V_{k}^{4}}{V_{2p}^{2}V_{2k+1}} ∑_{j=0}^{⌊k/2⌋} \frac{(\frac{1}{2})_{j}^{2} (\frac{5}{4})_{j} (−p)_{j} (p + 1)_{j}}{(1)_{j}^{2} (\frac{1}{4})_{j} (\frac{3}{2} + p)_{j} (\frac{1}{2} − p)_{j}} ,

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

Proof. Let us set a_{i} = 2S_{p}^{2i} + δ_{i}. Then

a_{i/2} = \begin{cases}2S_{p}^{i} + δ_{i/2}, & if i is even \\ 0, & if i is odd \end{cases} = (1 + (−1)^{i})S_{p}^{i} + δ_{i}.

With the notation of Proposition 13, the determinant to be evaluated is

|a_{(i+j)/2}|_{1}^{k} = |a_{(i+j+2)/2}|_{0}^{k−1} = H_{2}(k).

Thus by Proposition 13 we can express the value of this determinant in terms of the values of the corresponding determinants H_{0}(k).

We have

(1 + (−1)^{i})S_{p}^{i} + δ_{i} = ∑_{l=−p}^{p} l^{i},

so by Lemma 5, the determinant H_{0}(k) = |a_{(i+j)/2}|_{0}^{k−1} is equal to |S_{2p+1}^{i+j}|_{0}^{k−1}. This determinant may be evaluated by Lemma 11, which gives

H_{0}(k) = \frac{V_{2p+k}V_{2p−k}V_{k−1}^{4}}{V_{2p}^{2}V_{2k−1}} .

Therefore, with λ_{k} as in Proposition 13, we have λ_{0} = a_{0} = 2S_{p}^{0} = 2p + 1, and for k > 0,

λ_{k} = \frac{k^{2}}{4} \frac{(2p + k + 1)(2p − k + 1)}{(2k − 1)(2k + 1)}.

Thus by Proposition 13, we have

H_{2}(k) = λ_{0}^{−1}H_{0}(k + 1) ∑_{j=0}^{⌊k/2⌋} ∏_{i=1}^{j} \frac{λ_{2i−1}}{λ_{2i}}

= \frac{1}{2p + 1} \frac{V_{2p+k+1}V_{2p−k−1}V_{k}^{4}}{V_{2p}^{2}V_{2k+1}} ∑_{j=0}^{⌊k/2⌋} \frac{(\frac{1}{2})_{j}^{2} (\frac{5}{4})_{j} (−p)_{j} (p + 1)_{j}}{(1)_{j}^{2} (\frac{1}{4})_{j} (\frac{3}{2} + p)_{j} (\frac{1}{2} − p)_{j}} ,

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

We can now combine Lemma 10 with the determinant evaluation of Proposition 14 to count tilings of hexagons with a vertical lozenge in the center:

Theorem 15. The number of tilings of a (2m−1, 2n, 2m−1) hexagon with a vertical lozenge in the center is

\frac{V_{4m+2n−3}V_{2n−1}V_{2m−2}^{2}}{(2m + 2n − 1)V_{2m+2n−2}^{2}V_{4m−3}} ∑_{j=0}^{m−1} \frac{(\frac{1}{2})_{j}^{2} (\frac{5}{4})_{j} (1 − m − n)_{j} (m + n)_{j}}{(1)_{j}^{2} (\frac{1}{4})_{j} (\frac{1}{2} + m + n)_{j} (\frac{3}{2} − m − n)_{j}} ,

and the number of tilings of a (2m, 2n − 1, 2m) hexagon with a vertical lozenge in the center is

\frac{V_{4m+2n−2}V_{2n−2}V_{2m−1}^{2}}{(2m + 2n − 1)V_{2m+2n−2}^{2}V_{4m−1}} ∑_{j=0}^{m−1} \frac{(\frac{1}{2})_{j}^{2} (\frac{5}{4})_{j} (1 − m − n)_{j} (m + n)_{j}}{(1)_{j}^{2} (\frac{1}{4})_{j} (\frac{1}{2} + m + n)_{j} (\frac{3}{2} − m − n)_{j}} .

To finish the solution of Propp’s Problem 1, we need only evaluate the sum in Theorem 15 in the case m = n. To do this we use the Wilf-Zeilberger (WZ) method Lemma 16.

∑_{i=0}^{n−1} \frac{(\frac{1}{2})_{i}^{2} (\frac{5}{4})_{i} (1 − 2n)_{i} (2n)_{i}}{(1)_{i}^{2} (\frac{1}{4})_{i} (\frac{1}{2} + 2n)_{i} (\frac{3}{2} − 2n)_{i}} = \frac{4n − 1}{3}.

Proof. Let

Q(n, i) = \frac{1}{4n − 1} \frac{(\frac{1}{2})_{i}^{2} (\frac{5}{4})_{i} (1 − 2n)_{i} (2n)_{i}}{(1)_{i}^{2} (\frac{1}{4})_{i} (\frac{1}{2} + 2n)_{i} (\frac{3}{2} − 2n)_{i}} .

We want to prove that

∑_{i=0}^{n−1} Q(n, i) = \frac{1}{3}.

Since this identity is clearly true for n = 1, it is sufficient to prove that

∑_{i=0}^{n} Q(n + 1, i) − ∑_{i=0}^{n−1} Q(n, i) = 0

for n > 1.

To apply the WZ method, we must first find a function U(n, i) such that

U(n, i + 1) − U(n, i) = Q(n + 1, i) − Q(n, i).  (7)

With the help of Maple, we find that if we set

U(n, i) = \frac{i^{2} (2i + 1 − 4n) (1 + 4n) (8n^{2} + 4n − 2i^{2} + i + 1)}{(4i + 1) (2i + 1 + 4n) (i − 2n) (i − 1 − 2n) (2n + 1) n}Q(n, i)

then (7) is satisfied. (Once we have this formula for U(n, i), the verification of (7) is straightforward.)

Next, we sum identity (7) on i from 0 to n − 1 and add Q(n + 1, n) to both sides. The left side telescopes, and we get

Q(n + 1, n) + U(n, n) − U(n, 0) = ∑_{i=0}^{n} Q(n + 1, i) − ∑_{i=0}^{n−1} Q(n, i).  (8)

But U(n, 0) = 0 and we can easily check that Q(n + 1, n) + U(n, n) = 0. Thus the left side of (8) is 0, hence so is the right side.

Note. The sum in Lemma 16 is a partial sum of a special case of Dougall’s verywell-poised _{5}F_{4}(1) sum [4, p. 25, eq. (3)]: if the upper limit of summation were 2n−1 instead of n−1, we would have a special case of Dougall’s theorem. It is interesting to note that in Ciucu and Krattenthaler’s solution of Propp’s Problem 1, they used an analogous evaluation of a partial sum of the Pfaff-Saalschütz theorem [6, eq. (2.1)].

We can now finish our solution to Propp’s Problem 1:

Theorem 17. In a (2n − 1, 2n, 2n − 1) or (2n, 2n − 1, 2n) hexagon, the two central triangles are covered by a lozenge in exactly one-third of the tilings.

Proof. We compare the result of setting m = n in Corollary 12 with the result of setting m = n in 15 and evaluating the sum by Lemma 16.

8. Computing More Determinants

By Proposition 6, evaluating the Hankel determinant |(1 + (−1)^{i+j})S_{n}^{i+j+1}|_{0}^{k−1} will solve Propp’s Problem 2. To do this, we use the close connection between Hankel determinants and continued fractions that was implicit in our proof of Proposition 13. The following lemma is equivalent to [13, Thm. 7.2].

Lemma 18. Let {a_{i}}_{i=0}^{∞} be a sequence, and suppose that the generating function for the a_{i} has the continued fraction

∑_{i=0}^{∞} a_{i}x^{i} = \frac{λ_{0}}{1 − \frac{λ_{1}x}{1 − \frac{λ_{2}x}{1 − \frac{λ_{3}x}{1 − ⋯}}}}

Then

|a_{(i+j)/2}|_{0}^{k−1} = λ_{0}^{k}λ_{1}^{k−1} ⋯ λ_{k−1},

where we take a_{r} to be 0 if r is not an integer.

By Lemma 18, if we can find the continued fraction for

∑_{j=0}^{∞}(1 + (−1)^{j})S_{n}^{j+1}x^{j/2} = ∑_{i=0}^{∞} 2S_{n}^{2i+1}x^{i},

then we can evaluate the corresponding Hankel determinant.

The continued fraction in question is given by the following formula, which we prove in the next section.

Proposition 19.

∑_{i=0}^{∞} 2S_{n}^{2i+1}x^{i} = \frac{μ_{0}}{1 − \frac{μ_{1}x}{1 − \frac{μ_{2}x}{1 − ⋯}}},

where

μ_{0} = n(n + 1)
μ_{2i} = \frac{i}{4i + 2}(n + i + 1)(n − i), i ≥ 1
μ_{2i+1} = \frac{i + 1}{4i + 2}(n + i + 1)(n − i).

Now from Proposition 6, Lemma 18, and Proposition 19, we obtain the solution to Propp’s Problem 2:

Theorem 20. The number of tilings of a (k, 2n+1−k, k, k+1, 2n−k, k+1) hexagon without the central triangle is

\frac{(n − q)(n − q + 1)^{5} ⋯ n^{4q+1}(n + 1)^{4q+1} ⋯ (n + q + 1)}{2^{(2q)(2q+1)}3^{8(q−1)+2}5^{8(q−2)+2} ⋯ (2q + 1)^{2}} for k = 2q + 1,
\frac{(n − q + 1)^{3} ⋯ n^{4q−1}(n + 1)^{4q−1} ⋯ (n + q)^{3}}{2^{(2q−1)(2q)}3^{8(q−1)−2}5^{8(q−2)−2} ⋯ (2q − 1)^{6}} for k = 2q.

See [5] for Ciucu’s recent combinatorial proof of the same result.

9. Proof of the continued fraction

In this section we prove the equality in Proposition 19.

The exponential generating function for (1 + (−1)^{j−1})S_{n}^{j} is, by Lemma 1,

∑_{j=0}^{∞}(1 + (−1)^{j−1})S_{n}^{j} \frac{x^{j}}{j!} = \frac{e^{x}(e^{nx} − 1)}{e^{x} − 1} − \frac{e^{−x}(e^{−nx} − 1)}{e^{−x} − 1}

= \frac{(e^{nx} − 1)(e^{x} − e^{−nx})}{e^{x} − 1}

= 2\frac{sinh \frac{n}{2}x sinh \frac{n+1}{2}x}{sinh \frac{x}{2}}.

Now let L be the linear operator on formal power series defined by

L(∑_{i=0}^{∞} u_{i} \frac{x^{i}}{i!} ) = ∑_{i=0}^{∞} u_{i}x^{i}.

We note that L(f(x)) has the “formal” integral representation

L(f(x)) = \frac{1}{x} ∫_{0}^{∞} f(t)e^{−t/x} dt,

obtained by performing the integration term by term. If F (x) = L(f(x)), then this formula may be written as a Laplace transform

F (1/z) = z ∫_{0}^{∞} f(t)e^{−tz} dt,

and this is the form in which it is most often seen in the literature on continued fractions.

The continued fraction we need is given by the following formula, in which n need not be an integer. The case in which n is a nonnegative integer is clearly equivalent to Lemma 19.

Lemma 21.

L (\frac{sinh \frac{n}{2}x sinh \frac{n+1}{2}x}{sinh \frac{x}{2}}) = \frac{\binom{n+1}{2}x}{1 − \frac{μ_{1}x^{2}}{1 − \frac{μ_{2}x^{2}}{1 − ⋯}}},

where

μ_{2i} = \frac{i}{4i + 2}(n + i + 1)(n − i)
μ_{2i+1} = \frac{i + 1}{4i + 2}(n + i + 1)(n − i).

Lemma 21 is one of several continued fractions for this function given by Lange [18, pp. 259–260]. (A closely related continued fraction for the same function was given by Stieltjes [24].) For completeness, we give here a self-contained proof:

Lemma 22. Let f_{0}, f_{1}, f_{2}, … be formal power series in x with nonzero constant terms, and let c_{1}, c_{2}, … be constants such that for each k ≥ 1,

f_{k} − f_{k−1} = c_{k}x^{2}f_{k+1}.  (9)

Then for each m ≥ 1,

\frac{f_{m}}{f_{m−1}} = \frac{1}{1 − \frac{c_{m}x^{2}}{1 − \frac{c_{m+1}x^{2}}{1 − ⋯}}}

Proof. Equation (9) is equivalent to

\frac{f_{k}}{f_{k−1}} = \frac{1}{1 − c_{k}x^{2} \frac{f_{k+1}}{f_{k}}}.

Iterating this formula gives

\frac{f_{m}}{f_{m−1}} = \frac{1}{1 − \frac{c_{m}x^{2}}{1 − \frac{c_{m+1}x^{2}}{\frac{...}{1 − c_{m+n}x^{2} \frac{f_{m+n+1}}{f_{m+n}}}}}}

Taking the limit as n → ∞ yields the lemma.

Proof of Lemma 21. Let E = L^{−1}, so that

E(∑_{j=0}^{∞} a_{j}x^{j}) = ∑_{j=0}^{∞} a_{j} \frac{x^{j}}{j!} ,

and suppose that with f_{k} as in Lemma 22, g_{k} = E(x^{k}f_{k}). Multiplying the recurrence (9) by x^{k−2}, and using the fact that if u(x) is divisible by x then

E (\frac{u(x)}{x}) = \frac{d}{dx}E(u(x)),

we find that (9) is equivalent to

\frac{dg_{k}}{dx} − g_{k−1} = c_{k}g_{k+1}.  (10)

We now consider the case of Lemma 22 in which

c_{2i} = \frac{i}{4i + 2}(n + i + 1)(n − i)
c_{2i+1} = \frac{i + 1}{4i + 2}(n + i + 1)(n − i)

We shall express a solution of recurrence (10) in terms of the hypergeometric series, defined by

2F_{1} ( {a, b \atop c} | z) = ∑_{n=0}^{∞} \frac{(a)_{n}(b)_{n}}{n! (c)_{n}} z^{n},

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

We claim that a solution of recurrence (10) is

g_{k} = \frac{(e^{x} − 1)^{k}}{k!} e^{−nx}_{2}F_{1} ( {⌊\frac{k+1}{2}⌋ , ⌊\frac{k+1}{2}⌋ − n \atop k + 1} | 1 − e^{x})

×_{2}F_{1} ( {⌊\frac{k}{2}⌋ + 1, ⌊\frac{k}{2}⌋ − n \atop k + 1} | 1 − e^{x}) . (11)

The verification that g_{i} defined by (11) really does satisfy (10) is a straightforward, but tedious, computation using the formula

\frac{d}{dz}_{2}F_{1} ( {a, b \atop c} | z) = \frac{ab}{c}_{2}F_{1} ( {a + 1, b + 1 \atop c + 1} | z) ,

together with the contiguous relations for the hypergeometric series [1, p. 558]. (This computation was done with the help of Maple.)

It is not hard to show that g_{0} = 1. We now evaluate

g_{1} = (e^{x} − 1)e^{−nx}_{2}F_{1} ( {1, 1 − n \atop 2} | 1 − e^{x})_{2}F_{1} ( {1, −n \atop 2} | 1 − e^{x})

Using the easily verified fact that

2F_{1} ( {1, β \atop 2} | z) = \frac{1}{z(β − 1)} (\frac{1}{(1 − z)^{β−1}} − 1) ,  (12)

we find that

g_{1} = \frac{e^{−nx}(e^{nx} − 1)(e^{(n+1)x} − 1)}{n(n + 1)(e^{x} − 1)} = \frac{2}{n(n + 1)} \frac{sinh \frac{n}{2}x sinh \frac{n+1}{2}x}{sinh \frac{x}{2}}.

Thus f_{0} = 1, and

f_{1} = \frac{1}{x}L(g_{1}) = \frac{1}{\binom{n+1}{2}x}L (\frac{sinh \frac{n}{2}x sinh \frac{n+1}{2}x}{sinh \frac{x}{2}}) .

Substituting these values of f_{0} and f_{1} into the case m = 1 of Lemma 22, and multiplying both sides by \binom{n+1}{2}x, completes the proof of Lemma 21.

It is clear from the recurrence (10) and the value of g_{1} that g_{k} is a rational function of e^{x} and e^{nx}. Although we won’t need it, we can give an explicit formula that expresses g_{k} in this form by applying to (11) the formula

2F_{1} ( {m + 1, β \atop k + 1} | z) = (−1)^{k} \frac{k!}{m! z^{k}} [(−1)^{m} \frac{(1 − z)^{k−m−β}}{(1 − β)_{k−m}}

×_{2}F_{1} ( {−m, 1 − β \atop 1 − β − m + k} | 1 − z) − \frac{(1 − k)_{m}}{(1 − β)_{k}} ∑_{i=0}^{k−m−1} \frac{(β − k)_{i}(1 − k + m)_{i}}{i! (1 − k)_{i}} z^{i}],

for k ≥ m, which can be proved by equating coefficients of powers of z on both sides. (Note that (12) is the case m = 0, k = 1.)

10. Acknowledgments

We would like to thank Christian Krattenthaler for telling us about the status of his work on these problems, James Propp, for his assistance at various times during the writing of this paper, and an anonymous referee for a careful reading and helpful suggestions.

References

[1] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, Dover, New York, 1972.

[2] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Vol. 1, Addison-Wesley, Reading, Massachusetts, 1976.

[3] J. W. Archbold, Algebra, Pitman Paperbacks, Bath, 1970.

[4] W. N. Bailey, Generalized Hypergeometric Series, Cambridge University Press, London, 1935.

[5] M. Ciucu, “Enumeration of lozenge tilings of punctured hexagons,” J. Combin. Theory Ser. A., 83 (1998), 268-272.

[6] M. Ciucu and C. Krattenthaler, “The number of rhombus tilings of a symmetric hexagon which contain the central rhombus,” to appear in J. Combin. Theory Ser. A.

[7] H. Cohn, M. Larsen, and J. Propp, “The shape of a typical boxed plane partition,” New York J. Math. 4 (1998), 137-166.

[8] N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, “Alternating-Sign matrices and domino tilings”, J. Algebraic Combinatorics, 1 (1992), 111–132 and 219–234.

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

[10] R. A. Frazer, W. J. Duncan, and A. R. Collar, Elementary Matrices and Some Applications to Dynamics and Differential Equations, Cambridge University Press, 1947.

[11] F. R. Gantmacher, The Theory of Matrices, Volume 1, Chelsea, New York, 1959.

[12] P. Henrici, Applied and Computational Complex Analysis, Volume 1, Wiley, New York, 1974.

[13] W. B. Jones and W. J. Thron, Continued Fractions: Analytic Theory and Applications, Encyclopedia of Mathematics and Its Applications, Vol. 11, Addison-Wesley, Reading, Massachusetts, 1980.

[14] W. Jockusch and J. Propp, “Antisymmetric monotone triangles and domino tilings of quartered Aztec diamonds,” J. Algebraic Combinatorics, to be published.

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

[16] D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1973.

[17] C. Krattenthaler, “Schur function identities and the number of perfect matchings of holey Aztec rectangles,” preprint.

[18] L. J. Lange, “Continued fraction representations for functions related to the gamma function,” in Continued Fractions and Orthogonal Functions: Theory and Applications, ed. S. Clement Cooper and W. J. Thron, M. Dekker, 1994, pp. 233–279.

[19] W. H. Mills, D. P. Robbins, and H. Rumsey, Jr., “Alternating sign matrices and descending plane partitions,” J. Combin. Theory Ser. A 34 (1983), 340–359.

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

[21] J. Propp and R. Stanley, “Domino tilings with barriers,” to appear in J. Combin. Theory Ser. A.

[22] J. Propp, “Twenty open problems in enumeration of matchings,” math.CO/9801060.

[23] C. Radoux, “Calcul effectif de certains déterminants de Hankel,” Bull. Soc. Math. Belg. Sér. B 31 (1979), 49–55.

[24] T. J. Stieltjes, “Sur quelques intégrales définies et leur développement en fractions continues,”Ouvres Complètes, Vol. 2, P. Noordhoff, Groningen, 1918, pp. 378–391. Originally published in Quarterly Journal of Math. 24 (1890), 370–382.

[25] J. J. Sylvester, “On a certain fundamental theorem of determinants,” Philosophical Magazine (4) 2 (1851), 142–145.

[26] X. G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Conference Notes, Université du Québec à Montréal, 1983.

[27] H. S. Wilf and D. Zeilberger, “Rational functions certify combinatorial identities,”J. Amer. Math. Soc. 3 (1990), 147–158.

[28] A. Zavrotsky, “El Gesseliano” (Spanish), Notas de Matematicas, no. 73, Universidad de los Andes, Facultad de Ciencias, Departamento de Matematica, Merida, Venezuela, 1985.