ENUMERATION OF SYMMETRIC CENTERED RHOMBUS TILINGS OF A HEXAGON

ANISSE KASRAOUI AND CHRISTIAN KRATTENTHALER

Abstract. A rhombus tiling of a hexagon is said to be centered if it contains the central rhombus. We compute the number of vertically symmetric rhombus tilings of a hexagon with side lengths a, b, a, a, b, a which are centered. When a is odd and b is even, this shows that the probability that a random vertically symmetric rhombus tiling of an a, b, a, a, b, a hexagon is centered is exactly the same as the probability that a random rhombus tiling of an a, b, a, a, b, a hexagon is centered. This also leads to a factorization theorem for the number of all rhombus tilings of a hexagon which are centered.

1. Introduction

The enumeration of plane partitions, equivalently of rhombus tilings of a hexagon, was initiated by MacMahon in the early twentieth century. Let a, b and c be positive integers. By an (a, b, c)-hexagon we mean an equi-angular hexagon with side-lengths a, b, c, a, b, c. We always draw such a hexagon with the sides of lengths a, b, c, a, b, c in clockwise order starting from the southwestern side, so that the sides of length b are vertical. From a classical result of MacMahon [23, Sec. 429, q → 1], we know that the number of tilings of an (a, b, c)-hexagon by rhombi whose sides have length 1 and whose angles are 60 and 120 degrees (equivalently, of plane partitions contained in an a × b × c box) is given by the product

T (a, b, c) = ∏_{i=1}^{a} ∏_{j=1}^{b} ∏_{k=1}^{c} \frac{i + j + k − 1}{i + j + k − 2}.  (1.1)

We call such tilings rhombus tilings. The picture on the left in Figure 1 shows a rhombus tiling of a (3, 5, 4)-hexagon. MacMahon also conjectured that the number of vertically symmetric rhombus tilings of an (a, b, a)-hexagon (i.e, that are invariant under reflection across the vertical symmetry axis of the hexagon; see the picture on the right in Figure 3 for an example) is given by the product

ST (a, b, a) = ∏_{i=1}^{a} \frac{2i + b − 1}{2i − 1} ∏_{1≤i<j≤a} \frac{i + j + b − 1}{i + j − 1}.  (1.2)

This was first proved by Andrews [1]. Other proofs, and refinements, were later found by e.g. Gordon [15], Macdonald [24, pp. 83–85], Proctor [27, Prop. 7.3], Fischer [11], and the second author of the present paper [19, Theorem 13].

During the last two decades, there has been an increasing interest in enumerating rhombus tilings of planar regions with holes. One of the first results in this direction Figure 1. Left: a rhombus tiling of a (3, 5, 4)-hexagon. Right: a centered rhombus tiling of a (4, 5, 4)-hexagon where the central rhombus is marked.

Research supported by the Austrian Science Foundation FWF, grants Z130-N13 and S50-N15, the latter in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

concerned the enumeration of rhombus tilings of an (a, b, a)-hexagon that contain the central rhombus. (These tilings may be seen as the rhombus tilings of the region obtained from an (a, b, a)-hexagon by removing its central rhombus.) We call such tilings centered. Note that an (a, b, a)-hexagon has a central rhombus only if a and b have opposite parity. The picture on the right in Figure 1 shows a centered tiling of a (4, 5, 4)-hexagon. The corresponding enumeration result (see Theorem 1.1 below) is independently due to Ciucu and the second author [5, Theorems 1 and 2 and Corollaries 3 and 4] and to Gessel and Helfgott [17, Theorems 15 and 17]. For non-negative integers n and x, define

Q(n, x) = \frac{1}{2} \frac{(2n)!^{2} (2x)! (x + 2n − 1)!}{n!^{2} (x)! (2x + 4n − 2)!} (∑_{i=0}^{n−1} \frac{(−1)^{n−i−1}}{2n − 2i − 1} \frac{(x + n − i)_{2i}}{i!^{2}} ) ,  (1.3)

where (a)_{k} stands for the Pochhammer symbol, defined by (a)_{k} := a(a + 1) ⋯ (a + k − 1) for k ≥ 1, and (a)_{0} := 1.

Theorem 1.1. Let n and x be two non-negative integers.

(i) For x ≥ 1, the number of centered rhombus tilings of a (2n+1, 2x, 2n+1)-hexagon is Q(n + 1, x) · T (2n + 1, 2x, 2n + 1), where Q and T are defined by (1.3) and (1.1). Similarly, for n ≥ 1, the number of centered rhombus tilings of a (2n, 2x + 1, 2n)-hexagon is Q(n, x + 1) · T (2n, 2x + 1, 2n).

(ii) For n ≥ 1, exactly one third of the rhombus tilings of a (2n + 1, 2n, 2n + 1)-hexagon are centered. The same is true for a (2n, 2n + 1, 2n)-hexagon.

(iii) Let a be a non-negative real number. For x ∼ an, the probability that a random rhombus tiling of a (2n + 1, 2x, 2n + 1)-hexagon is centered is ∼ \frac{2}{π} arcsin(1/(a + 1)) as n tends to infinity. The same is true for a (2n, 2x + 1, 2n)-hexagon.

Generalizations of the preceding result were later obtained by Fulmek and the second author [12, 13], and by Fischer [10]. For other results on the enumeration of rhombus tilings of hexagons of which central triangles are removed, see e.g. [3, 4, 8, 9, 22]. Another result which is particularly relevant to our paper is the one by Ciucu and the second author in [7], where for the first time the number of rhombus tilings of a half (a, b, a)- hexagon with a triangular hole of size two and a free boundary was computed. Here, by a half (a, b, a)-hexagon with a free boundary we mean the region — denoted in the rest of the paper by F_{a,b,a} — obtained from the left half of an (a, b, a)-hexagon by regarding its boundary along ℓ, the vertical symmetry axis of the hexagon, as free; i.e, rhombi in a tiling of F_{a,b,a} are allowed to protrude outward across ℓ to its right. In Figure 2, the picture on the left shows a rhombus tiling of the half-hexagon F_{7,6,7}, the other two show tilings of F_{7,6,7} with triangular holes of size one and two.

\begin{matrix}ℓ \\ ℓ \\ ℓ \end{matrix}

Figure 2. Left: a rhombus tiling of the half-hexagon F_{7,6,7}. Middle: a tiling of F_{7,6,7} with a triangular hole of size two. Right: a tiling of F_{7,6,7} with a triangular hole of size one.

The present paper was motivated by an attempt to find similar results to those obtained in [7] for a triangular hole of size one. While we did not succeed for a general position of the hole, we have been able to obtain a formula for the number of rhombus tilings of the region F_{a,b,a}^{∗} obtained from the half-hexagon F_{a,b,a} by removing a triangular hole of size one pointing to the left such that the centre of its right side coincides with the centre of the free boundary. (This region is only defined if a and b have opposite parity.) The picture on the left in Figure 3 shows a tiling of F_{7,6,7}^{∗}. As illustrated in Figure 3, by reflecting the tilings of F_{a,b,a}^{∗} across the free boundary, it is easily seen that these are equinumerous with the centered vertically symmetric rhombus tilings of an (a, b, a)-hexagon. The next two theorems, which may be seen as a “symmetrization” of Theorem 1.1(i), are our main results.

Theorem 1.2. Let n and x be non-negative integers. For x ≥ 1, the number of centered vertically symmetric rhombus tilings of a (2n + 1, 2x, 2n + 1)-hexagon is Q(n + 1, x) · ST (2n + 1, 2x, 2n + 1), where Q and ST are defined by (1.3) and (1.2).

For a positive integer n and a non-negative integer x, define

U_{n}(x) = ∑_{i=1}^{n} ((2n − 1)!! + (−1)^{i+1}(2n)!!)\frac{(\frac{3}{2} − i)_{2n−1}}{(i − 1)! (2n − i)!}

× ((x + 1)_{i−1}(x + i + 1)_{2n−i} − (x + 1)_{2n−i}(x + 2n + 2 − i)_{i−1}), (1.4)

Figure 3. The correspondence between tilings of F_{2n+1,2x,2n+1}^{∗} and centered vertically symmetric tilings of a (2n + 1, 2x, 2n + 1)-hexagon.

and

R(n, x) = 2^{3n−2} \frac{(2x + 2)! (x + 2n)!}{n! (x + 1)! (2x + 4n)!} U_{n}(x).  (1.5)

Here, as usual, a!! stands for the double factorial, i.e., for a · (a − 2) · (a − 4) ⋯ 2 if a is even, and for a · (a − 2) · (a − 4) ⋯ 1 if a is odd.

Theorem 1.3. Let n and x be non-negative integers. For n ≥ 1, the number of centered vertically symmetric rhombus tilings of a (2n, 2x + 1, 2n)-hexagon is R(n, x) · ST (2n, 2x + 1, 2n), where R and ST are defined by (1.5) and (1.2).

The next result, which is rather striking and deserves further investigation, is immediate from Theorems 1.2 and 1.1.

Corollary 1.4. Let n and x be non-negative integers. The probability that a random vertically symmetric rhombus tiling of a (2n + 1, 2x, 2n + 1)-hexagon is centered is exactly the same as the probability that a random rhombus tiling of a (2n + 1, 2x, 2n + 1)-hexagon is centered.

We should note here that the preceding result leads to an interesting (and intriguing) factorization for the number of all centered tilings of a hexagon. Given a planar region R which is symmetric with respect to a vertical axis and to a horizontal axis, let T (R) be the set of all rhombus tilings of R. We also let T^{(|)}(R) (respectively T^{(−)}(R)) be the set of those tilings in T (R) that are vertically symmetric (respectively horizontally symmetric). Let H_{a,2b,a} be an (a, 2b, a)-hexagon. Ciucu and the second author [6] observed the factorization

#T (H_{a,2b,a}) = #T^{(|)}(H_{a,2b,a}) · #T^{(−)}(H_{a,2b,a}).  (1.6)

This can be proved by combining (1.1) and (1.2) with a formula of Proctor [28] for #T^{(−)}(H_{a,2b,a}) (equivalently, the number of transpose complementary plane partitions in a 2b × a × a box); see also [6], where the above relation was put in a more general context. Now, suppose that a is odd, and let H_{a,2b,a}^{∗} denote the region obtained by removing the central rhombus from H_{a,2b,a}. Recall that a centered tiling of H_{a,2b,a} is obviously equivalent to a tiling of H_{a,2b,a}^{∗}. Then, combining Corollary 1.4 with (1.6) (and noting that any horizontally symmetric tiling of H_{a,2b,a} is centered), we arrive at the following factorization for the number of centered tilings.

Corollary 1.5. For any non-negative integers n and x, we have

#T (H_{2n+1,2x,2n+1}^{∗}) = #T^{(|)}(H_{2n+1,2x,2n+1}^{∗}) · #T^{(−)}(H_{2n+1,2x,2n+1}^{∗}).  (1.7)

Note that the above factorization is very similar to the one in (1.6).

Another result which is immediate from Corollary 1.4 and Theorem 1.1 is the following.

Corollary 1.6. (i) For n ≥ 1, the probability that a random vertically symmetric rhombus tiling of a (2n + 1, 2n, 2n + 1)-hexagon is centered is 1/3.

(ii) Let a be a non-negative real number. For x ∼ an, the probability that a random vertically symmetric rhombus tiling of a (2n + 1, 2x, 2n + 1)-hexagon is centered is ∼ \frac{2}{π} arcsin(1/(a + 1)), as n tends to infinity.

As one can expect, the second part of the preceding proposition is still valid for a (2n, 2x + 1, 2n)-hexagon.

Corollary 1.7. Let a be a non-negative real number. Then, for x ∼ an, the probability that a random vertically symmetric rhombus tiling of a (2n, 2x+1, 2n)-hexagon is centered is ∼ \frac{2}{π} arcsin(1/(a + 1)), as n tends to infinity.

The rest of this paper is devoted to the proof of the above corollary and Theorems 1.2 and 1.3. As in many previous papers, our approach to proving Theorems 1.2 and 1.3 is to first translate the centered vertically symmetric rhombus tilings into families of nonintersecting lattice paths. Then, to enumerate these non-intersecting lattice paths, we use a slight extension of a theorem of Stembridge [29] to obtain Pfaffians for the numbers we are interested in. Here, due to the fact that we are considering an odd-size hole in our halfhexagon, we encounter a complication which has not appeared earlier (respectively has been circumvented or avoided so far): a naive direct application of the relevant formulas does not lead to formulas for the number of families of non-intersecting lattice paths but rather to “weighted” enumerations in which each family is assigned a weight of +1 or −1, depending on the sign of the permutation with respect to which starting points are connected with end points. There is a trick which is used here for the first time to cope with this difficulty: it consists of introducing appropriate edge weights to “correct” this sign, so that each family of non-intersecting lattice paths is indeed counted by +1 in the relevant formulas. All this is explained in Section 2.

The evaluation of the resulting Pfaffians occupies Sections 3 and 4, with some auxiliary results proved in Section 5. It is based on the “exhaustion/identification of factors” method (see e.g. [21, Sec. 2.4]) and turns out to be particularly demanding. In particular, we need a Pfaffian factorization due to Ciucu and the second author, an evaluation of a perturbed Mehta–Wang Pfaffian, and evaluations of very intricate combinatorial sums. In the final section, Section 6, we perform the asymptotic calculation needed to derive Corollary 1.7 from Theorem 1.3.

2. Centered vertically symmetric tilings, non-intersecting lattice paths and Pfaffians

2.1. Centered vertically symmetric tilings and non-intersecting lattice paths. As explained in the introduction (see Figure 3), centered vertically symmetric tilings of an (a, b, a)-hexagon may be seen as tilings of the region F_{a,b,a}^{∗}. Throughout this section, the term lattice path will always refer to a path in the lattice ℤ^{2} consisting of unit horizontal and vertical steps in the positive direction. There is a well known bijection between rhombus tilings of lattice regions and families of non-intersecting lattice paths. An illustration in our situation is given in Figure 4. By this bijection, tilings of F_{2n+1,2x,2n+1}^{∗}

Figure 4. The correspondence between tilings of F_{n,x,n}^{∗} and nonintersecting lattice paths.

are seen to be equinumerous with families (P_{1}, P_{2}, …, P_{2n+1}) of non-intersecting lattice paths, where for i = 1, 2, …, 2n + 1, P_{i} runs from (−i, i) to some point from the set I = {(−1, j) : 1 ≤ j ≤ 2x + 2n + 1} with the additional condition that (−1, x + n + 1) must be an ending point of some path. (We should note that an empty path, i.e., a path with no steps, may occur as in Figure 4, where the bottommost path is the empty path from (−1, 1) to (−1, 1).) Similarly, tilings of F_{2n,2x+1,2n}^{∗} are equinumerous with families (P_{1}, P_{2}, …, P_{2n}) of non-intersecting lattice paths, where P_{i} runs from (−i, i) to some point from the set I with the same additional condition. To enumerate these non-intersecting lattice paths, we shall use a slight extension of a theorem of Stembridge [29, Theorem 3.2], see Theorem 2.1 below.

2.2. Non-intersecting lattice paths and Pfaffians. We first set up some terminology. The Pfaffian of a skew-symmetric matrix A = (A_{i,j})_{1≤i,j≤2n} will be denoted by Pf A. It is well-known (see e.g. [29, Props. 2.2 and 2.3]) that the Pfaffian satisfies the following three properties:

(Pf A)^{2} = det A,  (2.1)
Pf(B A B^{t}) = (det B)(Pf A),  (2.2)
Pf_{1≤i,j≤2n}(x_{i}x_{j}A_{i,j}) = x_{1}x_{2} ⋯ x_{2n} Pf A,  (2.3)

for some 2n×2n matrix B. The sign of a permutation π ∈ 𝔖_{n}, where 𝔖_{n} is the symmetric group of rank n, will be denoted by sgn π. Recall that

sgn π = (−1)^{inv π},  (2.4)

where inv π is the number of inversions of π; i.e., the number of pairs (i, j) with 1 ≤ i < j ≤ n and π(i) > π(j).

Given a weight function w that assigns values in the field of complex numbers to each edge of the integer lattice ℤ^{2}, we extend w multiplicatively to multisets of edges, so that w(M) = ∏_{e∈M} w(e) for any such multiset M. The weight of a lattice path or r-tuple of lattice paths is defined as the weight of the underlying multiset of edges. Given any family F of edge multisets, we will write GF [F] for the generating function for F with respect to the weight w; i.e., GF [F] = ∑_{M∈F} w(M). In particular, let us define

h(A, B) = GF [P(A → B)] = ∑_{P ∈P(A→B)} w(P),  (2.5)

where P(A → B) stands for the set of lattice paths from A to B.

Theorem 2.1. Let A = (A_{1}, A_{2}, …, A_{p}), S = (S_{1}, S_{2}, …, S_{q}) and I = (I_{1}, I_{2}, …) be finite lists of points in the lattice ℤ^{2}, with p+q even. For π ∈ 𝔖_{p}, let P^{nonint}(A_{π} → (S, I)) denote the set of families (P_{1}, P_{2}, …, P_{p}) of non-intersecting lattice paths with P_{k} running from A_{π(k)} to S_{k}, for k = 1, 2, …, q, and to I_{j_{k}}, for k = q + 1, q + 2, …, p, the indices being required to satisfy j_{q+1} < j_{q+2} < … < j_{p}. Then

Pf ( \begin{matrix}Q & H \\ −H^{t} & 0 \end{matrix} ) = (−1)^{\binom{q}{2}} ∑_{π∈𝔖_{p}}(sgn π) GF [P^{nonint}(A_{π} → (S, I))],  (2.6)

where the matrix Q = (Q_{i,j})_{1≤i,j≤p} is defined by

Q_{i,j} = ∑_{1≤s<t} (h(A_{i}, I_{s}) h(A_{j}, I_{t}) − h(A_{j}, I_{s}) h(A_{i}, I_{t})),  (2.7)

and the matrix H = (H_{i,j})_{1≤i≤p,1≤j≤q} by

H_{i,j} = h(A_{i}, S_{j}),  (2.8)

with h(A, B) defined by (2.5).

The preceding theorem is a slight extension of a result of Stembridge [29, Theorem 3.2] and is just a weighted version of Theorem 5 in [7]. Since the proof of Stembridge’s theorem (alternatively, we may use the minor summation formula of Ishikawa and Wakayama [18, Theorem 2]) is easily adapted with only a little extra effort to the preceding result, the proof details are omitted.

2.3. Centered vertically symmetric tilings and Pfaffians. Combining the nonintersecting lattice path interpretation of centered vertically symmetric rhombus tilings with Theorem 2.1, we obtain the following counting formulas in terms of Pfaffians.

Lemma 2.2. Let n be a fixed non-negative integer. Then, for any non-negative integer x, the number of centered vertically symmetric rhombus tilings of a (2n + 1, 2x, 2n + 1)- hexagon is equal to the Pfaffian of the skew-symmetric matrix M(x) = (M_{i,j}(x))_{1≤i,j≤2n+2} defined by

M_{i,j}(x) = R_{i,j}(x) + T_{i,j}(x) − T_{j,i}(x), 1 ≤ i, j ≤ 2n + 1,  (2.9)
M_{i,2n+2}(x) = \binom{x + n}{i − 1},  1 ≤ i ≤ 2n + 1,  (2.10)

where R_{i,j}(x) and T_{i,j}(x) are defined by

R_{i,j}(x) := ∑_{t=1}^{2x+2n+1} \frac{j − i}{t}\binom{t}{i}\binom{t}{j} = ∑_{t=1}^{2x+2n+1} (\binom{t}{i}\binom{t − 1}{j − 1} − \binom{t − 1}{i − 1}\binom{t}{j}) , (2.11)

T_{i,j}(x) := \binom{2x + 2n + 1}{i} (\binom{x + n}{j} + \binom{x + n + 1}{j}) .  (2.12)

Lemma 2.3. Let n be a fixed positive integer. Then, for any non-negative integer x, the number of centered vertically symmetric rhombus tilings of a (2n, 2x + 1, 2n)-hexagon is equal to the Pfaffian of the skew-symmetric matrix N(x) = (N_{i,j}(x))_{1≤i,j≤2n+2} defined by

N_{i,j}(x) = M_{i,j}(x) = R_{i,j}(x) + T_{i,j}(x) − T_{j,i}(x),  1 ≤ i, j ≤ 2n + 1, (2.13)
N_{i,2n+1}(x) = \binom{2n + 2x + 1}{i} − \binom{n + x}{i} − \binom{n + x + 1}{i}, 1 ≤ i ≤ 2n,  (2.14)
N_{i,2n+2}(x) = M_{i,2n+2}(x) = \binom{x + n}{i − 1},  1 ≤ i ≤ 2n,  (2.15)
N_{2n+1,2n+2}(x) = 0,

where M_{i,j}(x), R_{i,j}(x) and T_{i,j}(x) are defined as in Lemma 2.2.

Remark 2.1. The matrices M(x) and N(x) differ only in the (2n+1)-st row and (2n+1)-st column.

Before we turn to the proof of these two lemmas, we provide an alternative expression for R_{i,j}(x) which has the advantage to be polynomial in x:

R_{i,j}(x) = ∑_{ℓ=0}^{i−1} \frac{j − i}{i}\binom{j − 1}{i − 1 − ℓ}\binom{ℓ + j}{ℓ}\binom{2x + 2n + 2}{ℓ + j + 1}.  (2.16)

The proof that the above relation is equivalent to (2.11) (for x ≥ 0) amounts to a routine computation (see e.g. the proof of Equation (4.13) in [7]). We should also notice that the equivalence of these two relations also holds for x < 0 once we interpret sums by

∑_{k=m}^{n−1} Expr(k) = \begin{cases}∑_{k=m}^{n−1} Expr(k), & if n > m, \\ 0, & if n = m, \\ − ∑_{k=n}^{m−1} Expr(k), & if n < m, \end{cases}  (2.17)

as in [7, Sec. 5]. With what we have said, the expression (2.11) for R_{i,j}(x) makes sense for negative integers x also and is equal to the expression in (2.16). We will make use of this fact later in this paper.

Proof of Lemma 2.2. Let T (F_{2n+1,2x,2n+1}^{∗}) denote the number of rhombus tilings of the region F_{2n+1,2x,2n+1}^{∗}. We apply Theorem 2.1. Let A, S and I be the list of points in ℤ^{2} defined by

A = (A_{1}, A_{2}, …, A_{2n+1}) with A_{i} = (−i, i),

S = (I_{n+x+1}) and I = (I_{1}, I_{2}, …, I_{2x+2n+1}) \ (I_{n+x+1}) with I_{j} = (−1, j). (2.18)

It follows from what we have said in Section 2.1 that

T (F_{2n+1,2x,2n+1}^{∗}) = ∑_{π∈𝔖_{2n+1}} #P^{nonint}(A_{π} → (S, I)),  (2.19)

where P^{nonint}(A_{π} → (S, I)) is defined as in Theorem 2.1. Therefore, by (2.6), in order to express T (H_{2n+1,2x}) in terms of a Pfaffian, it suffices to find a weight function that assigns sgn π to each family of paths in P^{nonint}(A_{π} → (S, I)) for π ∈ 𝔖_{2n+1}. To this end, it is convenient to slightly modify the list A (because of the possible occurrence of empty paths, as in Figure 4, which always have weight 1). Let Ã be defined by

Ã = (Ã_{1}, Ã_{2}, …, Ã_{2n+1}) with Ã_{1} = (−1, 0) and Ã_{i} = A_{i} = (−i, i) for i ≥ 2. (2.20)

It is easily checked that #P^{nonint}(A_{π} → (S, I)) = #P^{nonint}(Ã_{π} → (S, I)) for any π in 𝔖_{2n+1}. So, by (2.19), we have

T (F_{2n+1,2x,2n+1}^{∗}) = ∑_{π∈𝔖_{2n+1}} #P^{nonint}(Ã_{π} → (S, I)).  (2.21)

Let π = π_{1}π_{2} … π_{2n+1} be a permutation in 𝔖_{2n+1}, written in one-line notation, such that P^{nonint}(Ã_{π} → (S, I)) is non-empty. From the definition of the Ã_{i}’s and I_{j}’s, it is not difficult to see that the sequence π_{2}π_{3} ⋯ π_{2n+1} must be increasing, and thus the number of inversions of π, inv π, is equal to π_{1} − 1. This implies that, for any family (P_{1}, P_{2}, …, P_{2n+1}) in P^{nonint}(Ã_{π} → (S, I)), inv π is the number of paths P_{i} that end in a point I_{j} with j < n + x + 1. So, if w is a weight function on the edges of the lattice ℤ^{2} such that the weight of a path P from Ã_{i} to I_{j} satisfies

w(P) = \begin{cases}+1, & if j ≥ n + x + 1, \\ −1, & if j < n + x + 1, \end{cases}  (2.22)

we would obtain from (2.21), (2.4) and what we have said that

T (F_{2n+1,2x,2n+1}^{∗}) = ∑_{π∈𝔖_{2n+1}}(sgn π) GF [P^{nonint}(Ã_{π} → (S, I)],  (2.23)

where GF is the generating function with respect to the weight w, as defined in Section 2.2. Note that the construction of such a weight function w is easy: for instance, we may assign to each edge of the lattice ℤ^{2} the value 1 except for the edges {(−1, 0), (−1, 1)}, {(−2, j), (−1, j)} for 2 ≤ j < n + x + 1, and {(−1, n + x), (−1, n + x + 1)}, to which we assign the value −1. So, we may assume that (2.23) is true for some weight function w satisfying (2.22).

Let h(Ã_{i}, I_{j}) be defined as in (2.5). Then, by (2.22), we have h(Ã_{i}, I_{j}) = ϵ#P(Ã_{i} → I_{j}), where ϵ = −1 if j < n + x + 1 and ϵ = 1 otherwise, and where P(A → B) denotes the set of lattice paths from A to B, as earlier. In combination with the well-known counting formula for lattice paths with given starting and end point, this implies that

h(Ã_{i}, I_{j}) = (−1)^{χ(j<n+x+1)}\binom{j − 1}{i − 1},  (2.24)

where, as usual, for an assertion X, χ(X) = 1 if X is true and χ(X) = 0 otherwise. Combining (2.23) with Theorem 2.1, we see that

T (F_{2n+1,2x,2n+1}^{∗}) = Pf ( \begin{matrix}Q & H \\ −H^{t} & 0 \end{matrix} ) ,  (2.25)

where Q = (Q_{i,j})_{1≤i,j≤2n+1} is the matrix defined by

Q_{i,j} = _{∑_{1≤s<t≤2x+2n+1} ; s,t≠n+x+1}h(Ã_{i}, I_{s}) h(Ã_{j}, I_{t}) − h(Ã_{j}, I_{s}) h(Ã_{i}, I_{t}),  (2.26)

and H = (H_{i,1})_{1≤i≤2n+1} is the column vector defined by

H_{i,1} = h(Ã_{i}, I_{x+n+1}) = \binom{x + n}{i − 1},  (2.27)

where the last equality follows from (2.24). So, to complete the proof of the lemma, it suffices to show that the matrix entry Q_{i,j} in (2.26) is equal to the right-hand side of(2.9).

Let us define

P_{i,j}(s, t) = \binom{s − 1}{i − 1}\binom{t − 1}{j − 1} − \binom{s − 1}{j − 1}\binom{t − 1}{i − 1}.  (2.28)

Then, combining (2.26) with (2.24), we obtain

Q_{i,j} = ∑_{1≤s<t≤x+n} P_{i,j}(s, t) + ∑_{x+n+2≤s<t≤2x+2n+1} P_{i,j}(s, t) − ∑_{s=1}^{n+x} ∑_{t=n+x+2}^{2n+2x+1} P_{i,j}(s, t). (2.29)

By (2.28), the last sum in the preceding relation can be evaluated as follows:

∑_{s=1}^{n+x} ∑_{t=n+x+2}^{2n+2x+1} P_{i,j}(s, t) = ∑_{s=1}^{n+x} \binom{s − 1}{i − 1} ∑_{t=n+x+2}^{2n+2x+1} \binom{t − 1}{j − 1} − ∑_{s=1}^{n+x} \binom{s − 1}{j − 1} ∑_{t=n+x+2}^{2n+2x+1} \binom{t − 1}{i − 1}

\begin{matrix}= \binom{n + x}{i} (\binom{2n + 2x + 1}{j} − \binom{n + x + 1}{j}) \\ − \binom{n + x}{j} (\binom{2n + 2x + 1}{i} − \binom{n + x + 1}{i}) \end{matrix}  (2.30)

\begin{matrix}= \binom{n + x}{i}\binom{2n + 2x + 1}{j} − \binom{n + x}{j}\binom{2n + 2x + 1}{i} \\ + \frac{i − j}{n + x + 1}\binom{n + x + 1}{i}\binom{n + x + 1}{j}, \end{matrix}  (2.31)

where we used the well-known identity

∑_{ℓ=m}^{n} \binom{ℓ}{i} = \binom{n + 1}{i + 1} − \binom{m}{i + 1}  (2.32)

to obtain (2.30). Similarly, using (2.32), we can prove (for details, see e.g. [7, Eq. (4.10)], where the case M = 1 is treated) that

∑_{M≤s<t≤N} P_{i,j}(s, t) = ∑_{M≤s<t≤N} (\binom{s − 1}{i − 1}\binom{t − 1}{j − 1} − \binom{s − 1}{j − 1}\binom{t − 1}{i − 1})

= ∑_{t=M}^{N} \frac{j − i}{t}\binom{t}{i}\binom{t}{j} + \binom{N}{i}\binom{M − 1}{j} − \binom{N}{j}\binom{M − 1}{i}. (2.33)

Finally, after substituting (2.31) and (2.33) in (2.29), it is easily checked that the matrix entry Q_{i,j} is equal to the right-hand side of the relation (2.9). This finishes the proof. □

Proof of Lemma 2.3. Using the correspondence illustrated in Figure 4 and the same reasoning as in the proof of (2.21), we see that T (F_{2n,2x+1,2n}^{∗}), the number of tilings of the region F_{2n,2x+1,2n}^{∗}, is equal to the number of families (P_{1}, P_{2}, …, P_{2n}) of non-intersecting lattice paths, where for i = 1, 2, …, 2n, the path P_{i} runs from Ã_{i} to some I_{j}, with the additional condition that I_{n+x+1} must be an ending point of some path. Here, the Ã_{i}’s and I_{j}’s have the same meaning as in (2.20) and (2.18). To be able to use Theorem 2.1, we shall need to introduce a phantom vertex (see the remark after Theorem 3.1 in [29]) for the parity condition on p + q in Theorem 2.1 to be satisfied.

Let A′ = (A′_{1}, A′_{2}, …, A′_{2n+1}), S′ = (I′_{n+x+1}) and I′ = (I′_{1}, I′_{2}, …, I′_{2x+2n+2}) \ (I′_{n+x+1}) be the list of points in ℤ^{2} defined by

\begin{aligned}A′_{1} & = Ã_{1} = (−1, 0), A′_{i} = Ã_{i} = (−i, i) for 1 ≤ i ≤ 2n, A′_{2n+1} = (0, −1), \\ I′_{j} & = I_{j} = (−1, j) for 1 ≤ j ≤ 2x + 2n + 1, I′_{2x+2n+2} = A′_{2n+1} = (0, −1). \end{aligned} (2.34)

Then, from what we have said in the preceding paragraph it is not hard to show that

T (F_{2n,2x+1,2n}^{∗}) = ∑_{π∈𝔖_{2n+1}} #P^{nonint}(A′_{π} → (S′, I′)).  (2.35)

Let π = π_{1}π_{2} … π_{2n+1} be a permutation in 𝔖_{2n+1} such that P^{nonint}(A′_{π} → (S′, I′)) is non-empty. Then, from the definition of the A′_{i}’s and I′_{j}’s, it is not difficult to see that the sequence π_{2}π_{3} ⋯ π_{2n+1} must be increasing and π_{2n+1} = 2n + 1 (for, if (P_{1}, …, P_{2n+1}) ∈ P^{nonint}(A′_{π} → (S′, I′)), then P_{2n+1} must be the empty path from A′_{2n+1} to I′_{2x+2n+2}). Consequently, inv π is equal to π_{1} − 1. So, for any family (P_{1}, P_{2}, …, P_{2n+1}) in P^{nonint}(A′_{π} → (S′, I′)), it is also the number of paths P_{i} such that P_{i} ends at a point I′_{j} with 1 ≤ j < n + x + 1. In a way similar to the one in the proof of Lemma 2.2, one can find a weight function w′ on the edges of ℤ^{2} such that the weight of a path P from A′_{i} to I′_{j} satisfies

w′(P) = \begin{cases}+1, & if j ≥ n + x + 1, \\ −1, & if 1 ≤ j < n + x + 1. \end{cases}  (2.36)

We omit the details. It follows from (2.35), (2.4) and what we have said that

T (F_{2n,2x+1,2n}^{∗}) = ∑_{π∈𝔖_{2n+1}}(sgn π) GF [P^{nonint}(A′_{π} → (S′, I′))].  (2.37)

Similarly to (2.24), we have h(A′_{i}, I′_{j}) = ϵ#P(A′_{i} → I′_{j}), where ϵ = −1 if j < n + x + 1 and ϵ = 1 otherwise, whence

h(A′_{i}, I′_{j}) = \begin{cases}(−1)^{χ(j<n+x+1)}\binom{j−1}{i−1}, & if i ≠ 2n + 1 and j ≠ 2x + 2n + 2, \\ 1, & if (i, j) = (2n + 1, 2x + 2n + 2), \\ 0, & otherwise. \end{cases}  (2.38)

Combining (2.37) with Theorem 2.1 and (2.38), we obtain

T (F_{2n,2x+1,2n}^{∗}) = Pf ( \begin{matrix}Q & H \\ −H^{t} & 0 \end{matrix} ) ,  (2.39)

where Q = (Q_{i,j})_{1≤i,j≤2n+1} is the matrix defined by

Q_{i,j} = _{∑_{1≤s<t≤2x+2n+2} ; s,t≠n+x+1}h(A′_{i}, I′_{s}) h(A′_{j}, I′_{t}) − h(A′_{j}, I′_{s}) h(A′_{i}, I′_{t}),  (2.40)

and H = (H_{i,1})_{1≤i≤2n+1} is the column vector defined by

H_{i,1} = h(A′_{i}, I′_{x+n+1}) = χ(i ≠ 2n + 1)\binom{x + n}{i − 1},  (2.41)

where the last equality follows from (2.38).

Comparing (2.38) with (2.24), it is not hard to see that, for 1 ≤ i, j ≤ 2n, the righthand side of (2.40) is equal to the right-hand side of (2.26) (which was shown to be the right-hand side of (2.9)). Note that this can also be directly proved from the combinatorial interpretation of (2.26) and (2.40) (see e.g. Equation (3.1) in [29]). On the other hand, when 1 ≤ i ≤ 2n and j = 2n + 1, from (2.40) and (2.38) we infer

Q_{i,2n+1} = _{∑_{t=1}^{2x+2n+1} ; t≠n+x+1}h(A′_{i}, I′_{t}) = − ∑_{t=1}^{n+x} \binom{t − 1}{i − 1} + ∑_{t=n+x+2}^{2n+2x+1} \binom{t − 1}{i − 1},  (2.42)

which, by (2.32), simplifies to the right-hand side of (2.14). Summarizing, we have proved that the matrix in (2.39) is equal to the matrix N(x) described in the lemma. This finishes the proof. □

3. Proof of Theorem 1.2

Throughout this section, we assume that n is a (fixed) non-negative integer. From (1.2), it is easily checked that ST (2n + 1, 2x, 2n + 1) can be written in the form

ST (2n + 1, 2x, 2n + 1) = \frac{(x + \frac{1}{2})_{2n+1}}{(\frac{1}{2})_{2n+1}} ∏_{s=1}^{n} \frac{(2x + 2s)_{4n−4s+3}}{(2s)_{4n−4s+3}} .

This, combined with Lemma 2.2, implies that Theorem 1.2 is equivalent to the equation

Pf M(x) = \frac{1}{4} \frac{(2n + 2)!^{2} (2n)!}{(n + 1)!^{2} (4n + 1)!} ∏_{s=1}^{n} \frac{(2x + 2s)_{4n−4s+3}}{(2s)_{4n−4s+3}}

× (∑_{i=0}^{n} \frac{(−1)^{n−i}}{2n + 1 − 2i} \frac{(x + n + 1 − i)_{2i}}{(i!)^{2}} ) , (3.1)

where M(x) is the matrix defined in Lemma 2.2. We shall prove the latter formula.

An outline of the proof is as follows. In Section 3.1, we prove that Pf M(x) is a polynomial in x of degree at most 2n^{2} + 3n. Subsequently, in Section 3.2, we show that

Pf M(x) = (−1)^{n} Pf M(−2n − 1 − x).  (3.2)

Then, in Section 3.3, we argue that ∏_{s=1}^{n}(x + s)^{s} divides Pf M(x) as a polynomial in x, while in Section 3.4 we do the same for the product ∏_{s=1}^{n}(x + s + \frac{1}{2})^{s}. By (3.2), this implies that

(x + n + \frac{1}{2})^{n} ∏_{s=1}^{n−1} (x + s + \frac{1}{2})^{s} (x + 2n + 1 − s − \frac{1}{2})^{s} ∏_{s=1}^{n}(x + s)^{s}(x + 2n + 1 − s)^{s},

which simplifies to

2^{−2n^{2}−n} ∏_{s=1}^{n} (2x + 2s)_{4n−4s+3}  (3.3)

and is a polynomial of degree 2n^{2} + n, divides Pf M(x) as a polynomial in x. Altogether, this entails that

Pf M(x) = P (x) ∏_{s=1}^{n} (2x + 2s)_{4n−4s+3}  (3.4)

for some polynomial P (x) in x of degree at most 2n. Therefore, in order to prove (3.1), it remains to show that P (x) is equal to the polynomial K(x) defined by

K(x) = \frac{1}{4} \frac{(2n + 2)!^{2} (2n)!}{(n + 1)!^{2} (4n + 1)!} ∏_{s=1}^{n} \frac{1}{(2s)_{4n−4s+3}} (∑_{i=0}^{n} \frac{(−1)^{n−i}}{2n + 1 − 2i} \frac{(x + n + 1 − i)_{2i}}{(i!)^{2}} ) . (3.5)

Since P (x) and K(x) are polynomials in x of degree at most 2n, it suffices to show that P (x) = K(x) holds for 2n + 1 distinct values of x. In Section 3.5, we determine the evaluations of P (x) and K(x) at x = 0, −1, …, −n, which shows that P (x) = K(x) at x = 0, −1, …, −n. Since, by (3.4) and (3.2), P (x) = P (−2n − 1 − x), and, by (3.5), K(x) = K(−2n − 1 − x) for any x, this shows at the same time that P (x) = K(x) for x = −2n − 1, −2n, …, −n − 1. Altogether, we have found 2n + 2 values of x for which P (x) = K(x). This would complete the proof of (3.1).

3.1. Pf M(x) is a polynomial in x of degree at most 2n^{2} + 3n. By Lemma 2.2 and (2.16), the (i, j)-entry of M(x) is a polynomial in x of degree i + j if 1 ≤ i, j ≤ 2n + 1 and i ≠ j, and of degree i − 1 if 1 ≤ i ≤ 2n + 1 and j = 2n + 2. Moreover, M_{i,j}(x) = 0 if i = j. By the formal definition of a Pfaffian (see e.g. [29, Sec. 2]), this immediately shows that Pf M(x) is a polynomial in x. This also implies that in the defining expansion of the determinant det M(x) each nonzero term is a polynomial of degree

(∑_{i=1}^{2n+1} i) − 1 + (∑_{j=1}^{2n+1} j) − 1 = 4n^{2} + 6n.

Consequently, det M(x) is a polynomial of degree at most 4n^{2} + 6n. The claim then follows from (2.1).

3.2. Pf M(x) = (−1)^{n} Pf M(−2n − 1 − x). We shall transform, up to sign, M(x) into M(−2n − 1 − x) by a sequence of elementary row and column operations. More precisely, let B = (B_{i,j})_{1≤i,j≤2n+2} be the lower triangular matrix of size 2n + 2 defined by

B = ( \begin{matrix}& & & 0 \\ & (B_{i,j})\begin{matrix}1≤i≤2n+1 \\ 1≤j≤2n+1 \end{matrix} & & ⋮ \\ & & & 0 \\ 0 & ⋯ & 0 & −1 \end{matrix} ) , with B_{i,j} = \binom{i − 1}{j − 1} for 1 ≤ i, j ≤ 2n + 1, (3.6)

and let M^{(1)} = (M_{i,j}^{(1)})_{1≤i,j≤2n+2} be the skew-symmetric matrix (of size 2n + 2) defined

by M^{(1)} = B M(x) B^{t}. We claim that the (i, j)-entry in M^{(1)} is, up to the sign (−1)^{i+j}, the (i, j)-entry in M(−2n − 1 − x). Since det B = −1, by (2.2) we would obtain

Pf M^{(1)} = (det B)(Pf M(x)) = − Pf M(x),

and, on the other hand, by (2.3),

Pf M^{(1)} = (−1)^{1+2+···+(2n+2)} Pf M(−2n − 1 − x) = (−1)^{n+1} Pf M(−2n − 1 − x).

If we combine these two relations, this would lead to (3.2), as desired.

We now turn to the proof of the claim that M_{i,j}^{(1)} = (−1)^{i+j}M_{i,j}(−2n − 1 − x). By definition of the matrices M^{(1)} and B, we have

M_{i,j}^{(1)} = ∑_{a=1}^{i} ∑_{b=1}^{j} \binom{i − 1}{a − 1}\binom{j − 1}{b − 1}M_{a,b}(x), 1 ≤ i, j ≤ 2n + 1,  (3.7)

M_{i,2n+2}^{(1)} = − ∑_{a=1}^{i} \binom{i − 1}{a − 1}M_{a,2n+2}(x), 1 ≤ i ≤ 2n + 1.  (3.8)

Recall that, for 1 ≤ a, b ≤ 2n + 1, we have M_{a,b}(x) = R_{a,b}(x) + T_{a,b}(x) − T_{b,a}(x), where the R_{i,j}(x)’s and T_{i,j}(x)’s are given by (2.11) and (2.12). It was already shown in [7, Sec. 5, Step 1, Equations (5.5)–(5.10)] that

∑_{a=1}^{i} ∑_{b=1}^{j} \binom{i − 1}{a − 1}\binom{j − 1}{b − 1}R_{a,b}(x) = (−1)^{i+j}R_{i,j}(−2n − 1 − x).  (3.9)

On the other hand, using the expression (2.12), after a routine calculation we obtain

∑_{a=1}^{i} ∑_{b=1}^{j} \binom{i − 1}{a − 1}\binom{j − 1}{b − 1} T_{a,b}(x)

= ∑_{a=1}^{i} \binom{i − 1}{a − 1}\binom{2x + 2n + 1}{a} ∑_{b=1}^{j} \binom{j − 1}{b − 1} (\binom{x + n}{b} + \binom{x + n + 1}{b})

= (−1)^{i+j}\binom{−2x − 2n − 1}{i} (\binom{−n − x}{j} + \binom{−n − x − 1}{j})  (3.10)
= (−1)^{i+j} T_{i,j}(−2n − 1 − x),  (3.11)

where, to obtain (3.10), we used the identity

∑_{k≥0} \binom{L}{k − ϵ}\binom{M}{k} = \binom{L + M}{L + ϵ} = (−1)^{L+ϵ}\binom{−M − 1 + ϵ}{L + ϵ},  (3.12)

which follows from the Chu–Vandermonde summation formula. After substituting (2.9) in (3.7), it is immediate from (3.9) and (3.11) that M_{i,j}^{(1)} = (−1)^{i+j}M_{i,j}(−2n − 1 − x) for 1 ≤ i, j ≤ 2n + 1. Similarly, substituting (2.10) in (3.8), we obtain for 1 ≤ i ≤ 2n + 1 that

M_{i,2n+2}^{(1)} = − ∑_{a=1}^{i} \binom{i − 1}{a − 1}\binom{x + n}{a − 1} = (−1)^{i}\binom{−x − n − 1}{i − 1} = (−1)^{i}M_{i,2n+2}(−2n − 1 − x),

where the second equality follows again from (3.12) (specialized to ϵ = 0).

Summarizing, we have shown that M^{(1)} = ((−1)^{i+j}M_{i,j}(−2n − 1 − x))_{1≤i,j≤2n+2}, as desired. This finishes the proof of our claim.

3.3. ∏_{s=1}^{n}(x + s)^{s} divides Pf M(x). Let s be an integer with 1 ≤ s ≤ n. It is easily checked that,

for 2n − 2s + 2 ≤ a ≤ 2n + 1, the a-th row of the matrix M(−s) vanishes. (3.13)

Indeed, by Lemma 2.2, the entry in row a and column j of M(−s) equals

M_{a,j}(−s) = ∑_{t=1}^{2n−2s+1} \frac{j − a}{t}\binom{t}{a}\binom{t}{j} + \binom{2n − 2s + 1}{a} (\binom{n − s}{j} + \binom{n − s + 1}{j})

− \binom{2n − 2s + 1}{j} (\binom{n − s}{a} + \binom{n − s + 1}{a})

for 1 ≤ j ≤ 2n + 1, and M_{a,2n+2}(−s) = \binom{n−s}{a−1}. These entries are clearly zero if a > 2n − 2s + 1 since, for t = 1, …, 2n − 2s + 1, the binomial coefficients \binom{n−s}{a−1} and \binom{t}{a} vanish.

By (3.13), we have 2s linear combinations of the rows of the matrix M(x) that are linearly independent and vanish at x = −s. This, combined with the next lemma, yields the divisibility of Pf M(x) by (x + s)^{s}, as desired.

Lemma 3.1 ([20, Sec. 2]). Let A(x) be a skew-symmetric matrix with polynomial entries. A sufficient condition for (x − b)^{m} to divide Pf A(x) is that the dimension of the kernel of the matrix A(b) is at least 2m.

3.4. ∏_{s=1}^{n}(x + s + 1/2)^{s} divides Pf M(x). We first notice that some coefficients of the matrix M(x), when specialized to x = −s−1/2, 1 ≤ s ≤ n, have a relatively simple form. Namely, for 2n − 2s + 1 ≤ i ≤ 2n + 1 and j ≤ 2n + 1, we have

M_{i,j}(−s − 1/2) = −M_{j,i}(−s − 1/2) = −\binom{2n − 2s}{j} (\binom{n − s − \frac{1}{2}}{i} + \binom{n − s + \frac{1}{2}}{i}) .

(3.14)

Thus,

M_{i,j}(−s − 1/2) = 0 for 1 ≤ s ≤ n and 2n − 2s + 1 ≤ i, j ≤ 2n + 1.  (3.15)

Indeed, by (2.9), we have

M_{i,j}(−s − 1/2) = ∑_{t=1}^{2n−2s} \frac{j − i}{t}\binom{t}{i}\binom{t}{j} + \binom{2n − 2s}{i} (\binom{n − s − \frac{1}{2}}{j} + \binom{n − s + \frac{1}{2}}{j})

− \binom{2n − 2s}{j} (\binom{n − s − \frac{1}{2}}{i} + \binom{n − s + \frac{1}{2}}{i}) ,

and the binomial coefficients \binom{t}{i} vanish for t = 1, …, 2n − 2s and i ≥ 2n − 2s + 1.

3.4.1. The case 1 ≤ s ≤ n − 1. Suppose 1 ≤ s ≤ n − 1. We shall show that

(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1} · (row (2n − a) of M(−s − 1/2) )

− (n + s − \frac{1}{2}) \binom{2n}{a} · (row 2n of M(−s − 1/2) )

− a\binom{2n + 1}{a + 1} · (row (2n + 1) of M(−s − 1/2) ) = 0, (3.16)

for a = 1, …, 2s − 1, and that

∑_{i=1}^{2n−2s}(−2)^{i−1} · (row i of M(−s − 1/2) )

− 4^{n−s} \frac{(2n − 2s + 2)_{2s}}{(n − s + \frac{1}{2})_{2s−1}} · (row 2n of M(−s − 1/2) )

− 2n · 4^{n−s} \frac{(2n − 2s + 2)_{2s}}{(n − s + \frac{1}{2})_{2s}} · (row (2n + 1) of M(−s − 1/2) ) = 0. (3.17)

As these are 2s linear combinations of the rows of the matrix M(x) that are linearly independent and vanish at x = −s−1/2, by Lemma 3.1 this would lead to the divisibility of Pf M(x) by (x + s + \frac{1}{2})^{s}.

Proof of (3.16). Suppose 1 ≤ a ≤ 2s − 1. We have to show that, for 1 ≤ j ≤ 2n + 2, we have

(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1}M_{2n−a,j}(−s − 1/2) − (n + s − \frac{1}{2}) \binom{2n}{a}M_{2n,j}(−s − 1/2)

− a\binom{2n + 1}{a + 1}M_{2n+1,j}(−s − 1/2) = 0. (3.18)

(a) If 2n − 2s + 1 ≤ j ≤ 2n + 1, all the matrix entries in (3.18) are zero by (3.15). So, the identity is clearly true.

(b) Suppose 1 ≤ j ≤ 2n − 2s. By substituting (3.14) in (3.18), we obtain the relation

(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1} (\binom{n − s − \frac{1}{2}}{2n − a} + \binom{n − s + \frac{1}{2}}{2n − a})

− (n + s − \frac{1}{2}) \binom{2n}{a} (\binom{n − s − \frac{1}{2}}{2n} + \binom{n − s + \frac{1}{2}}{2n})

− a\binom{2n + 1}{a + 1} (\binom{n − s − \frac{1}{2}}{2n + 1} + \binom{n − s + \frac{1}{2}}{2n + 1}) = 0, (3.19)

as a routine verification shows.

(c) Suppose j = 2n + 2. By (2.10), (3.18) reduces to the relation

(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1}\binom{n − s − \frac{1}{2}}{2n − a − 1} − (n + s − \frac{1}{2}) \binom{2n}{a}\binom{n − s − \frac{1}{2}}{2n − 1}

− a\binom{2n + 1}{a + 1}\binom{n − s − \frac{1}{2}}{2n} = 0, (3.20)

which is again seen by a routine verification.

This finishes the proof of (3.16). □

Proof of (3.17). We have to show that, for 1 ≤ j ≤ 2n + 2, we have

∑_{i=1}^{2n−2s}(−2)^{i−1}M_{i,j}(−s − 1/2) = 4^{n−s} \frac{(2n − 2s + 2)_{2s}}{(n − s + \frac{1}{2})_{2s−1}} M_{2n,j}(−s − 1/2)

+ 2n · 4^{n−s} \frac{(2n − 2s + 2)_{2s}}{(n − s + \frac{1}{2})_{2s}} M_{2n+1,j}(−s − 1/2). (3.21)

(a) Suppose j = 2n + 2. Then, using the expression (2.10), it is easily checked that the right-hand side of (3.21) is zero (when specialized to j = 2n + 2), and thus (3.21) reduces to the relation

∑_{i=0}^{2n−2s−1}(−2)^{i}\binom{n − s − \frac{1}{2}}{i} = 0.  (3.22)

Reversing the order of summation over i (that is, we replace i by 2n − 2s − 1 − i), the left-hand side of (3.22) can be written using the standard hypergeometric notation

pF_{q}[\begin{matrix}a_{1}, …, a_{p} \\ b_{1}, …, b_{q} \end{matrix}; z] = ∑_{n≥0} \frac{(a_{1})_{n} ⋯ (a_{p})_{n}}{(b_{1})_{n} ⋯ (b_{q})_{n}} \frac{z^{n}}{n!}

as

(−2)^{2n−2s−1}\binom{n − s − \frac{1}{2}}{2n − 2s − 1}_{2}F_{1}[\begin{matrix}1, −2n + 2s + 1 \\ −n + s + \frac{3}{2} \end{matrix}; \frac{1}{2}] .

This is indeed zero (recall that 1 ≤ s ≤ n − 1) by means of Gauß’ second _{2}F_{1}-summation (cf. [30, (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{cases}0, & if N is an odd non-negative integer, \\ \begin{matrix}(\frac{1}{2}) & _{N/2} \\ (\frac{1−a}{2}) & _{N/2} \end{matrix} , & if N is an even non-negative integer. \end{cases}

(b) Suppose 2n − 2s + 1 ≤ j ≤ 2n + 1. Then, using the expressions (3.14) and (3.15) for the matrix entries in the sum in (3.21), it is easily checked that the right-hand side of (3.21) vanishes so that (3.21) reduces to the identity

∑_{i=1}^{2n−2s}(−2)^{i−1} (\binom{n − s − \frac{1}{2}}{j} + \binom{n − s + \frac{1}{2}}{j}) \binom{2n − 2s}{i} = 0,

which is an immediate consequence of the binomial theorem.

(c) Suppose 1 ≤ j ≤ 2n − 2s. Then, by (2.9), the left-hand side of (3.21) is

∑_{i=1}^{2n−2s}(−2)^{i−1}M_{i,j}(−s − 1/2) = ∑_{i=1}^{2n−2s}(−2)^{i−1} ∑_{t=1}^{2n−2s} \frac{j − i}{t}\binom{t}{i}\binom{t}{j}

+ (\binom{n − s − \frac{1}{2}}{j} + \binom{n − s + \frac{1}{2}}{j}) ∑_{i=1}^{2n−2s}(−2)^{i−1}\binom{2n − 2s}{i}

− \binom{2n − 2s}{j} ∑_{i=1}^{2n−2s}(−2)^{i−1} (\binom{n − s − \frac{1}{2}}{i} + \binom{n − s + \frac{1}{2}}{i}) . (3.23)

The first sum in (3.23) is equal to \binom{2n−2s}{j}. This can be deduced from the formula

∑_{i=1}^{N}(−2)^{i−1} ∑_{t=1}^{N} \frac{j − i}{t}\binom{t}{i}\binom{t}{j} = \frac{1 + (−1)^{N}}{2} \binom{N}{j},  (3.24)

which is valid for any non-negative integers N and j. For N even, (3.24) was proved in [7, proof of (5.21)]. The proof for odd N is similar to the case of even N and involves only elementary manipulations. It is thus left to the reader.

By the binomial theorem, the second sum in (3.23) vanishes. Moreover, the last sum in (3.23) simplifies to

∑_{i=1}^{2n−2s}(−2)^{i−1} (\binom{n − s − \frac{1}{2}}{i} + \binom{n − s + \frac{1}{2}}{i}) = 1 − 4^{n−s}\binom{n − s − \frac{1}{2}}{2n − 2s}.  (3.25)

This immediately follows from the telescoping equation

(−2)^{i−1} (\binom{n − s − \frac{1}{2}}{i} + \binom{n − s + \frac{1}{2}}{i}) = G(i + 1) − G(i),

with G(i) = −(−2)^{i−1}\binom{n−s− \frac{1}{2}}{i−1}. Finally, replacing the sums in (3.23) by their evaluated forms, we arrive at

∑_{i=1}^{2n−2s}(−2)^{i−1}M_{i,j}(−s − 1/2) = 4^{n−s}\binom{2n − 2s}{j}\binom{n − s − \frac{1}{2}}{2n − 2s}.  (3.26)

On the other hand, by (3.14), the right-hand side of (3.21) is equal to

− 4^{n−s} \frac{(2n − 2s + 2)_{2s}}{(n − s + \frac{1}{2})_{2s−1}} \binom{2n − 2s}{j} (\binom{n − s − \frac{1}{2}}{2n} + \binom{n − s + \frac{1}{2}}{2n})

− 2n4^{n−s} \frac{(2n − 2s + 2)_{2s}}{(n − s + \frac{1}{2})_{2s}} \binom{2n − 2s}{j} (\binom{n − s − \frac{1}{2}}{2n + 1} + \binom{n − s + \frac{1}{2}}{2n + 1}) .

Therefore, to prove that (3.21) holds for 1 ≤ j ≤ 2n − 2s, it suffices to show that the above expression is equal to the right-hand side of (3.26). This amounts to a routine verification.

This concludes the proof of (3.17). □

3.4.2. The case s = n. From (3.15), we see that all the coefficients of the i-th row, 1 ≤ i ≤ 2n + 1, of the matrix M(−n − 1/2) are zero except its last coefficient M_{i,2n+2}(−n − 1/2) (which is, by (2.10), equal to \binom{−1/2}{i−1}). It is then immediate to find 2n linear combinations of the rows of the matrix M(−n − 1/2) that are linearly independent and vanish. For instance, for a = 1, …, 2n, we have

(row a of M(−n − 1/2) ) − \frac{M_{a,2n+2}(−n − 1/2)}{M_{a+1,2n+2}(−n − \frac{1}{2})} · (row (a + 1) of M(−n − 1/2)) = 0.

This implies divisibility of Pf M(x) by (x + n + \frac{1}{2})^{n}.

3.5. P (x) = K(x) at x = 0, −1, …, −n. Let σ be a given integer with 0 ≤ σ ≤ n. It is not too hard to evaluate the polynomial K(x), defined by (3.5), at x = −σ. Indeed, using the Pfaff–Saalschütz summation (cf. [30, (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}} ,  (3.27)

where N is a non-negative integer, it is easily checked (see [5, Eq. (5.26)]) that

∑_{i=0}^{n} \frac{(−1)^{n−i}}{2n + 1 − 2i} \frac{(n − σ + 1 − i)_{2i}}{i!^{2}} = (−1)^{n+1} \frac{(n + \frac{3}{2})_{n−σ}}{2 (−n − \frac{1}{2})_{n+1−σ}} , 0 ≤ σ ≤ n. (3.28)

By inserting the latter identity in (3.5), after some simplification we arrive at

K(−σ) = (−1)^{σ} \frac{(4n − 2σ + 1)! (2σ)! (2n)!}{(2n − σ)! σ!(4n + 1)!} ∏_{s=1}^{n} \frac{(2s − 1)!}{(4n + 2 − 2s)!}, 0 ≤ σ ≤ n. (3.29)

The evaluation of P (x) at x = −σ is much more delicate. The polynomial P (x) is defined by means of (3.4). Since the product on the right-hand side of (3.4) is zero for x = −σ, 1 ≤ σ ≤ n, we should write (3.4) in the form

P (x) = \frac{2^{−σ}}{(x + σ)^{σ}} Pf M(x) _{∏_{s=1}^{n} ; s≠σ}(2x + 2s)^{−s} ∏_{s=1}^{n}(2x + 4n + 2 − 2s)^{−s}

× ∏_{s=1}^{n} (2x + 2s + 1)^{−s} ∏_{s=1}^{n−1} (2x + 4n + 1 − 2s)^{−s} ,

and subsequently specialize x = −σ. After some manipulation, we arrive at

P (−σ) = \frac{2^{−σ} ∏_{s=1}^{n−σ}(2s − 1)!}{∏_{s=1}^{σ−1}(2s)! ∏_{s=n−σ+1}^{2n−σ}(2s)!} (\frac{1}{(x + σ)^{σ}} Pf M(x)) |_{x=−σ}.  (3.30)

To evaluate (x + σ)^{−σ} Pf M(x) at x = −σ, we shall use the following lemma due to Ciucu and the second author who used it in a similar context.

Lemma 3.2 ([7, Lemma 11]). Let N, a, b be non-negative integers with a < b ≤ N, where N and b−a are even. Let A = (A_{i,j})_{1≤i,j≤N} be a skew-symmetric matrix with the following properties:

(1) The entries of A are polynomials in x.

(2) The entries in rows a + 1, a + 2, …, b (and, hence, also in the corresponding

columns) are divisible by x + s. Then

(\frac{1}{(x + s)^{(b−a)/2}} Pf A) |_{x=−s} = Pf Ã · Pf S,

where Ã is the matrix which arises from A by deleting rows and columns a+1, a+2, …, b and subsequently specializing x = −s, and

S = ((\frac{1}{x + s}A_{i,j}) |_{x=−s})_{a+1≤i,j≤b} .

Let σ be a given integer with 1 ≤ σ ≤ n. It follows from (3.13) that for 2n − 2σ + 2 ≤ i ≤ 2n + 1 the coefficients of the i-th row of the matrix M(x) are divisible by (x + σ). Applying Lemma 3.2, we obtain

(\frac{1}{(x + σ)^{σ}} Pf M(x)) |_{x=−σ} = Pf M̃ · Pf S,  (3.31)

where M̃ = (M̃_{i,j})_{1≤i,j≤2n−2σ+2} is the skew-symmetric matrix of size 2n − 2σ + 2 defined by

\begin{aligned}M̃_{i,j} & = M_{i,j}(−σ), 1 ≤ i, j ≤ 2n − 2σ + 1, \\ M̃_{i,2n−2σ+2} & = M_{i,2n+2}(−σ), 1 ≤ i ≤ 2n − 2σ + 1, \end{aligned}  (3.32)

and S = (S_{i,j})_{1≤i,j≤2σ} is the skew-symmetric matrix of size 2σ defined by

S = (( \frac{1}{x + σ} M_{i,j}(x)) |_{x=−σ} )_{2n−2σ+2≤i,j≤2n+1} .  (3.33)

We point out that (3.31) also holds for σ = 0 once we interpret the Pfaffian of an empty matrix (i.e., the Pfaffian of S) as 1. In particular, under this convention, the arguments below can be used for 0 ≤ σ ≤ n, that is, including σ = 0.

We shall prove that Pf M̃ = 1 and

Pf S = (−1)^{σ}2^{σ} (∏_{i=1}^{2σ}(2n − 2σ + i)!) (∏_{i=1}^{σ} \frac{(2i − 1)!}{(4n − 2σ + 2i + 1)!}) .  (3.34)

If we substitute these values for Pf M̃ and Pf S in (3.31), and then insert the resulting equation in (3.30), after some simplification we would arrive at

P (−σ) = (−1)^{σ} \frac{∏_{s=2n−2σ+1}^{2n} s! ∏_{s=1}^{σ}(2s − 1)! ∏_{s=1}^{n−σ}(2s − 1)!}{∏_{s=1}^{σ−1}(2s)! ∏_{s=n+1}^{2n−σ}(2s)! ∏_{s=0}^{σ−1}(4n + 1 − 2s)!}, 0 ≤ σ ≤ n. (3.35)

Then, a routine comparison of (3.35) with (3.29) would show that P (x) = K(x) at x = 0, −1, …, −n, as desired. So, to complete our proof, it remains to establish the claimed evaluations of Pf M̃ and Pf S.

Evaluation of Pf M̃. If we compare the matrix M̃ defined by (3.32) with the matrix M(x) in Lemma 2.2, then we see that M̃ is equal to the matrix M(x) in Lemma 2.2 with n replaced by n − σ and with x = 0. By Lemma 2.2, this implies that Pf M̃ is equal to the number of centered vertically symmetric tilings of a (2(n−σ)+1, 0, 2(n−σ)+1)-hexagon. In a tiling of such a hexagon, all rhombi are forced, and trivially the unique tiling of such a hexagon is centered and symmetric. Consequently, we have Pf M̃ = 1.

Evaluation of Pf S. By (3.33) and (2.9), the (i, j)-entry of the matrix S satisfies

S_{i,j} = \frac{R_{2N+1+i,2N+1+j}(x)}{x + σ} + \frac{T_{2N+1+i,2N+1+j}(x)}{x + σ} − \frac{T_{2N+1+j,2N+1+i}(x)}{x + σ}|_{x=−σ},

where we have set N = n − σ. Using expression (2.16) for the R_{i,j}’s and (2.12) for the T_{i,j}’s, after a routine calculation we arrive at

S_{i,j} = 2 · ∑_{ℓ=0}^{i+2n−2σ}(−1)^{ℓ+j+1} \frac{j − i}{i + 2n − 2σ + 1}\binom{j + 2n − 2σ}{i + 2n − 2σ − ℓ}

· \binom{ℓ + j + 2n − 2σ + 1}{ℓ}\frac{(2n − 2σ + 2)! (ℓ + j − 1)!}{(ℓ + j + 2n − 2σ + 2)!}. (3.36)

To derive the above equation, we used the following relations whose proof is left to the reader: for r, t with r ≥ 1 and t ≥ 0, and ϵ = 1, 2, we have

lim_{x→−σ} \frac{1}{x + σ} \binom{2x + 2n + t}{r + 2n − 2σ + t} = (−1)^{r−1}2 \frac{(2n − 2σ + t)! (r − 1)!}{(r + 2n − 2σ + t)!},
lim_{x→−σ} \binom{x + n + ϵ}{r + 2n − 2σ + 1} = 0.

Lemma 3.3. For integers a, i, j with a ≥ −1 and i, j ≥ 1, we have

∑_{ℓ=0}^{i+a}(−1)^{ℓ+j+1} \frac{j − i}{i + a + 1}\binom{j + a}{i + a − ℓ}\binom{ℓ + j + a + 1}{ℓ}\frac{(a + 2)! (ℓ + j − 1)!}{(ℓ + j + a + 2)!}

= (−1)^{i+j} \frac{(j − i) (a + i)! (a + j)!}{(2a + i + j + 2)!}.

The above result was proved in the particular case a = 2n − 2σ − 1 in [7, p. 277]. Since the arguments in [7, p. 277] can be used in the same way to prove Lemma 3.3, we omit the proof details. Combining the preceding lemma with (3.36), we arrive at

S_{i,j} = (−1)^{i+j} \frac{2 (j − i) (2n − 2σ + i)! (2n − 2σ + j)!}{(4n − 4σ + i + j + 2)!}.  (3.37)

Consequently, we have

Pf_{1≤i,j≤2σ}(S_{i,j}) = (−1)^{σ}2^{σ} (∏_{i=1}^{2σ}(2n − 2σ + i)!) Pf_{1≤i,j≤2σ} (\frac{j − i}{(4n − 4σ + i + j + 2)!}) ,

which simplifies to (3.34), as desired, by the Pfaffian evaluation

Pf_{0≤i,j≤2k−1} (\frac{(j − i)}{(b + i + j)!}) = ∏_{i=0}^{k−1} \frac{(2i + 1)!}{(b + 2k + 2i − 1)!}, k ≥ 1.  (3.38)

Note that the above equation is a slight variation of a Pfaffian evaluation due to Mehta and Wang (see [7, Cor. 10]). This completes the proof of (3.34).

4. Proof of Theorem 1.3

Again, throughout this section, we assume that n is a (fixed) positive integer. From (1.2), it is easily checked that ST (2n, 2x + 1, 2n) can be written in the form

ST (2n, 2x + 1, 2n) = \frac{(x + 1)_{2n}}{(\frac{1}{2})_{2n}} ∏_{s=1}^{n} \frac{(2x + 1 + 2s)_{4n−4s+1}}{(2s)_{4n−4s+1}} .

This, combined with Lemma 2.3, leads to the following reformulation of Theorem 1.3:

Pf N(x) = \frac{2^{5n−1}}{n! (4n)!} (x + 1)_{2n} ∏_{s=2}^{n} \frac{(2x + 2s)_{4n−4s+3}}{(2s)_{4n−4s+3}} U_{n}(x),  (4.1)

where N(x) is the matrix defined in Lemma 2.3 and U_{n}(x) is defined by (1.4). Our proof of (4.1) is, in spirit, quite similar to the proof of (3.1).

First, with exactly the same kind of reasoning as used in Section 3.1, it is easily seen that Pf N(x) is a polynomial in x of degree at most 2n^{2} + n − 1. We omit the details. In Section 4.1, we prove that

Pf N(x) = (−1)^{n+1} Pf N(−2n − 1 − x).  (4.2)

In Sections 4.2 and 4.3, we show that ∏_{s=1}^{n}(x + s)^{s} and ∏_{s=1}^{n−1}(x + s + \frac{3}{2})^{s} divide Pf N(x) as a polynomial in x. This, combined with (4.2), implies that

(x + n + \frac{1}{2})^{n−1} ∏_{s=1}^{n−2} (x + s + \frac{3}{2})^{s} (x + 2n + 1 − s − \frac{3}{2})^{s} ∏_{s=1}^{n}(x + s)^{s}(x + 2n + 1 − s)^{s},

which is equal to

2^{−2n^{2}+3n−1} (x + 1)_{2n} ∏_{s=2}^{n} (2x + 2s)_{4n−4s+3}  (4.3)

and is a polynomial of degree 2n^{2}−n+1, divides Pf N(x) as a polynomial in x. Altogether, we are led to the formula

Pf N(x) = T (x) (x + 1)_{2n} ∏_{s=2}^{n} (2x + 2s)_{4n−4s+3} ,  (4.4)

for some polynomial T (x) in x of degree at most 2n−2. Therefore, in order to prove (4.1), it remains to show that T (x) is equal to the polynomial L(x) defined by

L(x) = \frac{2^{5n−1}}{n! (4n)!} ∏_{s=2}^{n} \frac{1}{(2s)_{4n−4s+3}} U_{n}(x),  (4.5)

with U_{n}(x) given by (1.4). Since T (x) and L(x) are polynomials in x of degree at most 2n − 2, it suffices to show that T (x) = L(x) holds for 2n − 1 distinct values of x. In Section 4.4, we determine the evaluations of T (x) and L(x) at x = −1, …, −n, which shows that T (x) = L(x) at x = −1, …, −n. Since, by (4.4) and (4.2), T (x) = T (−2n − 1 − x) and, by (4.5), L(x) = L(−2n − 1 − x) for any x, this shows at the same time that T (x) = L(x) for x = −2n, −2n + 1, …, −n − 1. Altogether, this yields 2n values of x for which T (x) = L(x). This would complete the proof of (4.1).

4.1. Pf N(x) = (−1)^{n+1} Pf N(−2n−1−x). The proof is quite similar to the proof of (3.2) and requires only slight changes. Let B̃ be the lower triangular matrix of size 2n+2 defined by

B̃ = ( \begin{matrix}(B_{i,j})\begin{matrix}1≤i≤2n \\ 1≤j≤2n \end{matrix} & 0 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & −1 \end{matrix} ) , with B_{i,j} = \binom{i − 1}{j − 1} for 1 ≤ i, j ≤ 2n, (4.6)

and let N^{(1)} be the skew-symmetric matrix (of size 2n + 2) defined by N^{(1)} = B̃ N(x) B̃^{t}.

We claim that the (i, j)-entry in N^{(1)} is, up to the sign (−1)^{i+j}, the (i, j)-entry in N(−2n − 1 − x). First, from Remark 2.1, the definition of N^{(1)} and what we have proved in Section 3.2, we have

N_{i,j}^{(1)} = M_{i,j}^{(1)} = (−1)^{i+j}M_{i,j}(−2n − 1 − x) = (−1)^{i+j}N_{i,j}(−2n − 1 − x) if i, j ≠ 2n + 1,

where M^{(1)} is the matrix defined in Section 3.2. Furthermore, by definition of the matrices N^{(1)} and B̃ and (2.14), for 1 ≤ i ≤ 2n we have

N_{i,2n+1}^{(1)} = − ∑_{a=1}^{i} \binom{i − 1}{a − 1}N_{a,2n+2}(x)

= ∑_{a=1}^{i} \binom{i − 1}{a − 1} (\binom{x + n}{a} + \binom{x + n + 1}{a} − \binom{2x + 2n + 1}{a}) ,

which simplifies, by Chu–Vandermonde summation (see e.g. (3.12)) and (2.14), to

N_{i,2n+1}^{(1)} = (−1)^{i} (\binom{−x − n}{i} + \binom{−x − n − 1}{i} − \binom{−2x − 2n − 1}{i})
= (−1)^{i+1}N_{i,2n+1}(−2n − 1 − x).

Summarizing, we have shown that N_{i,j}^{(1)} = (−1)^{i+j}N_{i,j}(−2n − 1 − x) for all i, j. With exactly the same reasoning used in Section 3.2, this leads to (4.2).

4.2. ∏_{s=1}^{n}(x + s)^{s} divides Pf N(x). Let s be an integer with 1 ≤ s ≤ n. We claim that,

for 2n − 2s + 2 ≤ a ≤ 2n, the a-th row of the matrix N(−s) is zero,  (4.7)

and that

∑_{i=1}^{2n−2s+1}(−1)^{i−1} (2^{i−1} − \binom{i − 1}{n − s}) · (row i of N(−s)) − (row (2n + 1) of N(−s) ) = 0.

(4.8)

As these are 2s linear combinations of the rows of the matrix N(x) that are linearly independent and vanish at x = −s, this implies divisibility of Pf N(x) by (x + s)^{s}.

Proof of (4.7). Suppose 2n − 2s + 2 ≤ a ≤ 2n. It follows from Remark 2.1 and (3.13) that N_{a,j}(−s) = 0 if 1 ≤ j ≤ 2n + 2 and j ≠ 2n + 1. Moreover, by (2.14), we have

N_{a,2n+1}(−s) = \binom{2n − 2s + 1}{a} − \binom{n − s}{a} − \binom{n − s + 1}{a},

which is clearly zero since a > 2n − 2s + 1 ≥ n − s + 1. □

Proof of (4.8). We have to show that, for 1 ≤ j ≤ 2n + 2, there holds

∑_{i=1}^{2n−2s+1}(−2)^{i−1}N_{i,j}(−s) − ∑_{i=1}^{2n−2s+1}(−1)^{i−1}\binom{i − 1}{n − s}N_{i,j}(−s) − N_{2n+1,j}(−s) = 0. (4.9)

(a) Suppose j = 2n + 2. By (2.15), we have N_{i,2n+2}(−s) = \binom{n−s}{i−1} if i ≤ n − s + 1, and it equals 0 otherwise. Therefore, when j = 2n + 2, the left-hand side of (4.9) simplifies to

∑_{i=1}^{n−s+1}(−2)^{i−1}\binom{n − s}{i − 1} − ∑_{i=1}^{n−s+1}(−1)^{i−1}\binom{i − 1}{n − s}\binom{n − s}{i − 1} = (−1)^{n−s} − (−1)^{n−s} = 0,

as desired. That the first (respectively second) sum in the above relation is equal to (−1)^{n−s} is immediate from the binomial theorem (respectively from the fact that the term with index i = n − s + 1 is the only term which is nonzero).

(b) Suppose j = 2n + 1. Using the expression (2.14) for the matrix entry N_{i,2n+1}(−s), and noticing that N_{2n+1,2n+1}(−s) = 0, we see that (4.9) reduces to

∑_{i=1}^{2n−2s+1}(−1)^{i−1} (2^{i−1} − \binom{i − 1}{n − s}) (\binom{2n − 2s + 1}{i} − \binom{n − s}{i} − \binom{n − s + 1}{i}) = 0,

which is immediate from the summations

∑_{i=1}^{2n−2s+1}(−2)^{i−1}\binom{2n − 2s + 1}{i} = ∑_{i=1}^{2n−2s+1}(−2)^{i−1} (\binom{n − s}{i} + \binom{n − s + 1}{i}) = 1, (4.10)

∑_{i=1}^{2n−2s+1}(−1)^{i−1}\binom{i − 1}{n − s} (\binom{n − s}{i} + \binom{n − s + 1}{i}) = (−1)^{n−s},  (4.11)

∑_{i=1}^{2n−2s+1}(−1)^{i−1}\binom{i − 1}{n − s}\binom{2n − 2s + 1}{i} = (−1)^{n−s}.  (4.12)

Indeed, the two sums in (4.10) are easily evaluated by the binomial theorem. The sum in (4.11) has only one term which is nonzero, the term with index i = n − s + 1, which is equal to (−1)^{n−s}, whence (4.11). In the sum in (4.12), the terms with index i between 1 and n − s vanish. By shifting the summation index i by n − s + 1 (that is, we replace i by i + n − s + 1) and then using the relation (−1)^{i}\binom{i+n−s}{n−s} = \binom{−n+s−1}{i}, this sum becomes

(−1)^{n−s} ∑_{i=0}^{n−s} \binom{−n + s − 1}{i}\binom{2n − 2s + 1}{n − s − i},

which, by the Chu–Vandermonde summation formula, is equal to (−1)^{n−s}\binom{n−s}{n−s} = (−1)^{n−s}.

(c) Suppose 2n − 2s + 2 ≤ j ≤ 2n. From (4.7) and the skew-symmetry of N(−s), the j-th column of N(−s) is zero, and thus the relation (4.9) is clearly true.

(d) Suppose 1 ≤ j ≤ 2n − 2s + 1. Using the expressions (2.13) and (2.14) for the corresponding matrix entries, we see that (4.9) reduces to

∑_{i=1}^{2n−2s+1}(−1)^{i−1} (2^{i−1} − \binom{i − 1}{n − s}) (R_{i,j}(−s) + T_{i,j}(−s) − T_{j,i}(−s))

+ \binom{2n − 2s + 1}{j} − \binom{n − s}{j} − \binom{n − s + 1}{j} = 0, (4.13)

where R_{i,j}(x) and T_{i,j}(x) are defined as in (2.11) and (2.12).

From the expression (2.12) for T_{i,j}(x) and (4.10)–(4.12), we have

∑_{i=1}^{2n−2s+1}(−1)^{i−1} (2^{i−1} − \binom{i − 1}{n − s}) (T_{i,j}(−s) − T_{j,i}(−s))

= (1 − (−1)^{n−s}) (\binom{n − s}{j} + \binom{n − s + 1}{j} − \binom{2n − 2s + 1}{j}). (4.14)

From (3.24), we have

∑_{i=1}^{2n−2s+1}(−2)^{i−1}R_{i,j}(−s) = ∑_{i=1}^{2n−2s+1}(−2)^{i−1} ∑_{t=1}^{2n−2s+1} \frac{j − i}{t}\binom{t}{j}\binom{t}{i} = 0.  (4.15)

From the expression (2.11) for R_{i,j}(x), we have

∑_{i=1}^{2n−2s+1}(−1)^{i−1}\binom{i − 1}{n − s}R_{i,j}(−s)

= ∑_{i=1}^{2n−2s+1}(−1)^{i−1}\binom{i − 1}{n − s} ∑_{t=1}^{2n−2s+1} \binom{t − 1}{j − 1}\binom{t}{i} − \binom{t}{j}\binom{t − 1}{i − 1}

= ∑_{t=1}^{2n−2s+1} \binom{t − 1}{j − 1} ∑_{i=1}^{t}(−1)^{i−1}\binom{t}{i}\binom{i − 1}{n − s} − ∑_{t=1}^{2n−2s+1} \binom{t}{j} ∑_{i=1}^{t}(−1)^{i−1}\binom{t − 1}{i − 1}\binom{i − 1}{n − s},

where the last equality follows by interchanging the sums over i and t. In the latter expression, the first inner sum is zero if t ≤ n − s (because of the binomial coefficient \binom{i−1}{n−s}), and it is equal to (−1)^{n−s} if t > n − s (see (4.12) and its proof). The second inner sum is (−1)^{n−s} if t = n − s + 1, and it equals 0 otherwise, as can be checked by using the relation

\binom{t − 1}{i − 1}\binom{i − 1}{n − s} = \binom{t − 1}{n − s}\binom{t − 1 − (n − s)}{i − 1 − (n − s)}

and the binomial theorem.

Altogether, this implies that

∑_{i=1}^{2n−2s+1}(−1)^{i−1}\binom{i − 1}{n − s}R_{i,j}(−s) = (−1)^{n−s} ∑_{t=n−s+1}^{2n−2s+1} \binom{t − 1}{j − 1} − (−1)^{n−s}\binom{n − s + 1}{j}

= (−1)^{n−s} (\binom{2n − 2s + 1}{j} − \binom{n − s}{j} − \binom{n − s + 1}{j}) ,

where the last equality follows from (2.32). This, combined with (4.14) and (4.15), leads to (4.13). This completes the proof of (4.9). □

4.3. ∏_{s=1}^{n−1}(x + s + 3/2)^{s} divides Pf N(x). Let s be an integer with 1 ≤ s ≤ n − 1. We claim that, for a = 1, 2, …, 2s, we have

(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1} · (row (2n − 1 − a) of N(−s − 3/2) )

− (n + s − \frac{1}{2}) \binom{2n − 1}{a} · (row 2n − 1 of N(−s − 3/2) )

− a\binom{2n}{a + 1} · (row (2n) of N(−s − 3/2) ) = 0. (4.16)

Since these are 2s linear combinations of the rows of the matrix N(x) that are linearly independent and vanish at x = −s−3/2, this implies divisibility of Pf N(x) by (x+s+ \frac{3}{2})^{s}.

Proof of (4.16). Suppose 1 ≤ a ≤ 2s. We have to show that, for 1 ≤ j ≤ 2n + 2,

(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1}N_{2n−1−a,j}(−s − 3/2)

− (n + s − \frac{1}{2}) \binom{2n − 1}{a}N_{2n−1,j}(−s − 3/2) − a\binom{2n}{a + 1}N_{2n,j}(−s − 3/2) = 0. (4.17)

(a) Suppose 2n + 1 ≤ j ≤ 2n + 2. It follows from (2.14) that

N_{i,2n+1}(−s − 3/2) = −\binom{n − s − 3/2}{i} − \binom{n − s − 1/2}{i} if 2n − 2s − 1 ≤ i ≤ 2n.

Furthermore, by (2.15), we have N_{i,2n+2}(−s−3/2) = \binom{n−s−3/2}{i−1}. Therefore, equation (4.17) when specialized to j = 2n + 1 and j = 2n + 2 reduces to the identities

\begin{matrix}(−1)^{a+1}\binom{n + s − \frac{1}{2}}{a + 1} (\binom{n − s − 3/2}{2n − 1 − a} + \binom{n − s − 1/2}{2n − 1 − a}) \\ + (n + s − \frac{1}{2}) \binom{2n − 1}{a} (\binom{n − s − 3/2}{2n − 1} + \binom{n − s − 1/2}{2n − 1}) \\ + a\binom{2n}{a + 1} (\binom{n − s − 3/2}{2n} + \binom{n − s − 1/2}{2n}) = 0, \end{matrix}  (4.18)

\begin{matrix}(−1)^{a}\binom{n + s − \frac{1}{2}}{a + 1}\binom{n − s − \frac{3}{2}}{2n − a − 2} \\ − (n + s − \frac{1}{2}) \binom{2n − 1}{a}\binom{n − s − \frac{3}{2}}{2n − 2} − a\binom{2n}{a + 1}\binom{n − s − \frac{3}{2}}{2n − 1} = 0. \end{matrix} (4.19)

The proof of these relations amounts to a routine verification, and is consequently left to the reader.

(b) Suppose 2n − 2s − 1 ≤ j ≤ 2n. Combining Remark 2.1 with (3.15) with the skew-symmetry of N(−s − 3/2), we see that the j-th column of N(−s − 3/2) is zero, and thus (4.17) is clearly true.

(c) Suppose 1 ≤ j ≤ 2n − 2s − 2. It follows from Remark 2.1 and (3.14) that

N_{i,j}(−s − 3/2) = −\binom{2n − 2s − 2}{j} (\binom{n − s − \frac{3}{2}}{i} + \binom{n − s − \frac{1}{2}}{i})

for 2n − 2s − 1 ≤ i ≤ 2n. Inserting this in (4.17) and then dividing both sides of the resulted equality by \binom{2n−2s−2}{j} gives the relation (4.18), as a routine verification shows. This completes the proof of (4.17). □

4.4. T (x) = L(x) at x = −1, …, −n. Let σ be a given integer with 1 ≤ σ ≤ n. It is easy to evaluate the polynomial L(x), defined by (4.5), at x = −σ. After a routine calculation, we obtain

L(−σ) = \frac{2^{5n−1}}{n! (4n)!} ∏_{s=2}^{n} \frac{1}{(2s)_{4n−4s+3}} (\frac{3}{2} − σ)_{2n−1} ((−1)^{σ−1}(2n − 1)!! + (2n)!!). (4.20)

The evaluation of T (x) at x = −σ is much more delicate. For the same reason as the one in Section 3.5, we should write (4.4) in the form

T (x) = 2^{2n−σ} \frac{1}{(x + σ)^{σ}} Pf N(x) _{∏_{s=1}^{n} ; s≠σ}(2x + 2s)^{−s} ∏_{s=1}^{n}(2x + 4n + 2 − 2s)^{−s}

× ∏_{s=1}^{n−1} (2x + 3 + 2s)^{−s} ∏_{s=1}^{n−2} (2x + 4n − 1 − 2s)^{−s} ,

and subsequently specialize x = −σ. After some manipulation, this leads to

T (−σ) = (\frac{1}{(x + σ)^{σ}} Pf N(x)) |_{x=−σ} (−1)^{σ−1}2^{3−σ} \frac{(2σ − 3)! (4n − 2σ − 1)!}{(σ − 2)! (2n − σ − 1)!}

× \frac{∏_{s=1}^{n−σ}(2s − 1)!}{∏_{s=1}^{σ−1}(2s)! ∏_{s=n−σ+1}^{2n−σ}(2s)!}. (4.21)

Let B(x) = (B_{i,j}(x))_{1≤i,j≤2n+2} denote the matrix obtained from N(x) by first adding

∑_{i=1}^{2n−2σ+1}(−1)^{i} (2^{i−1} − \binom{i − 1}{n − σ}) · (row i of N(x))

to row 2n + 1, and then adding

∑_{i=1}^{2n−2σ+1}(−1)^{i} (2^{i−1} − \binom{i − 1}{n − σ}) · (column i of N(x))

to column 2n + 1. Of course, we have Pf B(x) = Pf N(x), and it follows from (4.7) and (4.8) that the i-th row of B(−σ), 2n − 2σ + 2 ≤ i ≤ 2n + 1, is zero, or equivalently, (x + σ) is a factor of each entry in the i-th row in matrix B(x). Applying Lemma 3.2 to the matrix B(x), we obtain

(\frac{1}{(x + σ)^{σ}} Pf N(x)) |_{x=−σ} = (\frac{1}{(x + σ)^{σ}} Pf B(x)) |_{x=−σ} = Pf B̃ · Pf D,  (4.22)

where B̃ is the matrix which arises from B(x) by deleting rows and columns 2n − 2σ + 2, 2n − 2σ + 3, …, 2n + 1 and subsequently specializing x = −σ, and where

D = ((\frac{1}{x + σ} B_{i,j}(x)) |_{x=−σ})_{2n−2σ+2≤i,j≤2n+1} .  (4.23)

By Remark 2.1 and the definition of the matrix B(x), we have B̃ = M̃ where M̃ is defined by (3.32). We have shown in Section 3.5 that Pf M̃ = 1, and thus Pf B̃ = 1. The evaluation of Pf D is much more complicated and is therefore postponed to the next section for the sake of better readability of the paper.

Lemma 4.1. We have

Pf D = (−1)^{σ−1}2^{5n−2} \frac{(σ − 1)! (n − σ)! (2n − σ)!}{n!^{2}} ((2n)!! + (−1)^{σ+1}(2n − 1)!!)

× (\frac{3}{2} − σ)_{2n−1} \frac{∏_{s=1}^{σ−2}(2s)!( ∏_{s=n−σ+1}^{n}(2s)!)^{2}}{∏_{s=2n−σ}^{2n}(2s)!} .

If we substitute the values obtained for Pf B̃ and Pf D in (4.22), and then insert the obtained result in (4.21), it is easy to check that T (−σ) is equal to the right-hand side of (4.20). Consequently, we have T (−σ) = L(−σ), as desired.

5. Evaluation of Pf D: Proof of Lemma 4.1

This section is dedicated to the evaluation of the Pfaffian of the matrix D defined by (4.23). We begin by describing more explicitly the entries of the matrix D in the next subsection. The subsequent subsection provides an efficient way to compute the Pfaffian of a skew-symmetric matrix which differs from a Mehta–Wang matrix of even size only in its last row and column. A more precise statement is given in Proposition 5.2. This allows us to write Pf D in the form of a multisum, which is evaluated in the last subsection.

Throughout this section, σ and n are positive integers with 1 ≤ σ ≤ n. For the sake of simplicity, we also set N = n − σ.

5.1. The entries of the matrix D.

Lemma 5.1. The matrix D = (D_{i,j})_{1≤i,j≤2σ} defined by (4.23) is a skew-symmetric matrix of size 2σ. For 1 ≤ i, j ≤ 2σ − 1, we have

D_{i,j} = (−1)^{i+j} \frac{2 (j − i) (2N + i)! (2N + j)!}{(4N + i + j + 2)!}.  (5.1)

For 1 ≤ j ≤ 2σ − 1, we have

D_{2σ,j} = \frac{(−1)^{j}2}{\binom{2N+j+1}{j−1}} ∑_{i=0}^{2N}(−1)^{i} (2^{i} − \binom{i}{N}) \frac{2N + j − i}{i + 1}

· ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j}{i − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}

+ \frac{(−1)^{N+j}}{(N + 1)\binom{2N+j+1}{j−1}} + \frac{(−1)^{j}(j − 1)N! (N + j − 1)!}{(2N + j + 1)!}. (5.2)

Proof. Combining the definitions of the matrices D and B(x) (see (4.23) and the paragraph above) with Remark 2.1, we see that, for 1 ≤ i, j ≤ 2σ − 1, the (i, j)-entry of D is equal to the (i, j)-entry of the matrix S defined in (3.33). Equation (5.1) then follows from (3.37).

Recall that N = n − σ and suppose 1 ≤ j ≤ 2σ − 1. Then, by (4.23) and the definition of the matrix B(x), we have

D_{2σ,j} = (\frac{N_{2n+1,2N+1+j}(x)}{x + σ} + ∑_{i=1}^{2N+1}(−1)^{i} (2^{i−1} − \binom{i − 1}{N}) \frac{N_{i,2N+1+j}(x)}{x + σ}) |_{x=−σ}. (5.3)

It is a routine matter to derive from (2.14) that

\frac{N_{2n+1,2N+1+j}(x)}{x + σ}|_{x=−σ} = −\frac{\binom{2x+2N+2σ+1}{2N+1+j}}{x + σ} + \frac{\binom{x+N+σ}{2N+1+j}}{x + σ} + \frac{\binom{x+N+σ+1}{2N+1+j}}{x + σ}|_{x=−σ}

= (−1)^{j}2\frac{(2N + 1)! (j − 1)!}{(2N + j + 1)!} + (−1)^{N+j} \frac{(N + j)! N!}{(2N + j + 1)!}

+ (−1)^{N+j−1} \frac{(N + 1)! (N + j − 1)!}{(2N + j + 1)!}.

Similarly, combining (2.13) with (2.12) and (2.16), for 1 ≤ i ≤ 2N + 1 we obtain

\frac{N_{i,2N+1+j}(x)}{x + σ}|_{x=−σ}

= ∑_{ℓ=0}^{i−1} \frac{2N + 1 + j − i}{i}\binom{2N + j}{i − 1 − ℓ}\binom{ℓ + 2N + 1 + j}{ℓ}(−1)^{ℓ+j−1}2\frac{(2N + 2)! (ℓ + j − 1)!}{(2N + j + 2 + ℓ)!}

+ \binom{2N + 1}{i}((−1)^{N+j} \frac{(N + j)! N!}{(2N + j + 1)!} + (−1)^{N+j−1} \frac{(N + 1)! (N + j − 1)!}{(2N + j + 1)!})

− (−1)^{j−1}2\frac{(2N + 1)! (j − 1)!}{(2N + j + 1)!} (\binom{N}{i} + \binom{N + 1}{i})

after a straightforward calculation. Substituting the last two identities in (5.3) and then using (4.10)–(4.12), we obtain (5.2) after some simplification. □

5.2. The Pfaffian of a perturbed Mehta–Wang matrix. Proposition 5.2. Let s, R be positive integers and A = (a_{i,j})_{1≤i,j≤2s} be a skew-symmetric matrix such that, for 1 ≤ i, j ≤ 2s − 1,

a_{i,j} = \frac{(j − i)}{(R + i + j)!}.  (5.4)

Then the Pfaffian of A satisfies the relation

Pf A = −2^{s−1}(s − 1)! (∑_{j=1}^{2s−1} a_{2s,j} · λ_{j}) ∏_{i=0}^{s−2} \frac{(2i + 1)!}{(R + 2s + 1 + 2i)!},  (5.5)

where, for 1 ≤ j ≤ 2s − 1, the term λ_{j} is defined by

λ_{j} = (−1)^{j+1} ∑_{k=0}^{s−1} \frac{2^{−k}}{k!} \binom{2k}{j + k − s}(R + 2s)_{j+k−s}.  (5.6)

Proof. Let B = (B_{i,j}) be the upper triangular matrix of size 2s defined by

B = ( λ_{1} λ_{2} ⋯ λ_{2s−1} 0 ; 0 I_{2s−1} ; ⋮ ; 0 ) ,

where I_{2s−1} stands for the identity matrix of size 2s − 1. Moreover, set Ã = B^{t}AB. Clearly, Ã = (ã_{i,j})_{1≤i,j≤2s} is a skew-matrix which differs from A only in its first column and its first row, and we have the relation

ã_{i,1} = ∑_{j=1}^{2s−1} a_{i,j} · λ_{j}.  (5.7)

We claim that ã_{i,1} = 0 for 1 ≤ i ≤ 2s − 1, so that

Ã = ( \begin{matrix}0 & 0 & ⋯ & 0 & −ã_{2s,1} \\ 0 & a_{2,2} & ⋯ & a_{2,2s−1} & a_{2,2s} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & a_{2s−1,2} & ⋯ & a_{2s−1,2s−1} & a_{2s−1,2s} \\ ã_{2s,1} & a_{2s,2} & ⋯ & a_{2s,2s−1} & a_{2s,2s} \end{matrix} ) .

This, combined with the relation Ã = B^{t}AB, would imply that

Pf Ã = −ã_{2s,1} Pf_{2≤i,j≤2s−1} (a_{i,j}) and Pf A = Pf Ã/ det B = 2^{s−1}(s − 1)! Pf Ã.

Consequently, we would have

Pf A = −2^{s−1}(s − 1)! ã_{2s,1} Pf_{2≤i,j≤2s−1} (\frac{j − i}{(R + i + j)!}) .

Proposition 5.2 then would immediately follow from (5.7) and the Pfaffian evaluation (3.38).

So, to complete the proof, it remains to verify our claim that ã_{i,1} = 0 for 1 ≤ i ≤ 2s−1. By (5.7) and (5.4)–(5.6), for 1 ≤ i ≤ 2s − 1 we have

ã_{i,1} = ∑_{j=1}^{2s−1} \frac{(j − i)}{(R + i + j)!}(−1)^{j+1} ∑_{k=0}^{s−1} \frac{2^{−k}}{k!} \binom{2k}{j + k − s}(R + 2s)_{j+k−s}  (5.8)

= ∑_{k=0}^{s−1} ∑_{j=0}^{2k} \frac{2^{−k}}{k!} \frac{(−1)^{j+s−k}(j + s − k − i)}{(R + i + j + s − k)!}\binom{2k}{j}(R + 2s)_{j},  (5.9)

where (5.9) follows from (5.8) by first interchanging the sums over j and k and then shifting the (now) inner sum over j by s − k. The inner sum in (5.9) can be rewritten, by splitting the term (j + s − k − i), as a sum of two _{2}F_{1}-series. After some manipulation, we obtain

ã_{i,1} = ∑_{k=0}^{s−1} \frac{2^{−k}}{k!} \frac{(−1)^{s−k+1}(2k)(R + 2s)}{(R + i + s − k + 1)!} _{2}F_{1}[\begin{matrix}R + 2s + 1, −2k + 1 \\ R + i + s − k + 2 \end{matrix}; 1]

+ ∑_{k=0}^{s−1} \frac{2^{−k}}{k!} \frac{(−1)^{s−k}(s − k − i)}{(R + i + s − k)!} _{2}F_{1}[\begin{matrix}R + 2s, −2k \\ R + i + s − k + 1 \end{matrix}; 1]

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

+ ∑_{k=0}^{s−1} \frac{2^{−k}}{k!} \frac{(−1)^{s−k}(s − k − i)(i − s − k + 1)_{2k}}{(R + i + s + k)!} ,

where the last equality follows from the Chu–Vandermonde summation formula. It is easily checked that each summand in the two above sums vanishes when i = s, whence ã_{s,1} = 0.

Now suppose i ≠ s. Splitting the term (s − k − i) in the second sum in the above expression, and rewriting the (now) three sums in hypergeometric notation, we arrive at

ã_{i,1} = \frac{(−1)^{s}(R + 2s)(i − s)}{(R + i + s + 1)!} _{2}F_{1}[\begin{matrix}1 + i − s, 1 + s − i \\ R + i + s + 2 \end{matrix}; \frac{1}{2}]

+ \frac{(−1)^{s}2^{−1}(i − s)_{2}}{(R + i + s + 1)!} _{2}F_{1}[\begin{matrix}2 + i − s, 1 + s − i \\ R + i + s + 2 \end{matrix}; \frac{1}{2}]

+ \frac{(−1)^{s}(s − i)}{(R + i + s)!} _{2}F_{1}[\begin{matrix}1 + i − s, s − i \\ R + i + s + 1 \end{matrix}; \frac{1}{2}] .

To see that the above expression vanishes, it suffices (after multiplying the above expression by (−1)^{s}(i − s)^{−1}(R + i + s + 1)!) to prove that

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

where a = 1 + i − s, b = s − i, c = R + i + s + 1 and x = 1/2. This identity can be easily derived from Gauß’ contiguous relations for the _{2}F_{1}-series, or, more directly, by extracting the coefficient of x^{n} in each side. In our case, we have to check that

(c − a)\frac{(a)_{n}(b + 1)_{n}}{(c + 1)_{n}(1)_{n}} + a (\frac{(a + 1)_{n}(b + 1)_{n}}{(c + 1)_{n}(1)_{n}} − \frac{(a + 1)_{n−1}(b + 1)_{n−1}}{(c + 1)_{n−1}(1)_{n−1}} ) − c\frac{(a)_{n}(b)_{n}}{(c)_{n}(1)_{n}} = 0,

which amounts to a routine computation. To summarize, we have proved that ã_{i,1} = 0 for 1 ≤ i ≤ 2s − 1. This completes the proof of Proposition 5.2. □

5.3. Proof of Lemma 4.1. It follows from (5.1) that we may apply Proposition 5.2 to the matrix

(\frac{(−1)^{i+j}D_{i,j}}{2(2N + i)! (2N + j)!})_{1≤i,j≤2σ} .

After some simplification, we obtain

Pf D = (−1)^{σ}2^{σ} (∏_{i=1}^{2σ}(2N + i)!) Pf_{1≤i,j≤2σ} (\frac{(−1)^{i+j}D_{i,j}}{2(2N + i)! (2N + j)!})

= (−1)^{σ}2^{2σ−2}(σ − 1)! ( ∏_{i=1}^{2σ−1}(2N + i)!) (∏_{i=0}^{σ−2} \frac{(2i + 1)!}{(4N + 2σ + 3 + 2i)!}) V (N, σ),

where

V (N, σ) = ∑_{j=1}^{2σ−1} \frac{D_{2σ,j}}{(2N + j)!} ∑_{k=0}^{σ−1} \frac{2^{−k}}{k!} \binom{2k}{j + k − σ}(4N + 2 + 2σ)_{j+k−σ}.  (5.10)

This easily leads to the following reformulation of Lemma 4.1.

Proposition 5.3. Let V (N, σ) be defined by (5.10). Then

V (N, σ) = \frac{2^{N+2}(2N + σ + 1)!}{(N + σ)! (4N + 2σ + 2)!} ((−1)^{σ}(2N + 2σ)!! − (2N + 2σ − 1)!!) .

CENTERED SYMMETRIC RHOMBUS TILINGS OF A HEXAGON 33

The first step towards a proof of the preceding proposition is to simplify expression (5.2) for D_{2σ,j}. We shall prove at the end of this section that

\frac{(−1)^{j+1}D_{2σ,j}}{(2N + j)!} = \frac{(j − 1)(2N + 1)!}{(4N + j + 3)!} (\frac{2(2N + 1)!}{N! (N + 1)!} − 2^{2N+2})

− \frac{(2N + 2)!}{(4N + j + 3)!} (\frac{4(2N + 1)!}{N! (N + 1)!} + 2^{2N+3}) − \frac{(j − 1)(N + j − 1)! N!}{(2N + j)! (2N + j + 1)!}

+ \frac{2(j − 1)(2N + 2)!}{(2N + j + 1)! (N + 1)!} ∑_{h=N}^{2N+1} \frac{(h + j − 1)! (h + 1)!}{(h − N)! (2N + j + h + 2)!}. (5.11)

Therefore, by (5.10), we have

V (N, σ) = (2N + 1)! (\frac{2(2N + 1)!}{N! (N + 1)!} − 2^{2N+2}) ∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}(j − 1)}{(4N + j + 3)!}λ_{j}(N, σ)

− (2N + 2)! (\frac{4(2N + 1)!}{N! (N + 1)!} + 2^{2N+3}) ∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}}{(4N + j + 3)!}λ_{j}(N, σ)

− N! ∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}(j − 1)(N + j − 1)!}{(2N + j)! (2N + j + 1)!}λ_{j}(N, σ)

+ \frac{2(2N + 2)!}{(N + 1)!} ∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}(j − 1)}{(2N + j + 1)!} ∑_{h=N}^{2N+1} \frac{(h + j − 1)! (h + 1)!}{(h − N)! (2N + j + h + 2)!}λ_{j}(N, σ), (5.12)

where we have set

λ_{j}(N, σ) = ∑_{k=0}^{σ−1} \frac{2^{−k}}{k!} \binom{2k}{j + k − σ}(4N + 2 + 2σ)_{j+k−σ}.  (5.13)

All the sums in (5.12) can be evaluated in closed-form expressions. Lemma 5.4. For all positive integers N and σ, we have

∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}(j − 1)}{(4N + j + 3)!}λ_{j}(N, σ) = 0,  (5.14)
∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}}{(4N + j + 3)!}λ_{j}(N, σ) = (−2)^{σ−1} \frac{(2N + σ + 1)!}{(2N + 2)! (4N + 2σ + 2)!},  (5.15)
∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}(j − 1)(N + j − 1)!}{(2N + j)! (2N + j + 1)!}λ_{j}(N, σ) = 0,  (5.16)
\begin{matrix}∑_{j=1}^{2σ−1} ∑_{h=N}^{2N+1} \frac{(−1)^{j+1}(j − 1) (h + j − 1)! (h + 1)!}{(h − N)! (2N + j + h + 2)! (2N + j + 1)!}λ_{j}(N, σ) \\ = \frac{(2N + σ + 1)!}{(N + 1)! (4N + 2σ + 2)!} ((−2)^{σ−1} − \frac{(N + 1)!^{2} (2N + 2σ)!}{2^{σ−1} (N + σ)!^{2} (2N + 2)!}) . \end{matrix}  (5.17)

At this point, we should notice that, after substituting these summations in (5.12), it becomes a routine matter to verify Proposition 5.3. So, to complete the proof of Lemma 4.1, it remains to prove the preceding lemma and (5.11).

Proof of Lemma 5.4. (1) The double sum on the left-hand side of (5.14) is the specialization i = 1, s = σ, and R = 4N + 2 of (5.8), which was shown to be zero in the proof of Proposition 5.2, whence (5.14).

(2) Let S_{1}(N, σ) denote the double sum on the left-hand side of (5.15). Interchanging the sums over j and k in S_{1}(N, σ), we see that the (now) inner sum over j can be written as a _{2}F_{1}-series which is summable by the Chu–Vandermonde formula. To be precise, we obtain

S_{1}(N, σ) = ∑_{j=1}^{2σ−1} \frac{(−1)^{j+1}}{(4N + j + 3)!} ∑_{k=0}^{σ−1} \frac{2^{−k}}{k!} \binom{2k}{j + k − σ}(4N + 2 + 2σ)_{j+k−σ}

= ∑_{k=0}^{σ−1} \frac{2^{−k}}{k!} \frac{(−1)^{σ−k+1}}{(4N + σ − k + 3)!} _{2}F_{1}[\begin{matrix}2N + 2σ + 2, −2k \\ 4N + 4 + σ − k \end{matrix}; 1]

= ∑_{k=0}^{σ−1} \frac{2^{−k}}{k!} \frac{(−1)^{σ−k+1}}{(4N + σ − k + 3)!} \frac{(2 − σ − k)_{2k}}{(4N + 4 + σ − k)_{2k}} .

Writing the above sum in hypergeometric notation, we arrive at

S_{1}(N, σ) = \frac{(−1)^{σ+1}}{(4N + σ + 3)!} _{2}F_{1}[\begin{matrix}σ − 1, 2 − σ \\ 4N + 4 + σ \end{matrix}; \frac{1}{2}] = (−1)^{σ+1}2^{σ−1} \frac{(2N + σ + 1)!}{(2N + 2)! (4N + 2σ + 2)!},

where the last equality follows from Bailey’s _{2}F_{1} summation formula (see [30, (1.7.1.8); Appendix (III.7)])

2F_{1}[\begin{matrix}a, 1 − a \\ b \end{matrix}; \frac{1}{2}] = \frac{Γ (\frac{b}{2}) Γ (\frac{1}{2} + \frac{b}{2})}{Γ (\frac{a}{2} + \frac{b}{2}) Γ (\frac{1}{2} − \frac{a}{2} + \frac{b}{2})}.

This finishes the proof of (5.15).

(3) Let S_{2}(N, σ) denote the double sum on the left-hand side of (5.16). We shall establish the recurrence

S_{2}(N, σ) + (4N + 2σ + 3)S_{2}(N, σ + 1) = 0,  σ ≥ 1.  (5.18)

Since it is easy to verify directly that S_{2}(N, 1) = 0, this would immediately imply the claim.

In order to prove (5.18), we use the Gosper–Zeilberger algorithm (cf. [16] and [26, § II.5] — the particular implementation that we used is the Mathematica implementation by Paule and Schorn [25]) to find that

F_{2}(N, σ, j, k)+(4N +2σ +3)F_{2}(N, σ +1, j, k) = G_{2}(N, σ, j, k +1)−G_{2}(N, σ, j, k), (5.19)

where F_{2}(N, σ, j, k) is the summand of the sum on the left-hand side of (5.16), that is,

F_{2}(N, σ, j, k) = (−1)^{j+1} \frac{(j − 1) (N + j − 1)!}{(2N + j)! (2N + j + 1)!} \frac{1}{2^{k} k!}\binom{2k}{j + k − σ}(4N + 2σ + 2)_{j+k−σ},

and

G_{2}(n, σ, j, k) = \frac{j + k − σ}{4N + 2σ + 2}F_{2}(N, σ, j, k).

We now sum both sides of (5.19) over k between 0 and σ − 1 and subsequently over j between 1 and 2σ − 1. Taking into account the telescoping effect on the right-hand side when we perform summation over k, we arrive at

S_{2}(N, σ) + (4N + 2σ + 3)S_{2}(N, σ + 1) − (4N + 2σ + 3) ∑_{j=1}^{2σ−1} F_{2}(N, σ + 1, j, σ)

− (4N + 2σ + 3)(F_{2}(N, σ + 1, 2σ, σ) + F_{2}(N, σ + 1, 2σ, σ − 1) + F_{2}(N, σ + 1, 2σ + 1, σ))

= ∑_{j=1}^{2σ−1}(G_{2}(N, σ, j, σ) − G_{2}(N, σ, j, 0)).

After some simplification, this becomes

S_{2}(N, σ) + (4N + 2σ + 3)S_{2}(N, σ + 1)

= (4N + 4σ + 3) ∑_{j=1}^{2σ−1} \frac{(−1)^{j} (j − 1) (N + j − 1)! (2σ)! (4N + 2σ + 3)_{j−1}}{2^{σ} (j − 1)! (2N + j)! (2N + j + 1)! σ! (2σ − j + 1)!}

+ \frac{2^{1−σ} (4N + 4σ + 3) (N + 2σ − 1)! (4N + 2σ + 3)_{2σ−1}}{(N + σ + 1) (σ − 2)! (2N + 2σ)!^{2}}

= (4N + 4σ + 3) ∑_{j=1}^{2σ+1} \frac{(−1)^{j} (j − 1) (N + j − 1)! (2σ)! (4N + 2σ + 3)_{j−1}}{2^{σ} (j − 1)! (2N + j)! (2N + j + 1)! σ! (2σ − j + 1)!}.

It remains to show that the right-hand side of this equation vanishes. In order to see this, we write the sum over j in hypergeometric notation. Thereby we obtain

S_{2}(N, σ) + (4N + 2σ + 3)S_{2}(N, σ + 1)

= \frac{2σ (4N + 4σ + 3) (4N + 2σ + 3) (N + 1)!}{2^{σ} σ! (2N + 2)! (2N + 3)!}_{3}F_{2}[\begin{matrix}−2σ + 1, 4N + 2σ + 4, N + 2 \\ 2N + 3, 2N + 4 \end{matrix}; 1] .

This _{3}F_{2}-series can be evaluated by means of Watson’s _{3}F_{2}-summation (see [30, (2.3.3.13); Appendix (III.23)])

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

In fact, because of the term Γ(\frac{1}{2} + \frac{a}{2}) in the denominator on the right-hand side, the series vanishes whenever a is an odd negative integer. The recurrence (5.18) follows immediately. This completes the proof of (5.16).

(4) Again, we prove the claim by induction on σ. To start the induction, we have to show that (5.17) holds for σ = 1. This is trivially the case, since in this case the sum over j reduces to just one term, the term for j = 1, so that both sides of (5.17) vanish.

Let S_{3}(N, σ) denote the triple sum on the left-hand side of (5.17). We now claim that S_{3}(N, σ) + (4N + 2σ + 3)S_{3}(N, σ + 1)

= −\frac{(4N + 4σ + 3) (N + 1)! (2N + σ + 1)! (2N + 2σ)!}{2^{σ} (2N + 2)! (N + σ)! (N + σ + 1)! (4N + 2σ + 2)!}, σ ≥ 1. (5.20)

Since the right-hand side of (5.17) satisfies the above recurrence — as is not difficult to check — this would prove the lemma.

In order to prove (5.20), we multiply both sides of (5.18) by

\frac{(h + j − 1)! (h + 1)!}{(h − N)! (2N + j + h + 2)!}/\frac{(N + j − 1)!}{(2N + j)!}

to find that

F_{3}(N, σ, j, h, k) + (4N + 2σ + 3)F_{3}(N, σ + 1, j, h, k)

= G_{3}(N, σ, j, h, k + 1) − G_{3}(N, σ, j, h, k), (5.21)

where F_{3}(N, σ, j, h, k) is the summand of the sum on the left-hand side of (5.17), that is,

F_{3}(N, σ, j, h, k) = (−1)^{j+1} \frac{(j − 1) (h + j − 1)! (h + 1)!}{(h − N)! (2N + j + h + 2)! (2N + j + 1)!}

× \frac{1}{2^{k} k!}\binom{2k}{j + k − σ}(4N + 2σ + 2)_{j+k−σ},

and

G_{3}(n, σ, j, h, k) = \frac{j + k − σ}{4N + 2σ + 2}F_{3}(N, σ, j, h, k).

We now sum both sides of (5.21) over k between 0 and σ − 1, and subsequently over j between 1 and 2σ − 1, and over h between N and 2N + 1. Taking into account the telescoping effect on the right-hand side when we perform summation over k, we arrive at

S_{3}(N, σ) + (4N + 2σ + 3)S_{3}(N, σ + 1) − (4N + 2σ + 3) ∑_{j=1}^{2σ−1} ∑_{h=N}^{2N+1} F_{3}(N, σ + 1, j, h, σ)

− (4N + 2σ + 3) ∑_{h=N}^{2N+1} (F_{3}(N, σ + 1, 2σ, h, σ)

+ F_{3}(N, σ + 1, 2σ, h, σ − 1) + F_{3}(N, σ + 1, 2σ + 1, h, σ))

= ∑_{j=1}^{2σ−1} ∑_{h=N}^{2N+1} (G_{3}(N, σ, j, h, σ) − G_{3}(N, σ, j, h, 0)).

After some simplification, this becomes

S_{3}(N, σ) + (4N + 2σ + 3)S_{3}(N, σ + 1)

= − ∑_{h=N}^{2N+1} ∑_{j=2}^{2σ−1} \frac{(−1)^{j} (4N + 4σ + 3) (h + j − 1)! (h + 1)! (2σ)! (4N + 2σ + 3)_{j−1}}{2^{σ} (j − 2)! (h − N)! (2N + j + h + 2)! (2N + j + 1)! σ! (2σ − j + 1)!}

CENTERED SYMMETRIC RHOMBUS TILINGS OF A HEXAGON 37

+ ∑_{h=N}^{2N+1} 4 (4N + 4σ + 3) (3 + 2h + 5N + 3hN + 2N^{2} + σ + hσ − 2Nσ

− 2hNσ − 4N^{2}σ − 4σ^{2} − 2hσ^{2} − 8Nσ^{2} − 4σ^{3})

· \frac{(h + 1)! (h + 2σ − 1)! (4N + 2σ + 3)_{2σ−1}}{2^{σ} (h − N)! (σ − 1)! (2N + 2σ + 2)! (2N + 2σ + h + 3)!}

= − ∑_{h=N}^{2N+1} ∑_{j=2}^{2σ+1} \frac{(−1)^{j} (4N + 4σ + 3) (h + j − 1)! (h + 1)! (2σ)! (4N + 2σ + 3)_{j−1}}{2^{σ} (j − 2)! (h − N)! (2N + j + h + 2)! (2N + j + 1)! σ! (2σ − j + 1)!}.

By writing the sum over j in hypergeometric notation, this turns into

S_{3}(N, σ) + (4N + 2σ + 3)S_{3}(N, σ + 1)

= − ∑_{h=N}^{2N+1} \frac{(4N + 2σ + 3) (4N + 4σ + 3) (h + 1)!^{2}}{2^{σ−1} (h − N)! (2N + 3)! (2N + h + 4)! (σ − 1)!}

·_{3}F_{2}[\begin{matrix}h + 2, 4N + 2σ + 4, −2σ + 1 \\ 2N + 4, 2N + h + 5 \end{matrix}; 1] .

Next we apply the contiguous relation

3F_{2}[\begin{matrix}a, b, c \\ d, e \end{matrix}; z] = \frac{b}{b − a}_{3}F_{2}[\begin{matrix}a, b + 1, c \\ d, e \end{matrix}; z] + \frac{a}{a − b}_{3}F_{2}[\begin{matrix}a + 1, b, c \\ d, e \end{matrix}; z] .

We obtain

S_{3}(N, σ) + (4N + 2σ + 3)S_{3}(N, σ + 1)

= − ∑_{h=N}^{2N+1} \frac{(4N + 2σ + 3) (4N + 2σ + 4) (4N + 4σ + 3) (h + 1)!^{2}}{2^{σ−1} (4N + 2σ − h + 2) (h − N)! (2N + 3)! (2N + h + 4)! (σ − 1)!}

·_{3}F_{2}[\begin{matrix}h + 2, 4N + 2σ + 5, −2σ + 1 \\ 2N + 4, 2N + h + 5 \end{matrix}; 1]

+ ∑_{h=N}^{2N+1} \frac{(4N + 2σ + 3) (4N + 4σ + 3) (h + 1)! (h + 2)!}{2^{σ−1} (4N + 2σ − h + 2) (h − N)! (2N + 3)! (2N + h + 4)! (σ − 1)!}

·_{3}F_{2}[\begin{matrix}h + 3, 4N + 2σ + 4, 1 − 2σ \\ 2N + 4, 2N + h + 5 \end{matrix}; 1] .

Both _{3}F_{2}-series can be evaluated by means of the Pfaff–Saalschütz summation formula (3.27). If we apply the formula, then, after some simplification, the above recurrence reduces to

S_{3}(N, σ) + (4N + 2σ + 3)S_{3}(N, σ + 1)

= 4 (4N + 2σ + 3) (4N + 4σ + 3) ∑_{h=N}^{2N+1} (1 + h − N + hN − 2N^{2} − 3σ − 4Nσ − 2σ^{2})

· \frac{(h + 1)!^{2} (2N + 3)_{2σ−2} (2 − h + 2N)_{2σ−2}}{2^{σ} (h − N)! (σ − 1)! (2N + 2σ + 2)! (2N + 2σ + h + 3)!}.

Let S_{4}(N, σ) denote the right-hand sum. The Gosper–Zeilberger algorithm then yields the recurrence

(2N + 2σ + 1)(4N + 4σ + 7)S_{4}(N, σ)

− 4(2N + 3)(N + σ + 2)(4N + 2σ + 3)(4N + 2σ + 5)(4N + 4σ + 3)S_{4}(N + 1, σ) = 0, (5.22)

with a half-page certificate, which we omit here for the sake of brevity. Since it is straightforward to check that S_{4}(1, σ) is equal to the right-hand side of (5.20) with N = 1, and that the right-hand side of (5.20) satisfies the recurrence in (5.22), the claimed recurrence (5.20) follows.

This completes the proof of (5.17), and thus of the lemma. □

We now turn our attention to the proof of (5.11).

Proof of (5.11). By (5.2), we have

D_{2σ,j} = \frac{(−1)^{j}2}{\binom{2N+j+1}{j−1}} · S + \frac{(−1)^{N+j}}{(N + 1)\binom{2N+j+1}{j−1}} + \frac{(−1)^{j}(j − 1) N! (N + j − 1)!}{(2N + j + 1)!},  (5.23)

where S stands for the double sum in (5.2), that is,

S = ∑_{i=0}^{2N}(−1)^{i} (2^{i} − \binom{i}{N}) \frac{2N + j − i}{i + 1} ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j}{i − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}.

By extending the sum over i, we may rewrite S as

∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N}) \frac{2N + j − i}{i + 1}

· ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j}{i − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}

+ (2^{2N+1} − \binom{2N + 1}{N}) \frac{j − 1}{2N + 2}

· ∑_{ℓ=0}^{2N+1}(−1)^{ℓ}\binom{2N + j}{2N + 1 − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}.

We concentrate now on the evaluation of the second sum over ℓ. It can be written as a _{2}F_{1}-series which is summable by means of the Chu–Vandermonde summation formula (in hypergeometric form; see [30, (1.7.7), Appendix (III.4)]), so that we obtain

(2^{2N+1} − \binom{2N + 1}{N}) \frac{j − 1}{2N + 2} ∑_{ℓ=0}^{2N+1}(−1)^{ℓ}\binom{2N + j}{2N + 1 − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}

= (2^{2N+1} − \binom{2N + 1}{N}) \frac{j − 1}{2N + 2}\binom{2N + j}{2N + 1}\frac{1}{2N + j + 2}_{2}F_{1}[\begin{matrix}2N + j + 2, −2N − 1 \\ 2N + j + 3 \end{matrix}; 1]

CENTERED SYMMETRIC RHOMBUS TILINGS OF A HEXAGON 39

= (2^{2N+1} − \binom{2N + 1}{N}) \frac{j − 1}{2N + 2}\binom{2N + j}{2N + 1}\frac{1}{2N + j + 2} \frac{(1)_{2N+1}}{(2N + j + 3)_{2N+1}}

= \frac{(j − 1) (2N + j)! (2N + j + 1)!}{(2N + 2) (j − 1)! (4N + j + 3)!} (2^{2N+1} − \binom{2N + 1}{N}) .

Consequently, our sum S is equal to

∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N}) \frac{2N + j − i}{i + 1} ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j}{i − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}

+ \frac{(j − 1) (2N + j)! (2N + j + 1)!}{(2N + 2) (j − 1)! (4N + j + 3)!} (2^{2N+1} − \binom{2N + 1}{N}) .

Next we apply the partial fraction expansion

\frac{1}{(i + 1)(2N + ℓ + j + 2)} = \frac{1}{2N + ℓ + j − i + 1} (\frac{1}{i + 1} − \frac{1}{2N + ℓ + j + 2}) .

Thus, we have

S = S_{1} − S_{2} + \frac{(j − 1) (2N + j)! (2N + j + 1)!}{(2N + 2) (j − 1)! (4N + j + 3)!} (2^{2N+1} − \binom{2N + 1}{N}) ,  (5.24)

where

S_{1} = \frac{1}{(2N + j + 1)} ∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N}) \frac{2N + j − i}{i + 1}

· ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j + 1}{i − ℓ}\binom{ℓ + j − 1}{ℓ}

and

S_{2} = \frac{1}{(2N + j + 1)} ∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N}) (2N + j − i)

· ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j + 1}{i − ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2N + ℓ + j + 2}.

We start with the evaluation of S_{1}. We have

∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{2N + j + 1}{i − ℓ}\binom{ℓ + j − 1}{ℓ} = \binom{2N + j + 1}{i}_{2}F_{1}[\begin{matrix}j, −i \\ 2N + j − i + 2 \end{matrix}; 1]

= \binom{2N + j + 1}{i}\frac{(2N − i + 2)_{i}}{(2N + j − i + 2)_{i}} = \binom{2N + 1}{i},

and therefore

S_{1} = \frac{1}{(2N + j + 1)} ∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N}) \frac{2N + j − i}{2N + 2}\binom{2N + 2}{i + 1}

= \frac{1}{(2N + j + 1)} ∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N})

· \frac{1}{2N + 2} ((2N + 2)\binom{2N + 1}{i + 1} + (j − 1)\binom{2N + 2}{i + 1})

= \frac{1}{(2N + j + 1)}( − \frac{1}{2}(−1)^{2N+1} + \frac{1}{2} + \frac{j − 1}{2N + 2} (−\frac{1}{2}(−1)^{2N+2} + \frac{1}{2}) )

− \frac{1}{(2N + j + 1)}((−1)^{N} \binom{2N + 1}{N + 1}_{2}F_{1}[\begin{matrix}N + 1, −N \\ N + 2 \end{matrix}; 1]

+ \frac{j − 1}{2N + 2}(−1)^{N} \binom{2N + 2}{N + 1}_{2}F_{1}[\begin{matrix}N + 1, −N − 1 \\ N + 2 \end{matrix}; 1] )

= \frac{1}{(2N + j + 1)}(1 − (−1)^{N} \binom{2N + 1}{N + 1}\frac{N! (N + 1)!}{(2N + 1)!}

− (−1)^{N} \frac{j − 1}{2N + 2}\binom{2N + 2}{N + 1}\frac{(N + 1)!^{2}}{(2N + 2)!})

= \frac{1}{2N + j + 1} − \frac{(−1)^{N}}{2N + 2}.

Next we consider the evaluation of S_{2}. We have

S_{2} = \frac{1}{(2N + j + 1)} ∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N}) (2N + j − i)

· ∑_{ℓ=0}^{i}(−1)^{ℓ}\binom{ℓ + j − 1}{ℓ}\frac{1}{2π\sqrt{−1}}( ∫_{C} \frac{(1 + z)^{2N+j+1}}{z^{i−ℓ+1}} dz)( ∫_{0}^{1} x^{2N+ℓ+j+1} dx),

where C is a small contour in the complex plane encircling the origin in positive orientation. The sum over ℓ can be extended to a sum from 0 to ∞ since the terms corresponding to ℓ’s which are larger than i vanish. Hence, by evaluating the (geometric) sum over ℓ, we may rewrite this as

S_{2} = \frac{1}{(2N + j + 1)2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} ∑_{i=0}^{2N+1}(−1)^{i} (2^{i} − \binom{i}{N})

· \frac{d}{dz} (z^{2N+j−i})\frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} dz dx

= −\frac{1}{(2N + j + 1)2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} ∑_{i=0}^{2N+1}(−1)^{i} (2^{2N+1−i} − \binom{2N + 1 − i}{N})

· \frac{d}{dz} (z^{i+j−1})\frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} dz dx.

Consequently,

S_{2} = \frac{1}{(2N + j + 1)}(−S_{3} + S_{4}),  (5.25)

CENTERED SYMMETRIC RHOMBUS TILINGS OF A HEXAGON 41

where

S_{3} = \frac{1}{2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} ∑_{i=0}^{2N+1}(−1)^{i}2^{2N+1−i} \frac{d}{dz} (z^{i+j−1})\frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} dz dx

and

S_{4} = \frac{1}{2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} ∑_{i=0}^{2N+1}(−1)^{i}\binom{2N + 1 − i}{N}

· \frac{d}{dz} (z^{i+j−1})\frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} dz dx.

Now we evaluate S_{3}. Similarly to before, we may extend the sum over i to a sum from 0 to ∞. The resulting sum is again a geometric series, so that we obtain

S_{3} = \frac{1}{2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} 2^{2N+1} \frac{d}{dz} (\frac{z^{j−1}}{1 + \frac{z}{2}} ) \frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} dz dx

= \frac{2^{2N+1}}{2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} \frac{(j − 1 + (j − 2)\frac{z}{2})}{(1 + \frac{z}{2})^{2}} \frac{(1 + z)^{2N+j+1}}{z^{2N+2}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} dz dx.

Now we do the substitution z → z/(1 − z). Thereby, we obtain

S_{3} = \frac{2^{2N+1}}{2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} \frac{(j − 1 − j \frac{z}{2})}{(1 − \frac{z}{2})^{2}} \frac{x^{2N+j+1}}{z^{2N+2} (1 − z(1 − x))^{j}} dz dx

= \frac{2^{2N+1}}{2π\sqrt{−1}} ∫_{C} ∫_{0}^{1} \frac{(j − 1 − j \frac{z}{2})}{(1 − \frac{z}{2})^{2}} \frac{x^{2N+j+1}}{z^{2N+2}} ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}z^{h}(1 − x)^{h} dz dx

= \frac{2^{2N+1}}{2π\sqrt{−1}} ∫_{C} \frac{(j − 1 − j \frac{z}{2})}{(1 − \frac{z}{2})^{2}} ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 2)!} \frac{1}{z^{2N+2−h}} dz

= 2^{2N+1} ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 2)!}

· ((j − 1)(2N + 2 − h) − j(2N + 1 − h)) 2^{−2N−1+h}

= ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 2)!} (−2N − 2 + h + j) 2^{h}

= ∑_{h=0}^{2N+1} (\binom{h + j}{h + 1}\frac{(2N + j + 1)! (h + 1)!}{(2N + j + h + 2)!}2^{h+1} − \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 1)!}2^{h})

= \binom{2N + j + 1}{2N + 2}\frac{(2N + j + 1)! (2N + 2)!}{(4N + j + 3)!}2^{2N+2} − 1

= 2^{2N+2} \frac{(2N + j + 1)!^{2}}{(4N + j + 3)! (j − 1)!} − 1.

Finally, we compute S_{4}. In the earlier definition of S_{4}, we may again extend the sum over i to a sum from 0 to ∞. Using

\binom{2N + 1 − i}{N} = \frac{1}{2π\sqrt{−1}} ∫C̃ \frac{(1 + u)^{2N+1−i}}{u^{N+1}} du,

where C̃ is a small contour in the complex plane encircling the origin in positive orientation, we then obtain

S_{4} = \frac{1}{(2π\sqrt{−1})^{2}} ∫_{C̃} ∫_{C} ∫_{0}^{1} ∑_{i=0}^{∞}(−1)^{i} \frac{d}{dz} (z^{i+j−1})\frac{(1 + u)^{2N+1−i}}{u^{N+1}}

· \frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} du dz dx

= \frac{1}{(2π\sqrt{−1})^{2}} ∫_{C̃} ∫_{C} ∫_{0}^{1} \frac{d}{dz} (\frac{z^{j−1}}{1 + \frac{z}{1+u}} ) \frac{(1 + u)^{2N+1}}{u^{N+1}}

· \frac{(1 + z)^{2N+j+1}}{z^{2N+j}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} du dz dx

= \frac{1}{(2π\sqrt{−1})^{2}} ∫_{C̃} ∫_{C} ∫_{0}^{1} \frac{(j − 1) + (j − 2)\frac{z}{1+u}}{(1 + \frac{z}{1+u})^{2}} \frac{(1 + u)^{2N+1}}{u^{N+1}}

· \frac{(1 + z)^{2N+j+1}}{z^{2N+2}} \frac{x^{2N+j+1}}{(1 + xz)^{j}} du dz dx.

Again we do the substitution z → z/(1 − z). Thereby, we obtain

S_{4} = \frac{1}{(2π\sqrt{−1})^{2}} ∫_{C̃} ∫_{C} ∫_{0}^{1} \frac{(j − 1)(1 + u) − z(1 + (j − 1)u)}{(1 − \frac{uz}{1+u})^{2}}

· \frac{(1 + u)^{2N}}{u^{N+1}} \frac{x^{2N+j+1}}{z^{2N+2}(1 − z(1 − x))^{j}} du dz dx

= \frac{1}{(2π\sqrt{−1})^{2}} ∫_{C̃} ∫_{C} ∫_{0}^{1} \frac{(j − 1)(1 + u) − z(1 + (j − 1)u)}{(1 − \frac{uz}{1+u})^{2}}

· \frac{(1 + u)^{2N}}{u^{N+1}} \frac{x^{2N+j+1}}{z^{2N+2}} ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}z^{h}(1 − x)^{h} du dz dx

= \frac{1}{(2π\sqrt{−1})^{2}} ∫_{C̃} ∫_{C}(j − 1)(1 + u) − z(1 + (j − 1)u) ∑_{s=0}^{∞}(s + 1) (\frac{uz}{1 + u})^{s} \frac{(1 + u)^{2N}}{u^{N+1}}

· ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 2)!} \frac{1}{z^{2N+2−h}} du dz

= ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 2)!}((j − 1)(2N + 2 − h)\binom{h}{h − N − 1}

− (2N + 1 − h)\binom{h}{h − N} − (j − 1)(2N + 1 − h)\binom{h}{h − N − 1})

= ∑_{h=0}^{2N+1} \binom{h + j − 1}{h}\frac{(2N + j + 1)! h!}{(2N + j + h + 2)!} \frac{h!}{(h − N)! (N + 1)!}

· ((j − 1)(h − N) − (2N + 1 − h)(N + 1))

= ∑_{h=0}^{2N+1} (\frac{(h + j − 1)! h! (2N + j + 1)!}{(j − 1)! (h − N − 1)! (N + 1)! (2N + j + h + 1)!}

− \frac{(h + j)! (h + 1)! (2N + j + 1)!}{(j − 1)! (h − N)! (N + 1)! (2N + j + h + 2)!})

+ (j − 1) ∑_{h=0}^{2N+1} \frac{(h + j − 1)! (h + 1)! (2N + j + 1)!}{(j − 1)! (h − N)! (N + 1)! (2N + j + h + 2)!}

= −\frac{(2N + 1 + j)!^{2} (2N + 2)!}{(j − 1)! (N + 1)!^{2} (4N + j + 3)!}

+ (j − 1) ∑_{h=0}^{2N+1} \frac{(h + j − 1)! (h + 1)! (2N + j + 1)!}{(j − 1)! (h − N)! (N + 1)! (2N + j + h + 2)!}.

If we substitute all our findings in (5.24) and (5.25), then we have shown that

S = S_{1} − S_{2} + \frac{(j − 1) (2N + j)! (2N + j + 1)!}{(2N + 2) (j − 1)! (4N + j + 3)!} (2^{2N+1} − \binom{2N + 1}{N})

= S_{1} + \frac{S_{3} − S_{4}}{2N + j + 1} + \frac{(j − 1) (2N + j)! (2N + j + 1)!}{(2N + 2) (j − 1)! (4N + j + 3)!} (2^{2N+1} − \binom{2N + 1}{N})

= \frac{1}{2N + j + 1} − \frac{(−1)^{N}}{2N + 2} + \frac{(j − 1) (2N + j)! (2N + j + 1)!}{(2N + 2) (j − 1)! (4N + j + 3)!} (2^{2N+1} − \binom{2N + 1}{N})

+ \frac{1}{2N + j + 1}(2^{2N+2} \frac{(2N + j + 1)!^{2}}{(4N + j + 3)! (j − 1)!} − 1 + \frac{(2N + 1 + j)!^{2} (2N + 2)!}{(j − 1)! (N + 1)!^{2} (4N + j + 3)!}

− (j − 1) ∑_{h=0}^{2N+1} \frac{(h + j − 1)! (h + 1)! (2N + j + 1)!}{(j − 1)! (h − N)! (N + 1)! (2N + j + h + 2)!}).

A combination of the latter identity with (5.23) leads, after some trivial simplification, to (5.11). This finishes the proof. □

6. Proof of Corollary 1.7

Throughout this section, all asymptotics are taken as n → ∞ and x ∼ an. By Theorem 1.3, the probability that a random vertically symmetric rhombus tiling of a (2n, 2x + 1, 2n)-hexagon is centered is equal to R(n, x). Using expressions (1.5) and (1.4), we see that R(n, x) can be written in hypergeometric notation (after reversing the order of summation in (1.4) and dividing the sum in four parts) as

R(n, x) = 2^{3n−2} \frac{(2x + 2)! (x + 2n)!}{n! (x + 1)! (2x + 4n)!}
×(\frac{(2n − 1)!! (\frac{3}{2} − n)_{2n−1}(x + 1)_{n−1}(x + n + 1)_{n}}{(n − 1)! n!}_{4}F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, −n − x \\ n + 1, \frac{3}{2} − n, 1 − n − x \end{matrix}; −1]

− \frac{(2n − 1)!! (\frac{3}{2} − n)_{2n−1}(x + 1)_{n}(x + n + 2)_{n−1}}{(n − 1)! n!}_{4}F_{3}[\begin{matrix}1, x + n + 1, n + \frac{1}{2}, 1 − n \\ n + 1, \frac{3}{2} − n, x + n + 2 \end{matrix}; −1]

+ \frac{(−1)^{n+1}(2n)!! (\frac{3}{2} − n)_{2n−1}(x + 1)_{n−1}(x + n + 1)_{n}}{(n − 1)! n!}_{4}F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, −n − x \\ n + 1, \frac{3}{2} − n, 1 − n − x \end{matrix}; 1]

− \frac{(−1)^{n+1}(2n)!! (\frac{3}{2} − n)_{2n−1}(x + 1)_{n}(x + n + 2)_{n−1}}{(n − 1)! n!}_{4}F_{3}[\begin{matrix}1, x + n + 1, n + \frac{1}{2}, 1 − n \\ n + 1, \frac{3}{2} − n, x + n + 2 \end{matrix}; 1] ).

This simplifies to

R(n, x) = (−1)^{n+1}2^{2n−2} \frac{(x + 2n)}{n(x + n)} \frac{Γ(2x + 2) Γ(x + 2n)^{2} Γ(n + \frac{1}{2})}{Γ(x + 1)^{2} Γ(2x + 4n) Γ(\frac{3}{2} − n) Γ(n)^{2}}

× ((−1)^{n+1} \frac{(2n)!}{4^{n} n!^{2}}_{4}F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, −n − x \\ n + 1, \frac{3}{2} − n, 1 − n − x \end{matrix}; −1]

− (−1)^{n+1} \frac{(2n)!}{4^{n} n!^{2}} \frac{x + n}{x + n + 1}_{4}F_{3}[\begin{matrix}1, x + n + 1, n + \frac{1}{2}, 1 − n \\ n + 1, \frac{3}{2} − n, x + n + 2 \end{matrix}; −1]

+_{4}F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, −n − x \\ n + 1, \frac{3}{2} − n, 1 − n − x \end{matrix}; 1]

− \frac{x + n}{x + n + 1}_{4}F_{3}[\begin{matrix}1, x + n + 1, n + \frac{1}{2}, 1 − n \\ n + 1, \frac{3}{2} − n, x + n + 2 \end{matrix}; 1] ). (6.1)

Using Stirling’s formula, it is a routine matter to determine the asymptotic behaviour of the term in the first row in (6.1):

(−1)^{n+1}2^{2n−2} \frac{(x + 2n)}{n(x + n)} \frac{Γ(2x + 2) Γ(x + 2n)^{2} Γ(n + \frac{1}{2})}{Γ(x + 1)^{2} Γ(2x + 4n) Γ(\frac{3}{2} − n) Γ(n)^{2}} ∼ \frac{\sqrt{a(a + 2)}}{π(a + 1)} \frac{1}{n}. (6.2)

To deal with the _{4}F_{3}-series in (6.1), we shall use the next lemma.

Lemma 6.1. Let b be a real number with |b| > 1. Then, for any non-negative integer r and any sequence (b_{n})_{n≥1} with b_{n} → b as n → ∞, we have

lim_{n→∞} \frac{1}{n} _{4}F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, b_{n}n + r \\ n + 1, \frac{3}{2} − n, b_{n}n + r + 1 \end{matrix}; 1] = \frac{2b}{b + 1}\sqrt{\frac{b + 1}{b − 1}} arctan (\sqrt{\frac{b − 1}{b + 1}}) . (6.3)

Before we prove this result, we show how it leads to Corollary 1.7. First, Lemma (6.3) provides the asymptotic behaviour of the last two _{4}F_{3}-series in (6.1). Moreover, it is easily checked that the absolute value of the first (respectively second) _{4}F_{3}-series is asymptotically less than the third _{4}F_{3}-series (respectively fourth) _{4}F_{3}-series in (6.1), which is O(n) by Lemma 6.1. This, combined with the fact that \frac{(2n)!}{4^{n} n!^{2}} ∼ (πn)^{−1/2}, shows that the contribution of the first two _{4}F_{3}-series in (6.1) is negligible in the limit. Altogether, by (6.2) and Lemma 6.1, we see that R(n, x) is asymptotically equal to

\frac{\sqrt{a(a + 2)}}{π(a + 1)} (\frac{2(a + 1)}{a}\sqrt{\frac{a}{a + 2}} arctan (\sqrt{\frac{a + 2}{a}})

−\frac{2(a + 1)}{a + 2}\sqrt{\frac{a + 2}{a}} arctan (\sqrt{\frac{a}{a + 2}}))

= \frac{2}{π} arctan (\frac{1}{\sqrt{a(a + 2)}}) = \frac{2}{π} arcsin (\frac{1}{a + 1}) ,

as desired. To conclude the proof of Corollary 1.7, it remains to prove Lemma 6.1.

Proof of Lemma 6.1. If we write the _{4}F_{3}-series in (6.3) explicitly as a sum over k, after some simplification, we obtain

4F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, b_{n}n + r, \\ n + 1, \frac{3}{2} − n, b_{n}n + r + 1 \end{matrix}; 1]

= ∑_{k=0}^{n−1} \frac{(n + \frac{1}{2})_{k}(1 − n)_{k}(b_{n}n + r)_{k}}{(n + 1)_{k}(\frac{3}{2} − n)_{k}(b_{n}n + r + 1)_{k}}

= ∑_{k=0}^{n−1} \frac{(b_{n}n + r)n(n − \frac{1}{2})}{(b_{n}n + r + k)} \frac{Γ(n)^{2} Γ(n + k + \frac{1}{2}) Γ(n − k − \frac{1}{2})}{Γ(n + \frac{1}{2})^{2} Γ(n + k + 1) Γ(n − k)}.  (6.4)

Let us denote the summand in the latter sum by F (n, k). It is easy to check that F (n, k) > 0 for 0 ≤ k ≤ n − 1, and that

F (n, 0) = 1 and F (n, n − 1) ∼ \frac{b}{b + 1}\sqrt{\frac{π}{2}} n^{1/2} as n → ∞.  (6.5)

Moreover, a routine computation shows that (\frac{∂^{2}}{∂k^{2}} F (n, k))/F (n, k) is equal to

(ψ(n + k + 1/2) − ψ(n − k − 1/2) − ψ(n + k + 1) + ψ(n − k) − \frac{1}{b_{n} + k + r})^{2}

+ (ψ_{1}(n + k + 1/2) + ψ_{1}(n − k − 1/2) − ψ_{1}(n + k + 1) − ψ_{1}(n − k) + \frac{1}{(b_{n} + k + r)^{2}} ),

where ψ and ψ_{1} are the digamma and trigamma functions defined by ψ(x) = \frac{d}{dx} log(Γ(x)) and ψ_{1}(x) = \frac{d^{2}}{dx^{2}} log(Γ(x)) = \frac{d}{dx}ψ(x). Since the trigamma function ψ_{1} is decreasing, the above expression is positive. Consequently, for fixed n ≥ 1, the summand F (n, k) is convex as a function in k. Combined with (6.5), this implies that the sum in (6.4) may be approximated by an integral and

∑_{k=0}^{n−1} F (n, k) = ∫_{0}^{n−1} F (n, k) dk + O(n^{1/2}) = ∫_{n^{1/3}}^{n−n^{1/3}} F (n, k) dk + O(n^{1/2+1/3}). (6.6)

Using the expression (6.4) for F (n, k) and the asymptotic approximation

Γ(z + \frac{1}{2}) = z^{−1/2}Γ(z + 1) (1 + O (z^{−1})) , z → ∞,

we see after some manipulation that

F (n, k) = \frac{b_{n}n}{(b_{n}n + k)\sqrt{1 − \frac{k^{2}}{n^{2}}}} (1 + O(n^{−1/3})) , for n^{1/3} ≤ k ≤ n − n^{1/3}.

Combined with (6.6), this leads to

∑_{k=0}^{n−1} F (n, k) = (∫_{n^{1/3}}^{n−n^{1/3}} \frac{b_{n}n}{(b_{n}n + k)\sqrt{1 − \frac{k^{2}}{n^{2}}}} dk) (1 + O(n^{−1/3})) + O(n^{5/6}),

which, after the substitution y = k/n, gives

∑_{k=0}^{n−1} F (n, k) = n (∫_{n^{−2/3}}^{1−n^{−2/3}} \frac{b_{n}}{(b_{n} + y)\sqrt{1 − y^{2}}} dy) (1 + O(n^{−1/3})) + O(n^{5/6}).

Dividing both sides by n and taking the limit, we obtain

lim_{n→∞} \frac{1}{n} _{4}F_{3}[\begin{matrix}1, n + \frac{1}{2}, 1 − n, b_{n}n + r, \\ n + 1, \frac{3}{2} − n, b_{n}n + r + 1 \end{matrix}; 1] = ∫_{0}^{1} \frac{b}{b + y} \frac{1}{\sqrt{1 − y^{2}}} dy.

To finish the proof of the lemma, it remains to check that the above integral is equal to the right-hand side of (6.3), which amounts to a routine computation. □

References

[1] G. E. Andrews. Plane partitions I: The MacMahon conjecture. Studies in: Studies in Foundations and Combinatorics, G.-C. Rota (ed.), Adv. in Math. Suppl. Studies, vol. 1, 1978, pp. 131–150.

[2] W. N. Bailey. Generalized Hypergeometric Series, Cambridge University Press, Cambridge, 1935.

[3] M. Ciucu. Enumeration of lozenge tilings of punctured hexagons. J. Combin. Theory Ser. A 83 (1998), 268–272.

[4] M. Ciucu, T. Eisenkölbl, C. Krattenthaler and D. Zare. Enumeration of lozenge tilings of hexagons with a central triangular hole. J. Combin. Theory Ser. A 95 (2001), 251–334.

[5] M. Ciucu and C. Krattenthaler. The number of centered lozenge tilings of a symmetric hexagon. J. Combin. Theory Ser. A 86 (1999), 103–126.

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

[7] M. Ciucu and C. Krattenthaler. The interaction of a gap with a free boundary in a two dimensional dimer system. Commun. Math. Phys. 302 (2011), 253–289.

[8] M. Ciucu and C. Krattenthaler. A dual of MacMahon’s theorem on plane partitions. Proc. Natl. Acad. Sci. USA 110 (2013), 4518–4523.

[9] T. Eisenkölbl. Rhombus tilings of a hexagon with two triangles missing on the symmetry axis. Electron. J. Combin. 6(1) (1999), Art. #R30, 19 pp.

[10] I. Fischer. Enumeration of rhombus tilings of a hexagon which contain a fixed rhombus in the centre. J. Combin. Theory Ser. A 96 (2001), 31–88.

[11] I. Fischer. Another refinement of the Bender–Knuth (ex-)conjecture. Europ. J. Combin. 27 (2006), 290–321.

[12] M. Fulmek and C. Krattenthaler. The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis I. Ann. Combin. 2 (1998), 19–41.

[13] M. Fulmek and C. Krattenthaler. The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis II. Europ. J. Combin. 21 (2000), 601–640.

[14] G. Gasper and M. Rahman. Basic Hypergeometric Series, Encyclopedia of Mathematics And Its Applications, vol. 35, Cambridge University Press, Cambridge, 1990.

[15] B. Gordon. A proof of the Bender–Knuth conjecture. Pacific J. Math. 108 (1983), 99–113.

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

[17] I. Gessel and H. Helfgott. Enumeration of tilings of diamonds and hexagons with defects. Electron. J. Combin. 6 (1999), Art. #R16, 26 pp.

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

[19] C. Krattenthaler, The Major Counting of Nonintersecting Lattice Paths and Generating Functions for Tableaux. Mem. Amer. Math. Soc., vol. 115, no. 552, Providence, R. I., 1995.

[20] C. Krattenthaler. An alternative evaluation of the Andrews–Burge determinant. In: Mathematical Essays in Honor of Gian-Carlo Rota, B. E. Sagan, R. P. Stanley (eds.), Progress in Math., vol. 161, Birkhäuser, Boston, 1998, pp. 263–270.

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

[22] C. Krattenthaler and S. Okada. The number of rhombus tilings of a “punctured” hexagon and the minor summation formula. Adv. Appl. Math. 21 (1998), 381–404.

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

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

[25] P. Paule and M. Schorn. A Mathematica version of Zeilberger’s algorithm for proving binomial coefficient identities. J. Symbol. Comp. 20 (1995), 673–698.

[26] M. Petkovšek, H. Wilf and D. Zeilberger. A=B, A. K. Peters, Wellesley, 1996.

[27] R. A. Proctor. Bruhat lattices, plane partitions generating functions, and minuscule representations. Europ. J. Combin. 5 (1984), 331–350.

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

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

[30] L. J. Slater. Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

Fakultät für Mathematik, Universität Wien, Nordbergstrasze 15, A-1090 Vienna, Austria