(−1)–ENUMERATION OF PLANE PARTITIONS WITH COMPLEMENTATION SYMMETRY

THERESIA EISENKÖLBL

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

                      E-mail: Theresia.Eisenkoelbl@univie.ac.at

Abstract. We compute the weighted enumeration of plane partitions contained in a given box with complementation symmetry where adding one half of an orbit of cubes and removing the other half of the orbit changes the weight by −1 as proposed by Kuperberg in math.CO/9810091. We use nonintersecting lattice path families to accomplish this for transpose–complementary, cyclically symmetric transpose– complementary and totally symmetric self–complementary plane partitions. For symmetric transpose–complementary and self–complementary plane partitions we get partial results. We also describe Kuperberg’s proof for the case of cyclically symmetric self–complementary plane partitions.

1. Introduction

A plane partition P can be defined as a finite set of points (i, j, k) with i, j, k > 0 and if (i, j, k) ∈ P and 1 ≤ i′ ≤ i, 1 ≤ j′ ≤ j, 1 ≤ k′ ≤ k then (i′, j′, k′) ∈ P. We interpret these points as midpoints of cubes and represent a plane partition by stacks of cubes (see Figure 1). If we have i ≤ a, j ≤ b and k ≤ c for all cubes of the plane partition, we say that the plane partition is contained in a box with sidelengths a, b, c.

Plane partitions were first introduced by MacMahon. One of his main results is the following [12, Art. 429, x → 1, proof in Art. 494]:

The number of all plane partitions contained in a box with sidelengths a, b, c equals

B(a, b, c) = ∏_{i=1}^{a} \frac{(c + i)_{b}}{(i)_{b}} ,  (1)

where (a)_{n} := a(a + 1)(a + 2) … (a + n − 1) is the usual shifted factorial. A plane partition can have several kinds of symmetries which we now list. A plane partition P is called

• symmetric if whenever (i, j, k) ∈ P then also (j, i, k) ∈ P,

• cyclically symmetric if whenever (i, j, k) ∈ P then also (j, k, i) ∈ P,

• totally symmetric if it is both symmetric and cyclically symmetric. A plane partition P contained in the box a × b × c is called • self–complementary if whenever (i, j, k) ∈ P then (a+1−i, b+1−j, c+1−k) ∉ P

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

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

for 1 ≤ i ≤ a, 1 ≤ j ≤ b, 1 ≤ k ≤ c.

A plane partition P contained in the box a × a × c is called

• transpose–complementary if whenever (i, j, k) ∈ P then (a + 1 − j, a + 1 − i, c + 1 − k) ∉ P for 1 ≤ i ≤ a, 1 ≤ j ≤ a, 1 ≤ k ≤ c (see Figure 1).

The various combinations of these symmetries lead to ten symmetry classes (cf. [19]).

It is known that for each of the ten classes the number of plane partitions contained in that class is given by a “nice” closed formula (see [19, 9, 3, 23]). Additionally, the four symmetry classes without complementation admit a natural q–enumeration. In the case of no symmetry this is also a result of MacMahon. The weight is just q^{#cubes}. If one counts symmetric plane partitions or cyclically symmetric plane partitions with respect to this weight then one obtains nice closed formulas as well (see [1, 2, 14]). The second weight which has been considered for the symmetry classes without complementation is q^{#orbits}. (Here, we mean orbits with respect to the symmetries of the applicable class.) Aside of the case of no symmetries (clearly, in this case the weights q^{#cubes} and q^{#orbits} are identical), there exist nice closed formulas for the enumeration of symmetric plane partitions (see [1] ) and, conjecturally, for totally symmetric plane partitions (see [19]).

Amazingly, upon setting q = −1 in these enumerations we get the plain enumeration of plane partitions with complementation symmetry (see [21, 22]). If we consider the plane partitions in a symmetry class with complementation symmetry, then there seems to be no natural q–enumeration (except in the case of self–complementary plane partitions [19]). In particular, counting these plane partitions with respect to q^{#cubes} gives nothing new because this statistic is constant for all the plane partitions in the symmetry class. (Obviously, counting with respect to q^{#orbits} makes no sense as well.) However, a natural (−1)–enumeration for plane partitions with complementation symmetry has been recently proposed by Kuperberg (cf. [8, pp.25/26]).

This (−1)–enumeration is defined as follows: A plane partition with complementation symmetry contains exactly one half of each orbit. Let a move consist of removing one half of an orbit and adding the other half. Two plane partitions are connected either by an odd or by an even number of moves, so it is possible to define a relative sign. The sign becomes absolute if we assign a certain plane partition the weight 1 (see Figure 15 for cyclically symmetric self–complementary, cyclically symmetric transpose– complementary and totally symmetric self–complementary plane partitions; see Figure 2 for (symmetric) transpose–complementary plane partitions and Figure 18 for self–complementary plane partitions).

For example, in the case of transpose–complementary plane partition this can be realized by counting the number n(P) of cubes contained in the upper half of the plane partition P and doing the enumeration ∑_{P} (−1)^{n(P)}.

In [8], Kuperberg conjectures that this (−1)–enumeration has a nice expression for all the six symmetry classes with complementation symmetry. He gives the result for the case of transpose–complementary plane partitions derived by the method of “forcing planarity”. This result is stated below in Theorem 1 and proved in a different way. Kuperberg has also found a proof for the case of cyclically symmetric self–complementary plane partitions [10] which we reproduce in Section 10. The same method could be used to prove Theorem 6 below except for the sign.

(−1)–ENUMERATION OF PLANE PARTITIONS 3

The main purpose of the present paper is to prove Kuperberg’s conjecture in almost all other cases. We determine the expressions for the (−1)–enumeration of cyclically symmetric transpose–complementary plane partitions and totally symmetric self–complementary plane partitions. We get partial results depending on the parity of the sidelengths for symmetric transpose–complementary plane partitions and self– complementary plane partitions. All these results are stated in Theorems 1–7 below. In fact, as it turns out, Kuperberg’s conjecture is only partially “true,” because in the case of symmetric transpose–complementary plane partitions there is one case in which there is apparently no compact expression for the (−1)–enumeration.

We now present these results.

Theorem 1 (Kuperberg). The enumeration of transpose–complementary plane partitions in a box with sides a × a × 2b with weight (−1)^{n(P)} equals 0 for b odd and a even and

∏_{j=1}^{⌈a/2⌉−1} \frac{(⌊b/2⌋ + j)(a − j)_{b}}{(j)_{b+1}}

else, where (a)_{n} denotes the shifted factorial a(a + 1) … (a + n − 1) and n(P) is the number of cubes in the plane partition P contained in the upper half of the box (cf. the explanation of the weight in the paragraphs preceding the theorem).

Theorem 2. The enumeration of symmetric transpose–complementary plane partitions in a box with sides 2α × 2α × 2b with weight (−1)^{n(P)} equals

\frac{∏k=1^{\frac{α}{2}}(b + 2k)_{α−1}}{∏k=1^{\frac{α}{2}}(2k)_{α−1}} for α even and b even

\frac{∏k=1^{\frac{α−1}{2}} (b + 2k)_{α}}{∏k=1^{\frac{α−1}{2}} (2k)_{α}} for α odd and b even
0 for b odd.

Here, n(P) denotes the number of cubes in P contained in the upper right quarter of the box (cf. the explanation of the weight in the paragraphs preceding Theorem 1).

Theorem 3. The enumeration of symmetric transpose–complementary plane partitions in a box with sides (2α + 1) × (2α + 1) × 2b with weight (−1)^{n(P)} has the form

∏_{k=1}^{α/2}(b/2 + k)_{α/2+1}(b + 2α + 2) · p_{1}(b) for α even and b even

∏_{k=1}^{α/2}((b − 1)/2 + k)_{α/2+1}(b − 1) · p_{2}(b) for α even and b odd

∏_{i=1}^{(α+1)/2}((α + b − 1)/2 − i + 2)_{2i−1} · p_{3}(b) for α odd and b even

∏_{i=1}^{(α+1)/2}((b + α)/2 − i + 1)_{2i−1} · p_{4}(b) for α odd and b odd.

Here, p_{1} and p_{2} are polynomials of degree (α/2)^{2}, p_{3} and p_{4} are polynomials of degree (α^{2} − 1)/4 and n(P) denotes the number of cubes in P contained in the upper right quarter of the box (cf. the explanation of the weight in the paragraphs preceding Theorem 1).

Theorem 4. The enumeration of cyclically symmetric transpose–complementary plane partitions in a box with sides 2α × 2α × 2α with weight (−1)^{n(P)} equals

( ∏_{k=1}^{(α−1)/2} \frac{(6k − 2)!}{(2k + α − 1)!})^{2} for α odd,
0  else,

where n(P) is the number of cubes in P contained in the upper right eighth of the box (cf. the explanation of the weight in the paragraphs preceding Theorem 1).

Theorem 5. The enumeration of totally symmetric self–complementary plane partitions in a box with sides 2α × 2α × 2α with weight (−1)^{n(P)} equals

∏_{k=1}^{(α−1)/2} \frac{(6k − 2)!}{(2k + α − 1)!} for α odd,
0  else.

Here, n(P) is the number of half orbits contained in the plane partition P and not contained in the plane partition shown in Figure 15, (cf. the explanation of the weight in the paragraphs preceding Theorem 1).

This is also the number of vertically symmetric alternating sign matrices of size (α + 2).

Theorem 6. For even a, b, c, the enumeration of self–complementary plane partitions in a box with sides a × b × c with weight (−1)^{n(P)} equals

B (\frac{a}{2}, \frac{b}{2}, \frac{c}{2}) ,

where B(a, b, c) is defined in Equation (1). Here, n(P) is the weight explained in the paragraphs preceding Theorem 1.

Theorem 7 (Kuperberg). The (−1)–enumeration of cyclically symmetric self–complementary plane partitions in a box with sides 2α × 2α × 2α with weight (−1)^{n(P)} is the square root of the ordinary enumeration, that is

± ∏_{k=0}^{α−1} \frac{(3k + 1)!}{(α + k)!}.  (2)

This is also the number of alternating sign matrices (see [26]), the number of totally symmetric self–complementary plane partitions [23] and the number of descending plane partitions. Results for small values of α suggest that the sign is +1 for all α.

Thus, the only cases that are still open are the case of symmetric transpose–complementary plane partitions in a box with two odd sides (in which case no nice formula seems to exist) and the case of self–complementary plane partitions in a box with at least one odd side. Here, the enumeration seems to have a nice closed form. The case a even and b and c odd is stated in the following conjecture.

Conjecture. For a even and b, c odd, the enumeration of self–complementary plane partitions in a box with sides a × b × c with weight (−1)^{n(P)} equals up to sign

B (\frac{a}{4}, \frac{b+1}{4}, \frac{c+1}{4})^{2} B (\frac{a}{4}, \frac{b−3}{4}, \frac{c+1}{4}) B (\frac{a}{4}, \frac{b+1}{4}, \frac{c−3}{4})

for a ≡ 0 (mod 4) and b ≡ c ≡ 3 (mod 4),

B (\frac{a}{4}, \frac{b−1}{4}, \frac{c−1}{4})^{2} B (\frac{a}{4}, \frac{b+3}{4}, \frac{c−1}{4}) B (\frac{a}{4}, \frac{b−1}{4}, \frac{c+3}{4})

for a ≡ 0 (mod 4) and b ≡ c ≡ 1 (mod 4),

B (\frac{a−2}{4}, \frac{b+1}{4}, \frac{c+1}{4})^{2} B (\frac{a+2}{4}, \frac{b−3}{4}, \frac{c+1}{4}) B (\frac{a+2}{4}, \frac{b+1}{4}, \frac{c−3}{4}) for a ≡ 2 (mod 4) and b ≡ c ≡ 3 (mod 4),

B (\frac{a+2}{4}, \frac{b−1}{4}, \frac{c−1}{4})^{2} B (\frac{a−2}{4}, \frac{b+3}{4}, \frac{c−1}{4}) B (\frac{a−2}{4}, \frac{b−1}{4}, \frac{c+3}{4}) for a ≡ 2 (mod 4) and b ≡ c ≡ 1 (mod 4),

B (\frac{a}{4}, \frac{b−1}{4}, \frac{c+1}{4})^{2} B (\frac{a}{4}, \frac{b−1}{4}, \frac{c+1}{4}) B (\frac{a}{4}, \frac{b+3}{4}, \frac{c−3}{4})

for a ≡ 0 (mod 4), b ≡ 1 (mod 4), c ≡ 3 (mod 4),

B (\frac{a}{4}, \frac{b+1}{4}, \frac{c−1}{4})^{2} B (\frac{a}{4}, \frac{b+1}{4}, \frac{c−1}{4}) B (\frac{a}{4}, \frac{b−3}{4}, \frac{c+3}{4})

for a ≡ 0 (mod 4), b ≡ 3 (mod 4), c ≡ 1 (mod 4),

0 for a ≡ 2 (mod 4) and b ≢ c (mod 4),

where B(a, b, c) is defined in Equation (1).

The remaining case are the self–complementary plane partitions with a odd and b and c even. Also there, the (−1)–enumeration seems to have a nice closed form but we did not bother to work out precise conjectures.

We prove Theorems 1–6 by adjusting a well-known bijection between plane partitions and families of nonintersecting lattice paths. In the cases of transpose–complementary plane partitions, cyclically symmetric transpose–complementary plane partitions and totally symmetric self–complementary plane partitions, these path families can be enumerated by a determinant given by the Gessel–Viennot method.

In the case of symmetric transpose–complementary and self–complementary plane partitions the path families can be enumerated by a sum of minors that can be expressed as a Pfaffian by a theorem of Ishikawa and Wakayama (see Lemma 11).

The resulting determinants and Pfaffians are then shown to be equal to the expressions given in the theorems.

Kuperberg’s proof of Theorem 7 uses a correspondence between plane partitions and perfect matchings and the Hafnian–Pfaffian method (see [8]) to express the enumeration as a Pfaffian and compares this to the Pfaffian of a known enumeration.

Theorem 1 is proved in Section 2. Theorem 2 is proved in Sections 3, 4 and 5. Theorem 3 is proved in Section 6. Theorem 4 is proved in Section 7. Theorem 5 is proved in Section 8. Theorem 6 is proved in Section 9. Kuperberg’s proof of Theorem 7 is given in Section 10.

} { 2b {  {  }  } 2b a a  a a

Figure 1. A transpose–complementary plane partition.

} { 2b {  {  }  } 2b a a  a a

Figure 2. A (symmetric) transpose–complementary plane partition with weight 1.

Acknowledgement. We thank Greg Kuperberg for his permission to reproduce his proof of Theorem 7, the (−1)–enumeration of cyclically symmetric self–complementary plane partitions.

2. Transpose–complementary plane partitions

The aim of this section is to compute the enumeration of transpose–complementary plane partitions contained in a given box with weight (−1)^{n(P)}, where n(P) is the number of cubes of P in the upper half of the box (cf. the paragraphs preceding Theorem 1). By the definition of transpose–complementary, the box must have sidelengths of the form a × a × 2b.

} { b {  } b a a a. The upper half of the tiling.  b. The corresponding path family. c. The path family isolated.  d. The path family made orthogonal.

Figure 3.

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

Step 1: From plane partitions to rhombus tilings The first step is using a well–known bijection between plane partitions and rhombus tilings to convert the problem to a tiling enumeration problem. (In this paper by rhombus we always mean a rhombus consisting of two equilateral triangles of sidelength 1.) The rhombus tiling of a hexagon with sides a, a, 2b, a, a, 2b corresponding to a given plane partition is simply a projection of the 3–dimensional stack of cubes to the plane (see Figure 1). It is easy to see that transpose–complementary plane partitions correspond to rhombus tilings with a horizontal symmetry axis. Step 2: From rhombus tilings to families of nonintersecting lattice paths. We use a variant of a well-known translation of rhombus tilings to families of nonintersecting lattice paths. We start with a rhombus tiling with a horizontal symmetry axis (see Figure 1). Clearly, the symmetry axis must be covered by horizontal rhombi. Since the tiling is symmetric we need only consider the rhombi lying above the symmetry axis (see Figure 3a). We mark the midpoints of the edges along the upper left side of length a and of the parallel edges on the zig-zag line (see Figure 3b). We connect these points by paths which follow the rhombi of the tiling as illustrated in Figure 3b. Clearly, the resulting paths are nonintersecting, i.e., no two paths have a common vertex. If we slightly distort the underlying lattice, we get orthogonal paths with south and east steps (see Figure 3d).

We can introduce a coordinate system in a way such that the coordinates of the starting points A_{i} and end points E_{j} are

A_{i} = (i − 1, b + i − 1),  i = 1, …, a,  (3)
E_{j} = (2j − 2, j − 1),  j = 1, …, a.  (4)

We have to find a description of the weight (−1)^{n(P)} in terms of the path families. A horizontal rhombus in the tiling can be viewed as the top square of a stack of cubes in the plane partition interpretation. Therefore, it is assigned the weight (−1)^{n}, where n is the number of cubes (i, j, k) with k > b below the square. In terms of paths this is the same as assigning to a path p the weight (−1)^{area1(p)} where area1(p) is the area between the path p and the horizontal line containing the lowest point of the path. We want to use instead the weight (−1)^{area2(p)} where area2(p) is the area between the path p and the x–axis to be able to apply Lemma 8 below. When we do this, we make an overall error of (−1)^{1^{2}+2^{2}+···+(a−1)^{2}} = (−1)^{a(a−1)/2}. Hence, we have to count families of nonintersecting lattice paths with starting points A_{i} (see (3)), end points E_{j} (see (4)) and weight (−1)^{area2(p)} and multiply the result by (−1)^{a(a−1)/2}. Step 3: From lattice paths to a determinant By the main theorem on nonintersecting lattice paths (see [11, Lemma 1] or [4, Theorem 1]) the weighted count of such families of paths can be expressed as a determinant. We employ the notation P(A_{i} → E_{j}) for the weighted count of paths from A_{i} to E_{j} and P(A → E, nonint.) for the weighted count of families of nonintersecting lattice paths with the ith path running from A_{i} to E_{i}, i = 1, 2, …, n. Note that the weight of a path is the product of the weights of its steps. Now we can state the theorem for paths with south and east steps in the integer lattice.

Lemma 8. Let A_{1}, A_{2}, …, A_{n}, E_{1}, E_{2}, …, E_{n} be integer points meeting the following condition: Any path from A_{i} to E_{l} has a common vertex with any path from A_{j} to E_{k} for any i, j, k, l with i < j and k < l.

Then we have

P(A → E, nonint.) = det_{1≤i,j≤n} (P(A_{i} → E_{j})).  (5)

This is still applicable if some of the points are isolated, i.e., unconnected to any other point.

The lemma is clearly applicable to the enumeration problem formulated in Step 2 since area2 is the sum of the areas between each horizontal step and the x–axis. Now we have to determine the matrix entries P(A_{i} → E_{j}) with A_{i} and E_{j} as in (3) and (4) and the weight (−1)^{area2(p)}. It is well-known that the enumeration of paths from (a, b) to (c, d) with weight q^{area1(p)} is the q–binomial coefficient \left[{c−a+b−d \atop c−a}\right]_{q}. The q–binomial coefficient (see [18, p. 26] for further information) is defined by

\left[{n \atop k}\right]_{q} = \frac{∏_{j=n−k+1}^{n}(1 − q^{j})}{∏_{j=1}^{k}(1 − q^{j})}.

Although it is not obvious from this definition, the q–binomial coefficient is a polynomial in q. So it makes sense to put q = −1. Since we want to use (−1)^{area2(p)} there is an additional factor of (−1)^{(j−1)(2j−1−i)}. In summary, the matrix entries are

M_{ij} = (−1)^{(j−1)(i−1)} [\begin{matrix}b + j − 1 \\ 2j − i − 1 \end{matrix}]_{−1} .

Writing M = (M_{ij}), 1 ≤ i, j ≤ a, the remaining task is to compute (−1)^{a(a−1)/2} det M. Step 4: Evaluation of a useful determinant For the evaluation of det M, we make use of the following determinant lemma by Krattenthaler [7, Lemma 2.2]:

Lemma 9.

det_{1≤i,j≤n} ((X_{j} + A_{n}) … (X_{j} + A_{i+1})(X_{j} + B_{i}) … (X_{j} + B_{2}))

= ∏_{1≤i<j≤n}(X_{i} − X_{j}) ∏_{2≤i≤j≤n}(B_{i} − A_{j}).

□

This lemma implies the following determinant evaluation, which is crucial in this section.

Lemma 10.

det_{1≤i,j≤α} (\binom{β + j}{2j − i − γ}) = ∏_{j=1}^{α} \frac{(β + j)!(j − 1)!(2β + γ + j + 1)_{j−1}}{(2j − 1 − γ)!(β + γ + j − 1)!} .

Proof. We start by taking out factors of the determinant:

det_{1≤i,j≤α} (\binom{β + j}{2j − i − γ}) = ∏_{j=1}^{α} \frac{(β + j)!}{(2j − 1 − γ)!(β + γ + α − j)!}(−2)^{\binom{α}{2}}

× det_{1≤i,j≤α} ((−j + \frac{γ+1}{2}) … (−j + \frac{γ+i−1}{2})(−j + α + β + γ) … (−j + β + γ + i + 1)) .

Now we are in the position to apply Lemma 9 with n = α, X_{k} = −k, A_{k} = β + γ + k, B_{k} = \frac{γ+k−1}{2}. After a little simplification we get the claimed result. □

Step 5: Evaluation of det M We want to evaluate (−1)^{a(a−1)/2} det M, where

M_{ij} = (−1)^{(i−1)(j−1)} [\begin{matrix}b + j − 1 \\ 2j − i − 1 \end{matrix}]_{−1} , 1 ≤ i, j ≤ a.

It is easy to verify that

\left[{n \atop k}\right]_{−1} = \begin{cases}0 & n even, k odd, \\ \binom{⌊n/2⌋}{⌊k/2⌋} & else. \end{cases}  (6)

So M_{ij} = 0 for b + j odd and i even. We split the problem into several cases according to the parities of a and b. Case 1: b even.

In this case we have M_{ij} = 0 for i even, j odd. If we rearrange the rows and columns of M so that the even–numbered ones come before the odd–numbered ones then we get a block matrix of the form (\begin{matrix}A & 0 \\ ∗ & B \end{matrix}), where A is a ⌊\frac{a}{2}⌋×⌊\frac{a}{2}⌋–matrix with A_{ij} = −\binom{\frac{b}{2} +j−1}{2j−i−1}

and B is a ⌈\frac{a}{2}⌉ × ⌈\frac{a}{2}⌉–matrix with B_{ij} = \binom{\frac{b}{2} +j−1}{2j−i−1}. Clearly, det M is now the product of the determinants of A and B. Therefore, we have

(−1)^{\frac{a(a−1)}{2}} det M = (−1)^{\frac{a(a−1)}{2}} det_{1≤i,j≤⌊\frac{a}{2}⌋} (−\binom{\frac{b}{2} + j − 1}{2j − i − 1}) det_{1≤i,j≤⌈\frac{a}{2}⌉} (\binom{\frac{b}{2} + j − 1}{2j − i − 1})

= det_{1≤i,j≤⌊\frac{a}{2}⌋} (\binom{\frac{b}{2} + j − 1}{2j − i − 1}) det_{1≤i,j≤⌈\frac{a}{2}⌉} (\binom{\frac{b}{2} + j − 1}{2j − i − 1}) .

For the first determinant we use Lemma 10 with β = b/2 − 1, γ = 1 and α = ⌊a/2⌋. For the second determinant we use Lemma 10 with β = b/2 − 1, γ = 1 and α = ⌈a/2⌉. It is a routine computation to check that the product of these two determinants can be written as

∏_{j=1}^{⌈a/2⌉−1} \frac{(b/2 + j)(a − j)_{b}}{(j)_{b+1}}  (7)

which agrees with the claimed expression in Theorem 1. Case 2: b odd and a even.

In this case, we have M_{ij} = 0 for i, j even. Again, rearranging rows and columns of M

according to parity as before yields a block form (\begin{matrix}0 & B \\ A & ∗ \end{matrix}), where A is an \frac{a}{2} × \frac{a}{2}–matrix

with A_{ij} = \binom{(b−1)/2+j}{2j−i} and B is an \frac{a}{2} × \frac{a}{2}–matrix with B_{ij} = \binom{(b−1)/2+j−1}{2j−i−2}. Now, det M is the product of the determinants of A and B times (−1)^{\frac{a}{2}} . Since the first column of B is obviously zero, det B and thus the entire weighted enumeration is equal to zero in this case. Case 3: b odd and a odd. It is easy to see that in this case

M_{i1} = \left[{b \atop 1 − i}\right]_{−1} = \begin{cases}1 & for i = 1 \\ 0 & else. \end{cases}

We expand det M along the first column and get det M̃ where M̃ is the (a−1)×(a−1)– matrix with M̃_{ij} = M_{i+1,j+1}. It is easy to check that M̃_{2i−1,2j−1} = 0. Again, we rearrange the rows and columns of M̃ such that the even-numbered ones come before the odd-numbered ones and get a block matrix of the form

(\begin{matrix}∗ & B \\ A & 0 \end{matrix}) ,

where A is an \frac{a−1}{2} × \frac{a−1}{2}–matrix with A_{ij} = M_{2i,2j+1} = \binom{(b−1)/2+j}{2j−i} and B is an \frac{a−1}{2} × \frac{a−1}{2}–

matrix with B_{ij} = M_{2i+1,2j} = \binom{(b−1)/2+j}{2j−i−1}. Therefore, (−1)^{a(a−1)/2} det M̃ is the product of the determinants of A and B times (−1)^{a(a−1)/2+(a−1)/2}, i.e., we have to evaluate

(−1)^{a(a−1)/2+(a−1)/2} det_{1≤i,j≤(a−1)/2} (\binom{(b − 1)/2 + j}{2j − i}) det_{1≤i,j≤(a−1)/2} (\binom{(b − 1)/2 + j}{2j − i − 1}) .

This is done by using Lemma 10 with α = (a − 1)/2, β = (b − 1)/2, γ = 0 and α = (a − 1)/2, β = (b − 1)/2, γ = 1, respectively.

} 2b } { 2b {  {  } a a a  a

Figure 4. A symmetric transpose–complementary plane partition.

We get after little simplification

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

which again agrees with the expression in Theorem 1. Thus Theorem 1 is proved.

3. Symmetric transpose–complementary plane partitions, I

In Sections 3–6 we carry out the (−1)–enumeration for symmetric transpose–complementary plane partitions contained in a given box, i.e., we count each half orbit of cubes contained in the upper half with −1. For example, the plane partition in Figure 4 has 10 cubes in the upper half but only 7 half orbits. Its weight is therefore (−1)^{7} = −1. On the other hand, the “half-full” plane partition in Figure 2 containing exactly the cubes (i, j, k) with k ≤ b is counted with weight 1. An alternative way to state this is counting each cube in the upper right quarter with −1.

Symmetric transpose–complementary plane partitions are contained in boxes with sidelengths a × a × 2b. In this section we treat the case a = 2α, α is even. The case of α being odd is done in Section 5. For the case a = 2α + 1 see Section 6.

For the remainder of this section we assume a = 2α and that α is even. Step 1: From plane partitions to rhombus tilings Again, we start by converting the plane partitions into rhombus tilings by projecting them to the plane. We get rhombus tilings of a hexagon with sidelengths 2α, 2α, 2b, 2α, 2α, 2b which have a vertical and a horizontal symmetry axis. These symmetry conditions imply that the corresponding rhombus tiling is determined by its upper right quarter. As in the previous section, in the tiling interpretation the horizontal axis is completely covered by horizontal rhombi.

Figure 5. A symmetric transpose–complementary plane partition.

Figure 6. The upper right quarter of the plane partition in Figure 5.

Step 2: From rhombus tilings to families of nonintersecting lattice paths. As before, we can convert each tiling to a family of nonintersecting lattice paths (see Figures 7 and 8). Here, the starting points may vary since the horizontal rhombi on the vertical axis can be in different places.

With a suitable coordinate system, the end points are

E_{j} = (2j − 2, j − 1), j = 1, …, α,  (8)

while the starting points are α points among the points

A_{i} = (0, i − 1), i = 1, …, α + b.  (9)

Figure 7. The corresponding paths.

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

Figure 8. The path family made orthogonal. Note that k_{1} = 3, k_{2} = 5, k_{3} = 7.

As before, the horizontal steps of the paths correspond to horizontal rhombi in the tiling interpretation which in turn correspond to the squares on the top of a stack of cubes. Each horizontal step should therefore carry the weight (−1)^{n} where n is the number of cubes (i, j, k) below the corresponding top square and in the upper half i.e. k > b. This leads to the weight area1(p) for each path p (the area below the path and above the lowest point of the path). However, this weight does not include the horizontal rhombi on the vertical symmetry axis, because the paths have no horizontal steps there. We can remedy this by assigning the additional factor (−1)^{i} to a path starting at A_{i}.

In summary, the weight of a path p starting at A_{i} is (−1)^{i+area1(p)}. Since our points A_{i} and E_{j} have even x–coordinates, area1(p) and area2(p) have the same parity in this case for all occurring paths. Therefore, we can use Lemma 8 for the enumeration of lattice path families for every fixed choice of starting points.

To make this precise, let G_{ij} = P(A_{i} → E_{j}) be the weighted enumeration of all paths running from A_{i} to E_{j}, 1 ≤ i ≤ α + b and 1 ≤ j ≤ α with weight (−1)^{i+area1(p)}. Then G_{ij} = (−1)^{i}\left[{i+j−2 \atop 2j−2}\right]_{−1}. For each path family we have to choose for the starting points α indices from 1, …, α + b, say k_{1} < k_{2} < ⋯ < k_{α}. By Equation (5) the enumeration of lattice path families with these starting points equals

det_{1≤i,j≤α} (P(A_{k_{i}} → E_{j})) = det_{1≤i,j≤α} (G_{k_{i},j}).

Therefore, the weighted count of all path families starting at α points among the A_{i}’s, 1 ≤ i ≤ α + b and ending at the points E_{j}, 1 ≤ j ≤ α equals

∑_{1≤k_{1}<···<k_{α}≤α+b} det_{1≤i,j≤α} (G_{k_{i},j}).

Step 3: The minor-summation formula

Our ingredient is a theorem by Ishikawa and Wakayama [6, Theorem 1(1)] which we use to express the sum in form of a Pfaffian. Recall that the Pfaffian of a skew– symmetric 2n × 2n–matrix M is defined as

Pf M = ∑_{m} sgn m ∏_{\begin{matrix}\{i,j\}∈m \\ i<j \end{matrix}} M_{ij},

where the sum runs over all m = {{m_{1}, m_{2}}, {m_{3}, m_{4}}, …, {m_{2n−1}, m_{2n}}} with the conditions {m_{1}, …, m_{2n}} = {1, …, 2n}, m_{2k−1} < m_{2k} and m_{1} < m_{3} < ⋯ < m_{2n−1}. The term sgn m is the sign of the permutation m_{1}m_{2}m_{3} … m_{2n}.

Specifically, (Pf M)^{2} = det M.

Our way of stating the theorem is taken from [16, Corollary 3.2].

Lemma 11. Suppose that n ≤ p and n is even. Let T = (t_{ik}) be a p × n matrix and A = (a_{kl}) be a p × p skew-symmetric matrix. Then we have

∑_{1≤k_{1}<···<k_{n}≤p} Pf (A_{k_{1},...,k_{n}}^{k_{1},...,k_{n}}) det(T_{k_{1},...,k_{n}}) = Pf(^{t}T AT),

where ^{t}T denotes the transpose of the matrix T, T_{k_{1},...,k_{n}} is the matrix composed of the rows of T with indices k_{1}, …, k_{n} and A_{k_{1},...,k_{n}}^{k_{1},...,k_{n}} is the matrix composed of the rows and columns of A with indices k_{1}, …, k_{n}.

The specialization a_{ij} = sgn(j − i) together with the fact that Pf A = 1 for this matrix gives the following theorem by Okada [15, Theorem 3] (cf. also [20, Thm. 3.1]):

Lemma 12. Suppose that n ≤ p and n is even. Let T = (t_{ik}) be a p × n matrix and A = (a_{kl}) be a p × p skew-symmetric matrix with a_{kl} = sgn(l − k). Then we have

∑_{1≤k_{1}<···<k_{n}≤p} det(T_{k_{1},...,k_{n}}) = Pf(^{t}T AT),

where ^{t}T denotes the transpose of the matrix T, T_{k_{1},...,k_{n}} is the matrix composed of the rows of T with indices k_{1}, …, k_{n} and Pf(M) denotes the Pfaffian of a skew–symmetric matrix M.

The sum obtained in Step 2 can be evaluated using Lemma 12 with n = α, p = α + b and T = G. Here we use the assumption that α is even.

We get the following expression for our (−1)–enumeration:

Pf_{1≤i,j≤α} (∑_{r=1}^{α+b} ∑_{l=1}^{α+b} G_{li}G_{rj} sgn(r − l)) ,

where

G_{ij} = (−1)^{i}\left[{i + j − 2 \atop 2j − 2}\right]_{−1} = (−1)^{i}\binom{⌊\frac{i+j−2}{2}⌋}{j − 1}.

We set

M_{ij}(α, b) := ∑_{r=1}^{α+b} ∑_{l=1}^{α+b} G_{li}G_{rj} sgn(r − l) for 1 ≤ i, j ≤ α.  (10)

With M = (M_{ij})_{i,j=1}^{α}, the (−1)–enumeration is equal to Pf M by the lemma above. Since M is skew-symmetric, we have Pf M = ±\sqrt{det M}. So our object is to prove the following lemma.

Lemma 13. With M defined as in (10), we have

det M = \begin{cases}(\frac{∏_{k=1}^{α/2}(b+2k)_{α−1}}{∏_{k=1}^{α/2}(2k)_{α−1}} )2 & for b even \\ 0 & else. \end{cases}

The proof of the lemma is given in Section 4.

For α even and b even, the entries of the Pfaffian are polynomials in b, so the result of the enumeration is continuous in b. Therefore, in order to determine the sign of Pf M, it suffices to determine the sign of the enumeration for b = 0. Trivially, this is 1. This is clearly the sign chosen in the statement of Theorem 2.

4. The proof of Lemma 13

First, we consider the case that b is odd (remember that α is still assumed to be even in this section). We have G_{l1} = (−1)^{l}, and since the sum ∑_{l=1}^{α+b}(−1)^{l} sgn(r − l) = 0 for all 1 ≤ r ≤ α + b we have M_{1j} = 0 for all j. Therefore det M = 0.

Now we assume that b is even. We claim that M_{2i,2j} = 0. To see this, consider the inner sum in the definition of M_{ij}. Most summands cancel with a neighbouring

summand since (−1)^{l} changes sign and \binom{⌊\frac{l+i−2}{2}⌋}{i − 1} has the same value. The remaining terms are those where l is close to r or close to the summation limits:

M_{2i,2j}(α, b) = ∑_{k=1}^{\frac{α+b}{2} −1}(−1)\binom{i − 1 + k}{2i − 1}\binom{j − 1 + k}{2j − 1}

+ ∑_{k=1}^{\frac{α+b}{2} −1}(−1)(−1)\binom{i − 1 + k}{2i − 1}\binom{j − 1 + k}{2j − 1}

+ ∑_{r=1}^{α+b−1}(−1)^{r}(−1)\binom{i − 1 + \frac{α+b}{2}}{2i − 1}\binom{j − 1 + ⌊\frac{r}{2}⌋}{2j − 1}. (11)

The first sum on the right-hand side corresponds to r = 2k + 1, l = 2k, the second sum corresponds to r = 2k, l = 2k + 1, and the third to l = α + b. The first two sums clearly cancel each other. The last sum vanishes because the (r = 1)–term is zero and the other summands cancel pairwise.

Hence, if we reorder M such that even–numbered rows and columns come before odd–numbered ones, we get a block matrix of the form

(\begin{matrix}0 & M̃ \\ −M̃ & N \end{matrix}) ,

where M̃ is an \frac{α}{2}×\frac{α}{2}–matrix with M̃_{ij} = M_{2i,2j−1}. Therefore, we have det M = (det M̃)^{2}. Using the argument described after (11), we can get rid of one of the sums in M̃_{ij} and write it as

M̃_{ij} = M_{2i,2j−1} = ∑_{k=1}^{\frac{α+b}{2}} \binom{k + j − 2}{2j − 2}\binom{k + i − 2}{2i − 2} for 1 ≤ i, j ≤ \frac{α}{2}.  (12)

The (i, j)–entry of the matrix M̃ is clearly a polynomial in b of degree 2i + 2j − 3. It follows that the determinant of M̃ is a polynomial in b of degree at most \frac{α}{2}(α − 1). We will find a closed form for this polynomial in three steps.

Step 1: ∏j=1^{\frac{α}{2}} (\frac{α+b}{2} − j + 1)_{2j−1} divides det M̃.

We apply Zeilberger’s algorithm [24, 25] to the sum (12) representing M̃_{ij} and get

(j + i − 1)M̃_{ij} + 2(2j + 2i − 1)M̃_{i+1,j}

= \frac{(α + b) (\frac{α+b}{2} − i + 1)_{2i−1} (\frac{α+b}{2} − j + 1)_{2j−1}}{(2i)!(2j − 2)!} . (13)

Therefore: If (\frac{α+b}{2} − j + 1)_{2j−1} divides M̃_{ij} then (\frac{α+b}{2} − j + 1)_{2j−1} divides M̃_{i+1,j}.

Since M̃_{1j} = ^{\frac{(\frac{α+b}{2} −j+1)_{2j−1}}{(2j−1)!}} , the jth column of M̃ is divisible by (\frac{α+b}{2} − j + 1)_{2j−1} for j = 1, … \frac{α}{2}. It follows immediately that

∏_{j=1}^{α/2}(\frac{α+b}{2} − j + 1)_{2j−1} divides det M̃.

Step 2: ∏_{t=1}^{\frac{α}{2} −1}(\frac{α+b}{2} − t + \frac{1}{2})_{2t} divides det M̃.

We prove this by showing that

(\frac{α+b}{2} − t + \frac{1}{2})_{2t} divides M̃_{t+1,j} + ∑_{s=1}^{t}(−1)^{s−1} \frac{\binom{2s−1}{s}}{(2s − 1)2^{4s−1}} M̃_{t+1−s,j}

for all j. The sum equals

M_{2t+2,2j−1} + ∑_{k=1}^{(α+b)/2} \binom{k + j − 2}{2j − 2} ∑_{s=1}^{t}(−1)^{s−1} \frac{\binom{2s−1}{s}}{(2s − 1)2^{4s−1}} \binom{k + t − s − 1}{2t − 2s}. (14)

We reverse the order of summation of the innermost sum and convert it to hypergeometric form, i.e., we want to write it in the form

rF_{s} [\begin{matrix}a_{1}, a_{2}, …, a_{r} \\ b_{1}, b_{2}, …, b_{s} \end{matrix}; z] = ∑_{n≥0} \frac{(a_{1})_{n}(a_{2})_{n} … (a_{r})_{n}}{(b_{1})_{n}(b_{2})_{n} … (b_{s})_{n}} \frac{z^{n}}{n!}

This generates an additional summand that has to be subtracted. To be precise, we get for the inner sum

∑_{s=1}^{t} \binom{2s − 1}{s}\frac{(−1)^{s−1}}{(2s − 1)2^{4s−1}} \binom{t − s + k − 1}{2t − 2s} =

= \frac{(−1)^{t}(t)_{t}}{2^{4t−1}(1 − 2t)(1)_{t}}_{3}F_{2} [\begin{matrix}k, 1 − k, −t \\ \frac{3}{2} − t, \frac{1}{2} \end{matrix}; 1] − \binom{k + t − 1}{2t}. (15)

The last term cancels exactly with the summand generated by M_{2t+2,2j−1}. Now we can apply the Pfaff–Saalschütz summation formula ([17], (2.3.1.3); Appendix (III.2)),

3F_{2}[\begin{matrix}a, b, −n \\ c, 1 + a + b − c − n \end{matrix}; 1] = \frac{(−a + c)_{n} (−b + c)_{n}}{(c)_{n} (−a − b + c)_{n}} ,  (16)

where n is a nonnegative integer.

Expression (14) becomes a single sum:

∑_{k=1}^{(α+b)/2} \binom{k + j − 2}{2j − 2}\frac{(k − 1/2)(k − t + 1/2)_{2t−1}}{(2t)!} .

The remaining sum can be evaluated by the Gosper algorithm [5]. It simplifies to

\binom{\frac{α+b}{2} + j − 2}{2j − 2}\frac{(\frac{α+b}{2} − t + \frac{1}{2})_{2t} (\frac{α+b}{2} + j − 1)}{(2t)!(2t + 2j − 1)}.

This is clearly divisible by (\frac{α+b}{2} − t + \frac{1}{2})_{2t} viewed as polynomial in b. Step 3: The degree and the leading term of the determinant.

In the previous two steps we have found a polynomial in b of degree ∑j=1^{\frac{α}{2}}(2j − 1) +

∑_{t=1}^{\frac{α}{2} −1} 2t = α^{2}/2 − α/2 which divides the determinant. The latter number is exactly the maximal possible degree of the determinant. Therefore, we know the determinant up to a factor which is independent of b. The factors we have found can be written as ∏k=1^{\frac{α}{2}}(b + 2k)_{α−1}. It is clear that in the original problem there is only one plane partition for b = 0 (the empty plane partition). So, det M̃(α, 0) = ±1. This proves that det M̃ = ± ∏_{k=1}^{α/2} \frac{(b+2k)_{α−1}}{(2k)_{α−1}} , as was claimed.

5. Symmetric transpose–complementary plane partitions, II

In this section, we treat the case a = 2α and α odd. We can convert the plane partitions to families of nonintersecting lattice paths as described in Section 3. We have to enumerate path families starting at α points among A_{i} = (0, i − 1), i = 1, …, α + b and ending at the points E_{j} = (2j − 2, j − 1), j = 1, …, α, where the weight of a path p from A_{i} to E_{j} is (−1)^{i+area1(p)}. (As in Section 3, area1 has the same parity as area2, so we can use area1 with Lemma 8.) We also know from Section 3 how to proceed from here in the case of an even number of fixed end points. So we just add a dummy path, i.e., a point A_{α+b+1} = E_{α+1} = (2α, α) which is not connected to the other points. Clearly P(A_{α+b+1} → E_{α+1}) = 1 and P(A_{i} → E_{α+1}) = P(A_{α+b+1} → E_{j}) = 0 for i ≠ α + b + 1 and j ≠ α + 1.

As before, because of Lemmas 8 and 12, the enumeration of nonintersecting lattice paths starting at α + 1 points among the points A_{i}, 1 ≤ i ≤ α + b + 1, and ending at the points E_{j}, 1 ≤ j ≤ α + 1, equals Pf_{1≤i,j≤α+1} (∑_{r=1}^{α+b+1} ∑_{l=1}^{α+b+1} G_{li}G_{rj} sgn(r − l)), where

G_{ij} = P(A_{i} → E_{j}) = \begin{cases}1 & for i = α + b + 1 and j = α + 1 \\ (−1)^{i}\left[{i+j−2 \atop 2j−2}\right]_{−1} & for i ≠ α + b + 1 and j ≠ α + 1 \\ 0 & else. \end{cases}

So we have to evaluate

\sqrt{det_{1≤i,j≤α+1} (M_{ij})},

where M_{ij} = ∑_{r=1}^{α+b+1} ∑_{l=1}^{α+b+1} G_{li}G_{rj} sgn(r − l). The right sign of the square root is easily found by the fact that the enumeration is 1 for b = 0 and the result must be a continuous function in b. Case 1: α, b odd It is a routine calculation to verify that M_{2i−1,2j−1} = 0 (cf. the computation in Equation (11)). After reordering the rows and columns of M such that the even–numbered rows and columns come before the odd–numbered ones we have a skew–symmetric block matrix. Therefore, the Pfaffian of M equals the determinant of one of the blocks up to sign. To be precise, we have to evaluate

det_{1≤i,j≤(α+1)/2} (M_{2i,2j−1}) .

It is readily seen that M_{α+1,2j−1} = 0 for all j.

Therefore, the final result is 0 in this case. Case 2: α odd, b even Similar to earlier calculations we see that M_{2i−1,2j−1} = 0. After reordering of rows and columns of the matrix according to parity to put it in block form, we obtain det_{1≤i,j≤(α+1)/2} (M_{2i,2j−1}) for our (−1)–enumeration, up to sign. It is easily seen that

M_{2i,1} = \begin{cases}1 & for 2i = α + 1, \\ 0 & else. \end{cases}

Expansion of det_{1≤i,j≤(α+1)/2} (M_{2i,2j−1}) with respect to the first column gives

det_{1≤i,j≤(α−1)/2} \binom{}{M_{ij}}

where M̃_{ij} = M_{2i,2j+1}.

It is a routine calculation to verify that

M̃_{ij} = − ∑_{k=1}^{(α+b−1)/2} \binom{k + i − 1}{2i − 1}\binom{k + j − 1}{2j − 1}.

We show analogously to Lemma 13 that

det M̃ = ±\frac{∏k=1^{\frac{α−1}{2}} (b + 2k)_{α}}{∏k=1^{\frac{α−1}{2}} (2k)_{α}} .

The proofs of the following steps are analogous to the corresponding steps in Section 4. Step 1’: ∏_{j=1}^{(α−1)/2}((α + b + 1)/2 − j)_{2j} divides det M̃. Step 2’: ∏_{t=0}^{(α−1)/2−1}((α + b)/2 − t)_{2t+1} divides det M̃. The appropriate linear combination here is

M̃_{t+1,j} + ∑_{s=1}^{t}(−1)^{s−1}\binom{2s − 1}{s}\frac{M̃_{t+1−s,j}}{(2s − 1)2^{4s−1}} .

Step 3’: The degree and the leading coefficient It is easy to check that the maximal degree of the determinant equals the number of factors already found. As noted before, the enumeration equals 1 for b = 0. Therefore, the constant term of the polynomial is ±1 for the determinant and 1 in the final result.

It remains to show that ∏_{j=1}^{(α−1)/2}((α + b + 1)/2 − j)_{2j} ∏_{t=0}^{(α−1)/2−1}((α + b)/2 − t)_{2t+1} is a constant multiple of ∏_{k=1}^{(α−1)/2}(b + 2k)_{α}, which is readily verified. Thus Theorem 2 is proved.

6. Symmetric transpose–complementary plane partitions, III

In this section we treat the case a = 2α + 1 (see Figure 9). We can still express the (−1)–enumeration as a Pfaffian whose entries are polynomials in b but the determinant does not factor completely. The first two steps of Section 3 are completely analogous: Step 1: From plane partitions to rhombus tilings Again, we start by converting the plane partitions to rhombus tilings by projecting them to the plane. We obtain rhombus tilings of a hexagon with sidelengths 2α + 1, 2α + 1, 2b, 2α + 1, 2α + 1, 2b which have a vertical and a horizontal symmetry axis. These symmetry conditions imply that the corresponding rhombus tiling is determined by its upper right quarter. Step 2: From rhombus tilings to families of nonintersecting lattice paths. As before, we can convert each tiling to a family of nonintersecting lattice paths (see Figure 10). Again, the starting points may vary since the horizontal rhombi on the vertical axis can be in different places.

The starting points and end points are only slightly different from the ones in the case a = 2α:

20 THERESIA EISENKÖLBL

Figure 9. A symmetric transpose–complementary plane partition with a = 2α + 1.

Figure 10. The corresponding paths.

With a suitable coordinate system, the end points are

E_{j} = (2j − 1, j − 1), j = 1, …, α,  (17)

while the starting points are α points among the points

A_{i} = (0, i − 1), i = 1, …, α + b.  (18)

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

Figure 11. The path family made orthogonal.

The weight of a path p starting at A_{i} is (−1)^{i+area1(p)} (cf. Step 2 of Section 3). Since area1(p) can also be thought of as the area left of the path (and therefore as weight of the vertical steps), we can use Lemma 8 again.

To make this precise, let G_{ij} = P(A_{i} → E_{j}) be the weighted enumeration of all paths running from A_{i} to E_{j}, 1 ≤ i ≤ α + b and 1 ≤ j ≤ α. Then G_{ij} = (−1)^{i}\left[{i+j−1 \atop 2j−1}\right]_{−1}. For each path family we have to choose for the starting points α indices from 1, …, α + b, say k_{1} < k_{2} < ⋯ < k_{α}. By Equation (5) the enumeration of lattice path families with these starting points equals

det_{1≤i,j≤α} (P(A_{k_{i}} → E_{j})) = det_{1≤i,j≤α} (G_{k_{i},j}).

Therefore, the weighted count of all path families starting at α points among the A_{i}’s, 1 ≤ i ≤ α + b and ending at the points E_{j}, 1 ≤ j ≤ α equals

∑_{1≤k_{1}<···<k_{α}≤α+b} det_{1≤i,j≤α} (G_{k_{i},j}).  (19)

Step 3: Application of the minor–summation formula Case 1: α even, b odd. If α is even, the minor–summation formula (see Lemma 12) is directly applicable. Therefore, the weighted count equals Pf_{1≤i,j≤α}(M_{ij}), where

M_{ij} = ∑_{r=1}^{α+b} ∑_{l=1}^{α+b}(−1)^{l}\left[{l + i − 1 \atop 2i − 1}\right]_{−1}(−1)^{r}\left[{r + j − 1 \atop 2j − 1}\right]_{−1} sgn(r − l).  (20)

First, we express M_{ij} as a single sum. We can add the summands corresponding to r = 0 and l = 0 because they are zero. In M_{ij} the term \left[{l+i−1 \atop 2i−1}\right]_{−1} is zero if l + i is odd, so the sum really runs only over l with the same parity as i. So, let i_{0} be 0 for i even and 1 for i odd. It is now clear that we can take the sum over l of the form l = i_{0} + 2k where k runs from 0 to (α + b − 1)/2. This gives \left[{l+i−1 \atop 2i−1}\right]_{−1} = \binom{k+⌊(i−1)/2⌋}{i−1}. Analogously, we choose j_{0} ∈ {0, 1} with the same parity as j and write r = j_{0} + 2u. We get

M_{ij} = ∑_{k=0}^{\frac{α+b−1}{2}} ∑_{u=0}^{\frac{α+b−1}{2}}(−1)^{i+j}\binom{k + ⌊\frac{i−1}{2}⌋}{i − 1}\binom{u + ⌊\frac{j−1}{2}⌋}{j − 1} sgn(2u + j_{0} − 2k − i_{0})

= ∑_{k=0}^{\frac{α+b−1}{2}}(−1)^{i+j}\binom{k + ⌊\frac{i−1}{2}⌋}{i − 1} (∑_{u=0}^{k−1} −\binom{u + ⌊\frac{j−1}{2}⌋}{j − 1}

+\binom{k + ⌊\frac{j−1}{2}⌋}{j − 1} sgn(j_{0} − i_{0}) + ∑_{u=k+1}^{\frac{α+b−1}{2}} \binom{u + ⌊\frac{j−1}{2}⌋}{j − 1})

= ∑_{k=0}^{\frac{α+b−1}{2}}(−1)^{i+j}\binom{k + ⌊\frac{i−1}{2}⌋}{i − 1} (−\binom{k + ⌊\frac{j−1}{2}⌋}{j} + \binom{k + ⌊\frac{j−1}{2}⌋}{j − 1} sgn(j_{0} − i_{0})

+\binom{\frac{α+b+1}{2} + ⌊\frac{j−1}{2}⌋}{j} − \binom{k + 1 + ⌊\frac{j−1}{2}⌋}{j})

The summand is clearly a polynomial in b and k, so after summation up to (α+b−1)/2 we get a polynomial in b. So the Pfaffian of M is again a polynomial in b. We will find several factors but this time the determinant is not fully factorizable.

If both indices are even, M_{ij} can be written in closed form (the sum with one occurrence of k is easy, the remaining terms can be done with Zeilberger’s algorithm). Therefore:

M_{2i,2j} = \binom{(α + b − 1)/2 + j}{2j}\binom{(α + b − 1)/2 + i}{2i}\frac{j − i}{j + i}.  (21)

We show the following result:

det(M(α, b)) = ((b − 1) ∏_{k=1}^{α/2}((b − 1)/2 + k)_{α/2+1}

× (polynomial of degree (α/2)^{2} − 1))^{2}.

We will do so by taking the factors ((α + b − 1)/2 − i + 1)_{2i} out of row 2i and the factors ((α + b − 1)/2 − j + 1)_{2j} out of column 2j.

We have already seen the the entry can be written as

M_{2i,j} = ∑_{k=0}^{(α+b−1)/2}(k − i + 1)_{2i−1}p(k),

where p is a polynomial.

The term (k − i + 1)_{2i−1} is zero for −i + 1 ≤ k ≤ i − 1. This holds for all occurring k if −i ≤ (α + b − 1)/2 ≤ i − 1. Therefore ((α + b − 1)/2 − i + 1)_{2i} divides M_{2i,2j}.

By the skewsymmetry of M the analogous result holds for the columns. Equation (21) ensures that there are enough factors at crossings of evenindexed rows and columns.

We have now the factors

(∏_{i=1}^{α/2}((α + b − 1)/2 − i + 1)_{2i})^{2}

which are easily seen to be the same as

(∏_{k=1}^{α/2}((b − 1)/2 + k)_{α/2+1})^{2} .

It remains to find the factor (b − 1)^{2}.

Let b = 1. Equation (19) reduces to the sum of minors obtained by deleting one row of the (α+1)×α–matrix G with G_{ij} = (−1)^{i}\left[{i+j−1 \atop 2j−1}\right]_{−1}. This sum equals the determinant

of the (α + 1) × (α + 1)–matrix G̃ obtained from G by appending the column vector

( 1 ; −1 ; ⋮ ; −1 ; 1 ). Since G̃_{2i,2j−1} = 0 (by (6)), it is enough to show that det \binom{}{G_{2i,2j}} = 0. This

follows from the fact that the first column contains only 1’s and the last column only −1’s.

Since the entries of the skew-symmetric matrix are polynomials in b the factor (b−1) must occur twice in the determinant. The degree of the remaining polynomial can be found by comparing the degree of the product with the degrees of the entries. Case 2: α even, b even.

We denote the (i, j)–entry in this case M̃_{ij} because it will be a different polynomial in b.

Starting from Equation (20) we get by a calculation analogous to the case b odd:

M̃_{ij} = ∑_{k=0}^{(α+b)/2−1}(−1)^{i+j}\binom{k + ⌊i/2⌋}{i − 1} (−\binom{k + ⌊j/2⌋}{j} − \binom{k + ⌊j/2⌋}{j − 1} sgn(j_{0} − i_{0})

+\binom{(α + b)/2 + ⌊j/2⌋}{j} − \binom{k + 1 + ⌊j/2⌋}{j})

It can now easily be checked that the substitution b → −b − 2α − 1 changes M̃_{ij}(α, b) to (−1)^{i+j}M_{ij}(α, b). The statement in Theorem 3 is just the analogous substitution.

This settles the case α even. Case 3: α odd, b even. As before, we add a dummy path. That is, we add a point A_{α+b+1} = E_{α+1} which is disconnected from all the other points. If we write G̃_{ij} for the enumeration of paths from A_{i} to E_{j} we get

G̃_{ij} = \begin{cases}G_{ij} & for i ≤ α + b, j ≤ α, \\ 1 & for i = α + b + 1, j = α + 1, \\ 0 & else. \end{cases}

Now, we can apply the minor–summation formula (see Lemma 12). Therefore, the weighted count equals Pf_{1≤i,j≤α+1}(M′_{ij}), where

M′_{ij} = ∑_{r=1}^{α+b+1} ∑_{l=1}^{α+b+1} G̃_{li}G̃_{rj} sgn(r − l).

We have

M′_{ij} = \begin{cases}M_{ij} & for i ≠ α + 1 and j ≠ α + 1, \\ −(−1)^{j}\binom{(α + b + 1)/2 + ⌊(j − 1)/2⌋}{j} & for i = α + 1, \\ (−1)^{i}\binom{(α + b + 1)/2 + ⌊(i − 1)/2⌋}{i} & for j = α + 1. \end{cases}

From previous results it is now easily seen that ((α+b−1)/2−i+2)_{2i−1} divides M′_{2i−1,j} for i = 1, …, (α + 1)/2, similarly for the columns. We have to check that we can take enough factors out at the crossings of rows and columns. Using Zeilberger’s algorithm again, we get

M′_{2i−1,2j−1} = \binom{(α + b − 1)/2 + j}{2j − 1}\binom{(α + b − 1)/2 + i}{2i − 1}\frac{j − i}{i + j − 1}.

Therefore, the product (∏_{i=1}^{(α+1)/2}((α + b − 1)/2 − i + 2)_{2i−1})^{2} divides the determinant.

This is easily seen to be the same as (∏_{k=1}^{(α+1)/2}(b/2 + k)_{(α+1)/2})^{2}. Therefore, the enumeration has the form

∏_{k=1}^{(α+1)/2}(b/2 + k)_{(α+1)/2} · (polynomial of degree (α^{2} − 1)/4 ).  (22)

Case 4: α odd, b odd. Analogously to the previous case, we get

M′′_{ij} = \begin{cases}M̃_{ij} & for i ≠ α + 1 and j ≠ α + 1, \\ −(−1)^{j}\binom{(α + b)/2 + ⌊j/2⌋}{j} & for i = α + 1, \\ (−1)^{i}\binom{(α + b)/2 + ⌊i/2⌋}{i} & for j = α + 1. \end{cases}

This is a polynomial in b. If we replace b with −b − 2α − 1 we get

(−1)^{i+j}M_{ij} for i ≠ α + 1 and j ≠ α + 1,
−(−1)^{j}(−1)^{j}\binom{(b + α − 1)/2 + ⌈j/2⌉}{j} for i = α + 1,
(−1)^{i}(−1)^{i}\binom{(b + α − 1)/2 + ⌈i/2⌉}{i} for j = α + 1,

which is clearly equal to (−1)^{i+j}M′_{ij}.

Replacing b with −b − 2α − 1 in Equation (22) yields the desired result.

This finishes the proof of Theorem 3. The remaining polynomials seem to be irreducible in general.

Figure 12. A cyclically symmetric transpose–complementary plane partition.

7. Cyclically symmetric transpose–complementary plane partitions.

In this section we treat the case of cyclically symmetric transpose–complementary plane partitions. These plane partitions are contained in boxes with sidelengths 2α × 2α × 2α. If we view such a plane partition as a rhombus tiling, it has a horizontal symmetry axis (because of being transpose–complementary). The cyclic symmetry gives two more symmetry axes (see Figure 12). The weight is (−1)^{n(P)}, where n(P) is the number of half orbits in the plane partition not contained in the plane partition shown in Figure 15. The orbits consist either of two cubes or of six cubes. The former ones consist of cubes with coordinates of the form (x, x, x) and it is easy to see that these cubes are part of a cyclically symmetric transpose–complementary plane partition if and only if 1 ≤ x ≤ α, so they do not contribute to the weight. The orbits consisting of 6 cubes have 3 cubes in the plane partition and 3 cubes outside. Therefore, it is enough to look at one of the six regions of the rhombus tiling (this corresponds to one of the 8 big cubes of sidelength α partitioning the box containing the plane partition). We choose the upper right region (see Figure 13). The weight is now simply (−1)^{n} where n is the number of cubes in this region.

As before, we can convert the rhombus tilings to families of nonintersecting lattice paths. With a suitable coordinate system the coordinates of the starting points A_{i} and

• _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ∘ ∘ ∘ ∘^{A_{1}} ^{A_{2}} ^{E_{1}}  ^{E_{2}}

Figure 13. A path family corresponding to a cyclically symmetric transpose–complementary plane partition.

the end points E_{j} are

A_{i} = (i, 2i)  i = 1, …, α − 1,  (23)
E_{j} = (2j, j)  j = 1, …, α − 1.  (24)

The weight is again (−1)^{area1(p)}. We want to use Lemma 8, so we have to use area2 instead of area1. This gives the sign (−1)^{j(2j−i)} in each entry and a global sign of (−1)^{∑_{k=1}^{α−1} k^{2}}. According to Lemma 8 and the paragraph after it, our (−1)–enumeration is given by

(−1)^{∑_{k=1}^{α−1} k^{2}} det_{1≤i,j≤α−1} ((−1)^{j(2j−i)}\left[{i + j \atop 2j − i}\right]_{−1}) .

The (−1)–binomial coefficient is 0 for i and j odd (cf. (6)), so the sign (−1)^{j(2j−i)} can be dropped. Now we reorder rows and columns so that odd indices come before even indices. The arising matrix has a zero block in the upper left corner. For even α, this block immediately forces the determinant to be zero. For odd α, we see that the determinant is the product of two identical determinants times (−1)^{(α−1)/2}. The sign cancels exactly with (−1)^{∑_{k=1}^{α−1} k^{2}}. Explicitly, the (−1)–enumeration reduces to

det_{1≤i,j≤(α−1)/2} (\left[{2i + 2j − 1 \atop 4j − 2i + 1}\right]_{−1})^{2}

= det_{1≤i,j≤(α−1)/2} (\binom{i + j − 1}{2j − i})^{2} = det_{0≤i,j≤(α−3)/2} (\binom{i + j + 1}{2i − j})^{2} . (25)

The determinant on the right-hand side is the case μ = 1, n = (α−1)/2 of the following identity from [13]:

det_{0≤i,j≤n−1} (\binom{μ + i + j}{2i − j})

= (−1)^{χ(n≡3(4))}2^{\binom{n−1}{2}} ∏_{i=1}^{n−1} \frac{(μ + i + 1)_{⌊(i+1)/2⌋}(−μ − 3n + i + 3/2)_{⌊i/2⌋}}{(i)_{i}} . (26)

It is a routine computation to verify that the square of the right hand side agrees with the expression in Theorem 4.

Figure 14. A totally symmetric self–complementary plane partition.

8. Totally symmetric self–complementary plane partitions

In this section we do the (−1)–enumeration of totally symmetric self–complementary plane partitions. The weight is (−1)^{n} where n is the number of half orbits in the plane partition which are not in the plane partition shown in Figure 15. The corresponding rhombus tilings have six symmetry axes dividing the hexagon in 12 parts (see Figure 14). It is enough to consider the tiling of one of them (see Figure 16). Clearly, the hexagon must have sidelengths of the form 2α × 2α × 2α. We use again nonintersecting lattice paths. With a suitable coordinate system the starting points are α − 1 points among A_{i} and the end points are E_{j}, where

A_{i} = (i, i) i = 1, …, 2α − 2,  (27)
E_{j} = (2j, j) j = 1, …, α − 1.  (28)

The appropriate weight of a path from A_{i} to E_{j} is (−1)^{area2(p)+i(i+1)/2} where area2 is the area between the path and the x–axis and the factor (−1)^{i(i+1)/2} accounts for the Figure 15. A totally (cyclically) symmetric self–complementary plane partition with weight 1.

rhombi on the symmetry axis. The enumeration of paths from A_{i} to E_{j} with this weight is thus

T_{ij} = \left[{j \atop i − j}\right]_{−1}(−1)^{j(2j−i)}(−1)^{i(i+1)/2}.

This weight gives the (−1)–enumeration up to a global sign. If we assign the plane partition in Figure 15 the weight 1, this global sign equals (−1)^{(α−1)/2} for odd α. Now we distinguish between two cases according to the parity of α. Case 1: α odd For odd α the number of endpoints – (α − 1) – is even. Therefore, Lemma 12 is applicable. The (−1)–enumeration is (−1)^{(α−1)/2} Pf M, where

M_{ij} = ∑_{k=1}^{2α−2} ∑_{l=1}^{2α−2} T_{ki} sgn(l − k)T_{lj} 1 ≤ i, j ≤ α − 1.

We claim that M_{2i−1,2j−1} = 0. This is proved by splitting the double sums according to the cases k = 2r, l = 2s, k = 2r, l = 2s − 1, k = 2r − 1, l = 2s − 1 and k = 2r − 1, l = 2s

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

Figure 16. A path family corresponding to a totally symmetric self– complementary plane partition.

into four double sums. Using Equation (6) we get

M_{2i−1,2j−1} = ∑_{r=1}^{α−1} ∑_{s=1}^{α−1} \binom{i − 1}{r − i}\binom{j − 1}{s − j}(−1)^{r+s} sgn(s − r)

+ ∑_{r=1}^{α−1} ∑_{s=1}^{α−1} \binom{i − 1}{r − i}\binom{j − 1}{s − j}(−1)^{r+s−1} sgn(2s − 2r − 1)

+ ∑_{r=1}^{α−1} ∑_{s=1}^{α−1} \binom{i − 1}{r − i}\binom{j − 1}{s − j}(−1)^{r+s} sgn(s − r)

+ ∑_{r=1}^{α−1} ∑_{s=1}^{α−1} \binom{i − 1}{r − i}\binom{j − 1}{s − j}(−1)^{r+s−1} sgn(2s − 2r + 1)

= ∑_{r=1}^{α−1} \binom{i − 1}{r − i}\binom{j − 1}{r − j}(−1)^{r+r−1} sgn(2r − 2r + 1)

+ ∑_{r=1}^{α−1} \binom{i − 1}{r − i}\binom{j − 1}{r − j}(−1)^{r+r−1} sgn(2r − 2r − 1)

In the last two steps we have used the fact that the first two sums and the last two sums cancel each other except for the terms with r = s in the second and fourth sum. These remaining terms cancel each other completely.

Now we can reorder the rows and columns of M such that the even-numbered ones come before the odd-numbered ones. We call this new matrix M′. We have Pf M = (−1)^{(α−1)(α+1)/8} Pf M′. Since M′ is skew-symmetric, we get a block matrix of the form

M′ = (\begin{matrix}∗ & A \\ −^{t}A & 0 \end{matrix}) ,

where A is an (α − 1)/2 × (α − 1)/2–matrix with A_{ij} = M_{2i,2j−1}.

It follows from the definition of the Pfaffian that Pf M′ = (−1)^{(α−1)(α−3)/8} det A. We want to evaluate (−1)^{(α−1)/2+(α−1)(α+1)/8+(α−1)(α−3)/8} det A = det A

Now we simplify A_{ij}.

A_{ij} = ∑_{k,l=1}^{2α−2} \left[{2i \atop k − 2i}\right]_{−1}\left[{2j − 1 \atop l − 2j + 1}\right]_{−1}(−1)^{l}(−1)^{k(k+1)/2+l(l+1)/2} sgn(l − k)

=^{k=2r} ∑_{l=1}^{2α−2} ∑_{r=1}^{α−1} \binom{i}{r − i}\binom{j − 1}{⌊(l + 1)/2 − j⌋}(−1)^{r}(−1)^{l(l−1)/2} sgn(l − 2r)

= ∑_{r=1}^{α−1} ∑_{l=1}^{2r−1} \binom{i}{r − i}\binom{j − 1}{⌊(l + 1)/2 − j⌋}(−1)^{r+l(l−1)/2}(−1)

+ ∑_{r=1}^{α−1} ∑_{l=2r+1}^{2α−2} \binom{i}{r − i}\binom{j − 1}{⌊(l + 1)/2 − j⌋}(−1)^{r+l(l−1)/2}

=^{(∗)} ∑_{r=1}^{α−1} \binom{i}{r − i}\binom{j − 1}{r − j}

= \binom{i + j − 1}{2j − i − 1}

At the step (∗) we have used the fact that two summands for l = 2s − 1 and l = 2s cancel each other. It remains to evaluate

det_{1≤i,j≤(α−1)/2} (\binom{i + j − 1}{2j − i − 1}) = det_{0≤i,j≤(α−3)/2} (\binom{i + j + 1}{2j − i}) .

This is just Equation (26) with i, j interchanged, n = (α − 1)/2 and μ = 1. Therefore, the weighted count equals

(−1)^{χ((α−1)/2≡3(4))}2^{\binom{(α−1)/2−1}{2}} ∏_{i=1}^{(α−1)/2−1} \frac{(i + 2)_{⌊(i+1)/2⌋}(−3(α − 1)/2 + i + 1/2)_{⌊i/2⌋}}{(i)_{i}}

which is easily seen to be the expression claimed in Theorem 5. Case 2: α even Since α − 1 is odd now, we need an additional path. Therefore, we use the following starting and end points:

A_{i} = (i, i) i = 0, …, 2α − 2,  (29)
E_{j} = (2j, j) j = 0, …, α − 1.  (30)

(−1)–ENUMERATION OF PLANE PARTITIONS 31

Again, the weighted enumeration of the paths from A_{i} to E_{j} is

T_{ij} = \left[{j \atop i − j}\right]_{−1}(−1)^{j(2j−i)}(−1)^{i(i+1)/2}.

By Lemma 12, we have to evaluate Pf M where M is the α × α–matrix with entries

M_{ij} = ∑_{k=0}^{2α−2} ∑_{l=0}^{2α−2} T_{ki} sgn(l − k)T_{lj}.

We show that Pf M = 0 by showing that M_{0j} = 0 for 0 ≤ j ≤ α − 1. We use the fact that

T_{k0} = \left[{0 \atop k}\right]_{−1}(−1)^{k(k+1)/2} = \begin{cases}1 & for k = 0 \\ 0 & else. \end{cases}

Therefore,

M_{0j} = ∑_{l=0}^{2α−2} ∑_{k=0}^{2α−2} T_{k0} sgn(l − k)T_{lj} = ∑_{l=1}^{2α−2} T_{lj}.

Let j = 2u be even with u ≠ 0 (j = 0 is trivial):

M_{0j} = ∑_{l=1}^{2α−2} \left[{j \atop l − j}\right]_{−1}(−1)^{lj}(−1)^{l(l+1)/2}

= ∑_{l=1}^{2α−2} \left[{2u \atop l − 2u}\right]_{−1}(−1)^{l(l+1)/2}

= ∑_{r=1}^{α−1} \binom{u}{r − u}(−1)^{r}

= ∑_{s=0}^{u} \binom{u}{s}(−1)^{s+u}

= 0

Now, let j = 2u + 1 be odd:

M_{0j} = ∑_{l=1}^{2α−2} \left[{j \atop l − j}\right]_{−1}(−1)^{lj}(−1)^{l(l+1)/2}

= ∑_{l=1}^{2α−2} \left[{2u + 1 \atop l − 2u − 1}\right]_{−1}(−1)^{l(l−1)/2}

= ∑_{r=1}^{α−1} \binom{u}{r − 1 − u}(−1)^{r} + ∑_{r=0}^{α−2} \binom{u}{r − u}(−1)^{r}

= ∑_{s=0}^{u} \binom{u}{s}(−1)^{s+u+1} + ∑_{s=0}^{u} \binom{u}{s}(−1)^{s+u}

= 0

Thus, Theorem 5 is proved.

} b } { b {  {  } c a c  a

Figure 17. A self–complementary plane partition.

} b } { b {  {  } c a c  a

Figure 18. A self–complementary plane partition with weight 1.

9. Self–complementary plane partitions

In this section we do the (−1)–enumeration for self–complementary plane partitions contained in boxes with even sidelengths. These plane partitions correspond to rhombus tilings with 180^{∘} rotational symmetry, see Figure 17 for an example. The weight is (−1)^{n(P)} where n(P) counts all half orbits in the plane partition P that are not in the half–full plane partition (cf. Figure 18). For example, the plane partition in Figure 17 has weight (−1)^{4} = 1.

The tiling is clearly determined by one half of the hexagon. Similarly to the previous cases, we find a bijection with families of nonintersecting lattice paths (see Figure 19). Without loss of generality we assume that b ≤ c. The result turns out to be symmetric in b and c, so we can drop this condition in the statement of Theorem 6.

} { b { {  } c − x a x  a + b

Figure 19. The paths for self–complementary plane partitions. (x = \frac{c−b}{2})

Write x for (c − b)/2. The starting points of the orthogonal version of our lattice paths are

A_{i} = (i − 1, b + i − 1) for i = 1, …, a.

The end points are a points chosen symmetrically among

E_{j} = (x + j − 1, j − 1) for j = 1, …, a + b.

We claim that for a path from A_{i} to E_{j} we can use the weight (−1)^{area2} multiplied by (−1)^{j} if j ≤ \frac{a+b}{2}. (area2 is the area between the path and the x–axis.) This can be expressed as a product of weights of individual steps, so Lemma 8 is applicable. We have to check that the weight changes sign if we replace a half orbit with the complementary half orbit. If one of the affected cubes is completely inside the half shown in Figure 19, area2 changes by one. If the two affected cubes are on the border of the figure, two symmetric endpoints, say E_{j} and E_{a+b+1−j}, are changed to E_{j+1} and E_{a+b−j} or vice versa. It is easily checked that in this case area2 changes by j + (a + b − j) which is even. The factor (−1)^{j} becomes (−1)^{j+1} which gives the desired sign change. It is straightforward to check that this weight equals (−1)^{1+···+a/2+x(0+···+(a/2−1))+(c−x)((a+b−1)+···+(a+b−a/2))} for the plane partition in Figure 18, so we have to multiply the path enumeration by the global sign (−1)^{a(a+2)/8+xa/2}.

Now define S to be an a × (a + b)–matrix with

S_{ij} = \begin{cases}(−1)^{(x+j−i)(j−1)}\left[{b+x \atop x+j−i}\right]_{−1}(−1)^{j} & for 1 ≤ j ≤ (a + b)/2, \\ (−1)^{(x+j−i)(j−1)}\left[{b+x \atop x+j−i}\right]_{−1} & for (a + b)/2 + 1 ≤ j ≤ a + b. \end{cases}

Observe that S_{ij} is the weighted enumeration of lattice paths from A_{i} to E_{j} with the weight described above. By Lemma 8 applied to all sets of fixed end points, the enumeration can be expressed as

∑_{1≤k_{1}<···<k_{a/2}≤(a+b)/2} det (S_{k_{1}}, …, S_{k_{a/2}}, S_{a+b+1−k_{a/2}}, …, S_{a+b+1−k_{1}}) ,

where S_{j} is the jth column of S.

We can express this sum as a single Pfaffian using the following lemma which is a simple consequence of Lemma 11:

Lemma 14. Let S be a 2m × 2n–matrix with m ≤ n and S^{∗} be the matrix

(S_{1}, …, S_{n}, S_{2n}, …, S_{n+1})

where S_{j} denotes the jth column of S. Let A be the matrix (\begin{matrix}0 & I_{n} \\ −I_{n} & 0 \end{matrix}). Then the

following identity holds:

∑_{1≤k_{1}<···<k_{m}≤n} det(S_{k_{1}}, …, S_{k_{m}}, S_{2n+1−k_{m}}, …, S_{2n+1−k_{1}}) = Pf(S^{∗}A(^{t}S^{∗})).

Proof. The proof follows from Lemma 11 with A = (\begin{matrix}0 & I_{n} \\ −I_{n} & 0 \end{matrix}) and T = ^{t}S^{∗}. The sign

of Pf (A_{k_{1},...,k_{m},k_{1}+n,...,k_{m}+n}^{k_{1},...,k_{m},k_{1}+n,...,k_{m}+n}) cancels exactly with the sign obtained from the reordering of the columns of S in the determinant. □

In our case 2m = a, 2n = a + b and

S_{ij}^{∗} = (−1)^{(x+j−i)(j−1)}\left[{b + x \atop x + j − i}\right]_{−1}(−1)^{j} for 1 ≤ j ≤ (a + b)/2,
S_{i(j+(a+b)/2)}^{∗} = (−1)^{(x−i)j}\left[{b + x \atop −a − 1 + j + i}\right]_{−1}  for 1 ≤ j ≤ (a + b)/2.

It remains to determine the Pfaffian of the a × a–matrix M = S^{∗}A(^{t}S^{∗}). We distinguish between two cases according to the parity of x.

Case 1: x odd In this case the entry M_{ij} of the a × a–matrix M = S^{∗}A(^{t}S^{∗}) can be written as

M_{ij} = ∑_{k=1}^{(a+b)/2}(−1)^{k(1+i+j)+1} ((−1)^{i}\binom{(b + x − 1)/2}{⌊(b + i − k)/2⌋}\binom{(b + x − 1)/2}{⌊(k + j − 1 − a)/2⌋}

− (−1)^{j}\binom{(b + x − 1)/2}{⌊(b + j − k)/2⌋}\binom{(b + x − 1)/2}{⌊(k + i − 1 − a)/2⌋}) .

The sum can be split into two parts according to even and odd summation indices, the sum over odd indices is reversed and then combined with the other sum. This gives

∑_{l=1}^{(a+b)/2} ((−1)^{j}\binom{(b + x − 1)/2}{b/2 − l + ⌊j/2⌋}\binom{(b + x − 1)/2}{l − a/2 + ⌊(i − 1)/2⌋}

−(−1)^{i}\binom{(b + x − 1)/2}{⌊(b + i)/2⌋ − l}\binom{(b + x − 1)/2}{l + ⌊(j − 1)/2⌋ − a/2}) .

By the Chu–Vandermonde summation formula this equals

M_{ij} = (−1)^{j}\binom{b + x − 1}{(b − a)/2 + ⌊j/2⌋ + ⌊(i − 1)/2⌋}

− (−1)^{i}\binom{b + x − 1}{(b − a)/2 + ⌊i/2⌋ + ⌊(j − 1)/2⌋}.

It is easily seen that M_{2i,2j} = 0. As before, we reorder the rows and columns so that even–indexed ones come before odd–indexed ones. We thus obtain a block matrix. The Pfaffian of M equals the determinant of the lower left block matrix.

So we have to evaluate

det_{1≤i,j≤a/2} M_{2i−1,2j} = det_{1≤i,j≤a/2} (\binom{b + x}{(b − a)/2 + i + j − 1}) .

This is done by taking \frac{(x+(b+a)/2−j+1)_{(b−a)/2+j}}{(b/2+j−1)!} out of the jth column, j = 1, 2, …, a/2, and (−1)^{i−1} out of the ith row, i = 1, 2, …, a/2, then applying Lemma 9 with X_{j} = j, B_{k} = −x − (b + a)/2 + k − 2 and A_{k} = (b − a)/2 + k − 1. This gives the desired result multiplied by (−1)^{1+···+(a/2−1)}, which cancels exactly with the global sign. Case 2: x even In this case the entry M_{ij} of the a × a–matrix M = S^{∗}A(^{t}S^{∗}) can be written as

M_{ij} = ∑_{k=1}^{(a+b)/2}(−1)^{k(1+i+j)} ((−1)^{i}\left[{b + x \atop b + i − k}\right]_{−1}\left[{b + x \atop k + j − 1 − a}\right]_{−1}

− (−1)^{j}\left[{b + x \atop b + j − k}\right]_{−1}\left[{b + x \atop k + i − 1 − a}\right]_{−1}) .

Here we have some vanishing entries. If i and j have the same parity then in each product of two (−1)–binomial coefficients one of them is zero. So as before we reorder even–indexed rows and columns before odd–indexed rows and columns and get a block matrix. By a calculation analogous to the previous subcase we get for the lower left block:

M_{2i−1,2j} = −\binom{b + x}{(b − a)/2 + i + j − 1}.

Up to the sign (−1)^{a/2} this is exactly the same determinant as in the previous subcase. Since this sign is the difference in the global signs generated by the change in parity of x, Theorem 6 is proved.

If not all sidelengths are even, we can express the (−1)–enumeration as a Pfaffian in a similar way. We find experimentally that the result has again a nice product formula for small values of a, b, c (see the conjecture on page 5), but the matrix does not contain blocks of zeros in these cases, so the analogous method does not work.

10. Cyclically symmetric self–complementary plane partitions

In this section we describe Kuperberg’s proof of Theorem 7 [10]. This proof is included here with his permission. Analogous to Section 8 the weight of a cyclically symmetric self–complementary plane partition (see Figure 20) is the number of its half orbits which are not in the plane partition shown in Figure 15.

We want to prove that the (−1)–enumeration of cyclically symmetric self–complementary plane partitions contained in a 2α×2α×2α–box is the square root of the weighted enumeration of cyclically symmetric plane partitions with weight (−1)^{# orbits} contained in the same box. This does indeed prove Theorem 7 because by the (−1)–phenomenon mentioned in the introduction the latter (−1)–enumeration is equal to the ordinary enumeration of cyclically symmetric self–complementary plane partitions which is known to equal (2) thanks to [9].

Figure 20. A cyclically symmetric self–complementary plane partition.

For proving equality we convert both (−1)–enumerations to the weighted enumeration of perfect matchings of certain graphs. (Perfect matchings are collections of edges such that every vertex of the graph is incident to exactly one edge.) Then we can express both enumerations as Pfaffians by the Hafnian–Pfaffian method described in [8]. Close inspection of the matrices reveals that the (−1)–enumeration of cyclically symmetric plane partitions is indeed the square of the (−1)–enumeration of self–complementary cyclically symmetric plane partitions. Step 1: The (−1)–enumeration of cyclically symmetric plane partitions equals the weighted enumeration of perfect matchings.

We start with the (−1)–enumeration of cyclically symmetric plane partitions. As before, these can be viewed as cyclically symmetric rhombus tilings. They are determined by the tiling of the upper third of the hexagon. Now we take the inner dual graph, i.e., the dual graph without the vertex corresponding to the unbounded face (see Figure 21). In this graph, the rhombus tiling corresponds to a perfect matching of that graph if we replace every rhombus with an edge (cf. [8]). The bold edges in the figure shall have weight −1. The pattern of bold edges can be described as follows: The edges crossing the vertical symmetry axis are alternately bold and not bold. The horizontal edges in the right half are also alternately bold and not bold in each column. From the two possible ways to do that we choose the horizontal edges that can be reached with steps

\begin{matrix}e_{1} \\ e_{2} \end{matrix}

Figure 21. The upper third of the hexagon and the inner dual graph.

to the northeast from the bold edges on the axis. The left half is just like the right half rotated by 60^{∘}.

We claim that this agrees with the weight (−1)^{#orbits of cubes}.

The removal or addition of a cube of the plane partition corresponds to exchanging three edges in the matching contained in one hexagon with the other three (cf. [8]). Since every hexagon of the graph contains exactly one bold edge, the product of the weights changes sign.

If the cube in question has coordinates (i, i, i) the removal or addition corresponds to switching between the two edges e_{1} and e_{2} in the matching which also changes the sign of the matching.

We can remove the edges e_{1} and e_{2} because they clearly correspond to one edge with weight 0. The resulting graph is shown in Figure 22. We stretch the edges lying on the vertical symmetry axis, rotate the two halves of the graph 30^{∘} outwards and obtain the graph in Figure 23. Step 2: The Hafnian–Pfaffian method expresses the number of perfect matchings as a Pfaffian

For the Hafnian–Pfaffian method we need an orientation of the graph such that every face contains an odd number of edges oriented clockwise.

Since the graph in Figure 23 is bipartite we can find a bipartite colouring with the rightmost vertices black and the leftmost vertices white. Now we can simply orient all edges from black vertices to white vertices. By the Hafnian–Pfaffian method the weighted enumeration equals the Pfaffian of the directed adjacency matrix up to sign. The entry (v, w) of this matrix is the weight of the edge (v, w) if it is oriented v → w and minus the weight otherwise. We abbreviate black and white with B and W, the left and the right half of the graph in Figure 23 with Le and Ri and get the following expression for the (−1)–enumeration of cyclically symmetric plane partitions:

Figure 22. Bold edges have weight −1.

Figure 23. The graph for cyclically symmetric plane partitions.

Pf (\begin{matrix}& BLe & BRi & W Ri & W Le \\ BLe & 0 & 0 & 0 & A \\ BRi & 0 & 0 & ^{t}A & B \\ W Ri & 0 & −A & 0 & 0 \\ W Le & −^{t}A & −^{t}B & 0 & 0 \end{matrix}) = |det (\begin{matrix}& W Ri & W Le \\ BLe & 0 & A \\ BRi & ^{t}A & B \end{matrix})| .  (31)

Here A is the matrix consisting of the weights of the edges running from the black vertices on the left to the white vertices on the left. The black vertices on the left are written in the same order as the white vertices on the right corresponding to them via rotation by 180^{∘}. The edges from the white vertices on the right to the black vertices on the right generate the matrix −A because rotation by 180^{∘} changes the orientation of the edges while everything else remains the same inside the triangles. The other occurrences Figure 24. The graph for cyclically symmetric self–complementary plane partitions.

of A follow from the fact that the adjacency matrix must be skew–symmetric. The zeros in the matrix come from the fact that there are no edges between two black or two white vertices and between black vertices on the left and white vertices on the right.

Step 3: The analogous two steps for cyclically symmetric self–complementary plane partitions.

Now we do the same thing for cyclically symmetric self–complementary plane partitions. The corresponding rhombus tilings are clearly determined by the tiling of a sixth of the hexagon. See Figure 24 for this triangle together with its inner dual graph. At the rightmost vertex there would be a loop which can be omitted because it can never be part of a perfect matching. (Alternatively, the center of such a rhombus tiling must always consist of six outward pointing rhombi.)

Again, we have to check the conditions of the Hafnian–Pfaffian method. First, we let the bold edges in Figure 24 have weight −1. They are in the same places as the bold edges in the left half of the graph in Figure 23. Thus, every hexagonal face of the graph contains exactly one bold edge. As before, this ensures that the addition or removal of a cube changes the weight of the corresponding matching. Second, we again orient edges between white and black vertices from black to white with the same colouring as before (i.e., the leftmost vertices are white). The edges from white to white vertices are oriented clockwise. The corresponding Pfaffian is

Pf (\begin{matrix}& BLe & W Le \\ BLe & 0 & Ā \\ W Le & −^{t}Ā & −B̄ \end{matrix}) ,

because there are no edges between black vertices.

Since the graph is the same as the left half of the graph for cyclically symmetric plane partitions, we get Ā = A. It is easy to check that also B̄ = B. Step 4: The Pfaffian of Step 2 is the square of the Pfaffian of Step 3

The (−1)–enumeration of cyclically symmetric self–complementary plane partitions equals

Pf (\begin{matrix}0 & A \\ −^{t}A & −B \end{matrix}) = ±\sqrt{det (\begin{matrix}0 & A \\ −^{t}A & −B \end{matrix})} = ±\sqrt{|det (\begin{matrix}0 & A \\ ^{t}A & B \end{matrix})|}.

The last expression is the square root of the (−1)–enumeration of cyclically symmetric plane partitions (see (31)). Thus, Theorem 7 is proved.

References

[1] G. E. Andrews, Plane partitions (II): The equivalence of the Bender–Knuth and the MacMahon conjectures, Pacific J. Math., 72 (1977), 283–291.

[2] G. E. Andrews, Plane partitions (I): The MacMahon conjecture, Adv. in Math. Suppl. Studies, 1 (1978), 131–150.

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

[4] I.M. Gessel, X. Viennot, Determinant, paths and plane partitions, Preprint, (1989).

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

[6] M. Ishikawa and M. Wakayama, Minor summation formula of Pfaffians, Linear and Multilinear Algebra 39 (1995), 285–305.

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

[8] G. Kuperberg, An exploration of the permanent-determinant method, Electron. J. Combin. 5, (1998), #R46, arXiv:math.CO/9810091.

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

[10] G. Kuperberg, Private communication. Nov 22nd, 2000.

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

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

[13] Mills, Robbins, Rumsey, Enumeration of a symmetry class of plane partitions, Discr. Math. 67, (1987), 43-55.

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

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

[16] S. Okada, Applications of minor summation formulas to rectangular-shaped representations of classical groups, J. Algebra, 205, (1998), 337–367.

[17] L.J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, (1966).

[18] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, (1986).

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

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

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

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

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

[24] D.Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195–204.

[25] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990), 207–211.

[26] D. Zeilberger, Proof of the alternating sign matrix conjecture, Electron. J. Combin. 3(2) “The Foata Festschrift” (1996), #R13, 84pp, arXiv:math.CO/9407211.