A new proof of the M–R–R conjecture — including a generalization

C. Krattenthaler^{†}

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

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

Abstract. We evaluate the determinant det_{0≤i,j≤n−1} (δ_{ij} + ∑_{t,k=0}^{n−1} \binom{i+μ}{t}\binom{k+ν}{k−t} \binom{j−k+μ−1}{j−k}2^{k−t}) which gives the 2-enumeration of certain shifted plane partitions. This generalizes a result of Andrews (Aequationes Math. 33 (1987), 230–250), who evaluated this determinant for ν = 0, thereby proving a conjecture of Mills, Robbins and Rumsey (Discrete Math. 67 (1987), 43–55).

1. Introduction. In their investigation on plane partition enumeration, Mills, Robbins and Rumsey [11, p. 50] came across the determinant

det_{0≤i,j≤n−1} (δ_{ij} + ∑_{t=0}^{n−1} ∑_{k=0}^{n−1} \binom{i + μ}{t}\binom{k}{k − t}\binom{j − k + μ − 1}{j − k}x^{k−t}) ,  (1.1)

which (in sec. 4 of their paper) they identified as the generating function for certain shifted plane partitions. For x = 1, this determinant was evaluated by Andrews [1]. The case μ = 0 established the enumeration of cyclically symmetric plane partitions, conjectured by Macdonald, and the case μ = 1 established the enumeration of descending plane partitions, conjectured by Andrews. Mills, Robbins and Rumsey [11] used Andrews’ determinant evaluation to evaluate the determinant

det_{0≤i,j≤n−1} (∑_{t=i}^{2j} \binom{i + μ}{t − i}\binom{j}{2j − t}x^{2j−t})  (1.2)

for x = 1, which established the enumeration of transpose-complementary symmetric plane partitions.

1991 Mathematics Subject Classification. Primary 05A15; Secondary 05A17, 15A15, 33C20..

Key words and phrases. Determinant evaluations, hypergeometric series, enumeration of plane partitions.

†Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-MAT

In the same paper they conjectured an evaluation of (1.1) (and also of (1.2)) for x = 2, which was established by Andrews [3], following the lines of his proof [1] for the evaluation of (1.1) for x = 1. (Andrews coined the name “M–R–R conjecture” for the “2-evaluation” of (1.1).)

In this paper we generalize the aforementioned determinant evaluations to the following result. Here and in the sequel, we use the standard notation (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, (a)_{0} := 1, for shifted factorials.

Theorem 1. Let n be a positive integer. Then

det_{0≤i,j≤n−1} (δ_{ij} + ∑_{t=0}^{n−1} ∑_{k=0}^{n−1} \binom{i + μ}{t}\binom{k + ν}{k − t}\binom{j − k + μ − 1}{j − k}2^{k−t})

= \{ \begin{matrix}2^{n(n+2)/4} \frac{(\frac{μ+ν+n+1}{2})n/2}{(n − 1)!!} ∏_{i=1}^{n/2−1} \frac{(\frac{μ+ν+1}{2} + i)_{i}^{2}}{(2i − 1)!!^{2}} & if n is even, \\ 2^{(n+1)^{2}/4} ∏_{i=1}^{(n−1)/2} \frac{(\frac{μ+ν+1}{2} + i)_{i}^{2}}{(2i − 1)!!^{2}} & if n is odd. \end{matrix} (1.3)

We prove this determinant evaluation in section 2. The method that we use for the proof is also applied successfully in [6, 7, 8] (see in particular the tutorial description in [8, sec. 2]). What we actually do in section 2 is to show that the determinant in (1.3) can be written as the product of two other determinants (see Lemma 2) and then evaluate these two other determinants (see Theorems 3 and 4). One of these, Theorem 3, generalizes the aforementioned evaluation of the determinant in (1.2). Finally, in section 3, we extend the combinatorial interpretation of (1.1) as the 2-enumeration of certain shifted plane partitions by showing that the determinant in (1.3) gives the 2-enumeration of a more general class of shifted plane partitions. Besides, this final section contains also a combinatorial interpretation for a determinant generalizing (1.2) which is important in the proof of Theorem 1. Remarks on how this connects to cyclically symmetric, transpose-complementary symmetric, and descending plane partitions can also be found there.

Concluding, we remark that the determinant in (1.3) has a simpler representation as

det_{0≤i,j≤n−1} (δ_{ij} + ∑_{t=0}^{j} \binom{i + μ + ν + t}{t}\binom{j + μ + ν}{j − t}) .  (1.4)

This is proved for ν = 0 in [3, Lemma 2] by using a quadratic _{2}F_{1} transformation formula and Chu-Vandermonde summation. The same procedure works for arbitrary ν. We may therefore omit the proof of this remark. The fact that the representation (1.4) shows a dependence on μ + ν only rather than on μ and ν independently, which is not apparent in the left-hand side of (1.3), explains why the result on the right-hand side of (1.3) is exactly Andrews’ result with μ replaced by μ + ν. However, similar explanations are not possible for our determinant evaluations in Theorems 3 and 4 on which our proof of Theorem 1 is based.

2. Proof of Theorem 1. We start by decomposing the determinant in (1.3) into a product of two other determinants. To be more precise, we prove the following decomposition for a determinant Z_{n}(x; μ, ν) (see the definition below) which reduces to the determinant in (1.3) for x = 2.

Lemma 2. Let Z_{n}(x; μ, ν) be defined by

Z_{n}(x; μ, ν) := det_{0≤i,j≤n−1} (δ_{ij} + ∑_{t=0}^{n−1} ∑_{k=0}^{n−1} \binom{i + μ}{t}\binom{k + ν}{k − t}\binom{j − k + μ − 1}{j − k}x^{k−t}) ,

let T_{n}(x; μ, ν) be defined by

T_{n}(x; μ, ν) := det_{0≤i,j≤n−1} (∑_{t=i}^{2j} \binom{i + μ}{t − i}\binom{j + ν}{2j − t}x^{2j−t}) ,

and let R_{n}(x; μ, ν) be defined by

R_{n}(x; μ, ν) := det_{0≤i,j≤n−1} ( ∑_{t=i}^{2j+1} (\binom{i + μ}{t − i − 1} + \binom{i + μ + 1}{t − i})

· (\binom{j + ν}{2j + 1 − t} + \binom{j + ν + 1}{2j + 1 − t}) x^{2j+1−t}).

Then for all positive integers n there hold

Z_{2n}(x; μ, ν) = T_{n}(x; μ, ν/2) R_{n}(x; μ, ν/2)

and

Z_{2n−1}(x; μ, ν) = 2 T_{n}(x; μ, ν/2) R_{n−1}(x; μ, ν/2).

Proof. In the case ν = 0 this is proved in [11, Theorem 5]. The proof of the above Lemma is completely analogous when one replaces the definitions of the matrices F and M in [11] by

F_{i,2j+s} = \binom{j + s + ν/2}{2j + s − i}(−x)^{2j+s−i} and M_{tk} = \binom{k + ν}{k − t}x^{k−t}.

The reader will not have any difficulties to fill in the details. □

In view of Lemma 2, Theorem 1 will be proved once we are able to evaluate the determinants T_{n}(2; μ, ν) and R_{n}(2; μ, ν). We start with the first of these two determinants.

Theorem 3. Let n be a positive integer. Then

T_{n}(2; μ, ν) = det_{0≤i,j≤n−1} (∑_{t=i}^{2j} \binom{i + μ}{t − i}\binom{j + ν}{2j − t}2^{2j−t}) = 2^{\binom{n}{2}} ∏_{i=1}^{n−1} \frac{(\frac{μ+1}{2} + ν + i)_{i}}{(2i − 1)!!} .

(2.1)

Proof. The proof consists of three steps. First, we shall show the right-hand side of (2.1) is indeed a factor of T_{n}(2; μ, ν) as a polynomial μ and ν. Let us assume for the moment that this is already done. Secondly, the degree of T_{n}(2; μ, ν) as a polynomial in μ and ν is obviously at most \binom{n}{2}. But the degree of the right-hand side of (2.1) is exactly \binom{n}{2}. Therefore it follows that

T_{n}(2; μ, ν) = C(n)2^{\binom{n}{2}} ∏_{i=1}^{n−1} \frac{(\frac{μ+1}{2} + ν + i)_{i}}{(2i − 1)!!} ,  (2.2)

with some C(n) independent of μ and ν. To compute C(n), on both sides of (2.2) compare coefficients of μ^{\binom{n}{2}}. On the right-hand side the coefficient is C(n)/ ∏_{i=1}^{n−1}(2i− 1)!!, whereas on the left-hand side the coefficient is

det_{0≤i,j≤n−1} (\frac{1}{(2j − i)!}) = ∏_{j=0}^{n−1} \frac{1}{(2j)!} det_{0≤i,j≤n−1} ((2j − i + 1)_{i})

= ∏_{i=0}^{n−1} \frac{1}{(2i)!} det_{0≤i,j≤n−1} ((2j)^{i})

= ∏_{i=0}^{n−1} \frac{1}{(2i)!} ∏_{0≤i<j≤n−1}(2j − 2i)

= ∏_{i=0}^{n−1} \frac{(2i)!!}{(2i)!}

= ∏_{i=1}^{n−1} \frac{1}{(2i − 1)!!},

where in the step from the first to the second line we used elementary column operations, and the subsequent step is just the Vandermonde determinant evaluation. Thus, (2.1) would be proved.

So, what remains is to prove that ∏_{i=1}^{n−1} ((μ + 1)/2 + ν + i)_{i} is indeed a factor of T_{n}(2; μ, ν).

Let us concentrate on a typical factor ((μ+1)/2+ν+i+l−1) = \frac{1}{2}(μ+2ν+2i+2l−1), 1 ≤ i ≤ n − 1, 1 ≤ l ≤ i, of this product. We claim that for each such factor there is a linear combination of the rows that vanishes if the factor vanishes. More precisely, we claim that for any i, l with 1 ≤ i ≤ n − 1, 1 ≤ l ≤ i there holds

∑_{s=i−l+1}^{i} 4^{s−i+l−1} \frac{(i − s + 1)_{s−i+l−1}}{(s − i + l − 1)!} · (row s of T_{n}(2; −2ν − 2i − 2l + 1, ν)) = 0,

if i + l is even, (2.3)

and

∑_{s=i−l}^{i} 4^{s−i+l} \frac{(i − s + 1)_{s−i+l}}{(s − i + l)!} \frac{(l + i − s)}{2l} · (row s of T_{n}(2; −2ν − 2i − 2l + 1, ν)) = 0,

if i + l is odd. (2.4)

Restricting to the j-th column, it is seen that this means to check

∑_{s=i−l+1}^{i} 4^{s−i+l−1} \frac{(i − s + 1)_{s−i+l−1}}{(s − i + l − 1)!} ∑_{t=s}^{2j} \binom{s − 2ν − 2i − 2l + 1}{t − s}\binom{j + ν}{2j − t}2^{2j−t} = 0,

if i + l is even,

and

∑_{s=i−l}^{i} 4^{s−i+l} \frac{(i − s + 1)_{s−i+l}}{(s − i + l)!} \frac{(l + i − s)}{2l}

· ∑_{t=s}^{2j} \binom{s − 2ν − 2i − 2l + 1}{t − s}\binom{j + ν}{2j − t}2^{2j−t} = 0, if i + l is odd. (2.5)

Written in terms of the standard hypergeometric notation

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

this is

∑_{s=i−l+1}^{i} 2^{s+2l+2j−2i−2} \frac{(i − s + 1)_{s−i+l−1}}{(s − i + l − 1)!} \frac{(s − j + ν + 1)_{2j−s}}{(2j − s)!}

·_{2}F_{1}[ \begin{matrix}−1 + 2ν + 2i + 2l − s, s − 2j \\ 1 + ν − j + s \end{matrix}; \frac{1}{2}] = 0, if i + l is even, (2.6)

and

∑_{s=i−l}^{i} 2^{s+2l+2j−2i} \frac{(i − s + 1)_{s−i+l}}{(s − i + l)!} \frac{(l + i − s)}{2l} \frac{(s − j + ν + 1)_{2j−s}}{(2j − s)!}

·_{2}F_{1}[ \begin{matrix}−1 + 2ν + 2i + 2l − s, s − 2j \\ 1 + ν − j + s \end{matrix}; \frac{1}{2}] = 0, if i + l is odd. (2.7)

In view of the algorithmic approach to binomial and hypergeometric series by Wilf and Zeilberger [14], these two identities can, in principle, be checked automatically, although there is still no efficient implementation available. Still, it is also of interest to look for a “classical” derivation by means of hypergeometric series identities, since such a derivation contains more information, in particular it could tell how to find extensions or q-analogues. We give such a “classical” derivation below. (Indeed, the question of finding q-analogues of the determinant evaluations in this paper appears to be an intriguing one. This question was already raised by Andrews in [3, Sec. 5].)

First, let us consider the case that i + l is even. We have to prove equation (2.6). We need an iteration of the contiguous relation

2F_{1}[ \begin{matrix}a, b \\ c \end{matrix}; z] = _{2}F_{1}[ \begin{matrix}a, b \\ c + 1 \end{matrix} ; z] + \frac{zab}{c (1 + c)} _{2}F_{1}[ \begin{matrix}a + 1, b + 1 \\ c + 2 \end{matrix} ; z] ,

namely,

2F_{1}[ \begin{matrix}a, b \\ c \end{matrix}; z] = ∑_{k=0}^{r} \binom{r}{k}\frac{z^{k} (a)_{k} (b)_{k}}{(c)_{k} (c + r)_{k}} _{2}F_{1}[ \begin{matrix}a + k, b + k \\ c + k + r \end{matrix}; z] .  (2.8)

If we apply (2.8) with r = i + l − s − 1 to the _{2}F_{1} in (2.6), then the left-hand side of (2.6) is turned into

∑_{s=i−l+1}^{i} 2^{s+2l+2j−2i−2} \frac{(i − s + 1)_{s−i+l−1}}{(s − i + l − 1)!} \frac{(s − j + ν + 1)_{2j−s}}{(2j − s)!}

∑_{k=0}^{i+l−s−1} \binom{i + l − s − 1}{k} (\frac{1}{2})^{k} \frac{(−1 + 2ν + 2i + 2l − s)_{k} (s − 2j)_{k}}{(1 + ν − j + s)_{k} (ν − j + i + l)_{k}}

·_{2}F_{1}[ \begin{matrix}−1 + 2ν + 2i + 2l − s + k, s − 2j + k \\ ν + i − j + k + l \end{matrix}; \frac{1}{2}] . (2.9)

Now observe that (2.9) is 0 if 2j < s because of the term (2j −s)! in the denominator. Hence, equation (2.6) is proved in this case. If on the other hand we have 2j ≥ s, then in the inner sum the summands with k > 2j − s vanish because of the term (s − 2j)_{k} in the numerator. So we need only consider summands with k ≤ 2j − s. In this case, the _{2}F_{1} series in the last line can be summed by the terminating version of Gauß’ second _{2}F_{1} summation [12, (1.7.1.9); Appendix (III.6)],

2F_{1}[ \begin{matrix}a, −n \\ \frac{1}{2} + \frac{a}{2} − \frac{n}{2} \end{matrix} ; \frac{1}{2}] = \{ \begin{matrix}0 & if n is an odd nonnegative integer, \\ (\frac{1}{2})_{n/2}_{(\frac{1}{2} − \frac{a}{2})_{n/2}} & if n is an even nonnegative integer. \end{matrix} (2.10)

Therefore, the _{2}F_{1} series in (2.9) does not vanish only if 2j − s − k is even and nonnegative. So, by using (2.10) in (2.9), by replacing k by 2k − s, and by interchanging the sums over s and k, we obtain after some simplification for the left-hand side in (2.6) the expression

∑_{k≥(i−l+1)/2} 4^{j−k} \frac{(\frac{1}{2})_{j−k} (1 + ν − j + 2k)_{2j−2k}}{(2 − ν − k − 2l)_{j−k} (2j + l − i − 1)!}

· \frac{(1 + i − 2j − l)_{2k+l−i−1} (i − 2k + l)_{2k+l−i−1} (−2 + 3l + i + 2ν)_{2k+l−i−1}}{(2k + l − i − 1)! (ν + i − j + l)_{2k+l−i−1}}

·_{3}F_{2}[ \begin{matrix}1 + i − 2k − l, 3 − i − 3l − 2ν, 1 − l \\ \frac{5}{2} − ν − k − 2l, 2 − 2l \end{matrix}; 1] . (2.11)

The _{3}F_{2} is summable by means of a terminating version of Watson’s _{3}F_{2} summation [12, (2.3.3.13); Appendix (III.23)]

3F_{2}[ \begin{matrix}−n, b, c \\ \frac{1}{2} + \frac{b}{2} − \frac{n}{2}, 2c \end{matrix}; 1]=\begin{cases}0 & if n is an odd nonnegative integer, \\ \begin{matrix}( \frac{1}{2} ) & _{n/2} & ( \frac{1}{2} − \frac{b}{2} + c) & _{n/2} \\ ( \frac{1}{2} − \frac{b}{2} ) & _{n/2} & ( \frac{1}{2} + c) & _{n/2} \end{matrix} & if n is an even nonnegative integer. \end{cases}

(2.12)

In fact, since we are in the case that i + l is even, the quantity 2k + l − i − 1 is odd. Also, it is nonnegative because we are summing over k ≥ (i − l + 1)/2. Therefore, by (2.12), the _{3}F_{2} in (2.11) vanishes for all k. Hence, the expression (2.11) equals 0. This establishes (2.6).

The case that i + l is odd can be treated in the same way. We leave it to the reader to modify the above proof of (2.6) appropriately in order to turn it into a proof of (2.7). □

Next we prove the promised evaluation for R_{n}(2; μ, ν).

Theorem 4. Let n be a positive integer. Then

R_{n}(2; μ, ν) = det_{0≤i,j≤n−1} ( ∑_{t=i}^{2j+1} (\binom{i + μ}{t − i − 1} + \binom{i + μ + 1}{t − i})

· (\binom{j + ν}{2j + 1 − t} + \binom{j + ν + 1}{2j + 1 − t}) 2^{2j+1−t})

= 2^{n+\binom{n+1}{2}} ∏_{i=1}^{n} \frac{(\frac{μ+1}{2} + ν + i)_{i}}{(2i − 1)!!} . (2.13)

Proof. We proceed in the same way as in the proof of Theorem 3. Therefore we can be briefer here. In particular, we leave it to the reader to check the degrees as polynomials in μ and ν of the right-hand and left-hand side of (2.13) and to compare coefficients of μ^{\binom{n}{2}}. What is more complicated here is to verify that the right-hand side of (2.13) is indeed a factor of R_{n}(2; μ, ν).

We have to prove that ∏_{i=1}^{n} ((μ + 1)/2 + ν + i)_{i} is indeed a factor of R_{n}(2; μ, ν). Again, let us concentrate on a typical factor ((μ + 1)/2 + ν + i + l − 1) = \frac{1}{2}(μ +

2ν + 2i + 2l − 1), 1 ≤ i ≤ n, 1 ≤ l ≤ i, of this product. We claim that for each such factor there is a linear combination of the rows that vanishes if the factor vanishes. More precisely, we claim that for any i, l with 1 ≤ i ≤ n, 1 ≤ l ≤ i there holds

∑_{s=i−l}^{i−1} 4^{s−i+l} \frac{(i − s)_{s−i+l}}{(s − i + l)!} · (row s of R_{n}(2; −2ν − 2i − 2l + 1, ν)) = 0,

if i + l is even, (2.14)

and

∑_{s=i−l−1}^{i−1} 4^{s−i+l+1} \frac{(i − s)_{s−i+l+1}}{(s − i + l + 1)!} \frac{(l + i − s − 1)}{2l}

· (row s of R_{n}(2; −2ν − 2i − 2l + 1, ν)) = 0, if i + l is odd. (2.15)

Also here, let us first consider the case that i + l is even. We have to prove (2.14). When restricted to the j-th column, this means to prove

∑_{s=i−l}^{i−1} 4^{s−i+l} \frac{(i − s)_{s−i+l}}{(s − i + l)!} ∑_{t=s+1}^{2j+1} \binom{s − 2ν − 2i − 2l + 1}{t − s − 1}\binom{j + ν}{2j + 1 − t}2^{2j+1−t}

+ ∑_{s=i−l}^{i−1} 4^{s−i+l} \frac{(i − s)_{s−i+l}}{(s − i + l)!} ∑_{t=s+1}^{2j+1} \binom{s − 2ν − 2i − 2l + 1}{t − s − 1}\binom{j + ν + 1}{2j + 1 − t}2^{2j+1−t}

+ ∑_{s=i−l}^{i−1} 4^{s−i+l} \frac{(i − s)_{s−i+l}}{(s − i + l)!} ∑_{t=s}^{2j+1} \binom{s − 2ν − 2i − 2l + 2}{t − s}\binom{j + ν}{2j + 1 − t}2^{2j+1−t}

+ ∑_{s=i−l}^{i−1} 4^{s−i+l} \frac{(i − s)_{s−i+l}}{(s − i + l)!} ∑_{t=s}^{2j+1} \binom{s − 2ν − 2i − 2l + 2}{t − s}\binom{j + ν + 1}{2j + 1 − t}2^{2j+1−t} = 0,

if i + l is even. (2.16)

Now, each of the four double sums in (2.16) is very similar to the one in (2.5). Therefore they allow the same “treatment” as we used for (2.5) in the proof of Theorem 3. I.e., in each of the four sums we write the inner sum as a _{2}F_{1}, apply the contiguous relation (2.8) with r = i + l − s − 1 to the first and third _{2}F_{1}, respectively with r = i + l − s − 2 to the second and fourth, sum the resulting _{2}F_{1} series by means of (2.10), then, depending on whether s − 2j + k has to be even or odd in order that the corresponding terms do not vanish, replace k by 2k−s respectively by 2k−s+1, interchange sums over s and k, and finally write the inner sums over s as hypergeometric series. What is obtained after simplification is the following:

∑_{k≥(i−l)/2} 4^{j−k} \frac{(\frac{1}{2})_{j−k} (1 + ν − j + 2k)_{2j−2k}}{(1 − ν − k − 2l)_{j−k} (2j + l − i)!}

· \frac{(i − 2j − l)_{2k+l−i} (i − 2k + l)_{2k+l−i} (i + 3l + 2ν − 1)_{2k+l−i}}{(2k + l − i)! (ν + i − j + l)_{2k+l−i}}

·_{3}F_{2}[ \begin{matrix}i − 2k − l, 2 − i − 3l − 2ν, 1 − l \\ \frac{3}{2} − ν − k − 2l, 1 − 2l \end{matrix}; 1]

+ ∑_{k≥(i−l)/2} 4^{j−k} \frac{(\frac{1}{2})_{j−k} (2 + ν − j + 2k)_{2j−2k}}{(1 − ν − k − 2l)_{j−k} (2j + l − i)!}

· \frac{(i − 2j − l)_{2k+l−i} (i − 2k + l − 1)_{2k+l−i} (i + 3l + 2ν − 1)_{2k+l−i}}{(2k + l − i)! (ν + i − j + l)_{2k+l−i}}

·_{3}F_{2}[ \begin{matrix}i − 2k − l, 2 − i − 3l − 2ν, 1 − l \\ \frac{3}{2} − ν − k − 2l, 2 − 2l \end{matrix}; 1]

+ ∑_{k≥(i−l)/2} 4^{j−k} \frac{(\frac{1}{2})_{j−k} (1 + ν − j + 2k)_{2j−2k}}{(1 − ν − k − 2l)_{j−k} (2j + l − i + 1)!}

· \frac{(i − 2j − l − 1)_{2k+l−i+1} (i − 2k + l − 1)_{2k+l−i+1} (i + 3l + 2ν − 2)_{2k+l−i+1}}{(2k + l − i + 1)! (ν + i − j + l − 1)_{2k+l−i+1}}

·_{3}F_{2}[ \begin{matrix}i − 2k − l − 1, 3 − i − 3l − 2ν, 1 − l \\ \frac{3}{2} − ν − k − 2l, 1 − 2l \end{matrix}; 1]

+ ∑_{k≥(i−l)/2} 4^{j−k} \frac{(\frac{1}{2})_{j−k} (2 + ν − j + 2k)_{2j−2k}}{(1 − ν − k − 2l)_{j−k} (2j + l − i + 1)!}

· \frac{(i − 2j − l − 1)_{2k+l−i+1} (i − 2k + l − 2)_{2k+l−i+1} (i + 3l + 2ν − 2)_{2k+l−i+1}}{(2k + l − i + 1)! (ν + i − j + l − 1)_{2k+l−i+1}}

·_{3}F_{2}[ \begin{matrix}i − 2k − l − 1, 3 − i − 3l − 2ν, 1 − l \\ \frac{3}{2} − ν − k − 2l, 2 − 2l \end{matrix}; 1] . (2.17)

In the previous proof we were finished at this point (to be precise, when arriving at (2.11)) because all the _{3}F_{2} series in (2.11) could be summed by means of Watson’s 3F_{2} summation (2.12) and turned out to equal 0 throughout. The expression in (2.17) however requires more work. It is only the fourth _{3}F_{2} in (2.17) which turns out to vanish when using (2.12). The second _{3}F_{2} can also be summed by means of (2.12), giving a nonzero result however. The first and third _{3}F_{2} cannot directly be summed by (2.12). We have to first apply the contiguous relation

rF_{s}[ \begin{matrix}a_{1}, a_{2}, A \\ b_{1}, B \end{matrix}; z] = _{r}F_{s}[ \begin{matrix}a_{1}, a_{2}, A − 1 \\ b_{1}, B − 1 \end{matrix} ; z]

+ \frac{a_{1} a_{2} (B − A) z}{b_{1} (B − 1) B}_{r}F_{s}[ \begin{matrix}a_{1} + 1, a_{2} + 1, A \\ b_{1} + 1, B + 1 \end{matrix} ; z] , (2.18)

to obtain

3F_{2}[ \begin{matrix}i − 2k − l, 2 − i − 3l − 2ν, 1 − l \\ \frac{3}{2} − ν − k − 2l, 1 − 2l \end{matrix}; 1] = _{3}F_{2}[ \begin{matrix}i − 2k − l, 2 − i − 3l − 2ν, −l \\ \frac{3}{2} − ν − k − 2l, −2l \end{matrix}; 1]

+ \begin{matrix}(i − 2k − l) & (2 − i − 3l − 2ν) \\ (1 − 2l) & (3 − 2k − 4l − 2ν) \end{matrix}_{3}F_{2}[ \begin{matrix}1 + i − 2k − l, 3 − i − 3l − 2ν, 1 − l \\ \frac{5}{2} − ν − k − 2l, 2 − 2l \end{matrix}; 1]

(2.19)

for the first _{3}F_{2}, and

3F_{2}[ \begin{matrix}−1 + i − 2k − l, 3 − i − 3l − 2ν, 1 − l \\ \frac{3}{2} − ν − k − 2l, 1 − 2l \end{matrix}; 1]

= _{3}F_{2}[ \begin{matrix}−1 + i − 2k − l, 3 − i − 3l − 2ν, −l \\ \frac{3}{2} − ν − k − 2l, −2l \end{matrix}; 1]

+ \begin{matrix}(2k + l − i + 1) & (−3 + i + 3l + 2ν) \\ (−1 + 2l) & (−3 + 2k + 4l + 2ν) \end{matrix}_{3}F_{2}[ \begin{matrix}i − 2k − l, 4 − i − 3l − 2ν, 1 − l \\ \frac{5}{2} − ν − k − 2l, 2 − 2l \end{matrix}; 1]

(2.20)

for the third. All the _{3}F_{2} series on the right-hand sides of (2.19) and (2.20) can be summed by means of (2.12). In either case, one of the two series vanishes, the other does not. If we perform all these _{3}F_{2} summations, and then write the resulting three sums over k in hypergeometric notation, the expression in (2.17) is transformed into

\frac{2^{2j+l−i}(\frac{1}{2})_{j+ \frac{l}{2} − \frac{i}{2}} (1 + i − j − l + ν)_{2j+l−i}}{(2j + l − i)! (1 − \frac{i}{2} − \frac{3l}{2} − ν)_{j+ \frac{l}{2}} − \frac{i}{2}}

×_{3}F_{2}[ \begin{matrix}\frac{i}{2} − j − \frac{l}{2}, −\frac{1}{2} + \frac{i}{2} + \frac{l}{2} + ν, 1 − l \\ \frac{1}{2} + \frac{i}{2} − \frac{j}{2} − \frac{l}{2} + \frac{ν}{2} , 1 + \frac{i}{2} − \frac{j}{2} − \frac{l}{2} + \frac{ν}{2} \end{matrix} ; 1]

+ \frac{2^{2j+l−i}(\frac{1}{2})_{j+ \frac{l}{2} − \frac{i}{2}} (2 + i − j − l + ν)_{2j+l−i}}{(2j + l − i)! (1 − \frac{i}{2} − \frac{3l}{2} − ν)_{j+ \frac{l}{2} − \frac{i}{2}}}

×_{3}F_{2}[ \begin{matrix}\frac{i}{2} − j − \frac{l}{2}, \frac{1}{2} + \frac{i}{2} + \frac{l}{2} + ν, 1 − l \\ 1 + \frac{i}{2} − \frac{j}{2} − \frac{l}{2} + \frac{ν}{2} , \frac{3}{2} + \frac{i}{2} − \frac{j}{2} − \frac{l}{2} + \frac{ν}{2} \end{matrix} ; 1]

− \frac{22^{2j+l−i}(\frac{1}{2})_{j+ \frac{l}{2} − \frac{i}{2}} (1 + i − j − l + ν)_{2j+l−i}}{(2j + l − i)! (2 − \frac{i}{2} − \frac{3l}{2} − ν)_{j+ \frac{l}{2} − \frac{i}{2}}}

×_{3}F_{2}[ \begin{matrix}\frac{i}{2} − j − \frac{l}{2}, −\frac{1}{2} + \frac{i}{2} + \frac{l}{2} + ν, 1 − l \\ \frac{1}{2} + \frac{i}{2} − \frac{j}{2} − \frac{l}{2} + \frac{ν}{2} , 1 + \frac{i}{2} − \frac{j}{2} − \frac{l}{2} + \frac{ν}{2} \end{matrix} ; 1] . (2.21)

All the _{3}F_{2} series in this expression can be summed by means of the Pfaff–Saalschütz summation [12, (2.3.1.3); Appendix (III.2)]

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

where n is a nonnegative integer. It is routine, although little tedious, to verify that thus the expression in (2.21) simplifies to 0.

The case that i + l is odd can be treated in the same way. We leave it to the reader fill in the details.

This shows that ∏_{i=1}^{n} ((μ + 1)/1 + ν + i)_{i} is indeed a factor of R_{n}(2; μ, ν). Thus the proof of the Theorem is complete. □

Now we can quickly prove Theorem 1.

Proof of Theorem 1. We combine Lemma 2 with x = 2 with Theorems 3 and 4. □

3. Plane partition enumeration. Here we describe briefly the combinatorial meaning of the determinants Z_{n}(x; μ, ν) and T_{n}(x; μ, ν). In order to do so, we recall some plane partition terminology. By a plane partition we mean an array π of positive integers of the form

π_{1,1} . . . . . . . . . . . . . . . . . . . . . π_{1,λ_{1}}
π_{2,1} . . . . . . . . . . . . . . π_{2,λ_{2}}
⋮  ...
π_{r,1} … π_{r,λ_{r}}

where the entries along rows and columns are weakly decreasing, and where λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r}.

Similarly, by a shifted plane partition we mean an array π of positive integers of the form

π_{11} π_{12} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . π_{1,λ_{1}}
π_{22} . . . . . . . . . . . . . . . . . . . . . . . . . . π_{2,λ_{2}}
...  ...
π_{rr} … π_{r,λ_{r}}

with the same properties as above.

Theorem 5. Let Z_{n}(μ, ν) be the set of shifted plane partitions with strict decrease along columns with no row length exceeding n and such that the first entry π_{ii} of each row exceeds the length λ_{i} − i + 1 of that row by precisely 2μ + ν. Furthermore, call an entry π_{i,j} of such a shifted plane partition special if μ < π_{i,j} ≤ μ + ν − i + j, and denote the number of all special entries of such a shifted plane partition π by s(π). Then the generating function ∑_{π} x^{s(π)} for all shifted plane partitions π in Z_{n}(μ, ν) equals Z_{n}(x; μ, ν).

Sketch of Proof. In the same way as in section 3 of [11] it can be seen that the shifted plane partitions under consideration are in bijection with families (P_{1}, P_{2}, …, P_{r}) of nonintersecting lattice paths (cf. [4, 5, 13] for information about nonintersecting lattice paths), P_{i} running from (0, λ_{i} − i + 2μ + ν) to (λ_{i} − i, 0), n ≥ λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{r}, r ≤ n. Under this correspondence special entries correspond to horizontal steps of lattice paths that are located in the region {(x, y) : μ ≤ y ≤ x + μ + ν}. By using this observation, and by invoking the main theorem of nonintersecting lattice paths [5, Cor. 2; 13, Theorem 1.2], the generating function in question can be written as a sum of determinants. Without much effort this sum of determinants can be transformed into a single determinant, which happens to be exactly Z_{n}(x; μ, ν). □

Remark. The special case ν = 0 of this Theorem was given by Mills, Robbins and Rumsey [11, sec. 4]. The reader is reminded at this point that for μ = ν = 0 the above set of shifted plane partitions is in bijection with cyclically symmetric plane partitions contained in an n × n × n box. On the other hand, for μ = 1, ν = 0 the above set of shifted plane partitions is in bijection with the set of descending plane partitions with entries bounded above by n + 1. The reader is referred to [9, 10, 11] for information on these issues.

Theorem 6. Let T_{n}(μ, ν) be the set of plane partitions of the triangular form

π_{1,1} . . . . . . . . . . . π_{1,n−1}
π_{2,1} … π_{2,n−2}
⋮  ...
π_{n−1,1}

with entries being at least 1 + ν, and with the first entry π_{i,1} in row i being at most n − i + 1 + μ. Furthermore, call an entry π_{i,j} of such a plane partition special if π_{i,j} ≤ j, and denote the number of all special entries of such a plane partition π by s(π). Then the generating function ∑_{π} x^{s(π)} for all plane partitions π in T_{n}(μ, ν) equals T_{n}(x; μ, ν).

Sketch of Proof. In the same way as in section 3 of [11] it can be seen that the plane partitions under consideration are in bijection with families (P_{1}, P_{2}, …, P_{r}) of nonintersecting lattice paths (cf. [4, 5, 13] for information about nonintersecting lattice paths), P_{i} running from (i, 2i + μ) to (2i, i + ν). Under this correspondence special entries correspond to horizontal steps of lattice paths that are located (weakly) below the main diagonal x = y. Again, by invoking the main theorem of nonintersecting lattice paths [5, Cor. 2; 13, Theorem 1.2], it is not difficult to see that the generating function in question is exactly T_{n}(x; μ, ν). □

Remark. The special case ν = 0 of this Theorem was given by Mills, Robbins and Rumsey [11, sec. 4]. In this context, we remind the reader that for μ = ν = 0 the above set of plane partitions is in bijection with transpose-complementary symmetric plane partitions contained in a (2n) × (2n) × (2n) box, see [11, sec. 2].

References

1. G. E. Andrews, Plane partitions (III): The weak Macdonald conjecture, Inventiones Math. 53 (1979), 193–225.

2. G. E. Andrews, Macdonald’s conjecture and descending plane partitions, Combinatorics, representation theory and statistical methods in groups, Young Day Proceedings (T. V. Narayana, R. M. Mathsen, J. G. Williams, eds.), Lecture Notes in Pure Math., vol. 57, Marcel Dekker, New York, Basel, 1980, pp. 91–106.

3. G. E. Andrews, Plane partitions (IV): A conjecture of Mills–Robbins–Rumsey, Aequationes Math. 33 (1987), 230–250.

4. I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300—321.

5. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint.

6. C. Krattenthaler, Determinant identities and a generalization of the number of totally symmetric self-complementary plane partitions, Elect. J. Combin. (to appear).

7. C. Krattenthaler, Some q-analogues of determinant identities which arose in plane partition enumeration, Seminaire Loth. Combin. (to appear).

8. C. Krattenthaler, An alternative evaluation of the Andrews–Burge determinant, preprint.

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

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

11. W. H. Mills, D. H. Robbins and H. Rumsey, Enumeration of a symmetry class of plane partitions, Discrete Math. 67 (1987), 43–55.

12. L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

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

14. H. S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math. 108 (1992), 575–633.

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