A FACTORIZATION THEOREM FOR LOZENGE TILINGS

OF A HEXAGON WITH TRIANGULAR HOLES

M. Ciucu^{†} and C. Krattenthaler^{‡}

Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA

Fakultät für Mathematik der Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

          WWW: http://www.mat.univie.ac.at/~kratt

Abstract. In this paper we present a combinatorial generalization of the fact that the number of plane partitions that fit in a 2a × b × b box is equal to the number of such plane partitions that are symmetric, times the number of such plane partitions for which the transpose is the same as the complement. We use the equivalent phrasing of this identity in terms of symmetry classes of lozenge tilings of a hexagon on the triangular lattice. Our generalization consists of allowing the hexagon have certain symmetrically placed holes along its horizontal symmetry axis. The special case when there are no holes can be viewed as a new, simpler proof of the enumeration of symmetric plane partitions.

1. Introduction

The enumeration of the ten symmetry classes of plane partitions that fit in a given box — equivalently, symmetry classes of lozenge tilings of hexagons on the triangular lattice — forms a classical chapter of enumerative combinatorics (see [21],[3],[2],[15],[23],[13]). Explicit product formulas exist for all symmetry classes, which makes it possible to find relations between them. One such striking relation is that

M(H_{2a,b,b}) = M_{−}(H_{2a,b,b}) M_{|}(H_{2a,b,b}),  (1.1)

†Research partially supported by NSF grants DMS-1101670 and DMS-1501052. ‡Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and

F50-N15, the latter in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics.”

Typeset by AMS-TEX

where H_{2a,b,b} is the hexagon of side-lengths 2a, b, b, 2a, b, b (clockwise from the western^{1} side), M(R) denotes the number of lozenge tilings^{2} of the lattice region R, and M_{−}(R) (resp., M_{|}(R)) is the number of lozenge tilings of R that are invariant under reflection across the horizontal (resp., vertical) symmetry axis of R (provided R possesses such symmetries).

Equation (1.1) is an immediate consequence of the explicit formulas enumerating the symmetry classes of plane partitions (in the notation of [21], M(H_{2a,b,b}) = N_{1}(2a, b, b) is the number of plane partitions fitting in a 2a×b×b box, M_{−}(H_{2a,b,b}) = N_{6}(2a, b, b) is the number of transpose-complementary plane partitions, and M_{|}(H_{2a,b,b}) = N_{2}(2a, b, b) is the number of symmetric plane partitions, fitting in the same box). However, the simplicity of (1.1) raises two natural questions: How can one see directly (without explicitly evaluating the terms) that the equation holds? And how can one generalize it?

We presented a generalization in terms of Schur functions in [8], which gave an algebraic reason for why equation (1.1) holds. In this paper we present a combinatorial generalization, in terms of hexagons that are allowed to have certain symmetrically placed holes along their horizontal symmetry axis. The special case when there are no holes can be regarded as a new proof of the enumeration of symmetric plane partitions (first proved by Andrews [1]), as it follows, via our factorization result, from the base case (due to MacMahon [18]) and the transpose-complementary case (due to Proctor [20]), as we explain in Section 6. Our results are described in the next section.

There are several other simple equations relating the symmetry classes of plane partitions which can be proved directly (see e.g. [5][7][16]). There is still no unified proof available for all ten symmetry classes, but new direct ways of relating them to one another may help achieving this goal.

2. The factorization theorem

Let n, m, l be positive integers, and let k_{1}, k_{2}, …, k_{l} be positive integers with k_{1} < k_{2} < ⋯ < k_{l} ≤ n/2. Denote by H_{n,2m}(k_{1}, k_{2}, …, k_{l}) the region obtained from the hexagon with side lengths n, 2m, n, n, 2m, n (where the sides of length 2m are vertical) by removing the following 2l triangles of side length two from along its horizontal symmetry axis: l left-pointing such triangles, with vertical sides at distances 2k_{1}, 2k_{2}, …, 2k_{l} from the left side of the hexagon (in units equal to \sqrt{3} times the lattice spacing), and their reflections across the vertical symmetry axis of the hexagon. Figure 2.1 shows the region H_{15,10}(2, 5, 7).

The factorization theorem which we prove in this paper is the following generalization of (1.1).

1Throughout this paper, we consider the triangular lattice drawn in the plane so that one of the families of lattice lines is vertical.

2A lozenge is the union of two unit triangles sharing an edge; a lozenge tiling of a lattice region R is a covering of R by lozenges, with no holes or overlaps.

Figure 2.1. The hexagon with holes H_{15,10}(2, 5, 7).

Theorem 2.1. For all positive integers n, m, l and positive integers k_{1}, k_{2}, … k_{l} with k_{1} < k_{2} < ⋯ < k_{l} ≤ n/2, we have

M (H_{n,2m}(k_{1}, k_{2}, …, k_{l})) = M_{−} (H_{n,2m}(k_{1}, k_{2}, …, k_{l})) M_{|} (H_{n,2m}(k_{1}, k_{2}, …, k_{l})) . (2.1)

There are n − 2l lozenge positions (i.e., positions that might be occupied by a lozenge in some tiling) along the horizontal symmetry axis of H_{n,2m}(k_{1}, k_{2}, …, k_{l}) which can accommodate horizontal lozenges (these are shaded in the picture on the left in Figure 2.2). Clearly, a necessary condition for a tiling to be symmetric about the horizontal symmetry axis is that all these n − 2l positions are occupied by horizontal lozenges.

It follows that, if we denote by H_{n,2m}^{+}(k_{1}, k_{2}, …, k_{l}) the portion of the region H_{n,2m}(k_{1}, k_{2}, …, k_{l}) that is above the zig-zag line which starts at the center of the left side of the hexagon and proceeds just above its horizontal symmetry axis until it reaches the center of the right side (for H_{15,10}(2, 5, 7) this construction is pictured on the left in Figure 2.2), then we have

M_{−} (H_{n,2m}(k_{1}, k_{2}, …, k_{l})) = M (H_{n,2m}^{+}(k_{1}, k_{2}, …, k_{l})) .  (2.2)

Note also that if F_{n,2m}(k_{1}, k_{2}, …, k_{l}) is the region consisting of the left half of H_{n,2m}(k_{1}, k_{2}, …, k_{l}), with the portion of its boundary that is along the vertical symmetry axis of H_{n,2m}(k_{1}, k_{2}, …, k_{l}) taken to be free (i.e., when considering lozenge Figure 2.2. The regions H_{15,10}^{+}(2, 5, 7) and H_{15,10}^{−}(2, 5, 7) (left); F_{15,10}(2, 5, 7) (right).

tilings of this region, lozenges are allowed to protrude out halfway across this part of the boundary; F_{15,10}(2, 5, 7) is illustrated on the right in Figure 2.2), then we have

M_{|} (H_{n,2m}(k_{1}, k_{2}, …, k_{l})) = M_{f} (F_{n,2m}(k_{1}, k_{2}, …, k_{l})) ,  (2.3)

where, for a lattice region R with free boundary conditions along some portion of its boundary, M_{f}(R) denotes the number of lozenge tilings of R in which lozenges are allowed to protrude out halfway across the free part of the boundary.

In view of (2.2) and (2.3), the statement of Theorem 2.1 is equivalent to the equality

M (H_{n,2m}(k_{1}, k_{2}, …, k_{l}))

= M (H_{n,2m}^{+}(k_{1}, k_{2}, …, k_{l})) M_{f} (F_{n,2m}(k_{1}, k_{2}, …, k_{l})). (2.4)

On the other hand, if H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l}) is the region below the zig-zag line that defined H_{n,2m}^{+}(k_{1}, k_{2}, …, k_{l}), with the extra specification that the n − 2l lozenge positions fitting in the “folds” of the zig-zag are weighted by 1/2 (the shaded positions on the left in Figure 2.2), then the factorization theorem of [4, Theorem 1.2] implies that

M (H_{n,2m}(k_{1}, k_{2}, …, k_{l}))

= 2^{n−2l} M (H_{n,2m}^{+}(k_{1}, k_{2}, …, k_{l})) M^{∗} (H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l})). (2.5)

Here, M^{∗} (H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l})) denotes the weighted count of the lozenge tilings of H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l}), in which each lozenge occupying one of the special n − 2l tile positions has weight 1/2, all other lozenges have weight 1, and the weight of a tiling is the product of the weights of its tiles.

Comparison of (2.5) with (2.4) shows that, in order to prove Theorem 2.1, it suffices to establish the relation

M_{f} (F_{n,2m}(k_{1}, k_{2}, …, k_{l})) = 2^{n−2l} M^{∗} (H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l})).  (2.6)

This is what we do in the next two sections.

3. Non-intersecting lattice paths, Pfaffians, and determinants

Recall that a family of lattice paths is called non-intersecting if no two paths in the family share a vertex. In this section, we interpret the perfect matching counts on each side of (2.6) as the (weighted) number of a certain family of non-intersecting lattice paths. Using well-known determinantal and Pfaffian formulas for the number of non-intersecting lattice paths, this enables us to express the left-hand side in terms of a Pfaffian and the right-hand side in terms of a determinant.

We start with the left-hand side. If we apply the standard translation of lozenge tilings to families of non-intersecting lattice paths (see e.g. [9] and [5]), then we obtain that M_{f} (F_{n,2m}(k_{1}, k_{2}, …, k_{l})) is equal to the number of all families

(P_{−m+1}, P_{−m+2}, …, P_{m}, P_{1^{−}}, P_{2^{−}}, …, P_{l^{−}}, P_{1^{+}}, P_{2^{+}}, …, P_{l^{+}})

of non-intersecting lattice paths, where for s ∈ {−m + 1, −m + 2, …, m}, P_{s} starts at A_{s} := (s, −s + 1), while, for t ∈ {1, 2, …, l}, P_{t^{−}} starts at B_{t^{−}} := (k_{t}, k_{t} + 1) and P_{t^{+}} starts at B_{t^{+}} := (k_{t} + 1, k_{t}), and all paths end somewhere on the line x + y = n + 1. See Figure 3.2 for the family of non-intersecting lattice paths which corresponds to the tiling in Figure 3.1 (which also indicates, by dotted lines, the non-intersecting paths of lozenges that encode that tiling).

By a slight extension of a theorem due to Okada [19, Theorem 3] and Stembridge [22, Theorem 3.1], the number of the above families of non-intersecting lattice paths can be expressed in terms of a Pfaffian. The reader should recall that the Pfaffian of a skew-symmetric 2n × 2n matrix A can be defined by (see e.g. [22, p. 102])

Pf A := ∑_{π∈M[1,...,2n]} sgn π_{∏_{i<j} i,j matched in π}A_{i,j} ,  (3.1)

where M[1, 2, …, 2n] denotes the set of all perfect matchings (1-factors) of (the complete graph on) {1, 2, …, 2n}, cr(π) is the number of crossings^{3} of the perfect matching π, and sgn π = (−1)^{cr(π)}. It is a well-known fact (see e.g. [22, Prop. 2.2]) that

(Pf A)^{2} = det A.  (3.2)

Theorem 3.1 (Okada, Stembridge). Let {u_{1}, u_{2}, …, u_{p}} and I = {I_{1}, I_{2}, … } be finite sets of lattice points in the integer lattice ℤ^{2}, with p even. Let 𝔖_{p} be the

3A crossing is a quadruple i < j < k < l such that, under π, i is paired with k, and j is paired with l.

A lozenge tiling of the region F_{8,8}(2); the right boundary is free. The dotted lines mark paths of lozenges. They determine the tiling uniquely.

Figure 3.1

symmetric group on {1, 2, …, p}, set u_{π} = (u_{π(1)}, u_{π(2)}, …, u_{π(p)}), and denote by P^{nonint}(u_{π} → I) the number of families (P_{1}, P_{2}, …, P_{p}) of non-intersecting lattice paths consisting of unit horizontal and vertical steps in the positive direction, with P_{k} running from u_{π(k)} to I_{j_{k}}, k = 1, 2, …, p, for some indices j_{1}, j_{2}, …, j_{p} satisfying j_{1} < j_{2} < ⋯ < j_{p}.

Then we have

∑_{π∈𝔖_{p}}(sgn π) · P^{nonint}(u_{π} → I) = Pf(Q),  (3.3)

with the matrix Q = (Q_{i,j})_{1≤i,j≤p} given by

Q_{i,j} = ∑_{1≤u<v} (P(u_{i} → I_{u}) · P(u_{j} → I_{v}) − P(u_{j} → I_{u}) · P(u_{i} → I_{v})),  (3.4)

where P(A → E) denotes the number of lattice paths from A to E.

Application of this formula to our situation leads to the following intermediate result. In its statement, and throughout this paper, sums in which the lower in-

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}_{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • • • • •  • • • • • • • • • •  ∘^{A_{−3}}^{A_{−2}}^{A_{−1}}^{A_{0}} _{A_{1}} _{A_{2}} _{A_{3}} _{A_{4}}^{B_{1^{−}}}^{B_{1^{+}}}^{P_{1^{−}}}^{P_{1^{+}}}  _{P_{4}}_{P_{3}}_{P_{2}}^{P_{1}}^{P_{0}}^{P_{−1}}^{P_{−2}}^{P_{−3}}  _{x}^{y}

The paths of lozenges of Figure 3.1 drawn as non-intersecting lattice paths on ℤ^{2}

Figure 3.2

dex is larger than the upper index have to be interpreted according to the standard convention

∑_{r=m}^{n−1} Expr(k) = \{ \begin{matrix}∑_{r=m}^{n−1} Expr(k) & n > m \\ 0 & n = m \\ − ∑_{k=n}^{m−1} Expr(k) & n < m. \end{matrix}  (3.5)

Proposition 3.2. Let n, m, l be positive integers, and k_{1}, k_{2}, … k_{l} positive integers with k_{1} < k_{2} < ⋯ < k_{l} ≤ n/2. The number of families

(P_{−m+1}, P_{−m+2}, …, P_{m}, P_{1^{−}}, P_{2^{−}}, …, P_{l^{−}}, P_{1^{+}}, P_{2^{+}}, …, P_{l^{+}})

of non-intersecting lattice paths, where for s ∈ {−m + 1, −m + 2, …, m}, P_{s} starts at A_{s} = (s, −s + 1), while, for t ∈ {1, 2, …, l}, P_{t^{−}} starts at B_{t^{−}} = (k_{t}, k_{t} + 1) and P_{t^{+}} starts at B_{t^{+}} = (k_{t} + 1, k_{t}), and all paths end somewhere on the line x + y = n + 1, is equal to

(−1)^{\binom{l}{2}} Pf(M),  (3.6)

where M is the skew-symmetric matrix with rows and columns indexed by {−m + 1, −m + 2, …, m, 1^{−}, 2^{−}, …, l^{−}, 1^{+}, 2^{+}, …, l^{+}}, and entries given by

M_{i,j} = \{ \begin{matrix}∑_{r=i−j+1}^{j−i} \binom{2n}{n+r}, & if − m + 1 ≤ i < j ≤ m, \\ ∑_{r=i+1}^{−i} \binom{2n−2k_{t}}{n−k_{t}+r}, & if −m + 1 ≤ i ≤ m and j = t^{−}, \\ ∑_{r=i}^{−i+1} \binom{2n−2k_{t}}{n−k_{t}+r}, & if −m + 1 ≤ i ≤ m and j = t^{+}, \\ 0, & if i = t^{−}, j = t̂^{−}, and 1 ≤ t < t̂≤ l, \\ \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂} + \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂+1}, & if i = t^{−}, j = t̂^{+}, and 1 ≤ t, t̂≤ l, \\ 0, & if i = t^{+}, j = t̂^{+}, and 1 ≤ t < t̂≤ l. \end{matrix}

Proof. We choose p = 2m + 2l, u_{i} = A_{−m+i} for i = 1, 2, …, 2m, u_{i} = B_{(i−2m)^{−}} for i = 2m+1, 2m+2, …, 2m+l, u_{i} = B_{(i−2m−l)^{+}} for i = 2m+l+1, 2m+l+2, …, 2m+2l, and I_{j} = (j, n + 1 − j) for j = −m + 1, −m + 2, …, n + m in Theorem 3.1. It is not difficult to convince oneself that, for this choice of starting and ending points, all families of non-intersecting lattice paths counted on the left-hand side of (3.3) give rise to permutations π which have the same sign, and this sign is (−1)^{\binom{l}{2}}. Hence, the right-hand side of (3.3) indeed counts the families of non-intersecting lattice paths that we need to count, up to the overall sign (−1)^{\binom{l}{2}}. Then by Theorem 3.1, the number of these families is given by the Pfaffian (−1)^{\binom{l}{2}} Pf(Q), where the entries of the skew-symmetric matrix Q are given by (3.4). Consequently, for all pairs of indices (i, j) with 1 ≤ i < j ≤ 2m + 2l, we have to compute the sum on the right-hand side of (3.4). Since, in our situation, the definition of the starting points u_{i} has three different cases, we have to distinguish six cases. Since all of them are very similar, we treat only one here in detail.

We choose the case of the (i, j)-entry of Q with 1 ≤ i < j ≤ 2m. For this we have to compute the sum^{4}

∑_{−m+1≤u<v≤n+m} (P((i, −i + 1) → (u, n + 1 − u)) · P((j, −j + 1) → (v, n + 1 − v))

− P((j, −j + 1) → (u, n + 1 − u)) · P((i, −i + 1) → (v, n + 1 − v))).

4We point out that the convention concerning row and column indices in Theorem 3.1 is different from the indexation which we use here.

Using the simple fact that P((a, b) → (c, d)) = \binom{c+d−a−b}{c−a}, the above sum turns into

∑_{−m+1≤u<v≤n+m} (\binom{n}{u − i}\binom{n}{v − j} − \binom{n}{u − j}\binom{n}{v − i})

= ∑_{v=0}^{n+m} ∑_{u=−m+1}^{n+m} (\binom{n}{n − u + i}\binom{n}{u + v − j} − \binom{n}{n − u + j}\binom{n}{u + v − i})

= ∑_{v=0}^{n+m} (\binom{2n}{n + v + i − j} − \binom{2n}{n + v + j − i})

= ∑_{v=0}^{n+m} (\binom{2n}{n − v + j − i} − \binom{2n}{n − v + i − j})

= ∑_{r=1}^{j−i} \binom{2n}{n + r} + ∑_{r=i−j+1}^{0} \binom{2n}{n + r} = ∑_{r=i−j+1}^{j−i} \binom{2n}{n + r},

where we used the Chu–Vandermonde summation formula in the third line. This is exactly the corresponding expression in the definition of M_{i,j}. □

Now we turn to the right-hand side of (2.6). We encode the lozenge tilings of H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l}) by families of non-intersecting paths of lozenges (equivalently, lattice paths) connecting vertical unit segments on its boundary. See Figures 3.3 and 3.4 for an example of this correspondence. The power of 2 can then be absorbed by noticing that

2^{n−2l} M^{∗} (H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l}))

is equal to the weighted enumeration of families (P_{1}, P_{2}, …, P_{m}, P_{1^{+}}, P_{2^{+}}, …, P_{l^{+}}) of non-intersecting lattice paths, where, for 1 ≤ s ≤ m, the path P_{s} runs from A_{s} := (s, −s + 1) to E_{s} := (n + s, n − s + 1), for 1 ≤ t ≤ l, the path P_{t^{+}} runs from B_{t^{+}} := (k_{t} +1, k_{t}) to E_{s} := (n−k_{t} +1, n−k_{t}), the paths never cross the main diagonal x = y, and the weight of a family of paths is 2^{T}, where T is the number of touching points of the paths in the family with the main diagonal.

Indeed, if there are k such touching points, then there are precisely n − 2l − k lozenges occupying positions weighted by 1/2 (see Figure 3.3) in the lozenge tiling of H_{n,2m}^{−}(k_{1}, k_{2}, …, k_{l}) corresponding to that family of lattice paths, and thus the weight of that tiling is

(\frac{1}{2})^{n−2l−k} = (\frac{1}{2})^{n−2l} 2^{k}.

Then the fraction on the right-hand side above cancels the factor of 2^{n−2l} on the right-hand side of (2.6), and the above claim follows.

By the classical Lindström–Gessel–Viennot formula for the enumeration of nonintersecting lattice paths (see [17][10][22]), the above weighted count can be written in terms of a determinant. Below we recall this formula.

Let G = (V, E) be a weighted directed acyclic graph with vertices V and directed edges E, with weight function w on its edges. The weight w(P) of a path P in the

2m{  n }

A lozenge tiling of H_{8,8}^{−}(2)

Figure 3.3

graph is defined by ∏_{e} w(e), where the product is over all edges e of the path. We denote the set of all paths in G from u to v by P(u → v), and the set of all families (P_{1}, P_{2}, …, P_{p}) of paths, where P_{i} runs from u_{i} to v_{i}, i = 1, 2, …, p, by P(u → v), with u = (u_{1}, u_{2}, …, u_{p}) and v = (v_{1}, v_{2}, …, v_{p}). Denote by P^{+}(u → v) the set of all families (P_{1}, P_{2}, …, P_{p}) in P(u → v) that are non-intersecting.

The weight w(P) of a family P = (P_{1}, P_{2}, …, P_{p}) of paths is defined as the product ∏_{i=1}^{p} w(P_{i}) of all the weights of the paths in the family. Finally, given a set M with weight function w, we write GF(M; w) for the generating function ∑_{x∈M} w(x).

Theorem 3.3 (Lindström, Gessel and Viennot). With the above notation, we assume that the only permutation π ∈ 𝔖_{p} for which a family of non-intersecting lattice paths (P_{1}, P_{2}, …, P_{p}) exists such that the path P_{i} connects u_{i} with v_{π(i)} is the identity permutation. Then

GF(P^{+}(u → v); w) = det_{1≤i,j≤p} ( GF(P(u_{j} → v_{i}); w)).  (3.7)

Application of this formula to our situation leads to the following intermediate result.

Proposition 3.4. Let n, m, l be positive integers, and k_{1}, k_{2}, … k_{l} positive integers with k_{1} < k_{2} < ⋯ < k_{l} ≤ n/2. Then the generating function ∑_{P} w(P) of all families

P = (P_{1}, P_{2}, …, P_{m}, P_{1^{+}}, P_{2^{+}}, …, P_{l^{+}})

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∘; ∘; A_{1}; A_{2}; A_{3}; A_{4}; B_{1^{+}}; P_{1^{+}}; P_{4}; P_{3}; P_{2}; P_{1}; x = y; x; y]

The paths of lozenges of Figure 3.3 drawn as non-intersecting lattice paths on ℤ^{2}

Figure 3.4

of non-intersecting lattice paths, where, for 1 ≤ s ≤ m, the path P_{s} runs from A_{s} = (s, −s + 1) to E_{s} = (n + s, n − s + 1), for 1 ≤ t ≤ l, the path P_{t^{+}} runs from B_{t^{+}} = (k_{t} + 1, k_{t}) to E_{t} := (n − k_{t} + 1, n − k_{t}), all the paths never crossing over the main diagonal x = y, and the weight w(P) of a path family P being 2^{T (P)} — where T (P) is the number of touching points of the paths in P with the main diagonal — is given by

det(N),

where N is the matrix with rows and columns indexed by {1, 2, …, m, 1^{+}, 2^{+}, …, l^{+}}, and entries given by

N_{i,j} = \{ \begin{matrix}\binom{2n}{n+j−i} + \binom{2n}{n−i−j+1}, & if 1 ≤ i, j ≤ m, \\ \binom{2n−2k_{t}}{n−k_{t}−i+1} + \binom{2n−2k_{t}}{n−k_{t}−i}, & if 1 ≤ i ≤ m and j = t^{+}, \\ \binom{2n−2k_{t}}{n−k_{t}−j+1} + \binom{2n−2k_{t}}{n−k_{t}−j}, & if i = t^{+} and 1 ≤ j ≤ m , \\ \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂} + \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂−1}, & if i = t^{+}, j = t̂^{+}, and 1 ≤ t, t̂≤ l. \end{matrix}

Proof. We choose p = m + l, u_{i} = A_{i} for i = 1, 2, …, m, and u_{i} = B_{(i−m)^{+}} for i = m + 1, m + 2, …, m + l in Theorem 3.3. The underlying directed graph G is the graph whose vertices are the lattice points in ℤ^{2} lying on or below the main diagonal x = y, and whose edges are the horizontal edges (x, y) → (x + 1, y) and vertical edges (x, y − 1) → (x, y) with x ≥ y. The weight of horizontal edges is 1, as is the weight of vertical edges (x, y − 1) → (x, y) for x > y, while the weight of a vertical edge (x, x − 1) → (x, x) is 2. Then it is not difficult to see that, for this choice of starting and ending points, the technical condition formulated at the beginning of the statement of Theorem 3.3 is satisfied. We can therefore apply the theorem. In order to express the entries of the resulting determinant, we have to compute the generating function

GF ((a, b) → (c, d); w),  (3.8)

where a > b and c > d. We claim that this generating function is given by

\binom{c + d − a − b}{c − a} + \binom{c + d − a − b}{d − a}.  (3.9)

Once this is shown, the displayed expressions for the entries N_{i,j} readily follow.

For the proof of our claim, we note that the generating function in (3.8) is a generating function for paths from (a, b) to (c, d) which never cross above the main diagonal x = y, and in which the weight of a path P is 2^{T (P)}, where T (P) is the number of touching points of P with the main diagonal. We may interpret this weight combinatorially as follows: each of the above paths P gives rise to 2^{T (P)} paths if we reflect path portions between two successive touching points across the main diagonal x = y, as well as the portion of the path from the last touching point until the end point (c, d). As a moment’s thought shows, in this way we obtain all paths from (a, b) to (c, d) (meaning that we also obtain the ones which do cross above the main diagonal) as well as all paths from (a, b) to (d, c). The total number of these paths is given by (3.9). This completes the proof. □

4. Equality of Pfaffian and determinant

We have seen in the previous section that, in order to establish (2.6), we must show that the signed Pfaffian expression in (3.6) equals the determinant in Proposition 3.4. This is what we do in this section.

We should note that the matrix M in Proposition 3.2 has the form

M = ( \begin{matrix}X & Y \\ −Y^{t} & Z \end{matrix} ) ,

where X = (x_{j−i})_{−m+1≤i,j≤m} and Z = (z_{i,j})_{i,j∈{1^{−},...,l^{−},1^{+},...,l^{+}}} are skew-symmetric, and Y = (y_{i,j})_{−m+1≤i≤m, j∈{1^{−},...,l^{−},1^{+},...,l^{+}}} is a 2m × 2l matrix. Recalling the convention (3.5) of how to read sums, close inspection reveals that y_{i,t^{−}} = −y_{−i,t^{−}} and y_{i,t^{+}} = −y_{−i+2,t^{+}}, for all i with −m + 1 ≤ i ≤ m for which both sides of an equality are defined, and 1 ≤ t ≤ l. These properties are fundamental in the next lemma.

Lemma 4.1. For a positive integer m and a non-negative integer l, let A be a matrix of the form

A = ( \begin{matrix}X & Y \\ −Y^{t} & Z \end{matrix} ) ,

where X = (x_{j−i})_{−m+1≤i,j≤m} and Z = (z_{i,j})_{i,j∈{1^{−},...,l^{−},1^{+},...,l^{+}}} are skew-symmetric, and Y = (y_{i,j})_{−m+1≤i≤m, j∈{1^{−},...,l^{−},1^{+},...,l^{+}}} is a 2m×2l matrix. Suppose in addition that y_{i,t^{−}} = −y_{−i,t^{−}} and y_{i,t^{+}} = −y_{−i+2,t^{+}}, for all i with −m + 1 ≤ i ≤ m for which both sides of an equality are defined, and 1 ≤ t ≤ l, and that z_{i,j} = 0 for all i, j ∈ {1^{−}, …, l^{−}}. Then

Pf(A) = (−1)^{\binom{l}{2}} det(B),

where

B = ( \begin{matrix}X̄ & Ȳ_{1} \\ Ȳ_{2} & Z̄ \end{matrix} ) ,

with

X̄ = (x̄_{i,j})_{1≤i,j≤m},
Ȳ_{1} = (y_{−i+1,j})_{1≤i≤m, j∈{1^{+},...,l^{+}}},
Ȳ_{2} = (−y_{i,j})_{i∈{1^{−},...,l^{−}}, 1≤j≤m},
Z̄ = (z_{i,j})_{i∈{1^{−},...,l^{−}}, j∈{1^{+},...,l^{+}}},

and the entries of X̄ are defined by

x̄_{i,j} = x_{|j−i|+1} + x_{|j−i|+3} + ⋯ + x_{i+j−1}.

Proof. Starting from A, we construct a new matrix Â as follows. Replace the i-th row of A by the sum

∑_{r=0}^{−i}(row i + 2r of A),

for i = 0, −1, …, −m + 1. In the resulting matrix, do the analogous operations with the columns. Denote the matrix obtained this way by Â. Note that these operations do not change the value of Pf(A), so Pf(A) = Pf(Â).

For −m + 1 ≤ i, j ≤ 0, the (i, j)-entry in Â is

∑_{r=0}^{−i} ∑_{s=0}^{−j} x_{j+2s−i−2r} = ∑_{t=i}^{−j}(min{−i, −j − t} − max{0, −t} + 1) x_{j−i+2t}.  (4.1)

By assumption, the matrix X is skew-symmetric, that is, we have x_{r} = −x_{−r} for −m + 1 ≤ r ≤ m. One readily verifies that

min{−i, −j −t}−max{0, −t}+1 = min{−i, −j −(i−j −t)}−max{0, −(i−j −t)}+1,

which is invariant under the replacement t → i − j − t. Together with the skewsymmetry, this implies that the sum in (4.1) vanishes, and, hence, the (i, j)-entry in Â for −m + 1 ≤ i, j ≤ 0 is zero.

Next we compute the (i, j)-entry of Â for −m + 1 ≤ i ≤ 0 and 1 ≤ j ≤ m. This entry is not affected by the column operations. Hence, it equals

∑_{r=0}^{−i} x_{j−i−2r} = \{ \begin{matrix}x_{j−i} + x_{j−i−2} + ⋯ + x_{j+i}, & if j + i ≥ 1, \\ x_{j−i} + x_{j−i−2} + ⋯ + x_{−j−i+2}, & if j + i ≤ 0, \end{matrix}  (4.2)

where, in the second case, we used again that x_{r} = −x_{−r} for all r.

Now we compute the (i, j)-entry of Â for −m+1 ≤ i ≤ 0 and j = t^{−} with 1 ≤ t ≤ l. Again, this entry is not affected by the column operations, and, hence, it equals

∑_{r=0}^{−i} y_{i+2r,t^{−}} = 0,

where we used the property that y_{r,t^{−}} = −y_{−r,t^{−}} for all r and t. So also these entries vanish.

Finally, we compute the (i, j)-entry of Â for −m + 1 ≤ i ≤ 0 and j = t^{+} with 1 ≤ t ≤ l. Also this entry is not affected by the column operations, and, hence, it equals

∑_{r=0}^{−i} y_{i+2r,t^{+}} = y_{i,t^{+}} + ∑_{r=1}^{−i} y_{i+2r,t^{+}} = y_{i,t^{+}},

where we used the property that y_{r,t^{+}} = −y_{−r+2,t^{+}} for all r and t. In other words, these entries do not change. The same is true for all other entries above the diagonal which we did not yet consider, as they are not affected by our row and column operations. Since we did the same operation on the columns as we did on the rows, the resulting matrix Â is still skew-symmetric.

Summarizing, the new matrix Â has the block form

Â = ( \begin{matrix}0 & X̂ & 0 & Y_{−,+} \\ −X̂^{t} & X^{+} & Y_{+,−} & Y_{+,+} \\ 0 & −Y_{+,−}^{t} & 0 & Z_{−,+} \\ −Y_{−,+}^{t} & −Y_{+,+}^{t} & −Z_{−,+}^{t} & Z_{+,+} \end{matrix} ) ,

where

X^{+} = (x_{j−i})_{1≤i,j≤m},
X̂ = (x̂_{i,j})_{−m+1≤i≤0, 1≤j≤m},

with entry x̂_{i,j} given by (4.2),

Y_{−,+} = (y_{i,j})_{−m+1≤i≤0, j∈{1^{+},...,l^{+}}},
Y_{+,−} = (y_{i,j})_{1≤i≤m, j∈{1^{−},...,l^{−}}},
Y_{+,+} = (y_{i,j})_{1≤i≤m, j∈{1^{+},...,l^{+}}},

and

Z_{−,+} = (z_{i,j})_{i∈{1^{−},...,l^{−}}, j∈{1^{+},...,l^{+}}},
Z_{+,+} = (z_{i,j})_{i,j∈{1^{+},...,l^{+}}}.

By rearranging rows and columns in the same way, this matrix may be brought into the form

( \begin{matrix}0 & 0 & X̂ & Y_{−,+} \\ 0 & 0 & −Y_{+,−}^{t} & Z_{−,+} \\ −X̂^{t} & Y_{+,−} & X^{+} & Y_{+,+} \\ −Y_{−,+}^{t} & −Z_{−,+}^{t} & −Y_{+,+}^{t} & Z_{+,+} \end{matrix} ) .

All these operations did not change the value of the Pfaffian, except for a sign of (−1)^{ml}. However, by the identity^{5}

Pf ( \begin{matrix}0 & D \\ −D^{t} & E \end{matrix} ) = (−1)^{\binom{d}{2}} det(D)

for any d × d matrix D, the Pfaffian of the last matrix is simply

Pf(A) = Pf(Â) = (−1)^{\binom{m+l}{2}+ml} det ( \begin{matrix}X̂ & Y_{−,+} \\ −Y_{+,−}^{t} & Z_{−,+} \end{matrix} ) .

Here, to be in line with the indexations of the blocks in this matrix, the rows are indexed by i ∈ {−m+1, −m+2, …, 0, 1^{−}, 2^{−}, …, l^{−}}, while the columns are indexed by j ∈ {1, 2, …, m, 1^{+}, 2^{+}, …, l^{+}}. We change the row index i, with i = −m+1, −m+ 2, …, 0, to −i + 1. This amounts to reversing the order of these rows. The new row index will then range in {1, 2, …, m, 1^{−}, 2^{−}, …, l^{−}}. Hence, this leads to

Pf(A) = Pf(Â) = (−1)^{\binom{m}{2}+\binom{m+l}{2}+ml} det ( \begin{matrix}X̄ & Ȳ_{1} \\ −Y_{+,−}^{t} & Z_{−,+} \end{matrix} )

= (−1)^{\binom{l}{2}} det ( \begin{matrix}X̄ & Ȳ_{1} \\ Ȳ_{2} & Z̄ \end{matrix} ) ,

where X̄, Ȳ_{1}, Ȳ_{2}, and Z̄ are as in the statement of the lemma. This is exactly (−1)^{\binom{l}{2}} det(B), and thus the proof is complete. □

Remark. Gordon’s Pfaffian reduction [11, Lemma 1] is the special case of Lemma 4.1 where l = 0. Indeed, the row and column manipulations which we performed during the above proof are the ones which Gordon used in his proof.

Proof of Theorem 2.1. By Lemma 4.1, the signed Pfaffian in (3.6) is equal to

det ( \begin{matrix}x_{|j−i|+1} + x_{|j−i|+3} + ⋯ + x_{i+j−1} & ∑{i \atop r=−i+1} \binom{2n−2kt̂}{n−kt̂+r} \\ ∑{j \atop r=−j+1} \binom{2n−2k_{t}}{n−k_{t}+r} & \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂} + \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂+1} \end{matrix} ) ,

5Up to sign, the identity follows by using that the determinant is the square of the Pfaffian; the sign follows by noticing that for E = 0 this is Cayley’s identity.

where 1 ≤ i, j ≤ m and 1 ≤ t, t̂≤ l, and

x_{i} = ∑_{r=−i+1}^{i} \binom{2n}{n + r}

for all i.

The last series of operations consists in subtracting the (m − 1)-st row from the m-th, the (m − 2)-nd row from the (m − 1)-st, …, the first from the second, and subsequently doing the analogous operations with the columns. One sees immediately that this converts the above determinant into

det ( \begin{matrix}∗ & \binom{2n−2kt̂}{n−kt̂−i+1} + \binom{2n−2kt̂}{n−kt̂+i} \\ \binom{2n−2k_{t}}{n−k_{t}−j+1} + \binom{2n−2k_{t}}{n−k_{t}+j} & \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂} + \binom{2n−2k_{t}−2kt̂}{n−k_{t}−kt̂+1} \end{matrix} ) ,

where the entries in the block marked by ∗ have still to be computed. Comparison with the definition of the matrix N in Proposition 3.4 shows that the matrix of which the determinant is taken above is precisely the same as N in the top-right, bottomleft, and bottom-right blocks. A somewhat more involved calculation shows that the top-left block (marked by ∗) of the above matrix also agrees with the corresponding block of N. This completes the proof of the equality of the signed Pfaffian (3.6) and the determinant in Proposition 3.4, and, hence, the proof of Theorem 2.1. □

Remark. The row and column operations which we performed during the above proof are the ones which Stembridge uses to prove Theorem 7.1(a) in [22]. Again, the difference here is that our matrix has l more rows and l more columns.

5. Odd holes

Since k contiguous triangular holes of side two are equivalent, from the point of view of counting the lozenge tilings of the region from which they are removed, to a single triangular hole of side 2k, one sees that Theorem 2.1 covers in fact the case when an arbitrary, symmetric collection of even triangular holes is removed from along the horizontal symmetry axis. What about odd holes?

In order for the factorization identity to be meaningful, all three kinds of tilings it involves need to exist. However, it is easy to see that, if there is an odd triangular hole with its vertical side not going through the center of the underlying hexagon, there is no horizontally symmetric tiling. The only way for odd holes to be present and horizontally symmetric tilings to exist is if there are only two of them, symmetric about the center of the hexagon and touching along their vertical edges (so as to form a rhombus). In addition to them, we may have an arbitrary collection of triangular holes of side two as in the previous sections.

It turns out that the factorization identity holds in this more general case as well. Let n, m, l be positive integers, and let x and k_{1}, k_{2}, …, k_{l} be positive integers so

that k_{1} < k_{2} < ⋯ < k_{l} ≤ n/2. One readily sees that the region H_{n+x,2m}(k_{1}, k_{2}, …, k_{l}) has a horizontal lattice rhombus of side length x at its center precisely if n is even. Assume that this is so, and denote by H_{n,2m}(k_{1}, k_{2}, …, k_{l}; x) the region obtained from

Figure 5.1. The region H_{15,10}(∅; 7).

H_{n+x,2m}(k_{1}, k_{2}, …, k_{l}) by removing from its center this horizontal lattice rhombus of side x. (See Figure 5.1; in particular, we are still considering the hexagon with side lengths n + x, 2m, n + x, n + x, 2m, n + x with some holes inside.)

Then we have the following extension of Theorem 2.1.

Theorem 5.1. For all positive integers n, m, l, with n even, and all positive integers x, k_{1}, k_{2}, …, k_{l} with k_{1} < k_{2} < ⋯ < k_{l} ≤ n/2, we have

M (H_{n,2m}(k_{1}, k_{2}, …, k_{l}; x))

= M_{−} (H_{n,2m}(k_{1}, k_{2}, …, k_{l}; x)) M_{|} (H_{n,2m}(k_{1}, k_{2}, …, k_{l}; x)) . (5.1)

Proof. Note that for even x this identity holds by Theorem 2.1. We deduce it for odd values of x by showing that, for fixed n and m, and fixed k_{1}, …, k_{l}, both sides of (5.1) are polynomial in x.

Suppose, for the sake of the brevity of the write-up, that l = 0, i.e., there are no holes besides the two holes of side x touching at the center. We will see that polynomiality in x in the general case follows by the same argument.

Let m and n be fixed, and allow x to vary. In each tiling of H_{n,2m}(∅; x), there are precisely n horizontal lozenges bisected by the vertical symmetry axis. Indeed, the tiling is encoded by a family of 2m non-intersecting paths of lozenges running from the left side of the hexagon to its right side, and each crosses the vertical symmetry axis along a unit lattice segment; the remaining n unit segments along that symmetry axis must therefore be occupied by horizontal lozenges.

Fix some set S consisting of n such horizontal lozenges, and denote by L_{n,2m}(S; x) (resp., R_{n,2m}(S; x)) the portion of H_{n,2m}(∅; x) minus the union of the tiles in S that is to the left (resp., to the right) of the vertical symmetry axis. Then we can write

M (H_{n,2m}(∅; x)) = ∑_{S} M (L_{n,2m}(S; x)) M (R_{n,2m}(S; x)) ,  (5.2)

where the sum ranges over all \binom{n+m}{n} possible choices of the set S.

Since L_{n,2m}(S; x) and R_{n,2m}(S; x) are congruent, their number of lozenge tilings is the same. Thus, by (5.2), in order to prove that M (H_{n,2m}(∅; x)) is a polynomial in x, it suffices to show that so is M (L_{n,2m}(S; x)), for any S.

This can be seen as follows. Encoding the lozenge tilings of L_{n,2m}(S; x) by paths of lozenges running from its left to its right sides, and interpreting them as nonintersecting lattice paths, we obtain that M (L_{n,2m}(S; x)) is equal to the number of 2m-tuples of non-intersecting lattice paths on ℤ^{2} having starting points (2m−i, i−1), i = 1, …, 2m, and some fixed 2m-element subset of

\{(2m + n + x − j, j − 1) : j ∈ \{1, …, m + \frac{n}{2}\} ∪ \{m + \frac{n}{2} + x + 1, …, 2m + n + x\}\}

(5.3)

as the set of its ending points. By the Lindström-Gessel-Viennot theorem, this is given by a determinant of order 2m, whose entries are binomial coefficients. One readily sees that each of the resulting binomial coefficients is a polynomial in x. It follows that so is the determinant of the matrix, and the polynomiality of M (H_{n,2m}(∅; x)) as a function of x follows.

The very same argument proves the polynomiality in x of M_{|} (H_{n,2m}(∅; x)). Indeed, the only difference is that now the expression corresponding to (5.2) only has the first factor of the summand of (5.2).

The polynomiality in x of M_{−} (H_{n,2m}(∅; x)) follows by a similar argument, applied to the portion of H_{n,2m}(∅; x) that is above a zig-zag lattice line analogous to the one in Figure 2.2.

Consider now the case when l is not necessarily zero. The effect of the presence of the l holes of side two in the left half of the hexagon is to introduce 2l more lattice paths (except when looking at the horizontally symmetric tilings, when it is only l more lattice paths), with starting points having some fixed coordinates (not involving x), and ending points still chosen from among the elements of the set (5.3). It is then clear that the above arguments work equally well in this general case, showing that all three quantities in (5.1) are polynomials in x. Since the two sides of (5.1) agree for all even values of x (cf. Theorem 2.1), it follows that they agree for all x. This completes the proof. □

Remark. The case l = 0, x = 1 was first proved, by a different method, by Kasraoui and the second author in [12]. An alternative way to view this, is that a combination of this case of Theorem 5.1 with the main result in [6] yields a new proof of the main result in [12].

6. Concluding remarks

The factorization result proved in this paper is reminiscent of the symmetries considered by Kuperberg in [16, Sec. IV.C], especially given that, in the terminology of [16], one of our symmetries is color-preserving and the other color-reversing. However, it turns out that the factorization we prove in this paper does not hold even under small changes in the structure of the holes we considered. The fact that our factorization result depends so strongly on the geometry of the holes indicates that it is of a kind different from the ones considered in [16].

Given the equivalence of lozenge tilings of a hexagon with plane partitions contained in a given box (cf. [9]), one way to view the special case l = 0 of Theorem 2.1 is that it gives a new proof for the enumeration of symmetric plane partitions contained in a given box (first proved by Andrews [1]). Indeed, by our factorization result, the latter is the ratio of the total number of plane partitions that fit in the box and the number of those that are transpose-complementary. The formula for the total number (due to MacMahon [18]) can easily be proved inductively using Kuo’s graphical condensation (cf. [14]), while the transpose-complementary case (first proved by Proctor [20]) can be directly deduced from MacMahon’s result by applying the matchings factorization theorem (cf. [4]). From the point of view of [7], this adds a seventh symmetry class that can be proved in a combinatorial way.

It would be interesting to find some more direct relations between the symmetry classes of plane partitions, and also to find an algebraic generalization of the factorization presented in this paper in the style of [8], which generalized the special case l = 0 of the main theorem here in terms of Schur functions.

References

1. G. E. Andrews, Plane partitions I: The MacMahon conjecture, Studies in foundations and combinatorics, G.-C. Rota ed., Adv. in Math. Suppl. Studies, Vol. 1, 1978, pp. 131–150.

2. G. E. Andrews, Plane partitions V: The t.s.s.c.p.p. conjecture, J. Combin. Theory Ser. A 66 (1994), 28–39.

3. D. M. Bressoud, Proofs and confirmations — The story of the alternating sign matrix conjecture, Cambridge University Press, Cambridge, 1999.

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

5. M. Ciucu, The equivalence between enumerating cyclically symmetric, self-complementary and totally symmetric, self-complementary plane partitions, J. Combin. Theory Ser. A 86 (1999), 382–389.

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 \frac{1}{2} symmetry classes, Advanced Study in Pure Mathematics 28 (2000), 83-103.

8. M. Ciucu and C. Krattenthaler, A factorization theorem for classical group characters, with applications to plane partitions and rhombus tilings, Advances in Combinatorial Mathematics: Proceedings of the Waterloo Workshop in Computer Algebra 2008 (I. Kotsireas, E. Zima, eds.), Springer, New York, 2010, pp. 39–60.

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

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

    at http://www.cs.brandeis.edu/~ira.

11. B. Gordon, Notes on plane partitions V, J. Combin. Theory Ser. B 11 (1971), 157–168.

12. A. Kasraoui and C. Krattenthaler, Enumeration of symmetric centered rhombus tilings of a hexagon, preprint (2013), available at arxiv.org/abs/1306.1403.

13. C. Koutschan, M. Kauers and D. Zeilberger, A proof of George Andrews’ and David Robbins’ q-TSPP-conjecture, Proc. Natl. Acad. Sci. USA 108 (2011), 2196–2199.

14. E. H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004), 29–57.

15. G. Kuperberg, Four symmetry classes of plane partitions under one roof, J. Combin. Theory Ser. A 75 (1994), 295–315.

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

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

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

19. S. Okada, On the generating functions for certain classes of plane partitions, J. Combin. Theory Ser. A 51 (1989), 1–23.

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

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

22. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. Math. 83 (1990), 96–131.

23. J. R. Stembridge, The enumeration of totally symmetric plane partitions, Adv. in Math. 111 (1995), 227–245.

Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA

Fakultät für Mathematik der Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.