Schur Function Identities and the Number of

Perfect Matchings of Holey Aztec Rectangles

C. Krattenthaler

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

           WWW: http://radon.mat.univie.ac.at/People/kratt

Dedicated to Richard Askey

Abstract. We compute the number of perfect matchings of an M ×N Aztec rectangle where |N − M| vertices have been removed along a line. A particular case solves a problem posed by Propp. Our enumeration results follow from certain identities for Schur functions, which are established by the combinatorics of nonintersecting lattice paths.

1. Introduction. Consider a (2M + 1) × (2N + 1) rectangular chessboard and suppose that the corners are black. The M × N Aztec rectangle is the graph whose vertices are the white squares and whose edges connect precisely those pairs of white squares that are diagonally adjacent, see Figure 1.a for an example. An M × N Aztec rectangle does not have any perfect matching, except if M = N. If, however, we remove |N − M| vertices from it in a suitable way, then the “holey” Aztec rectangle which is obtained in this manner (see Figures 3 and 4 for examples) does allow perfect matchings. For example, Ciucu [2, Theorem 4.1] computed, for even M and M ≤ N, the precise number of all perfect matchings of an M ×N Aztec rectangle where N −M vertices on the horizontal symmetry axis are removed (see Theorem 7).

In Problem 10 of his list [14] (see also [15]) of “20 open problems on enumeration of matchings”, Propp asks for the number of all perfect matchings of a (2n − 1) × 2n Aztec rectangle where one vertex which is adjacent to the central vertex is removed

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

Key words and phrases. domino tilings, perfect matchings, holey Aztec rectangle, Aztec diamond, nonintersecting lattice paths, Schur functions.

This research was partially supported by the Austrian Science Foundation FWF, grant P12094-MAT.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; •; •; •; •; •; •; •; •; •; •; •; •]

a. A 3 × 4 Aztec rectangle b. A 3 × 4 Aztec rectangle with a vertex adjacent to the central vertex removed

Figure 1

(it does not matter which of the four vertices adjacent to the central one is removed; see Figure 1.b for an example).

The original purpose of this paper was to solve this problem. (An independent solution was found by Helfgott and Gessel [9, Sec. 6].) What we do in fact is, quite generally, to describe a method, based on certain Schur function identities (see Section 3), which allows us to compute the number of all perfect matchings of an M × N Aztec rectangle where |N − M| vertices are removed along a horizontal line. The expressions that are obtained (see Theorems 11 and 12) are ⌊d/2⌋-fold sums, where d is the “distance” of the line from the symmetry axis (“distance” has the obvious meaning here, see Section 4). Thus, the closer the horizontal line is to the symmetry axis, the simpler are the obtained expressions. In particular, closed forms are obtained if the line is the symmetry axis or “by 1 off” the symmetry axis. This includes Ciucu’s enumeration and the case of Propp’s problem (see Theorems 7–10). In addition, with the help of hypergeometric-type summations (Theorem 6), we also obtain closed forms if the vertices which are not removed “form an arithmetic progression” (Theorems 13 and 14) or “form a geometric progression” (Theorems 15 and 16), regardless on which line they are removed.

As a basis for our method we take a careful selection of ideas which appear in the literature in connection with this theme. To be more concrete, Ciucu proves his above cited enumeration result by applying his matchings factorization theorem for symmetric graphs [2, Theorem 1.2] and then using a formula due to Mills, Robbins and Rumsey [13, Theorem 2] (see Lemma 1) for the number of perfect matchings of an M × N Aztec rectangle with |N − M| of its top-most vertices removed. This approach does of course not generalize since there is no symmetry if vertices are removed arbitrarily along a horizontal line different from the symmetry axis. However, as an afterthought [2, Remark 4.3], he sketches a second approach, which again makes use of the formula due to Mills, Robbins and Rumsey, and which finally boils down to establishing a certain Schur function identity (see Theorem 3), which he states as a conjecture. It is this approach that we are going to adapt (in a slightly modified fashion). Proofs of the aforementioned Schur function identity were immediately provided by Tesler (private communication), and independently by Fulmek [5]. In fact, as was pointed out by Propp and Stanley [16, Remark after Theorem 2], the Schur function identity was already known, as it results from an old determinant identity of Sylvester. Whereas this observation and Tesler’s proof (which makes use of Laplace expansion of a certain matrix) do not seem to be of any help for our generalizations, Fulmek’s idea of proof of making use of nonintersecting lattice paths (which is, as pointed out by A. Hamel, in fact a rediscovery of an idea of Goulden [8]) is exactly the right tool for proving the variations of this Schur function identity that we need for our purpose.

Our paper is organized as follows. In the next section we list two auxiliary results, one of which is the formula of Mills, Robbins and Rumsey and the other is a variation of it. In Section 3 we review Fulmek’s lattice path proof of Ciucu’s Schur function identity and describe how the same idea leads to a whole family of variations of the identity. Also contained in this section is the hypergeometric-type summation that was mentioned earlier. Finally, in Section 4, we describe our method how to enumerate all perfect matchings of an M × N Aztec rectangle where |N − M| vertices are removed along a horizontal line, and list our results. The method simply consists of breaking the Aztec rectangle into two parts along this horizontal line, and then handling the resulting summations by taking advantage of the Schur function identities from Section 3. The impatient reader may immediately jump to this section, and come back to Section 2, respectively Section 3, when results from there are cited.

2. Two auxiliary lemmas. First, we quote Theorem 2 from [13], in the translation as described by Ciucu [2, (4.4)] (see also equation (7) in [3]).

Lemma 1. The number of perfect matchings of an m × n Aztec rectangle, where all the vertices in the top-most row, except for the a_{1}-st, the a_{2}-nd, …, and the a_{m}-th vertex, have been removed (see Figure 2.a for an example with m = 3, n = 5, a_{1} = 1, a_{2} = 3, a_{3} = 5), equals

\frac{2^{\binom{m+1}{2}}}{∏_{i=1}^{m}(i − 1)!} ∏_{1≤i<j≤m}(a_{j} − a_{i}).  (2.1)

Next, we state a variant of this result for an Aztec rectangle with a holey “half-row” (see the last paragraph of Part 1 of [3], and also [9, Lemma 2]).

Lemma 2. The number of perfect matchings of an m × n Aztec rectangle, where all the vertices in the top-most row have been removed, and where the a_{1}-st, the a_{2}- nd, …, and the a_{m}-th vertex of the row next to the top-most row have been removed (see Figure 2.b for an example with m = 3, n = 5, a_{1} = 3, a_{2} = 5, a_{3} = 6), equals

\frac{2^{\binom{m}{2}}}{∏_{i=1}^{m}(i − 1)!} ∏_{1≤i<j≤m}(a_{j} − a_{i}).  (2.2)

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; •; •; •; •; •; •; •; •; •; •; •; ∘; •; •; •; •; •; ∘; ∘; ∘; ∘; ∘; ∘]

a. A 3 × 5 Aztec rectangle with some vertices b. A 3 × 5 Aztec rectangle with all vertices in the top row removed in the top row removed and some

vertices in the next row removed

Figure 2

3. Schur function identities. Let A = {a_{1}, a_{2}, …, a_{m}} be a set of positive integers with a_{1} < a_{2} < ⋯ < a_{m}. The connection between enumeration of perfect matchings of holey Aztec rectangles and Schur functions is set up by the identity (see [12, Ex. I.3.4])

s_{λ(A)}(1^{m}) = s_{λ(A)}(\underbrace{1, 1, …, 1}_{m times}) = \frac{∏_{1≤i<j≤m}(a_{j} − a_{i})}{∏_{i=1}^{m}(i − 1)!},  (3.1)

where λ(A) is by definition the partition (a_{m}−m+1, …, a_{2}−1, a_{1}). It is the ubiquitous “Vandermonde” product, as it appears in Lemmas 1 and 2 and (3.1), which makes it natural to consider Schur functions in this context, see Section 4.

Let us recall Ciucu’s Schur function identity [2, Conj. 4.5] and Fulmek’s [5] proof of it. Here and in the sequel, we use the short notation X_{n} for the sequence of variables x_{1}, x_{2}, …, x_{n}.

Theorem 3. Let T = {t_{1}, t_{2}, …, t_{2m}} be a set of positive integers with t_{1} < t_{2} < ⋯ < t_{2m}. Then

∑ s_{λ(A)}(X_{n}) · s_{λ(B)}(X_{n}) = 2^{m}s_{λ(t_{2},t_{4},...,t_{2m})}(X_{n}) · s_{λ(t_{1},t_{3},...,t_{2m−1})}(X_{n}), (3.2)

where the sum is over all pairs of disjoint sets A and B whose union is T and whose cardinalities are given by |A| = |B| = m.

Sketch of Proof. By the main theorem of nonintersecting lattice paths [7, Cor. 2; 18, Theorem 1.2], a Schur function s_{λ(A)}(X_{n}) can be interpreted combinatorially as the generating function ∑_{P} w(P), where the sum is over all families P = (P_{1}, P_{2}, …, P_{m}) of nonintersecting lattice paths consisting of horizontal and vertical unit steps, P_{i} running from (i − 1, 1) to (a_{i}, n), i = 1, 2, …, m, and where the weight w(.) is defined via edge weights in which vertical edges have weight 1 and a horizontal edge at height h has weight x_{h} (see also [6, Sec. 3; 17, Sec. 4.5]).

Thus, the left-hand side of (3.2) can be interpreted as a generating function for pairs (P^{g}, P^{r}) of families of nonintersecting lattice paths, the i-th path of P^{g} running from (i − 1, 1) to (a_{i}, n), with a_{i} being the i-th element of A, i = 1, 2, …, m, and the i-th path of P^{r} running from (i − 1, 1) to (b_{i}, n), with b_{i} being the i-th element of B, i = 1, 2, …, m. Say that the paths of P^{g} are coloured green, and those of P^{r} are coloured red. Likewise, the right-hand side of (3.2) can be interpreted as a generating function for triples (Q^{g}, Q^{r}, C), where Q^{g} and Q^{r} are families of nonintersecting lattice paths, the i-th path of Q^{g} running from (i − 1, 1) to (t_{2i}, n), i = 1, 2, …, m, and the i-th path of Q^{r} running from (i−1, 1) to (t_{2i−1}, n), i = 1, 2, …, m, and where C is a {0, 1}-sequence of length m.

Identity (3.2) will be proved once we are able to set up a (weight-preserving) bijection between “left-hand side pairs” and “right-hand side triples”. Fulmek does this in the following way. Let (P^{g}, P^{r}) be a “left-hand side pair” as described above. Then Fulmek defines a (non-crossing) matching of the end points (t_{i}, n), i = 1, 2, …, 2m, by “down-up” trails. Beginning in some end point we move down along the path which ends in this point. When we meet a path of colour different from the path along which we were moving, then we continue to move up along the new path. This procedure is iterated, interchanging the roles of up and down every time, of course. Finally, we will terminate, in an up-move, in another end point. It is easy to see that in that manner an end point with odd index, (t_{2i−1}, n) say, is always connected with an end point of even index, (t_{2j}, n) say. The triple (Q^{g}, Q^{r}, C) is now defined as follows. For any i, i = 1, 2, …, m, we consider the down-up trail starting in (t_{2i−1}, n). If the path ending in that end point is green then we interchange colours along the down-up trail and we put C_{i} = 1. On the other hand, if the path ending in that end point is red then we leave the paths as they are and put C_{i} = 0. By definition, Q^{g} is the family of green paths thus obtained, Q^{r} is the family of red paths thus obtained, and C is the sequence C_{1}, C_{2}, …, C_{m} thus obtained.

It is easy to see that this mapping has all the required properties. We refer the reader to [5]. □

For the solution of Propp’s Problem 10, we need a variant of Theorem 3.

Theorem 4. Let T = {t_{1}, t_{2}, …, t_{2m+1}} be a set of positive integers with t_{1} < t_{2} < ⋯ < t_{2m+1}. Then

∑ s_{λ(A)}(X_{n}) · s_{λ(B)}(X_{n+1}) = 2^{m}s_{λ(t_{2},t_{4},...,t_{2m})}(X_{n}) · s_{λ(t_{1},t_{3},...,t_{2m+1})}(X_{n+1}), (3.3)

where the sum is over all disjoint pairs of sets A and B whose union is T and whose cardinalities are given by |A| = m and |B| = m + 1.

Sketch of Proof. We proceed in the same manner as in the proof of Theorem 3. In particular, the left-hand side of (3.3) can be interpreted as a generating function for pairs (P^{g}, P^{r}) of families of nonintersecting lattice paths, the i-th path of P^{g} running from (i − 1, 1) to (a_{i}, n), with a_{i} being the i-th element of A, i = 1, 2, …, m, and the i-th path of P^{r} running from (i − 1, 0) to (b_{i}, n), with b_{i} being the i-th element of B, i = 1, 2, …, m + 1. Likewise, the right-hand side of (3.3) can be interpreted as a generating function for triples (Q^{g}, Q^{r}, C), where Q^{g} and Q^{r} are families of nonintersecting lattice paths, the i-th path of Q^{g} running from (i − 1, 1) to (t_{2i}, n), i = 1, 2, …, m, and the i-th path of Q^{r} running from (i − 1, 0) to (t_{2i−1}, n), i = 1, 2, …, m + 1, and where C is a {0, 1}-sequence of length m.

For setting up a bijection between “left-hand side pairs” and “right-hand side triples”, we construct again the down-up trails for a pair (P^{g}, P^{r}). However, since the number of end points is now odd, it is impossible to obtain a complete matching of the end points. In fact, what is obtained is a (non-crossing) matching on only 2m end points, while a single end point is “matched” to the “additional” starting point of red paths, (m, 0). Besides, the corresponding down-up trail, which connects this single end point with (m, 0), cannot touch any of the other down-up trails. Hence, it has odd index, i.e., it is an end point (t_{2ℓ−1}, n), say. Furthermore, since this trail must end with a “down part”, moving into (m, 0), which is the starting point of a red path only, and since all “down parts” are equally coloured red (as well as all the “up parts” are coloured in the opposite colour green), the end point (t_{2ℓ−1}, n) is the end point of a red path.

To define the triple (Q^{g}, Q^{r}, C) we must modify the definition in the proof of Theorem 3 only slightly. Namely, instead of considering the down-up trail starting in (t_{2i−1}, n) for any i between 1 and m + 1, and possibly performing a recolouring and defining C_{i}, we do it only for all i between 1 and m + 1 that are different from ℓ. (Recall that (t_{2ℓ−1}, n) is matched to a starting point and that the path ending in this point must be red.) Everything else remains the same, except that the sequence C is now defined as C_{1}, C_{2}, …, C_{ℓ−1}, C_{ℓ+1}, …, C_{m+1}. □

Clearly, there is nothing which could prevent us from considering the next summation in this family, of which (3.2) and (3.3) are the first members,

∑ s_{λ(A)}(X_{n}) · s_{λ(B)}(X_{n+2}),

where the sum is over all disjoint pairs of sets A and B whose union is T = {t_{1}, t_{2}, …, t_{2m+2}} and whose cardinalities are given by |A| = m and |B| = m + 2. In general, we would consider

∑ s_{λ(A)}(X_{n}) · s_{λ(B)}(X_{n+d}),

where the sum is over all disjoint pairs of sets A and B whose union is T = {t_{1}, t_{2}, …, t_{2m+d}} and whose cardinalities are given by |A| = m and |B| = m + d. Of course, the matching and “colouring scheme” will not lead to closed forms in general, the reason being that d end points will be matched to starting points. What is obtained is a result in form of a ⌊d/2⌋-fold sum, which we state next.

Theorem 5. Let T = {t_{1}, t_{2}, …, t_{2m+d}} be a set of positive integers with t_{1} < t_{2} < ⋯ < t_{2m+d}. Then

∑ s_{λ(A)}(X_{n}) · s_{λ(B)}(X_{n+d})

= 2^{m} ∑_{1≤k_{1}<k_{2}<···<k_{⌊d/2⌋}≤m+⌊d/2⌋} s_{λ({t_{2},t_{4},...,t_{2m+d}}\{2k_{1},2k_{2},...,2k_{⌊d/2⌋}})}(X_{n})

· s_{λ({t_{1},t_{3},...,t_{2m+1}}∪{2k_{1},2k_{2},...,2k_{⌊d/2⌋}})}(X_{n+d}), (3.4)

where the sum is over all disjoint pairs of sets A and B whose union is T and whose cardinalities are given by |A| = m and |B| = m+d, and where complement and union in the indices on the right-hand side have the obvious meaning. (In particular, in case of ‘union’ the elements are brought in order before applying the λ-operation).

The last piece that we need for our enumerations is summations for sums that will result from application of Theorem 5. These are (basic) hypergeometric-type multiple sums. The corresponding summations (which we need for the proofs of Theorems 13– 16) can be derived either from a Schur function identity, or, as was pointed out by the referee, from a q-integral evaluation that was originally conjectured by Askey [1, Conjecture 8], and subsequently proved by Evans [4] and Kadell [10]. We provide both of these derivations.

Theorem 6. With the usual definition of shifted factorials, (a)_{k} := a(a+1) ⋯ (a+ k − 1) for k ≥ 1, and (a)_{0} := 1, we have

∑_{0≤k_{1}<k_{2}<···<k_{s}≤m} ∏_{1≤i<j≤s}(k_{j} − k_{i})^{2} ∏_{i=1}^{s} \frac{(x)_{k_{i}} (y)_{m−k_{i}}}{(k_{i})! (m − k_{i})!}

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

With the usual definition of shifted q-factorials, (a; q)_{k} := (1−a)(1−aq) ⋯ (1−aq^{k−1}) for k ≥ 1, and (a; q)_{0} := 1, we have

∑_{0≤k_{1}<k_{2}<···<k_{s}≤m} y^{∑_{i=1}^{s} k_{i}} ∏_{1≤i<j≤s}(q^{k_{j}} − q^{k_{i}})^{2} ∏_{i=1}^{s} \frac{(x; q)_{k_{i}} (y; q)_{m−k_{i}}}{(q; q)_{k_{i}} (q; q)_{m−k_{i}}}

= q^{2\binom{s}{3}}y^{\binom{s}{2}} ∏_{i=1}^{s} \frac{(x; q)_{i−1} (y; q)_{i−1} (xyq^{i+s−2}; q)_{m−s+1} (q; q)_{i−1}}{(q; q)_{m−i+1}} . (3.6)

First Proof. It suffices to prove identity (3.6). For, identity (3.5) immediately results from (3.6), by performing the replacements x → q^{x} and y → q^{y} in (3.6), then dividing both sides by (1 − q)^{s(s−1)}, and subsequently performing the limit q → 1.

We start with the well-known Schur function identity (see [12, I, (5.9)])

s_{λ}(x_{1}, …, x_{α}, y_{1}, …, y_{β}) = ∑_{μ} s_{λ/μ}(x_{1}, …, x_{α})s_{μ}(y_{1}, …, y_{β}),  (3.7)

where the sum is over all partitions μ that are contained in the partition λ. The special case which is relevant for us is the case that λ is a rectangle, λ = (M^{s}) say. Then the skew Schur function s_{λ/μ}(x_{1}, …, x_{α}) = s_{(M^{s})/μ}(x_{1}, …, x_{α}) equals an ordinary Schur function, namely we have

s_{(M^{s})/μ}(x_{1}, …, x_{α}) = s_{μ′}(x_{1}, …, x_{α}),  (3.8)

where, given μ = (μ_{1}, μ_{2}, …, μ_{s}), the partition μ′ is defined by μ′ = (M − μ_{s}, M − μ_{s−1}, …, M − μ_{1}).

Now we set x_{i} = q^{i}, i = 1, 2, …, α, and y_{i} = q^{α+i}, i = 1, 2, …, β, in (3.7). Use of (3.8), of the formula (which follows, for example, from a combination of [12, I, (3.4) and §2, Ex. 3] and [11, Theorem 26, (3.11)], or from a combination of the exercises [12, I, §3, Ex. 1; §1, Ex. 1(3); §1, Ex. 3])

s_{μ}(q^{K+1}, q^{K+2}, …, q^{K+L})

= q^{2\binom{s+1}{3}+(K+1) ∑_{i=1}^{s} μ_{i}} \frac{∏_{1≤i<j≤s}(q^{μ_{j}−j} − q^{μ_{i}−i}) ∏_{i=1}^{s}(q^{L+1−i}; q)_{μ_{i}}}{∏_{i=1}^{s}(q; q)_{μ_{i}−i+s}} ,

and routine manipulations show, that (3.7) is equivalent to (3.6), with the relations k_{i} = μ_{i} − i + s, x = q^{α−s+1}, y = q^{β−s+1}, m = M + s − 1.

Hence, we know that (3.6) is true if x and y are positive integer powers of q. In order to extend (3.6) to all x and y, we observe that, first, for fixed s and m, left-hand side and right-hand side of (3.6) are polynomials in x and y with degree bounded by a fixed quantity, and second, that (3.6) is true for an infinite number of x’s and y’s. Therefore (3.6) must be true in general.

Second Proof. Again, it suffices to prove (3.6). In order to do that, we set n = s, c = 1 and α = βq^{m+a} in Theorem 1.1 of [4]. The assignment of α has the effect that the q-integral with respect to t_{i} in this theorem is a sum over the points t_{i} = β, βq, …, βq^{m+a−1}. Thus, in this special case the theorem reads

\frac{(1 − q)^{s}}{s!} ∑_{k_{1}=0}^{m+a−1} ∑_{k_{2}=0}^{m+a−1} ⋯ ∑_{k_{s}=0}^{m+a−1} β^{s}q^{∑_{i=1}^{s} k_{i}}( ∏_{i=1}^{s}(q^{1−m−a+k_{i}}; q)_{a−1} (q^{k_{i}+1}; q)_{b−1})

· (β^{2\binom{s}{2}} ∏_{1≤i<j≤s}(q^{k_{i}} − q^{k_{j}})^{2})

= (−1)^{\binom{s}{2}}q^{\binom{s}{3}} ∏_{j=0}^{s−1} β^{2j+2}q^{(m+a)(j+1)}(1 − q)^{n−2j}

· \frac{(q; q)_{a+j−1} (q; q)_{b+j−1} (q; q)_{j} (q^{m+a}; q)_{b+j} (q^{−m−a}; q)_{a+j}}{(q; q)_{a+b+s+j−2} β(q^{m+a} − 1)} .

Since the summand of the sum on the left-hand side is invariant under permutations of the k_{i}’s, and since it vanishes unless all the k_{i}’s are pairwise different, we may replace \frac{1}{s!} ∑_{k_{1},k_{2},...,k_{s}≥0} by ∑_{0≤k_{1}<k_{2}<···<k_{s}}. Then, upon some rearrangement and cancellation of terms, we obtain (3.6) with x = q^{b} and y = q^{a}. □

4. The enumeration results. Now we are ready to state our enumeration results for holey Aztec rectangles. For the sake of completeness, we start by repeating Ciucu’s enumeration that was mentioned in the Introduction.

Theorem 7 [2, Theorem 4.1]. Let m and N be positive integers with 2m ≤ N. Then the number of perfect matchings of a 2m × N Aztec rectangle, where all the vertices on the central horizontal row, except for the t_{1}-st, the t_{2}-nd, …, and the t_{2m}-th vertex, have been removed (see Figure 3.a for an example with m = 2, N = 7, a_{1} = 1, a_{2} = 4, a_{3} = 5, a_{4} = 7), equals

\frac{2^{m^{2}+2m}}{∏_{i=1}^{m}(i − 1)!^{2}} ∏_{1≤i<j≤m}(t_{2j} − t_{2i}) ∏_{1≤i<j≤m}(t_{2j−1} − t_{2i−1}).  (4.1)

[figure: •; ∘; ∘; •; •; ∘; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; •; ∘; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

a. A 4 × 7 Aztec rectangle with some vertices b. A 5 × 3 Aztec rectangle with some vertices on the central row removed on the central line removed

Figure 3

Our first new result is an analogue of this theorem for an odd number of rows. It was also obtained independently by Helfgott and Gessel [9, Proposition 8].

Theorem 8. Let m and N be positive integers with 2m − 1 ≥ N. Then the number of perfect matchings of a (2m − 1) × N Aztec rectangle, where all the vertices on the central horizontal row, except for the t_{1}-st, the t_{2}-nd, …, and the t_{2N−2m+2}- nd vertex, have been removed (see Figure 3.b for an example with m = 3, N = 3, a_{1} = 2, a_{2} = 4), equals

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

× ∏_{1≤i<j≤N−m+1}(t_{2j} − t_{2i}) ∏_{1≤i<j≤N−m+1}(t_{2j−1} − t_{2i−1}). (4.2)

Proof. Let S = {s_{1}, s_{2}, …, s_{2m−N−1}} be the complement of T = {t_{1}, t_{2}, …, t_{2N−2m+2}} in {1, 2, …, N + 1}.

Any perfect matching of the holey Aztec rectangle under consideration can be naturally split along the central horizontal line. The lower half is a perfect matching of an m×N Aztec rectangle, where m vertices in the top-most row have been removed, including the vertices whose indices are in S. Likewise, the upper half is a perfect matching of an m×N Aztec rectangle, where m vertices in the bottom-most row have been removed, including the vertices whose indices are in S, and avoiding the other vertices that are removed in the lower half. Hence, by Lemma 2, the total number of perfect matchings that we are interested in is the sum

∑ \frac{2^{\binom{m}{2}}}{∏_{i=1}^{m}(i − 1)!} ∏_{1≤i<j≤m}(a_{j} − a_{i})\frac{2^{\binom{m}{2}}}{∏_{i=1}^{m}(i − 1)!} ∏_{1≤i<j≤m}(b_{j} − b_{i}),

where the sum is over all pairs of sets A = {a_{1}, a_{2}, …, a_{m}} and B = {b_{1}, b_{2}, …, b_{m}}, whose union is the complete set of indices {1, 2, …, N + 1}, and whose intersection is S. Next we extract the common factors that are generated by A and B, thus obtaining the sum

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

× ∑ ∏_{1≤i<j≤N−m+1}(a′_{j} − a′_{i}) ∏_{1≤i<j≤N−m+1}(b′_{j} − b′_{i}),

where the sum is over all pairs of disjoint sets A′ = {a′_{1}, a′_{2}, …, a′_{N−m+1}} and B = {b′_{1}, b′_{2}, …, b′_{N−m+1}}, whose union is {1, 2, …, N + 1}\S.

Now we may use (3.1) to rewrite this last expression as

\frac{2^{m^{2}−m} ∏_{i=1}^{2m−N−1}(s_{i} − 1)! (N + 1 − s_{i})!}{∏_{i=N−m+2}^{m}(i − 1)!^{2}} ∑ s_{λ(A′)}(1^{N−m+1}) · s_{λ(B′)}(1^{N−m+1}).

The sum can be evaluated by means of Theorem 3. Renewed use of (3.1) and some simplification eventually leads to (4.2). □

Our next two theorems concern the enumeration of perfect matchings of holey Aztec rectangles, where the “holes” are on a horizontal row next to the central horizontal row. Both theorems, when suitably specialized, solve Propp’s Problem 10 in [14] that was mentioned in the Introduction. The second theorem, Theorem 10, was also obtained independently by Helfgott and Gessel [9, Proposition 9].

In general, we say that a horizontal row, H say, is by d below the central horizontal row, if it is below the central horizontal row and if a shortest path from any vertex of H to some vertex on the central horizontal row along the edges of the Aztec rectangle needs exactly d steps.

Theorem 9. Let m and N be positive integers with 2m + 1 ≤ N. Then the number of perfect matchings of a (2m + 1) × N Aztec rectangle, where all the vertices on the horizontal row that is by 1 below the central row, except for the t_{1}-st, the t_{2}- nd, …, and the t_{2m+1}-st vertex, have been removed (see Figure 4.a for an example with m = 2, N = 7, a_{1} = 1, a_{2} = 2, a_{3} = 4, a_{4} = 5, a_{5} = 7), equals

\frac{2^{m^{2}+3m+1}}{∏_{i=1}^{m}(i − 1)! ∏_{i=1}^{m+1}(i − 1)!} ∏_{1≤i<j≤m}(t_{2j} − t_{2i}) ∏_{1≤i<j≤m+1}(t_{2j−1} − t_{2i−1}).  (4.3)

Proof. Let T = {t_{1}, t_{2}, …, t_{2m+1}}.

Similar to the proof of Theorem 8, we may split any perfect matching of the holey Aztec rectangle under consideration along this horizontal line which is by 1 off the central line. An application of Lemma 1 yields that the number of perfect matchings that we are interested in equals

∑ \frac{2^{\binom{m+1}{2}}}{∏_{i=1}^{m}(i − 1)!} ∏_{1≤i<j≤m}(a_{j} − a_{i})\frac{2^{\binom{m+2}{2}}}{∏_{i=1}^{m+1}(i − 1)!} ∏_{1≤i<j≤m+1}(b_{j} − b_{i}),

where the sum is over all pairs of disjoint sets A = {a_{1}, a_{2}, …, a_{m}} and B = {b_{1}, b_{2}, …, b_{m+1}}, whose union is the set T. By using (3.1), it is seen that this expression can be rewritten as

2^{m^{2}+2m+1} ∑ s_{λ(A)}(1^{m}) · s_{λ(B)}(1^{m+1}),

where the sum is over the same set of pairs (A, B). Clearly, the sum can be evaluated by means of Theorem 4. Renewed use of (3.1) gives (4.3) immediately. □

[figure: •; •; ∘; •; •; ∘; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; •; ∘; ∘; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

a. A 5 × 7 Aztec rectangle with some vertices b. A 6 × 3 Aztec rectangle with some vertices on the row next to the central row removed on the row next to the central line removed

Figure 4

Theorem 10. Let m and N be positive integers with 2m ≥ N. Then the number of perfect matchings of a 2m × N Aztec rectangle, where all the vertices on the horizontal row that is by 1 below the central row, except for the t_{1}-st, the t_{2}-nd, …, and the t_{2N−2m+1}-st vertex, have been removed (see Figure 4.b for an example with m = 3, N = 3, a_{1} = 2), equals

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

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

Theorem 10 can be proved in the same way as Theorem 8, except that Theorem 4 is used instead of Theorem 3. We leave the details to the reader.

Of course, the special case N = 2m + 2 of Theorem 9 as well as the special case N = 2m − 1 of Theorem 10 yields a solution of Problem 10 in [14].

Clearly, we may continue in this manner, and derive formulas for the number of perfect matchings of an M ×N Aztec rectangle, where |N −M| vertices on a horizontal row which is by d off the central horizontal row have been removed. By following the line of the proofs of Theorems 8–10, we obtain ⌊d/2⌋-fold summations if we apply Theorem 5. We just state the result and leave the routine details of verification to the reader.

Theorem 11. Let m and N be positive integers, and let d be a nonnegative integer, with 2m + d ≤ N. Then the number of perfect matchings of a (2m + d) × N Aztec rectangle, where all the vertices on the horizontal row that is by d below the central row, except for the t_{1}-st, the t_{2}-nd, …, and the t_{2m+d}-th vertex, have been removed, equals

\frac{2^{m^{2}+(d+2)m+\binom{d+1}{2}}}{∏_{i=1}^{m}(i − 1)! ∏_{i=1}^{m+d}(i − 1)!} ∏_{1≤i<j≤m+⌊d/2⌋}(t_{2j} − t_{2i}) ∏_{1≤i<j≤m+⌈d/2⌉}(t_{2j−1} − t_{2i−1})

× ∑_{1≤k_{1}<k_{2}<···<k_{⌊d/2⌋}≤m+⌊d/2⌋} ( ∏_{1≤i<j≤⌊d/2⌋}(t_{2k_{j}} − t_{2k_{i}})^{2} ∏_{i=1}^{⌊d/2⌋} \begin{matrix}∏_{j=1}^{m+⌈d/2⌉} & |t_{2k_{i}} − t_{2j−1}| \\ ∏_{j=1}^{m+⌊d/2⌋} ; j≠k_{i} & |t_{2k_{i}} − t_{2j}| \end{matrix}).

(4.5)

Theorem 12. Let m and N be positive integers, and let d be a nonnegative integer, with 2m + d − 1 ≥ N. Then the number of perfect matchings of a (2m + d − 1) × N Aztec rectangle, where all the vertices on the horizontal row that is by d below the central row, except for the t_{1}-st, the t_{2}-nd, …, and the t_{2N−2m−d+2}-nd vertex, have been removed, equals

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

× ∏_{1≤i<j≤N−m+1−⌈d/2⌉}(t_{2j} − t_{2i}) ∏_{1≤i<j≤N−m+1−⌊d/2⌋}(t_{2j−1} − t_{2i−1})

× ∑_{1≤k_{1}<k_{2}<···<k_{⌊d/2⌋}≤N−m+1−⌈d/2⌉} ( ∏_{1≤i<j≤⌊d/2⌋}(t_{2k_{j}} − t_{2k_{i}})^{2}

· ∏_{i=1}^{⌊d/2⌋} \begin{matrix}∏_{j=1}^{N−m+1−⌊d/2⌋} & |t_{2k_{i}} − t_{2j−1}| \\ ∏_{j=1}^{N−m+1−⌈d/2⌉} ; j≠k_{i} & |t_{2k_{i}} − t_{2j}| \end{matrix}), (4.6)

where the product ∏_{i=m+d+1}^{N+1}(i − 1)! has to be interpreted as 1 if N = m + d − 1 and as 0 if N < m + d − 1, and similarly for the other products.

It is natural to ask if there are cases where the sums in (4.5) or (4.6) can be simplified. Indeed, thanks to Theorem 6, there are two such cases. One is the case where the gaps between the vertices that are not removed are always the same, i.e., where the corresponding t_{i}’s form an arithmetic progression. The other is the case where the quotients of successive gaps between the vertices that are not removed are always the same, i.e., where the corresponding t_{i}’s form a (shifted) geometric progression.

The following two theorems contain the results for the case of arithmetic progressions. We want to point out that both of them (as well as Theorems 7 and 8 of course) contain the well-known enumeration of all perfect matchings of an Aztec diamond [3] as special case.

Theorem 13. Let m, N, C, D be positive integers, and let d be a nonnegative integer, with 2m + d ≤ N and C + (2m + d − 1)D ≤ N. Then the number of perfect matchings of a (2m + d) × N Aztec rectangle, where all the vertices on the horizontal row that is by d below the central row, except for the C-th, the (C +D)-th, (C + 2D)-th, …, and the (C + (2m + d − 1)D)-th vertex, have been removed, equals

2^{\binom{2m+d+1}{2}} D^{m^{2}+(d−1)m+\binom{d}{2}}.  (4.7)

Theorem 14. Let m, N, C, D be positive integers, and let d be a nonnegative integer, with 2m + d − 1 ≥ N and C + (2N − 2m − d + 1)D ≤ N + 1. Then the number of perfect matchings of a (2m + d − 1) × N Aztec rectangle, where all the vertices on the horizontal row that is by d below the central row, except for the C-th, the (C + D)-th, (C + 2D)-th, …, and the (C + (2N − 2m − d + 1)D)-th vertex, have been removed, equals

2^{\binom{2m+d}{2}+(N+1)(N−2m−d+1)} D^{m^{2}+(d−1)m+\binom{d}{2}+N(N−2m−d+1)}

× \frac{∏_{i=m+1}^{N+1}(i − 1)! ∏_{i=m+d+1}^{N+1}(i − 1)! ∏_{i=1}^{N−m+1}(i − 1)! ∏_{i=1}^{N−m−d+1}(i − 1)!}{∏_{i=1}^{2N−2m−d+2}(C + D(i − 1) − 1)! (N + 1 − C − D(i − 1))!}, (4.8)

where the product ∏_{i=m+d+1}^{N+1}(i − 1)! has to be interpreted as 1 if N = m + d − 1 and as 0 if N < m + d − 1, and similarly for the other products.

Proof of Theorems 13 and 14. We set t_{i} = C + D(i − 1), i = 1, 2, …, in Theorems 11 and 12. The resulting sums turn out to be exactly of the form of the left-hand side of (3.5), with x = 1/2 and y = 3/2, respectively x = 3/2 and y = 3/2, depending on d being even or odd. Hence, it can be evaluated. The obtained expressions can be drastically simplified and eventually turn into (4.7) and (4.8), respectively. □

The results for the case of (shifted) geometric progressions are the following two.

Theorem 15. Let m and N be positive integers, let d be a nonnegative integer, let C, D, q be rational numbers, q > 1, such that C + D, C + Dq, C + Dq^{2}, …, C + Dq^{2m+d−1} are integers, and such that 2m + d ≤ N and C + Dq^{2m+d−1} ≤ N. Then the number of perfect matchings of a (2m + d) × N Aztec rectangle, where all the vertices on the horizontal row that is by d below the central row, except for the (C + D)-th, the (C + Dq)-th, (C + Dq^{2})-th, …, and the (C + Dq^{2m+d−1})-th vertex, have been removed, equals

2^{m^{2}+(d+2)m+\binom{d+1}{2}} D^{m^{2}+(d−1)m+\binom{d}{2}}q^{\frac{1}{6} (m+d−1)(4m^{2}+(2d−5)m+d(d−2))}

× \frac{∏_{i=1}^{m} |(q^{2}; q^{2})_{i−1}| ∏_{i=1}^{m+d} |(q^{2}; q^{2})_{i−1}|}{∏_{i=1}^{d}(−q; q)_{i−1} ∏_{i=1}^{m}(i − 1)! ∏_{i=1}^{m+d}(i − 1)!}. (4.9)

Theorem 16. Let m and N be positive integers, let d be a nonnegative integer, let C, D, q be rational numbers, q > 1, such that C + D, C + Dq, C + Dq^{2}, …, C+Dq^{2N−2m−d+1} are integers, and such that 2m+d−1 ≥ N and C+Dq^{2N−2m−d+1} ≤ N + 1. Then the number of perfect matchings of a (2m + d − 1) × N Aztec rectangle, where all the vertices on the horizontal row that is by d below the central row, except for the (C+D)-th, the (C+Dq)-th, (C+Dq^{2})-th, …, and the (C+Dq^{2N−2m−d+1})-th vertex, have been removed, equals

2^{m^{2}+(d−2)m+\binom{d−1}{2}+N} D^{m^{2}+(d−1)m+\binom{d}{2}+N(N−2m−d+1)}

× q^{\frac{1}{6} (N−m)(4(N−m−d+1)^{2}+(2d−5)(N−m−d+1)+d(d−2))}

× \frac{∏_{i=m+1}^{N+1}(i − 1)! ∏_{i=m+d+1}^{N+1}(i − 1)! ∏_{i=1}^{N−m+1} |(q^{2}; q^{2})_{i−1}| ∏_{i=1}^{N−m−d+1} |(q^{2}; q^{2})_{i−1}|}{∏_{i=1}^{d}(−q; q)_{i−1} ∏_{i=1}^{2N−2m−d+2}(C + Dq^{i−1} − 1)! (N + 1 − C − Dq^{i−1})!}, (4.10)

where the product ∏_{i=m+d+1}^{N+1}(i − 1)! has to be interpreted as 1 if N = m + d − 1 and as 0 if N < m + d − 1, and similarly for the other products.

Proof of Theorems 15 and 16. We set t_{i} = C + Dq^{i−1}, i = 1, 2, …, in Theorems 11 and 12. The resulting sums turn out to be exactly of the form of the left-hand side of (3.6), with q → q^{2}, x = q and y = q^{3}, respectively x = q^{3} and y = q^{3}, depending on d being even or odd. Hence, it can be evaluated. The obtained expressions can be drastically simplified and eventually turn into (4.9) and (4.10), respectively. □

It should be observed that, formally, Theorems 13 and 14 can be seen as limit cases of Theorems 15 and 16. Namely, if in Theorems 15 and 16 we replace C by \frac{q^{C}−1}{q−1} − \frac{q^{D}−1}{(q−1)^{2}} and D by \frac{q^{D}−1}{(q−1)^{2}} , and then perform the limit q → 1^{+}, we obtain, formally, Theorems 13 and 14.

Acknowledgement. I am indebted to the anonymous referee for an extremely careful reading of the manuscript and for pointing out that Theorem 6 is also a special case of the q-integral evaluation proved in [4] and [10].

References

1. R. Askey, Some basic hypergeometric extensions of integrals of Selberg and Andrews, SIAM J. Math. Anal. 11 (1980), 938–951.

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

3. M. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings (Parts 1, 2), J. Alg. Combin. 1 (1992), 111–132, 219–234.

4. R. J. Evans, Multidimensional beta and gamma integrals, Contemp. Math. 166 (1994), 341–359.

5. M. Fulmek, A Schur function identity, J. Combin. Theory Ser. A 77 (1997), 177–180.

6. M. Fulmek and C. Krattenthaler, Lattice path proofs for determinant formulas for symplectic and orthogonal characters, J. Combin. Theory Ser. A 77 (1997), 3–50.

7. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint (1989).

8. I. P. Goulden, Quadratic forms of skew Schur functions, Europ. J. Combin. 9 (1988), 161–168.

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

10. K. W. J. Kadell, A simple proof of an Aomoto-type generalization of Askey’s last conjectured Selberg q-integral, preprint.

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

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

13. W. H. Mills, D. H. Robbins and H. Rumsey, Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (1983), 340–359.

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

15. J. Propp, Enumeration of matchings: Problems and progress, New Perspectives in Geometric Combinatorics (L. J. Billera, A. Björner, C. Green, R. Simion, R. P. Stanley, eds.), Mathematical Sciences Research Institute publication #37, Cambridge University Press, Cambridge 1999, (to appear).

16. J. Propp and R. P. Stanley, Domino tilings with barriers, J. Combin. Theory Ser. A 87 (1999), 347–356.

17. B. E. Sagan, The symmetric group, Wadsworth & Brooks/Cole, Pacific Grove, California, 1991.

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

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