Some q-analogues of determinant identities

which arose in plane partition enumeration

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 prove q-analogues of two determinant identities of a previous paper of the author. These determinant identities are related to the enumeration of totally symmetric self-complementary plane partitions.

1. Introduction. Enumeration of plane partitions almost always leads to the problem of evaluating some determinant, see [1, 2, 3, 4, 5, 6, 7, 9, 11, 12, 16, 17, 18, 19, 21, 22, 23, 24]. In a recent paper [13], we evaluated three determinants in order to prove a conjecture of Robbins and Zeilberger [26, Conjecture C’=B’] which generalizes the enumeration of totally symmetric self-complementary plane partitions. Two of these three determinant evaluations [13, Theorems 8 and 10] read as follows, using the usual notation (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, (a)_{0} := 1, for shifted factorials:

For any nonnegative integer n there hold

det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)!}{(x + 2i − j)! (y + 2j − i)!})

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

33D20..

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

Key words and phrases. determinant evaluations, totally symmetric self-complementary plane partitions, basic hypergeometric series.

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

and

det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)! (y − x + 3j − 3i)}{(x + 2i − j + 1)! (y + 2j − i + 1)!})

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

· ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(x)_{k} (y)_{n−k}.  (1.2)

The purpose of this paper is to provide q-analogues for these two determinant evaluations. In the statements of our q-analogues we use the standard “q-notations” (a; q)_{∞} := ∏_{i=0}^{∞}(1 − aq^{i}) and (a; q)_{β} := (a; q)_{∞}/(aq^{β}; q)_{∞} for shifted q-factorials, so that in particular for any nonnegative integer we have (a; q)_{n} = (1−a)(1−aq) ⋯ (1− aq^{n−1}), and

[ \begin{matrix}n \\ k \end{matrix} ]_{q} := \frac{(1 − q^{n})(1 − q^{n−1}) ⋯ (1 − q^{n−k+1})}{(1 − q^{k})(1 − q^{k−1}) ⋯ (1 − q)}

for the q-binomials.

Our q-analogue of (1.1) reads as follows.

Theorem 1. For any nonnegative integer there holds

det_{0≤i,j≤n−1} (\frac{(q; q)_{x+y+i+j−1}}{(q; q)_{x+2i−j} (q; q)_{y+2j−i}} \frac{q^{−2ij}}{(−q^{x+y+1}; q)_{i+j}} )

= ∏_{i=0}^{n−1} q^{−2i^{2}} \frac{(q^{2}; q^{2})_{i} (q; q)_{x+y+i−1} (q^{2x+y+2i}; q)_{i} (q^{x+2y+2i}; q)_{i}}{(q; q)_{x+2i} (q; q)_{y+2i} (−q^{x+y+1}; q)_{n−1+i}} . (1.3)

Our q-analogue of (1.2) is the following.

Theorem 2. For any nonnegative integer n there holds

det_{0≤i,j≤n−1} (\frac{(q; q)_{x+y+i+j−1} (1 − q^{y+2j−i} − q^{y+2j−i+1} + q^{x+y+i+j+1})}{(q; q)_{x+2i−j+1} (q; q)_{y+2j−i+1}}

· \frac{q^{−2ij}}{(−q^{x+y+2}; q)_{i+j}} )

= ∏_{i=0}^{n−1} (q^{−2i^{2}} \frac{(q^{2}; q^{2})_{i} (q; q)_{x+y+i−1} (q^{2x+y+2i+1}; q)_{i} (q^{x+2y+2i+1}; q)_{i}}{(q; q)_{x+2i+1} (q; q)_{y+2i+1} (−q^{x+y+2}; q)_{n−1+i}} )

× ∑_{k=0}^{n}(−1)^{k}q^{nk}\left[{n \atop k}\right]_{q}q^{yk} (q^{x}; q)_{k} (q^{y}; q)_{n−k}. (1.4)

We prove the (easier) Theorem 1 in section 2, and subsequently Theorem 2 in section 3. The method that we use is also applied successfully in [13, 14, 15].

The reader should observe that the q-analogues (1.3) and (1.4) when specialized to q = 1 slightly differ from the identities (1.1) respectively (1.2) which they generalize in that they contain powers of 2 on both sides, which however cancel as is easily seen. This fact makes it unclear what the combinatorial significance of (1.3) or (1.4) could be, while there is definitely a combinatorial meaning for (1.1) and (1.2), at least in special cases, see [13, Theorem 1; 6, sec. 5].

Identity (1.3) is a generalization of a determinant evaluation of Andrews and Stanton [7, Cor. 3] to which it reduces on setting y = 1. The paper [7] contains another generalization [7, Theorem 8] which is different from ours.

As mentioned at the very beginning, there is a third determinant evaluation in [13, Theorem 2; cf. Corollary 3]. However, I was not able to find a q-analogue for this determinant evaluation. Finding such a q-analogue could be a challenging problem.

2. Proof of Theorem 1. First we rewrite the statement (1.3). We take as many common factors out of the rows and columns of the determinant in (1.3) as possible, such that the entries become polynomials in q^{x} and q^{y}. To be precise, we take

∏_{i=0}^{n−1} \frac{(q; q)_{x+y+i−1}}{(q; q)_{x+2i} (q; q)_{y+2n−2} (−q^{x+y+1}; q)_{n−1+i}}

out of the i-the row, i = 0, 1, …, n − 1, and we take (q^{y+2j+1}; q)_{2n−2j−2}, j = 0, 1, …, n − 1, out of the j-th row. Thus the determinant in (1.3) becomes

∏_{i=0}^{n−1} \frac{(q; q)_{x+y+i−1}}{(q; q)_{x+2i} (q; q)_{y+2i} (−q^{x+y+1}; q)_{n−1+i}}

× det_{0≤i,j≤n−1} (q^{−2ij} (q^{x+y+i}; q)_{j} (q^{x+2i−j+1}; q)_{j}

· (q^{y+2j−i+1}; q)_{i} (−q^{x+y+i+j+1}; q)_{n−j−1}).

By comparing with (1.3) we see that we have to prove

det_{0≤i,j≤n−1} (q^{−2ij} (q^{x+y+i}; q)_{j} (q^{x+2i−j+1}; q)_{j}

· (q^{y+2j−i+1}; q)_{i} (−q^{x+y+i+j+1}; q)_{n−j−1})

= ∏_{i=0}^{n−1} (q^{−2i^{2}} (q^{2}; q^{2})_{i} (q^{2x+y+2i}; q)_{i} (q^{x+2y+2i}; q)_{i}),

or, if we replace q^{x} by x and q^{y} by y, equivalently

det_{0≤i,j≤n−1} (q^{−2ij} (xyq^{i}; q)_{j} (xq^{2i−j+1}; q)_{j} (yq^{2j−i+1}; q)_{i} (−xyq^{i+j+1}; q)_{n−j−1})

= ∏_{i=0}^{n−1} (q^{−2i^{2}} (q^{2}; q^{2})_{i} (x^{2}yq^{2i}; q)_{i} (xy^{2}q^{2i}; q)_{i}). (2.1)

For convenience, let us denote the determinant on the left-hand side of (2.1) by D_{1}(x, y; n).

Our proof of (2.1) is divided into four steps. In steps 1 and 2 we show that the right-hand side of (2.1) divides D_{1}(x, y; n) as a polynomial in x and y. Then, in Step 3 we show that the (total) degree in x and y of D_{1}(x, y; n) is 6\binom{n}{2}, which is exactly the degree of the right-hand side, so that D_{1}(x, y; n) is a constant multiple of the right-hand side. Finally we show in step 4 that this constant equals 1.

Step 1. ∏_{i=0}^{n−1}(x^{2}yq^{2i}; q)_{i} is a factor of D_{1}(x, y; n). Let us first concentrate on a typical factor (1−x^{2}yq^{2i+l}), 0 ≤ i ≤ n−1, 0 ≤ l < i, of the product ∏_{i=1}^{n−1}(x^{2}yq^{2i}; q)_{i}. 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 0 ≤ i ≤ n − 1, 0 ≤ l < i there holds

∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+3)}{2} −(i−l)(2i+2l+1)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+1}; q)_{2i−2s}}{(q^{−2i−l+s}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}} · (row s of D_{1}(x, q^{−2i−l}/x^{2}; n))

= (row i of D_{1}(x, q^{−2i−l}/x^{2}; n)). (2.2)

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

∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+3)}{2} −(i−l)(2i+2l+1)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+1}; q)_{2i−2s}}{(q^{−2i−l+s}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}} · q^{−2sj} (q^{−2i−l+s}/x; q)_{j} (xq^{2s−j+1}; q)_{j}

· (q^{−2i−l+2j−s+1}/x^{2}; q)_{s} (−q^{1−2i+j−l+s}/x; q)_{n−j−1}
= q^{−2ij} (q^{−i−l}/x; q)_{j} (xq^{2i−j+1}; q)_{j}

× (q^{−3i−l+2j+1}/x^{2}; q)_{i} (−q^{1−i+j−l}/x; q)_{n−j−1}. (2.3)

Of course, this identity can be proven routinely by means of the q-version of Zeilberger’s algorithm (see the description in [10]; see also [25]). However, it is certainly more interesting to find which basic hypergeometric identity is “behind” (2.3). Mizan Rahman has kindly informed me that it is in fact a special case of a transformation formula of his [20, (3.12); 8, (3.8.13)]. Namely, the left-hand side of (2.3) can be rewritten in the form

q^{−2jl} (q^{1−2i+2j−2l}/x^{2}; q)_{l} (−q^{1−2i+j}/x; q)_{−1+i−j−l+n}

× (q^{−i−l}/x; q)_{−i+j+l}(q^{1−j+2l}x; q)_{2i+j−2l}

× ∑_{k=0}^{⌊(i−l)/2⌋} \frac{(1 − q^{3k−2i+2l})}{(1 − q^{−2i+2l})} \frac{(−q^{−i+l}; q)_{k} (q^{2i−2j+2l}x^{2}; q)_{k} (q^{−2i+j}/x; q)_{k}}{(q; q)_{k} (q^{1−i+l}; q)_{k} (−q^{1−2i+j}/x; q)_{k}}

· \frac{(q^{−i+l}; q^{2})_{k} (q^{1−i+l}; q^{2})_{k}}{(q^{1−j+2l}x; q^{2})_{k} (q^{2−j+2l}x; q^{2})_{k}} q^{k},

and so can be summed by using Lemma A1 with n = i − l, b = q^{2i−2j+2l}x^{2}, and c = q^{−2i+j}/x. Lemma A1 indeed follows from the aforementioned transformation formula of Rahman, as is shown in the Appendix.

This establishes the claim that the determinant D_{1}(x, y; n) vanishes if a factor (1 − x^{2}yq^{2i+l}), 0 ≤ i ≤ n − 1, 0 ≤ l < i, vanishes. Since for equal factors the corresponding linear combinations of the rows are linearly independent, the complete product ∏_{i=0}^{n−1}(x^{2}yq^{2i}; q)_{i} must divide the determinant D_{1}(x, y; n).

Step 2. ∏_{i=0}^{n−1}(xy^{2}q^{2i}; q)_{i} is a factor of D_{1}(x, y; n). The reasoning that ∏_{i=0}^{n−1}(xy^{2}q^{2i})_{i} is a factor of D_{1}(x, y; n) is similar. Also here, let us concentrate on a typical factor (1 − xy^{2}q^{2j+l}), 0 ≤ j ≤ n − 1, 0 ≤ l < j. This time we claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 0 ≤ j ≤ n − 1, 0 ≤ l < j there holds

∑_{s=l}^{⌊(j+l)/2⌋} q^{\frac{(s−l)(5s+3l+3)}{2} −(j−l)(2j+2l+1)}y^{2(s−j)} \frac{(1 − q^{2j−3s+l})}{(1 − q^{j−s})} \frac{(q^{j−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(yq^{2s+1}; q)_{2j−2s}}{(−q; q)_{j−s}} · (column s of D_{1}(q^{−2j−l}/y^{2}, y; n))

= (column j of D_{1}(q^{−2j−l}/y^{2}, y; n)).

Restricting to the i-th row, we see that this means to check

∑_{s=l}^{⌊(j+l)/2⌋} q^{\frac{(s−l)(5s+3l+3)}{2} −(j−l)(2j+2l+1)}y^{2(s−j)} \frac{(1 − q^{2j−3s+l})}{(1 − q^{j−s})} \frac{(q^{j−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(yq^{2s+1}; q)_{2j−2s}}{(−q; q)_{j−s}} · q^{−2is} (q^{−2j−l+i}/y; q)_{s} (q^{−2j−l+2i−s+1}/y^{2}; q)_{s}

· (yq^{2s−i+1}; q)_{i}(−q^{1+i−2j−l+s}/y; q)_{n−s−1}
= q^{−2ij} (q^{−2j−l+i}/y; q)_{j} (q^{−3j−l+2i+1}/y^{2}; q)_{j}

· (yq^{2j−i+1}; q)_{i} (−q^{1+i−j−l}/y; q)_{n−j−1}.

The observation that this summation is equivalent to (2.3) with x replaced by y and with i and j interchanged establishes the claim. Similarly to as before, this shows that the complete product ∏_{i=0}^{n−1}(xy^{2}q^{2i}; q)_{i} divides D_{1}(x, y; n).

Altogether, this implies that ∏_{i=0}^{n−1} ((x^{2}yq^{2i}; q)_{i} (xy^{2}q^{2i}; q)_{i}), and hence the righthand side of (2.1), divides D_{1}(x, y; n), as desired.

Step 3. D_{1}(x, y; n) is a polynomial in x and y of degree 6\binom{n}{2}. This is because each term in the defining expansion of the determinant D_{1}(x, y; n) (the determinant on the left-hand side of (2.1)) has degree 6\binom{n}{2} as a polynomial in x and y. Since the right-hand side of (2.1), which by steps 1 and 2 divides D_{1}(x, y; n) as a polynomial in x and y, also has degree 6\binom{n}{2}, D_{1}(x, y; n) and the right-hand side of (2.1) differ only by a multiplicative constant.

Step 4. The evaluation of the multiplicative constant. To show that the multiplicative constant, which according to step 3 is between D_{1}(x, y; n) (the left-hand side of (2.1)) and the right-hand side of (2.1), is indeed 1, we compare the constant coefficient on both sides of (2.1).

The constant term of D_{1}(x, y; n) equals det_{0≤i,j,≤n−1}(q^{−2ij}). This is a Vandermonde determinant and hence equals

∏_{1≤i<j≤n}(q^{−2j} − q^{−2i}) = q^{∑_{j=1}^{n}(−2j^{2})} ∏_{1≤i<j≤n}(1 − q^{2j−2i}) = q^{∑_{j=1}^{n}(−2j^{2})} ∏_{i=0}^{n−1}(q^{2}; q^{2})_{i}.

This is exactly the constant term of the right-hand side of (2.1). So indeed, the left-hand and right-hand side of (2.1) are equal, which completes the proof of the Theorem. □

3. Proof of Theorem 2. Proving Theorem 2 is more difficult. The reader may take the fact that the determinant in (1.4) does not factor completely into “cyclotomic” factors (unlike the determinant in (1.3)) as an indication why this is the case.

We begin by manipulating the determinant on the left-hand side of (1.4), quite analogously as at the beginning of the proof of (1.3). Namely, we take

∏_{i=0}^{n−1} \frac{(q; q)_{x+y+i−1}}{(q; q)_{x+2i+1} (q; q)_{y+2n−1} (−q^{x+y+2}; q)_{n−1+i}}

out of the i-th row, i = 0, 1, …, n−1, and we take (q^{y+2j+2}; q)_{2n−2j−2} out of the j-th column, j = 0, 1, …, n − 1. Thus the determinant in (1.4) becomes

∏_{i=0}^{n−1} \frac{(q; q)_{x+y+i−1}}{(q; q)_{x+2i+1} (q; q)_{y+2i+1} (−q^{x+y+2}; q)_{n−1+i}}

× det_{0≤i,j≤n−1} (q^{−2ij} (q^{x+y+i}; q)_{j} (q^{x+2i−j+2}; q)_{j} (q^{y+2j−i+2}; q)_{i} (−q^{x+y+i+j+2}; q)_{n−j−1}

· (1 − q^{y+2j−i} − q^{y+2j−i+1} + q^{x+y+i+j+1})).

By comparing with (1.4), and replacing q^{x} by x and q^{y} by y, we see that Theorem 2 is equivalent to the statement:

det_{0≤i,j≤n−1} (q^{−2ij} (xyq^{i}; q)_{j} (xq^{2i−j+2}; q)_{j} (yq^{2j−i+2}; q)_{i} (−xyq^{i+j+2}; q)_{n−j−1}

· (1 − yq^{2j−i} − yq^{2j−i+1} + xyq^{i+j+1}))

= ∏_{i=0}^{n−1} (q^{−2i^{2}} (q^{2}; q^{2})_{i} (x^{2}yq^{2i+1}; q)_{i} (xy^{2}q^{2i+1}; q)_{i})

× ∑_{k=0}^{n}(−1)^{k}q^{nk}\left[{n \atop k}\right]_{q}y^{k} (x; q)_{k} (y; q)_{n−k}. (3.1)

For convenience, let us denote the determinant in (3.1) by D_{2}(x, y; n).

In order to be able to finally prove (3.1), we have to go through a sequence of three Lemmas. As a first approximation, we identify most of the factors of D_{2}(x, y; n).

Lemma 1. For any nonnegative integer n there holds

D_{2}(x, y; n) = det_{0≤i,j≤n−1} (q^{−2ij} (xyq^{i}; q)_{j} (xq^{2i−j+2}; q)_{j} (yq^{2j−i+2}; q)_{i}

· (−xyq^{i+j+2}; q)_{n−j−1} (1 − yq^{2j−i} − yq^{2j−i+1} + xyq^{i+j+1}))

= ∏_{i=0}^{n−1} ((x^{2}yq^{2i+1}; q)_{i} (xy^{2}q^{2i+1}; q)_{i}) · P (x, y; n), (3.2)

where P (x, y; n) is a polynomial in x and y, of degree n in x, and also of degree n in y.

Proof. What we have to prove is that

∏_{i=0}^{n−1} ((x^{2}yq^{2i+1}; q)_{i} (xy^{2}q^{2i+1}; q)_{i})  (3.3)

divides D_{2}(x, y; n) as a polynomial in x and y. Once this is done, it follows immediately that the remaining factor P (x, y; n) then must have degree n in x and also in y. For, in the expansion of the determinant D_{2}(x, y; n) each term has degree 3\binom{n}{2} + n in x, and the same holds for the degree in y. On the other hand, the degree in x of the product (3.3) is 3\binom{n}{2}, the same being true for the degree in y. Therefore P (x, y; n) must be a polynomial with degree n in x and degree n in y.

In order to show that indeed the product (3.3) divides D_{2}(x, y; n), we first consider just one half of this product, ∏_{i=0}^{n−1}(x^{2}yq^{2i+1}; q)_{i}. Let us first concentrate on a typical factor (1 − x^{2}yq^{2i+l+1}), 0 ≤ i ≤ n − 1, 0 ≤ l < i. Analogously to the proof of Theorem 1, 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 0 ≤ i ≤ n − 1, 0 ≤ l < i there holds

∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+7)}{2} −(i−l)(2i+2l+3)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+2}; q)_{2i−2s}}{(q^{−2i−l+s−1}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}} · (row s of D_{2}(x, q^{−2i−l−1}/x^{2}; n))

= (row i of D_{2}(x, q^{−2i−l−1}/x^{2}; n)). (3.4)

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

∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+7)}{2} −(i−l)(2i+2l+3)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+2}; q)_{2i−2s}}{(q^{−2i−l+s−1}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}} · q^{−2sj} (q^{−2i−l+s−1}/x; q)_{j} (xq^{2s−j+2}; q)_{j}

· (q^{−2i−l+2j−s+1}/x^{2}; q)_{s} (−q^{s+j+1−2i−l}/x; q)_{n−j−1}

· (1 − \frac{q^{2j−s−2i−l−1}}{x^{2}} − \frac{q^{2j−s−2i−l}}{x^{2}} + \frac{q^{s+j−2i−l}}{x} )

= q^{−2ij} (q^{−i−l−1}/x; q)_{j} (q^{2i−j+2}x; q)_{j} (q^{−3i+2j−l+1}/x^{2}; q)_{i}

× (−q^{1−i+j−l}/x; q)_{n−j−1} (1 − \frac{q^{−3i+2j−l−1}}{x^{2}} − \frac{q^{−3i+2j−l}}{x^{2}} + \frac{q^{−i+j−l}}{x} ) . (3.5)

We may rewrite the left-hand side sum as

− \frac{q^{2l^{2}−2i^{2}−2jl+2j−5i+l−1}x^{2l−2i−2}}{(−q; q)_{i−l−1}} (q^{1−2i+2j−2l}/x^{2}; q)_{l} (−q^{1−2i+j}/x; q)_{n+i−j−l−1}

× (q^{−1−i−l}/x; q)_{−i+j+l} (q^{2−j+2l}x; q)_{2i+j−2l}

× ∑_{k=0}^{⌊(i−l)/2⌋}(1 + q − q^{1−j+2l+2k}x − q^{1+2i+2l−2j+k}x^{2})\frac{(1 − q^{3k−2i+2l})}{(1 − q^{−2i+2l})}

· \frac{(−q^{−i+l}; q)_{k} (q^{2i−2j+2l}x^{2}; q)_{k} (q^{−1−2i+j}/x; q)_{k}}{(−q^{1−2i+j}/x; q)_{k} (q^{1−i+l}; q)_{k} (q; q)_{k}} \frac{(q^{−i+l}; q^{2})_{k} (q^{1−i+l}; q^{2})_{k}}{(q^{2−j+2l}x; q^{2})_{k} (q^{3−j+2l}x; q^{2})_{k}} q^{2k}.

The series can be summed by Lemma A2 with n = i − l and B = xq^{2l−j}. After some manipulation one arrives at the right-hand side of (3.5).

This establishes the claim that the determinant D_{2}(x, y; n) vanishes if a factor (1 − x^{2}yq^{2i+l+1}), 0 ≤ i ≤ n − 1, 0 ≤ l < i, vanishes. Again, since for equal factors the corresponding linear combinations of the rows are linearly independent, the complete product ∏_{i=0}^{n−1}(x^{2}yq^{2i+1}; q)_{i} divides D_{2}(x, y; n).

The reasoning that ∏_{i=0}^{n−1}(xy^{2}q^{2i+1}; q)_{i} is a factor of D_{2}(x, y; n) is similar. Also here, let us concentrate on a typical factor (1 − xy^{2}q^{2j+l+1}), 0 ≤ j ≤ n − 1, 0 ≤ l < j. This time we claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 0 ≤ j ≤ n − 1, 0 ≤ l < j there holds

∑_{s=l}^{⌊(j+l)/2⌋} q^{(s−l)(5s+3l+3)/2−((j−l)(2j+2l+1))}y^{2(s−j)} \frac{(1 − q^{2j+l−3s})}{(1 − q^{j−s})} \frac{(q^{1+j+l−2s}; q)_{s−l}}{(−q; q)_{j−s} (q; q)_{s−l}}
· (yq^{2s+2}; q)_{2j−2s} · (column s of D_{2}(q^{−2j−l−1}/y^{2}, y; n))

= (column j of D_{2}(q^{−2j−l−1}/y^{2}, y; n)). (3.6)

Restricting to the i-th row, we see that this means to check

∑_{s=l}^{⌊(j+l)/2⌋} q^{(s−l)(5s+3l+3)/2−((j−l)(2j+2l+1))}y^{2(s−j)} \frac{(1 − q^{2j+l−3s})}{(1 − q^{j−s})} \frac{(q^{1+j+l−2s}; q)_{s−l}}{(−q; q)_{j−s} (q; q)_{s−l}}
· (yq^{2s+2}; q)_{2j−2s} · q^{−2is}(q^{−1+i−2j−l}/y; q)_{s} (q^{1+2i−2j−l−s}/y^{2}; q)_{s}

· (yq^{2s−i+2}; q)_{i} (−q^{1+i−2j−l+s}/y; q)_{n−s−1} (1 − yq^{2s−i} − yq^{2s−i+1} + \frac{q^{i−2j−l+s}}{y} )

= q^{−2ij} (q^{−1+i−2j−l}/y; q)_{j}(q^{1+2i−3j−l}/y^{2}; q)_{j} (yq^{2j−i+2}; q)_{i}

× (−q^{1+i−j−l}/y; q)_{n−j−1} (1 − yq^{2j−i} − yq^{2j−i+1} + \frac{q^{i−j−l}}{y} ) . (3.7)

Again, we rewrite the left-hand side series,

− \frac{q^{1+2j−i−2ij}y}{(−q; q)_{j−l−1}} (q^{1+2i−2j−2l}/y^{2}; q)_{l} (q^{−1−2j}/y; q)_{i+2j−2l} (−q^{1+i−2j}/y; q)_{n−l−1}

× (q^{−1+i−2j−l}/y; q)_{l−i} (q^{2−i+2j}y; q)_{i}

× ∑_{k=0}^{⌊(j−l)/2⌋} (1 + \frac{1}{q} − \frac{q^{2i−2j−2l−k−1}}{y^{2}} − \frac{q^{i−2l−2k−1}}{y} ) \frac{(1 − q^{−3k+2j−2l})}{(1 − q^{2j−2l})}

· \frac{(−q^{j−l}; q^{−1})_{k} (q^{2i−2j−2l}/y^{2}; q^{−1})_{k} (q^{2j−i+1}y; q^{−1})_{k}}{(−q^{−1−i+2j}y; q^{−1})_{k} (q^{−1+j−l}; q^{−1})_{k} (q^{−1}; q^{−1})_{k}}

· \frac{(q^{j−l}; q^{−2})_{k} (q^{−1+j−l}; q^{−2})_{k}}{(q^{−2+i−2l}/y; q^{−2})_{k} (q^{−3+i−2l}/y; q^{−2})_{k}} q^{−2k}.

The series can be summed by Lemma A2 with q replaced by 1/q, n = j − l, B = q^{−2l+i}/y. Similarly to as before, this eventually shows that the complete product ∏_{i=0}^{n−1}(xy^{2}q^{2i+1}; q)_{i} divides D_{2}(x, y; n).

Altogether, this implies that ∏_{i=0}^{n−1} ((x^{2}yq^{2i+1}; q)_{i} (xy^{2}q^{2i+1}; q)_{i}) divides D_{2}(x, y; n), as desired. This completes the proof of Lemma 1. □

Next, we locates several zeros of the polynomial factor P (x, y; n) of D_{2}(x, y; n) (recall (3.2) for the definition of P (x, y; n) and D_{2}(x, y; n)).

Lemma 2. If u, v are nonnegative integers with u + v ≤ n − 1, then P (q^{−u}, q^{−v}; n) = 0, with P (x, y; n) the polynomial in (3.2).

Proof. Let u, v be nonnegative integers with u + v ≤ n − 1. The polynomial P (x, y; n) is defined by (3.2),

D_{2}(x, y; n) = ∏_{i=0}^{n−1} ((x^{2}yq^{2i+1}; q)_{i} (xy^{2}q^{2i+1}; q)_{i}) · P (x, y; n),  (3.8)

where D_{2}(x, y; n) is the determinant in (3.1), respectively (3.2). What we would like to do is to set x = q^{−u} and y = q^{−v} in (3.8), prove that D_{2}(q^{−u}, q^{−v}; n) equals 0, that the product on the right-hand side of (3.8) is nonzero, and conclude that therefore P (q^{−u}, q^{−v}; n) must be 0. However, the product on the right-hand side of (3.8) unfortunately (usually) is 0 for x = q^{−u} and y = q^{−v}. Therefore we have to find a way around this difficulty.

To begin with, we set y = q^{−v} in (3.8). Before setting x = q^{−u}, we have to cancel all factors of the form (1 − xq^{u}) that occur in the product on the right-hand side of (3.8). To accomplish this, we have to “generate” these factors on the left-hand side. This is done by reading through the proof of Lemma 1 with y = q^{−v}. To make this more precise, observe that (1 − xq^{u}) divides a typical factor 1 − x^{2}q^{−v+2i+l+1}, 0 ≤ i ≤ n − 1, 0 ≤ l < i, of the first half of the product in (3.8) if and only if 2u = −v + 2i + l + 1. Therefore, if we recall (3.4), for each solution (i, l) of

2u = −v + 2i + l + 1, with 0 ≤ i ≤ n − 1, 0 ≤ l < i,  (3.9)

we subtract the linear combination

∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+7)}{2} −(i−l)(2i+2l+3)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+2}; q)_{2i−2s}}{(q^{−2i−l+s−1}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}} · (row s of D_{2}(x, q^{−v}; n))

(3.10)

of rows of D_{2}(x, q^{−v}; n) from row i of D_{2}(x, q^{−v}; n). Let us denote the resulting determinant by D̃_{2}(x, q^{−v}; n). By (3.4), the effect is that (1 − x^{2}q^{−v+2i+l+1}) = (1 − x^{2}q^{2u}) (the equality being due to (3.9)), is a factor of each entry of the i-th row of D̃_{2}(x, q^{−v}; n), for each solution (i, l) of (3.9), in particular (1−xq^{u}) is a factor of each entry of the i-th row of D̃_{2}(x, q^{−v}; n). For later use we record that the (i, j)-entry of D̃_{2}(x, q^{−v}; n), (i, l) a solution of (3.9), reads

q^{−2ij} (xq^{−v+i}; q)_{j} (xq^{2i−j+2}; q)_{j} (q^{−v+2j−i+2}; q)_{i} (−xq^{−v+i+j+2}; q)_{n−j−1}

× (1 − q^{−v+2j−i} − q^{−v+2j−i+1} + xq^{−v+i+j+1})

− ∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+7)}{2} −(i−l)(2i+2l+3)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+2}; q)_{2i−2s}}{(q^{−2i−l+s−1}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}}

· q^{−2sj} (xq^{−v+s}; q)_{j} (xq^{2s−j+2}; q)_{j} (q^{−v+2j−s+2}; q)_{s}

· (−xq^{−v+s+j+2}; q)_{n−j−1} (1 − q^{−v+2j−s} − q^{−v+2j−s+1} + xq^{−v+s+j+1}). (3.11)

Similar considerations concern the second half of the product in (3.8). Omitting the details, for each solution (j, l) of

u = −2v + 2j + l + 1, with 0 ≤ j ≤ n − 1, 0 ≤ l < j,  (3.12)

we subtract the linear combination

∑_{s=l}^{⌊(j+l)/2⌋} q^{(s−l)(5s+3l+3)/2−((j−l)(2j+2l+1))}q^{−2v(s−j)}

· \frac{(1 − q^{2j+l−3s})}{(1 − q^{j−s})} \frac{(q^{1+j+l−2s}; q)_{s−l}}{(−q; q)_{j−s} (q; q)_{s−l}} (q^{−v+2s+2}; q)_{2j−2s} · (column s of D̃_{2}(x, q^{−v}; n))

of columns of D̃_{2}(x, q^{−v}; n) (we definitely mean D̃_{2}(x, q^{−v}; n), and not D_{2}(x, q^{−v}; n)) from column j of D̃_{2}(x, q^{−v}; n). By (3.6), each entry of the j-th column of the new determinant will have (1−xq^{u}) as a factor. We remark that entries that were changed by a row and column operations will now have (1 − xq^{u})^{2} as a factor. Now we take (1 − xq^{u}) out of the i-th row, for each solution (i, l) of (3.9), and we take (1 − xq^{u}) out of the j-th column, for each solution (j, l) of (3.12). We denote the resulting determinant by \overline{D}_{2}(x, q^{−v}; n). Thus, we have

D_{2}(x, q^{−v}; n) = (1 − xq^{u})^{#(solutions (i,l) of (3.9))+#(solutions (j,l) of (3.12))} \overline{D}_{2}(x, q^{−v}; n).

Plugging this into (3.8), we see that now all factors (1 − xq^{u}) can be cancelled on both sides, so that we obtain

\overline{D}_{2}(x, q^{−v}; n) = C(x, q^{−v}; n) P (x, q^{−v}; n),

for some C(x, q^{−v}; n) that does not vanish for x = q^{−u}. Hence, if we are able to prove that \overline{D}_{2}(q^{−u}, q^{−v}; n) = 0, it would follow that P (q^{−u}, q^{−v}; n) = 0, which is what we want to establish.

So we are left with showing that \overline{D}_{2}(q^{−u}, q^{−v}; n) = 0. This will be implied by the following two claims: The matrix of which \overline{D}_{2}(q^{−u}, q^{−v}; n) is the determinant has a block form (see (3.13)), where

Claim 1. the upper-right block, consisting of the entries that are in one of the rows 0, 1, …, u + v and one of the columns u + v + 1, u + v + 2, …, n − 1, is a zero matrix, and where

Claim 2. the determinant of the upper-left block, N, consisting of the entries that are in one of the rows 0, 1, …, u + v and one of the columns 0, 1, …, u + v, equals 0. (Note that it is at this point that we need the assumption u + v ≤ n − 1 in the Lemma. It guarantees that the picture (3.13) makes sense, meaning that row u + v and column u + v are really a row and a column of the matrix; recall that the rows and columns are numbered from 0 to n − 1.)

N 0 ∗ ∗ _{← i=u+v}^{j =u+v}^{↓}  (3.13)

Indeed, Claim 1 and Claim 2 imply \overline{D}_{2}(q^{−u}, q^{−v}; n) = 0. For, the determinant of a block matrix of the form (3.13) equals the product of the determinants of the upper-left block and the lower-right block, the first determinant being equal to 0 by Claim 2.

Claim 1 is most obvious for all the entries that did not change in the transition from D_{2}(x, q^{−v}; n) to \overline{D}_{2}(x, q^{−v}; n). For, the (i, j)-entry of D_{2}(x, q^{−v}; n), by its definition in (3.1), is

q^{−2ij} (q^{−u−v+i}; q)_{j} (q^{−u+2i−j+2}; q)_{j} (q^{−v+2j−i+2}; q)_{i} (−q^{−u−v+i+j+2}; q)_{n−j−1}

· (1 − q^{−v+2j−i} − q^{−v+2j−i+1} + q^{−u−v+i+j+1}). (3.14)

Clearly, if 0 ≤ i ≤ u + v and u + v + 1 ≤ j ≤ n − 1, we have (q^{−u−v+i}; q)_{j} = 0, and so the complete expression in (3.14) is 0.

On the other hand, let us consider an (i, j)-entry of \overline{D}_{2}(x, q^{−v}; n) that changed in the transition from D_{2}(x, q^{−v}; n) to \overline{D}_{2}(x, q^{−v}; n). First we want to know, where such an entry could be located. If it changed under a row operation, then (i, l) is a solution of (3.9), for some l. By (3.9) we have

−v + 2i + 1 ≤ −v + 2i + l + 1 = 2u and 2u = −v + 2i + l + 1 ≤ −v + 3i,

and so,

\frac{2u + v}{3} ≤ i ≤ \frac{2u + v − 1}{2}.  (3.15)

If the (i, j)-entry changed under a column operation, then (j, l) is a solution of (3.12), for some l. Similar arguments then give, using (3.12), that

\frac{u + 2v}{3} ≤ j ≤ \frac{u + 2v − 1}{2}.  (3.16)

In particular we have j < u + v, so an (i, j)-entry that is located in the upper-right block, which we are currently interested in, did not change under a column operation.

But it could have changed under a row operation. Such an (i, j)-entry is given by (3.11) divided by (1 − xq^{u}). (Recall that (3.11) was the expression for an (i, j)-entry that changed under a row operation before we factored (1 − xq^{u}) out of the i-th row.) Thus, it can be written as

\frac{(xq^{−v+i}; q)_{u+v−i+1}}{(1 − xq^{u})} (q^{−2ij} (xq^{u+1}; q)_{i+j−u−v−1} (xq^{2i−j+2}; q)_{j} (q^{−v+2j−i+2}; q)_{i}

× (−xq^{−v+i+j+2}; q)_{n−j−1} (1 − q^{−v+2j−i} − q^{−v+2j−i+1} + xq^{−v+i+j+1})

− ∑_{s=l}^{⌊(i+l)/2⌋} q^{\frac{(s−l)(5s+3l+7)}{2} −(i−l)(2i+2l+3)}x^{2(s−i)} \frac{(1 − q^{2i−3s+l})}{(1 − q^{i−s})} \frac{(q^{i−2s+l+1}; q)_{s−l}}{(q; q)_{s−l}}

· \frac{(xq^{2s+2}; q)_{2i−2s}}{(q^{−2i−l+s−1}/x; q)_{i−s}} \frac{(−q^{−2i−l+n+s}/x; q)_{i−s}}{(−q; q)_{i−s}}

· q^{−2sj} (xq^{−v+s}; q)_{i−s} (xq^{u+1}; q)_{j+s−u−v−1} (xq^{2s−j+2}; q)_{j} (q^{−v+2j−s+2}; q)_{s}

· (−xq^{−v+s+j+2}; q)_{n−j−1} (1 − q^{−v+2j−s} − q^{−v+2j−s+1} + xq^{−v+s+j+1})). (3.17)

We have to show that (3.17) vanishes for x → q^{−u}. Because of the denominators, it is not even evident that (3.17) is well-defined when x → q^{−u}. However, by (3.15) we have u + v − i ≥ (v + 1)/2 ≥ 0. Hence,

\frac{(xq^{−v+i})_{u+v−i+1}}{(1 − xq^{u})} = (xq^{−v+i})_{u+v−i},

and so the first term in (3.17) is well-defined when x → q^{−u}. Furthermore, the denominator in the sum in (3.17) (neglecting the terms that do not depend on x) when x → q^{−u} becomes

(q^{u−2i−l+s−1}; q)_{i−s} = (1 − q^{u−2i−l+s−1}) ⋯ (1 − q^{u−i−l−2}).  (3.18)

By (3.9) and (3.15) we have u − i − l − 2 = −u − v + i − 1 ≤ \frac{1}{2}(−v − 3) < 0. Therefore, all the terms in (3.18) are nonzero, which means that the denominator in the sum in (3.17) is nonzero when x → q^{−u}. Hence, (3.17) is well-defined for x → q^{−u}. To demonstrate that it actually vanishes for x → q^{−u}, we show that the second term in (3.17) (the term in big parentheses) equals 0 for x = q^{−u}.

To see this, set x = q^{−u}, and by (3.9) replace l by 2u + v − 2i − 1 in the sum (3.17), and then convert it into hypergeometric notation, to obtain

− q^{4ij+4j− \frac{i}{2} + \frac{3i^{2}}{2} −u−4iu−4ju+2u^{2}− \frac{5v}{2} −5iv−2jv+4uv+ \frac{3v^{2}}{2}}

× (−1; q)_{−3i+2u+v} (q; q)_{−2−2i+j+u} (−q^{1−2i+j+u}; q)_{3i−j+n−2u−v}
× (q^{3+2i+2j−2u−2v}; q)_{−1−2i+2u+v} (q^{−4i−j+3u+2v}; q)_{2+6i+j−4u−2v}

× ∑_{k=0}^{⌊(−2u−v+3i+1)/2⌋}(+1 + q − q^{−1−2i−2j+k+2u+2v} − q^{−1−4i−j+2k+3u+2v})

· \frac{(1 − q^{1−6i+4u+2v})}{(1 − q^{−2−6i+4u+2v})} \frac{(−q^{−1−3i+2u+v}; q)_{k} (q^{−2−2i−2j+2u+2v}; q)_{k} (q^{−1−2i+j+u}; q)_{k}}{(q^{−3i+2u+v}; q)_{k} − q^{1−2i+j+u}; q)_{k} (q; q)_{k}}

· \frac{(q^{−1−3i+2u+v}; q^{2})_{k} (q^{−3i+2u+v}; q^{2})_{k}}{(q^{−4i−j+3u+2v}; q^{2})_{k} (q^{1−4i−j+3u+2v}; q^{2})_{k}} q^{2k}. (3.19)

The series can be summed by means of Lemma A2 with n = −2u − v + 3i + 1 and B = q^{3u+2v−4i−j−2}. Then, after simplification, (3.19) becomes

q^{−2ij}(q; q)_{i+j−u−v−1} (q^{−u+2i−j+2}; q)_{j} (q^{−v+2j−i+2}; q)_{i}

× (−q^{−u−v+i+j+2}; q)_{n−j−1} (1 − q^{−v+2j−i} − q^{−v+2j−i} + q^{−u−v+i+j+1}) ,

which is exactly the first term in big parentheses in (3.17) for x = q^{−u}. Therefore, the term in big parentheses in (3.17) vanishes for x = q^{−u}. This settles Claim 1.

Next we turn to Claim 2. We have to prove that the determinant of the matrix N, consisting of the entries of \overline{D}_{2}(q^{−u}, q^{−v}; n) that are in one of the rows 0, 1, …, u + v and one of the columns 0, 1, …, u + v (recall (3.13)), equals 0. We do this by locating enough zeros in the matrix N.

We concentrate on the entries that did not change in the transition from D_{2}(x, q^{−v}; n) to \overline{D}_{2}(x, q^{−v}; n). For the location of the various regions in the matrix N that we are going to describe, always consult Figure 1 which gives a rough sketch.

N = [figure: i = 0; i = ⌈ \frac{u−1}{2} ⌉; i = ⌈ \frac{2u+v}{3} ⌉ − 2 + χ(u ≡ v(3)); i = ⌊ \frac{2u+v−1}{2} ⌋ + 1; i = u + v; 0; j =; j =; _{⌈ \frac{v−1}{2} ⌉}; ⌈ \frac{u+2v}{3} ⌉ − 1; j =; j =; ⌊_{\frac{u+2v−1}{2}} ⌋ + 1; u + v; j =; i = \frac{u+j−2}{2}; j = \frac{v+i−2}{2}; i + j = u + v; I; II; IV; III]

Figure 1

By earlier considerations, an (i, j)-entry did not change if i is outside the range (3.15), i.e.,

0 ≤ i ≤ ⌈\frac{2u + v}{3} ⌉ − 1 or ⌊\frac{2u + v − 1}{2}⌋ + 1 ≤ i ≤ n − 1,  (3.20)

and if j is outside the range (3.16), i.e.,

0 ≤ j ≤ ⌈\frac{u + 2v}{3} ⌉ − 1 or ⌊\frac{u + 2v − 1}{2}⌋ + 1 ≤ j ≤ n − 1.  (3.21)

As we already noted, such an (i, j)-entry is given by (3.14). The first term in (3.14) vanishes if and only if

i ≤ u + v and i + j > u + v.  (3.22)

The second term in (3.14) vanishes if and only if

⌈\frac{u − 1}{2}⌉ ≤ i ≤ \frac{u + j − 2}{2}.  (3.23)

The third term in (3.14) vanishes if and only if

⌈\frac{v − 1}{2}⌉ ≤ j ≤ \frac{v + i − 2}{2}.  (3.24)

Obviously, the fourth term in (3.14) never vanishes. Finally, we need the following sufficient conditions in order the fifth term to vanish: The fifth term in (3.14) vanishes if

u − v = 3(i − j) and u + v − i − j = 0 or 2.  (3.25)

Now we claim that in the following four regions of N all the entries are 0, except for the cases u = 0, v = 1, and u = 1, v = 0, which we treat separately. Again, to get an idea of the location of these regions, consult Figure 1.

Region I: All (i, j)-entries with

⌈\frac{u − 1}{2}⌉ ≤ i ≤ ⌈\frac{2u + v}{3} ⌉ − 2 + χ(u ≡ v (mod 3))

and ⌈\frac{v − 1}{2}⌉ ≤ j ≤ ⌈\frac{u + 2v}{3} ⌉ − 1, (3.26)

where χ(A)=1 if A is true and χ(A)=0 otherwise.

Region II: All (i, j)-entries with

⌈\frac{u − 1}{2}⌉ ≤ i ≤ ⌈\frac{2u + v}{3} ⌉ − 2 + χ(u ≡ v (mod 3))

and ⌊\frac{u + 2v − 1}{2}⌋ + 1 ≤ j ≤ u + v. (3.27)

Region III: All (i, j)-entries with

⌊\frac{2u + v − 1}{2}⌋ + 1 ≤ i ≤ u + v and ⌈\frac{v − 1}{2}⌉ ≤ j ≤ ⌈\frac{u + 2v}{3} ⌉ − 1.  (3.28)

Region IV: All (i, j)-entries with

⌊\frac{2u + v − 1}{2}⌋ + 1 ≤ i ≤ u + v and ⌊\frac{u + 2v − 1}{2}⌋ + 1 ≤ j ≤ u + v.  (3.29)

Instantly we observe that all four regions satisfy (3.20) and (3.21). So, all the entries in these regions are given by (3.14). Hence, to verify that all these entries are 0 we have to show that for each entry one of (3.22)–(3.25) is true. Of course, we treat the four regions separately.

ad Region I. First let i ≤ ⌈(2u + v)/3⌉ − 2. In case that i ≤ j + (u − v)/3, we have

i ≤ \frac{i + j + \frac{u−v}{3}}{2} ≤ \frac{⌈\frac{2u+v}{3} ⌉ − 2 + j + \frac{u−v}{3}}{2}

≤ \frac{\frac{2u+v}{3} + \frac{2}{3} − 2 + j + \frac{u−v}{3}}{2} = \frac{u + j − 2}{2} + \frac{1}{3}.

Combined with (3.26), this implies that (3.23) is satisfied. On the other hand, in case that i > j + (u − v)/3, or equivalently,

i ≥ j + \frac{u − v}{3} + \frac{1}{3},  (3.30)

we have, using the last inequality in (3.26),

j ≤ \frac{i + j − \frac{u−v}{3} − \frac{1}{3}}{2} ≤ \frac{i + ⌈\frac{u+2v}{3} ⌉ − 1 − \frac{u−v}{3} − \frac{1}{3}}{2}

≤ \frac{i + \frac{u+2v}{3} + \frac{2}{3} − 1 − \frac{u−v}{3} − \frac{1}{3}}{2} = \frac{v + i − 2}{2} + \frac{2}{3}.

Combined with (3.26), this implies that (3.24) is satisfied, unless j = (v + i − 1)/2. But if we plug this into (3.30), we obtain i ≥ (2u + v)/3 − 1/3, a contradiction to our assumption i ≤ ⌈(2u + v)/3⌉ − 2.

Collecting our results so far, we have seen that if u − v ≡ 1, 2 (mod 3), then each (i, j)-entry in region I satisfies (3.23) or (3.24). If u ≡ v (mod 3), region I also contains entries from row i = (2u + v)/3 − 1. First let j ≤ (u + 2v)/3 − 2. Then it is immediate that (3.24) is satisfied. If j = (u + 2v)/3 − 1, then (3.25) is satisfied. This shows that if u ≡ v (mod 3) then an (i, j)-entry in region I satisfies (3.23), (3.24), or (3.25).

ad Region II. Here, by (3.27), we have

i + j ≥ ⌈\frac{u − 1}{2}⌉ + ⌊\frac{u + 2v − 1}{2}⌋ + 1 = u + v.

Hence, (3.22) is satisfied, except when i = ⌈(u − 1)/2⌉ and j = ⌊(u + 2v − 1)/2⌋ + 1. But in that case there holds (3.23), apart from a few exceptional cases. For, if u ≠ 0, 2 then

⌈\frac{u − 1}{2}⌉ ≤ \frac{u + ⌊\frac{u−1}{2}⌋ − 1}{2}.

Since v is nonnegative it follows that

⌈\frac{u − 1}{2}⌉ ≤ \frac{u + (⌊\frac{u+2v−1}{2}⌋ + 1) − 2}{2},  (3.31)

which is nothing but (3.23) with the current choices of i and j. Thus, (3.23) is satisfied except when u = 0 or u = 2. But (3.31), and hence (3.23), holds in more cases. Namely, by inspection, if u = 0, then (3.31) holds for v ≥ 2, and if u = 2, then (3.31) holds for v ≥ 1. So the only cases in which (3.31) is not true are u = v = 0, u = 0 and v = 1, u = 2 and v = 0. Starting from the back, the case u = 2, v = 0 does not bother us, since in that case region II is empty (there is no i satisfying (3.27)). The case u = 0, v = 1 is one of the exceptional cases that are treated separately. Finally, in case u = v = 0 we have i = ⌈(u − 1)/2⌉ = 0 and j = ⌊(u + 2v − 1)/2⌋ + 1 = 0. Hence, (3.25) is satisfied.

ad Region III. We argue as in the considerations concerning region II. In fact, the arguments given there can be used word by word, with i and j interchanged, and with u and v interchanged.

ad Region IV. By (3.29) we have

i + j ≥ ⌊\frac{2u + v − 1}{2}⌋ + 1 + ⌊\frac{u + 2v − 1}{2}⌋ + 1 ≥ \frac{3u + 3v}{2} + 1 > u + v.

Hence, (3.22) is satisfied.

Consequently, if we are not in one of the cases u = 0, v = 1, or u = 1, v = 0, then the rows ⌈(u − 1)/2⌉ , …, ⌈(2u + v)/3⌉ − 2 + χ(u ≡ v (mod 3)), ⌊(2u + v − 1)/2⌋ + 1, …, u + v are rows with zeros in columns ⌈(v − 1)/2⌉ , …, ⌈(u + 2v)/3⌉ − 1, ⌊(u + 2v − 1)/2⌋ + 1, …, u + v. These are

⌈\frac{2u + v}{3} ⌉ − 1 + χ(u ≡ v (mod 3)) − ⌈\frac{u − 1}{2}⌉ + u + v − ⌊\frac{2u + v − 1}{2}⌋ (3.32)

rows, containing possibly nontrivial entries in only

⌈\frac{v − 1}{2}⌉ + ⌊\frac{u + 2v − 1}{2}⌋ − ⌈\frac{u + 2v}{3} ⌉ + 1  (3.33)

columns. By simple algebra, the difference between (3.32) and (3.33) equals

u − v + ⌈\frac{v − u}{3}⌉ + ⌈\frac{2v − 2u}{3}⌉ + χ(u ≡ v (mod 3)).  (3.34)

As is easily verified, the expression (3.34) equals 1 always. So we have found N + 1 rows (with N the expression in (3.33)) that actually live in ℝ^{N} (ℝ denoting the set of real numbers). Hence, they must be linearly dependent. This implies that the determinant of N must be 0.

Finally we settle the cases u = 0, v = 1, and u = 1, v = 0. If u = 0 and v = 1 then the matrix N is a 2 × 2 matrix (cf. Figure 1) in which row 1 vanishes. For, i = 1 and j = 0 satisfy (3.20), (3.21), and (3.24), while i = 1 and j = 1 satisfy (3.20), (3.21), and (3.22). Hence, det(N) = 0. Similarly, if u = 1 and v = 0 then the matrix N is a 2 × 2 matrix in which column 1 vanishes. For, i = 0 and j = 1 satisfy (3.20), (3.21), and (3.23), while i = 1 and j = 1 satisfy (3.20), (3.21), and (3.22). Hence again, det(N) = 0.

Altogether, this implies that P (q^{−u}, q^{−v}; n) = 0, as we observed earlier. And this is what we wanted to prove. □

As last lemma we prove a characterization theorem for the “big factor” on the righthand side of (1.4) (more precisely, on the right-hand side of (3.1)), which we wish to identify as P (x, y; n). We shall eventually show that P (x, y; n) has all the properties (1)–(4) that are stated below and thus be able to finish the proof of Theorem 2.

Lemma 3. The polynomial

Q(x, y; n) = ∏_{i=0}^{n−1} (q^{−2i^{2}}(q^{2}; q^{2})_{i}) ∑_{k=0}^{n}(−1)^{k}q^{nk}\left[{n \atop k}\right]_{q}y^{k}(x; q)_{k}(y; q)_{n−k}  (3.35)

satisfies the following four properties:

(1) Q(x, y; n) is a polynomial in x and y, of degree n in x, and also of degree n in y.

(2) Q(q^{−u}, q^{−v}; n) = 0 for all nonnegative integers u and v with u + v ≤ n − 1.

(3) Q(x/y, y; n) is a polynomial in x and y.

(4) Q(−q^{−n}/y, y; n) = (−1)^{n}q^{\binom{n}{2}}(−q; q)_{n} ∏_{i=0}^{n−1} (q^{−2i^{2}}(q^{2}; q^{2})_{i}) y^{n}, for any nonneg-

ative integer n. Moreover, the conditions (1)–(4) determine a polynomial in x and y uniquely.

Proof. ad (1). This is obvious from the definition (3.35).

ad (2). We have (q^{−u}; q)_{k} = 0 for k > u. Hence, if k > u the corresponding summand in the sum in (3.35) vanishes for x = q^{−u} and y = q^{−v}. Now let k ≤ u. Because of u + v ≤ n − 1 it follows that k < n − v, or equivalently, n − k > v. But this implies (q^{−v}; q)_{n−k} = 0. Therefore also any summand with k ≤ u vanishes for x = q^{−u} and y = q^{−v}. Thus, Q(q^{−u}, q^{−v}; n) = 0, as desired.

ad (3). This is obvious from the definition (3.35).

ad (4). Setting x = −q^{−n}/y in (3.35), we get

\frac{Q(−q^{−n}/y, y; n)}{∏_{i=0}^{n−1} (q^{−2i^{2}}(q^{2}; q^{2})_{i})} = ∑_{k=0}^{n}(−1)^{k}q^{nk}\left[{n \atop k}\right]_{q}y^{k}(−q^{−n}/y; q)_{k}(y; q)_{n−k},

or after little manipulation,

\frac{Q(−q^{−n}/y, y; n)}{∏_{i=0}^{n−1} (q^{−2i^{2}}(q^{2}; q^{2})_{i})} = (y; q)_{n} ∑_{k=0}^{n} \frac{(−q^{−n}/y; q)_{k} (q^{−n}; q)_{k}}{(q^{1−n}/y; q)_{k} (q; q)_{k}} (−q^{n+1})^{k} .

The sum on the right-hand side can be summed by means of the q-Vandermonde summation [8, (1.5.2); Appendix (II.7)],

∑_{k=0}^{n} \frac{(a; q)_{k} (q^{−n}; q)_{k}}{(c; q)_{k} (q; q)_{k}} (\frac{cq^{n}}{a} )^{k} = \begin{matrix}(c/a; q) & n \\ (c; q) & n \end{matrix} ,

where n is a nonnegative integer. Thus we obtain

\frac{Q(−q^{−n}/y, y; n)}{∏_{i=0}^{n−1} (q^{−2i^{2}}(q^{2}; q^{2})_{i})} = (−1)^{n}q^{\binom{n}{2}}(−q; q)_{n} y^{n},

as desired.

Finally we have to confirm that indeed the properties (1)–(4) determine a polynomial in x and y uniquely.

Let H(x, y) be a polynomial in x and y satisfying conditions (1)–(4). Because of (1), H(x, y) can be written in the form

H(x, y) = ∑_{0≤i,j≤n}a_{ij} y^{n−j} (x; q)_{i} (y; q)_{j},  (3.36)

with uniquely determined coefficients a_{ij}. Now, in (3.36) we set x = 1 and y = q^{−v}, 0 ≤ v ≤ n − 1. Because of (2), we obtain 0 = ∑_{j=0}^{v} a_{0j} q^{−v(n−j)}(q^{−v}; q)_{j}. From this system of equations we get a_{0j} = 0 for 0 ≤ j ≤ n − 1. Similarly, by using (2) with x = q^{−1}, q^{−2}, …, q^{−(n−1)}, we get a_{ij} = 0 whenever i + j ≤ n − 1.

Thus, H(x, y) can be written in the form

H(x, y) = _{∑_{i,j≥0} ; i+j≥n}a_{ij} y^{n−j} (x; q)_{i} (y; q)_{j}.

Next, property (3) comes into effect. According to that property, we have that

H(x/y, y; n) = _{∑_{i,j≥0} ; i+j≥n}a_{ij} y^{n−i−j} (y − x)(y − qx) ⋯ (y − q^{i−1}x) (y; q)_{j}  (3.37)

is a polynomial in x and y. Let (i, j) be a pair with a_{ij} ≠ 0, where i + j is maximal, and if there are several such pairs then choose one with maximal i. Then there occurs a term y^{n−i−j}x^{i} in the corresponding summand in (3.37) which does not cancel. If i + j > n then the exponent of y is negative. However, this would contradict (3).

Therefore, H(x, y) can be written in the form

H(x, y; n) = ∑_{k=0}^{n} b_{k} y^{k} (x; q)_{k} (y; q)_{n−k},

where we set b_{k} := a_{k,n−k}.

Now we apply (4). We have

(−1)^{n}q^{\binom{n}{2}}(−q; q)_{n} ∏_{i=0}^{n−1} (q^{−2i^{2}}(q^{2}; q^{2})_{i})y^{n} = H(−q^{−n}/y, y; n)

= ∑_{k=0}^{n} b_{k} y^{k} (−q^{−n}/y; q)_{k} (y; q)_{n−k}

= ∑_{k=0}^{n} b_{k} q^{\binom{k}{2}−nk} (−yq^{n−k+1}; q)_{k} (y; q)_{n−k}. (3.38)

It is straight-forward to see that the polynomials

(−yq^{n−k+1}; q)_{k} (y; q)_{n−k}, k = 0, 1, …, n,

are linearly independent. Hence, by comparison of coefficients, equation (3.38) determines the coefficients b_{k}, k = 0, 1, …, n, uniquely, which implies that H(x, y) is uniquely determined.

This completes the proof of the Lemma. □

Finally we are in the position to finalize the proof of Theorem 2.

Proof of Theorem 2. We verify that P (x, y; n) has properties (1)–(4) in Lemma 3. Once this is done, it follows from Lemma 3 that P (x, y; n) equals the polynomial Q(x, y; n) in (3.35), which is exactly what we want to show. This would complete the proof of Theorem 2.

Now, P (x, y; n) satisfies property (1) because of Lemma 1, and it satisfies property (2) because of Lemma 2.

To check property (3), replace x by x/y in (3.2) and then multiply both sides by y^{\binom{n}{2}}. Thus we obtain

det_{0≤i,j≤n−1} (q^{−2ij} (xq^{i}; q)_{j} (y − xq^{2i−j+2}) ⋯ (y − xq^{2i+1}) (yq^{2j−i+2}; q)_{i}

· (−xq^{i+j+2}; q)_{n−j−1} (1 − yq^{2j−i} − yq^{2j−i+1} + xq^{i+j+1}))

= ∏_{i=0}^{n−1} ((y − x^{2}q^{2i+1}) ⋯ (y − x^{2}q^{3i}) (xyq^{2i+1}; q)_{i}) · P (x/y, y; n).

The left-hand side and the product on the right-hand side are polynomial. Besides, we know that the product on the right-hand side divides the left-hand side. So evidently, P (x/y, y; n) is a polynomial in x and y.

Finally, regarding property (4), set x = −q^{−n}/y in (3.2). Then, in the matrix on the left-hand side, the term (q^{−n+i+j+2})_{n−j−1} appears. This term vanishes whenever i + j ≤ n − 2. Hence, the matrix has triangular form. So the determinant is easily calculated. Property (4) then follows after simplification. □

Appendix: Some basic hypergeometric identities

Here we prove the basic hypergeometric identities that are needed in the text. We start with the summation needed in the proof of Theorem 1.

Lemma A1. Let n be a positive integer. Then

∑_{k=0}^{⌊n/2⌋} \frac{(1 − q^{3k−2n})}{(1 − q^{−2n})} \frac{(−q^{−n}; q)_{k} (b; q)_{k} (c; q)_{k} (q^{1−2n}/bc; q)_{k} (q^{−n}; q^{2})_{k} (q^{1−n}; q^{2})_{k}}{(q; q)_{k} (q^{1−n}; q)_{k} (q^{2−2n}/b; q^{2})_{k} (q^{2−2n}/c; q^{2})_{k} (bcq; q^{2})_{k}} q^{k}

= \frac{(b; q)_{n} (c; q)_{n} (bcq^{n}; q)_{n} (−q; q)_{n−1}}{(b; q^{2})_{n} (c; q^{2})_{n} (bcq; q^{2})_{n}} . (A.1)

Proof. We start with Rahman’s transformation formula [20, (3.12); 8, (3.8.13)]

∑_{k=0}^{∞} \frac{(1 − aq^{3k})}{1 − a} \frac{(b; q)_{k} (c; q)_{k} (aq/bc; q)_{k}}{(q; q)_{k} (aq/d; q)_{k} (d; q)_{k}} \frac{(a; q^{2})_{k} (d; q^{2})_{k} (aq/d; q^{2})_{k}}{(aq^{2}/b; q^{2})_{k} (aq^{2}/c; q^{2}) (bcq; q^{2})_{k}} q^{k}

= \frac{(aq^{2}; q^{2})_{∞} (bq; q^{2})_{∞} (cq; q^{2})_{∞} (aq^{2}/bc; q^{2})_{∞}}{(q; q^{2})_{∞} (aq^{2}/b; q^{2})_{∞} (aq^{2}/c; q^{2})_{∞} (bcq; q^{2})_{∞}}

× ∑_{k=0}^{∞} \frac{(b; q^{2})_{k} (c; q^{2})_{k} (aq/bc; q^{2})_{k}}{(q^{2}; q^{2})_{k} (dq; q^{2})_{k} (aq^{2}/d; q^{2})_{k}} q^{2k}. (A.2)

Setting a = q^{−2n} in this transformation formula, with n integral and n ≥ 1, we obtain a summation for a terminating series,

∑_{k=0}^{n} \frac{(1 − q^{3k−2n})}{(1 − q^{−2n})} \frac{(b; q)_{k} (c; q)_{k} (q^{1−2n}/bc; q)_{k}}{(q; q)_{k} (q^{1−2n}/d; q)_{k} (d; q)_{k}}

· \frac{(q^{−2n}; q^{2})_{k} (d; q^{2})_{k} (q^{1−2n}/d; q^{2})_{k}}{(q^{2−2n}/b; q^{2})_{k} (q^{2−2n}/c; q^{2})_{k} (bcq; q^{2})_{k}} q^{k} = 0. (A.3)

Now we let d tend to q^{−n}. The effect is that all terms with n/2 < k < n vanish. Hence, only the terms with 0 ≤ k ≤ n/2 and the one with k = n remain. Thus, if we simplify the resulting (k = n)-term and put it on the right-hand side, we obtain exactly (A.1). □

Finally we prove the summation which is needed in the proof of Theorem 2.

Lemma A2. Let n be a positive integer. Then

∑_{k=0}^{⌊n/2⌋} (1 + q − B^{2}q^{1+2n+k} − Bq^{1+2k}) \frac{(1 − q^{3k−2n})}{(1 − q^{−2n})}

· \frac{(−q^{−n}; q)_{k} (B^{2}q^{2n}; q)_{k} (q^{−1−2n}/B; q)_{k}}{(−q^{1−2n}/B; q)_{k} (q^{1−n}; q)_{k} (q; q)_{k}} \frac{(q^{−n}; q^{2})_{k} (q^{1−n}; q^{2})_{k}}{(Bq^{2}; q^{2})_{k} (Bq^{3}; q^{2})_{k}} q^{2k}

= q^{−\binom{n}{2}} (1 + q − Bq^{1+2n} − B^{2}q^{1+3n}) \frac{(−q; q)_{n−1}}{(−Bq^{n}; q)_{n}} \frac{(B^{2}q^{2n}; q)_{n}}{(Bq^{2}; q)_{n}} . (A.4)

Proof. For the left-hand side of (A.4) we have

∑_{k=0}^{⌊n/2⌋} (1 + q − B^{2}q^{1+2n+k} − Bq^{1+2k}) \frac{(1 − q^{3k−2n})}{(1 − q^{−2n})}

· \frac{(−q^{−n}; q)_{k} (B^{2}q^{2n}; q)_{k} (q^{−1−2n}/B; q)_{k}}{(−q^{1−2n}/B; q)_{k} (q^{1−n}; q)_{k} (q; q)_{k}} \frac{(q^{−n}; q^{2})_{k} (q^{1−n}; q^{2})_{k}}{(Bq^{2}; q^{2})_{k} (Bq^{3}; q^{2})_{k}} q^{2k}

= q \frac{(1 + Bq^{2n}) (1 − B^{2}q^{2n}) (1 − B^{2}q^{1+2n})}{(1 − B^{3}q^{1+4n})} ∑_{k=0}^{⌊n/2⌋} \frac{(1 − q^{3k−2n})}{(1 − q^{−2n})}

· \frac{(−q^{−n}; q)_{k} (B^{2}q^{2+2n}; q)_{k} (q^{−1−2n}/B; q)_{k}}{(−1/Bq^{2n}; q)_{k} (q^{1−n}; q)_{k} (q; q)_{k}} \frac{(q^{−n}; q^{2})_{k} (q^{1−n}; q^{2})_{k}}{(Bq^{2}; q^{2})_{k} (Bq^{3}; q^{2})_{k}} q^{k}

+ \frac{(1 − Bq) (1 − Bq^{1+2n})}{(1 − B^{3}q^{1+4n})} ∑_{k=0}^{⌊n/2⌋} \frac{(1 − q^{3k−2n})}{(1 − q^{−2n})} \frac{(−q^{−n}; q)_{k} (B^{2}q^{2n}; q)_{k} (1/Bq^{2n}; q)_{k}}{(−q^{1−2n}/B; q)_{k} (q^{1−n}; q)_{k} (q; q)_{k}}

· \frac{(q^{−n}; q^{2})_{k} (q^{1−n}; q^{2})_{k}}{(Bq; q^{2})_{k} (Bq^{2}; q^{2})_{k}} q^{k}.

Each of the series on the right-hand side of this identity can be summed by means of Lemma A1. After little manipulation we arrive at (A.4). □

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, Studies in Foundations and Combinatorics (G.-C. Rota, ed.), Adv. in Math. Suppl. Studies, Vol.1, 1978, pp. 131–150.

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

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

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

6. G. E. Andrews and W. H. Burge, Determinant identities, Pacific J. Math. 158 (1993), 1–14.

7. G. E. Andrews and D. W. Stanton, Determinants in plane partition enumeration, preprint.

8. G. Gasper and M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, Cambridge, 1990.

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

10. T. H. Koornwinder, On Zeilberger’s algorithm and its q-analogue, J. Comput. Appl. Math. 48 (1993), 91–111.

11. C. Krattenthaler, A determinant evaluation and some enumeration results for plane partitions, Number-Theoretic Analysis (E. Hlawka, R. F. Tichy, eds.), Lect. Notes in Math. 1452, Springer-Verlag, Berlin, New York, 1990, pp. 121–131.

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

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

14. C. Krattenthaler, An alternative evaluation of the Andrews–Burge determinant, to appear in the ”Rotafestschrift”.

15. C. Krattenthaler, A new proof of the MRR-conjecture — including a generalization, preprint.

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

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

18. W. H. Mills, D. H. Robbins and H. Rumsey, Self–complementary totally symmetric plane partitions, J. Combin. Theory A 42 (1986), 277–292.

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

20. M. Rahman, Some quadratic and cubic summation formulas for basic hypergeometric series, Can. J. Math. 45 (1993), 394–411.

21. R. P. Stanley, A baker’s dozen of conjectures concerning plane partitions, Combinatoire énumérative (G. Labelle, P. Leroux, eds.), Lecture Notes in Math. 1234, Springer, BerlinNew York, 1986, pp. 285–293.

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

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

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

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

26. D. Zeilberger, A constant term identity featuring the ubiquitous (and mysterious) Andrews– Mills–Robbins–Rumsey numbers 1, 2, 7, 42, 429, …, J. Combin. Theory Ser. A 66 (1994), 17–27.

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