THE INTERACTION OF A GAP WITH A FREE

BOUNDARY IN A TWO DIMENSIONAL DIMER SYSTEM

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

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

Fakultät für Mathematik der Universität Wien, Nordbergstraße 15, A-1090 Wien, Austria.

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

Abstract. Let ℓ be a fixed vertical lattice line of the unit triangular lattice in the plane, and let H be the half plane to the left of ℓ. We consider lozenge tilings of H that have a triangular gap of side-length two and in which ℓ is a free boundary — i.e., tiles are allowed to protrude out half-way across ℓ. We prove that the correlation function of this gap near the free boundary has asymptotics \frac{1}{4πr}, r → ∞, where r is the distance from the gap to the free boundary. This parallels the electrostatic phenomenon by which the field of an electric charge near a conductor can be obtained by the method of images.

1. Introduction

The study of the interaction of gaps in dimer coverings was introduced in the literature by Fisher and Stephenson [15]. This pioneering work contains three different types of gap interaction in dimer systems on the square lattice: (i) interaction of two dimer-gaps (equivalently, interaction of two fixed dimers required to be contained in the dimer coverings); (ii) interaction of two non-dimer-gaps (specifically, two monomers), and (iii) the interaction of a dimer-gap with a constrained boundary (edge or corner).

The first of these types of interactions was later generalized by Kenyon [20] to an arbitrary number of dimer-gaps on the square and hexagonal lattices, and recently by Kenyon, Okounkov and Sheffield [22] to general planar bipartite lattices. Interactions of the second type were studied by the first author of the present paper in [5][6][7][8][9], where close analogies to two dimensional electrostatics were established.

Typeset by AMS-TEX

†Research partially supported by NSF grant DMS-0500616.

‡Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory.”

Two instances of interaction of non-dimer-gaps with constrained boundaries can be found in [21, Section 7.5] (interaction of a monomer with a constrained straight line boundary on the square lattice), and respectively [6, Theorem 2.2] (interaction of a family of triangular gaps with a constrained straight line boundary on the hexagonal lattice).

In this paper we determine the interaction of a triangular gap with a free straight line boundary (i.e., dimers are allowed to protrude out across it) on the hexagonal lattice. This type of interaction has not been treated before in the literature. (We are aware of one other paper, namely [12], addressing the asymptotic behavior of lozenge tilings under the presence of a free boundary, but the regions considered there contain no gaps.) We find that the gap is attracted to the free boundary in precise analogy to the (two dimensional) electrostatic phenomenon in which an electric charge is attracted by a straight line conductor when placed near it.

This develops further the analogy between dimer systems with gaps and electrostatics that the first author has described in [6][7][8][9]. More generally, our result shows that in any physical system that can be modeled by dimer coverings, a gap will tend to be attracted to an interface corresponding to a free boundary. This effect, purely entropic in origin, is reminiscent of the Cheerios effect by which an air bubble at the surface of a liquid in a container is attracted to the walls [35] (note that the Cheerios effect is not entropic in origin).

2. Set-up and results

There seem to be no methods in the literature for finding the interaction of a gap “in a sea of dimers” with a free boundary. However, as V. I. Arnold said, “mathematics is a part of physics where experiments are cheap.” We now design such an experiment in order to determine the interaction of a gap in a dimer system on the hexagonal lattice with a free boundary.

Consider the triangular lattice in the plane consisting of unit equilateral triangles, drawn so that one family of lattice lines is vertical. Note that the hexagonal lattice is the dual of the triangular lattice. (To be precise, the hexagonal graph arises as the graph whose vertices are the unit triangles, and whose edges connect precisely those unit triangles that share an edge.) Dimers on the hexagonal lattice then correspond to lozenges (i.e., unit rhombi) consisting of pairs of adjacent unit triangles.

The free boundary we choose is a lattice line ℓ — say vertical — on the triangular lattice, to the left of which the plane is covered completely and without overlapping by lozenges, except for a gap ◁_{2} in the shape of a triangle of side-length 2, pointing to the left; the lozenges are allowed to protrude halfway across the free boundary, to its right. (Figure 1 pictures a portion of such a tiling.)

We define the correlation function (or simply correlation) of the hole ◁_{2} with the free boundary ℓ as follows. Choose a rectangular system of coordinates in which ℓ is the yaxis, the origin is some lattice point on ℓ, and the unit is the lattice spacing. Let ◁_{2}(k) be the placement of ◁_{2} so that the center C of its right side has coordinates (−k\sqrt{3}, 0) (i.e., C and the origin are the endpoints of a string of k contiguous horizontal lozenges; Figure 1 illustrates ◁_{2}(2), the origin being denoted by O there). Let H_{n,x} be the lattice hexagon of side-lengths 2n, 2n, 2x, 2n, 2n, 2x (in counter-clockwise order, starting with the

O C  ℓ

A partial lozenge tiling of the left half plane with a gap

Figure 1

southwestern side) centered at the origin (thus H_{n,x} is vertically symmetric about ℓ, and its horizontal symmetry axis cuts ◁_{2}(k) into two equal parts; for example, Figure 2 shows the hexagon H_{4,4} with the triangular hole ◁_{2}(2)). Let F_{n,x} be the region obtained from the left half of H_{n,x} by regarding its boundary along ℓ as free (i.e., lozenges in a tiling of F_{n,x} are allowed to protrude outward across ℓ). Figure 3 shows the region F_{3,3} together with such a lozenge tiling; the origin is labelled by O.

Following [15] and [6], for any fixed integer k ≥ 0 we define the correlation of ◁_{2}(k) with the free boundary ℓ, denoted ω_{f}(k), by

ω_{f}(k) := lim_{n→∞} \frac{M(F_{n,n} \ ◁_{2}(k))}{M(F_{n,n})},  (2.1)

where M(R) stands for the number of lozenge tilings of the region R (if R has portions of the boundary that are free — as in our case — then it is understood that what we count is tilings in which lozenges are allowed to protrude out across the free portions). A tiling of F_{4,4} \ ◁_{2}(2) of this type is illustrated in Figure 1.

} } 2x{  2n 2n  O ℓ

The hexagon H_{n,x} with n = x = 4

Figure 2

We note that, by [11], in a regular hexagon lozenges have maximum entropy statistics (in the scaling limit) at the center. According to this, (2.1) is a natural definition for the correlation function. An analogous definition was used in [6].

In fact, it is worth generalizing the definition of correlation (2.1) to the situation when the side-lengths 2n and 2x of the half hexagon F_{n,x} go to infinity at different rates. More precisely, for any real number ξ > 0, define ω_{f}(k; ξ) by

ω_{f}(k; ξ) := lim_{n→∞} \frac{M(F_{n,ξ_{n}n} \ ◁_{2}(k))}{M(F_{n,ξ_{n}n})},  (2.2)

where (ξ_{n})_{n≥1} is a suitable sequence of rational numbers approaching ξ. (“Suitable” here means that we have to choose ξ_{n} in such a way that ξ_{n}n is integral.) The number ω_{f}(k; ξ) is the correlation of the triangular gap ◁_{2}(k) with the free boundary, obtained when the large regions used in the definition are the left halfs of hexagons that are not necessarily regular, but have their left vertical side ξ times as long as the two oblique sides.

Figure 3

In Lemma 13 we obtain an exact expression for ω_{f}(k; ξ) in terms of an integral. What affords this is an exact formula for M(F_{n,x} \ ◁_{2}(k)), which we present in Theorem 4. We then deduce the asymptotics of ω_{f}(k; ξ) as k → ∞ using Laplace’s method (see Lemma 14 and the proof of Theorem 1 in Section 7). The result is the following.

Theorem 1. As k → ∞, the correlation ω_{f}(k; ξ) is asymptotically

ω_{f}(k; ξ) ∼ \frac{1}{π(1 + ξ)^{2}\sqrt{ξ(2 + ξ)}} · \frac{1}{k} (\frac{2}{1 + ξ} )^{4k} .  (2.3)

Remark 1. Note that, by the results of [11], we should expect distorted dimer statistics around the gap for ξ ≠ 1. As the theorem above shows, the distortion is quite radical. Indeed, for ξ = 1, Theorem 1 gives

ω_{f}(k) = ω_{f}(k; 1) ∼ \frac{1}{4π\sqrt{3}} · \frac{1}{k} = \frac{1}{4π} \frac{1}{d(◁_{2}(k), ℓ)},  (2.4)

where d is the Euclidean distance. However, for ξ ≠ 1, ω_{f}(k; ξ) decays exponentially to 0 or blows up exponentially, according as ξ > 1 or ξ < 1.

Remark 2. The exponential behavior of ω_{f}(k; ξ) for ξ ≠ 1 is in fact closely mirrored also in the setting of [6], where the correlation of holes was defined by including them at the center of large hexagons. Indeed, using arguments of [6], it follows that the correlation of two ◁_{2}’s on the symmetry axis of the hexagons is exponential for ξ ≠ 1. This has the interesting consequence that the limits of entries of the inverse Kasteleyn matrices of hexagons on the one hand and of “corresponding” tori on the other do not agree, not even at the center of the hexagons.

To be more precise, note that the center of large hexagons is in the liquid regime of [22]. By [32, Ch. 8 and 9] (see also [22, Theorem 2.1]), there exists an ergodic Gibbs measure coming from (weighted) lozenge tilings on a large torus whose slope is the same as the slope of the limit shape at the center of the large hexagon. One might be tempted to guess that, in this situation, the entries of the inverse Kasteleyn matrix (which determine correlation) behave similarly in the limit. However, using [22, Theorem 4.3, (7), with P (z, w) = a+bz+cw and Q(z, w) = 1] and appropriate asymptotic expansions in the special case that we are interested in, it turns out that the correlation of two ◁_{2}’s under any torus measure in the liquid regime behaves polynomially in the distance of the ◁_{2}’s, in contrast to the exponential behavior for the hexagon mentioned above.

This provides a concrete example highlighting the subtlety of taking limits of entries of the inverse Kasteleyn matrix: they depend quite sensitively on how the infinite plane is achieved as a limit of graphs.

In [7] the first author described how a distribution of fixed holes on the triangular lattice defines in a natural way two vector fields. The F-field is a discrete vector field defined at the center of each left-pointing unit triangle e, and equal to the expected orientation of the lozenge covering e (under the uniform measure on the set of tilings). To define the T-field, one introduces an extra “test-hole” t and measures the relative change in the correlation function under small displacements of it, as the other holes are kept fixed. One can prove (details will appear elsewhere) that in the scaling limit of the lattice spacing approaching zero, this relative change is given by the scalar product of the displacement vector with a certain vector T(z), where z is the point to which the test hole t shrinks when the lattice spacing approaches zero. This defines the second field.

When these fields are generated by lozenge tilings that cover the entire plane with the exception of a finite collection of fixed-size holes (the case treated in [7] and [9]), both the T-field and the scaling limit of the F-field turn out to be equal, up to a constant multiple, to the electrostatic field of the two dimensional physical system obtained by viewing the holes as electrical charges.

But what if we do not tile the entire plane, but only the half-plane to the left of the free boundary ℓ, and we have no holes?

The above definitions for the F-field and T-field would still work, provided (i) the scaling limit of the discrete field defining F exists, and (ii) the scaling limit of the relative changes in the correlation function under small displacements of a test hole exists and is given by taking scalar products of the displacement vector with the vectors of a certain field.

Our exact determination of ω_{f}(k; ξ) (see Lemma 13) allows us to verify (ii) for displacements along the horizontal direction. ◁_{2}(k) plays now the role of a test charge. The expression that measures the relative change in correlation in this case is \frac{ω_{f} (k+1;ξ)}{ω_{f} (k;ξ)} − 1. What we have to do is to determine the leading term in the asymptotics of this expression as k → ∞. We obtain the following result, whose proof is given in Section 7.

Theorem 2. We have

\frac{ω_{f}(k + 1; ξ)}{ω_{f}(k; ξ)} − 1 = \{ \begin{matrix}(\frac{2}{1 + ξ} )^{4} − 1 + O (\frac{1}{k} ) & if ξ ≠ 1, \\ −\frac{1}{k} + O (\frac{1}{k^{2}} ) & if ξ = 1, \end{matrix}  (2.5)

as k → ∞.

Remark 3. In order to indicate the dependence on ξ (the asymptotic ratio of the sides of our half hexagon), we write T_{ξ} for the T-field. By symmetry, displacements of ◁_{2}(k) parallel to ℓ leave ω_{f} unchanged, so the relative change in ω_{f} corresponding to such displacements is zero.

Suppose that ξ ≠ 1. Then, provided the field T_{ξ} exists, it follows from Theorem 2 that its value at z is

T_{ξ}(z) = \frac{e_{1}}{2\sqrt{3}} ((\frac{2}{1 + ξ} )^{4} − 1) ,  (2.6)

where e_{1} is the unit vector in the positive direction of the x-axis (the 2\sqrt{3} at the denominator comes from the fact that T_{ξ} arises from the expression on the left-hand side of (2.5) divided by the product of the displacement, \sqrt{3} in this case, and the “charge” of the hole ◁_{2}(k), which is 2; see [7] for details). In particular, the field T_{ξ} is constant.

On the other hand, if ξ = 1, then the second assertion in Theorem 2 yields

T_{1}(z) = −\frac{e_{1}}{2\sqrt{3} k} = −\frac{e_{1}}{2 d(z, ℓ)}.  (2.7)

Note that by [7] we would obtain (up to a multiplicative constant of 2) the same T-field at z if we look at tilings of the entire plane, with the mirror image of our test-hole ◁_{2}(k) being a fixed hole. This is analogous to the phenomenon in electrostatics by which the field created by an electric charge placed near a conductor can be obtained by the method of images (see e.g. [13, Chapter 6]).

The F-field could be determined by an “experiment” analogous to the one we described at the beginning of this section: simply replace ◁_{2}(k) by L(k), the horizontal lozenge contained in ◁_{2}(k).

Recall that, by definition, the F-field at a left-pointing unit triangle ◁ is determined by the probabilities p_{1}, p_{2}, p_{3} that ◁ is occupied by a horizontal, northwest-pointing, or southwest-pointing lozenge, respectively. More precisely, (cf. [9])

F(◁) = p_{1}e_{1} + p_{2}e_{2} + p_{3}e_{3},

where e_{1}, e_{2}, e_{3} are unit vectors parallel to the long diagonals of the above three lozenges, that is, e_{1} = (1, 0), e_{2} = (−\frac{1}{2}, \frac{\sqrt{3}}{2}), e_{3} = (−\frac{1}{2}, −\frac{\sqrt{3}}{2}). Hence, since p_{2} = p_{3} by symmetry and p_{1} + p_{2} + p_{3} = 1, it suffices to determine p_{1}, that is, the limit of the proportion of the number of lozenge tilings of F_{n,x} that contain L(k), as n and x go to infinity so that x/n approaches a fixed positive real number ξ.

It turns out that, for fixed n, x, and k, the number of lozenge tilings of F_{n,x} \ L(k) is given by a formula similar to (3.2), namely by the formula in Theorem 15. By lemmas that are analogous to Lemmas 12–14 (see Lemmas 16 and 17, and the text in between), one can then derive that the probability p_{1} is given by (see Corollary 18)

p_{1} = \frac{2}{π} arctan \frac{1}{\sqrt{ξ(2 + ξ)}}.  (2.8)

Using standard formulas for trigonometric functions, it can be seen that this value agrees with the probability of finding a lozenge in the center of a random tiling of a hexagon with side-lengths 2n, 2n, 2x, 2n, 2n, 2x in the limit n, x → ∞ so that x/n approaches ξ, as given in [11, Conjecture 6.1] (with x = y = 0, α = γ = 1, β = ξ), proved in [3, Theorem 3.12]. (In fact, in the special case that is relevant here, Conjecture 6.1 of [11] was proved earlier in [10, Cor. 4].) Thus, the free boundary has no disturbing effect at all on the lozenge statistics.

Let F_{ξ} denote the F-field for the above situation. Then the definition of the F-field and the above considerations imply the following result.

Corollary 3. Let e(k) be the leftmost left-pointing unit triangle of ◁_{2}(k). Then

F_{ξ}(e(k)) = \frac{3p_{1} − 1}{2}e_{1},  (2.9)

where p_{1} is given by (2.8).

Remark 4. In the case where ξ = 1, equations (2.7) and (2.9) imply that, in sharp contrast to the case of lozenge tilings of the plane with a finite number of fixed size holes, where the T- and F-field are the same up to a constant multiple (cf. the second paragraph after Remark 2), for the half-plane with free boundary the fields T and F have radically different behavior: while in the scaling limit the former behaves as the electrostatic field near a conductor, the latter is zero.

It is amusing that, aside from ξ = 1, there is precisely one other value of ξ where the field intensities in (2.6) and (2.9) agree. Figure 4 shows a plot of the two functions, with the intensity in (2.9) being the one approaching −1/2 for ξ → ∞. Numerically, this other value of ξ is 3.28262 …

Our approach to proving Theorems 1 and 2 consists of solving first the counting problem exactly, see Theorem 4. This result generalizes Andrews’ theorem [1] (which proved MacMahon’s conjecture on symmetric plane partitions) in the case q = 1. Its proof is given in Sections 4 and 5, with some auxiliary results proved separately in Section 6. It is based on the “exhaustion/identification of factors” method described in [25, Sec. 2.4]. In Section 7, we perform the asymptotic calculations needed to derive Theorems 1 and 2 from the exact counting results. The final section, Section 8, presents the results that are needed for the determination of the F-field F_{ξ} reported in Corollary 3.

3. An exact tiling enumeration formula

Tilings of the region F_{n,x} are clearly equivalent to tilings of the hexagon H_{n,x} that are invariant under reflection across its symmetry axis ℓ. Counting such tilings was a problem

Figure 4

considered (in the equivalent form of symmetric plane partitions) by MacMahon in the early twentieth century (see [28, p. 270]). MacMahon conjectured that the number of vertically symmetric lozenge tilings of a hexagon with side-lengths 2n, 2n, 2x, 2n, 2n, 2x is equal to

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

where (α)_{m} is the Pochhammer symbol, defined by (α)_{m} := α(α + 1) ⋯ (α + m − 1) for m ≥ 1, and (α)_{0} := 1. This was first proved by Andrews [1]. Other proofs, and refinements, were later found by e.g. Gordon [17], Macdonald [27, pp. 83–85], Proctor [31, Prop. 7.3], Fischer [14], and the second author of the present paper [23, Theorem 13].

Our “experiment” — counting M(F_{n,x} \ ◁_{2}(k)) — is by the same token equivalent to counting vertically symmetric lozenge tilings of H_{n,x} with two missing triangles (compare Figures 1 and 5). This is in fact a generalization of MacMahon’s symmetric plane partitions problem (see Remark 5).

The key result that allows deducing Theorems 1 and 2 is the following.

ℓ } } 2x{  2n 2n

A symmetric lozenge tiling of the hexagon H_{n,x} with two holes

Figure 5

Theorem 4. For all positive integers n, x and nonnegative integers k ≤ n − 1, we have

M(F_{n,x} \ ◁_{2}(k)) = \binom{4k + 1}{2k} \frac{(n + k)!}{(x + n − k)_{2k+1}} ∏_{s=1}^{n} \frac{(2x + 2s)_{4n−4s+1}}{(2s)_{4n−4s+1}}

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

· ((x)_{i} (x + i + 1)_{n−k−i−1} (x + n + k + 1)_{n−k}

− (x)_{n−k} (x + n + k + 1)_{n−k−i−1} (x + 2n − i + 1)_{i}). (3.2)

Remark 5. Replacing x by x − 1, n by n + 1, and k by n, one can see that the above formula specializes to MacMahon’s formula (3.1). More precisely, because of forced lozenges (see Figure 6), the enumeration problem in the statement of Theorem 4 reduces to the

Forced lozenges when the hole touches the left border

Figure 6

problem of enumerating vertically symmetric lozenge tilings of a hexagon with side-lengths 2n, 2n, 2x, 2n, 2n, 2x.

The proof of Theorem 4 is given in the next two sections. In Section 4, we show that M(F_{n,x}\◁_{2}(k)) can be expressed in terms of a certain Pfaffian. This Pfaffian is then evaluated in Section 5.

4. Lozenge tilings and nonintersecting lattice paths

The purpose of this section is to find a manageable expression for M(F_{n,x} \ ◁_{2}(k)) (see Lemma 6 at the end of this section). In this context, we will find it more convenient to think of the tilings of F_{n,x} \ ◁_{2}(k) directly as tilings of a half hexagon with an open boundary (cf. Figure 7) as opposed to symmetric tilings of a hexagon with two holes (cf. Figure 5). There is a well known bijection between lozenge tilings of lattice regions and families of “paths of lozenges” (see Figure 7), which in turn are equivalent to families of non-intersecting lattice paths (see Figure 8). Its application to our situation is illustrated in Figures 7 and 8. The origin of the system of coordinates indicated in Figure 8 corresponds to the point O′ in Figure 7 (note that the bottommost path of lozenges in Figure 7 is empty for the illustrated tiling; the corresponding lattice path in Figure 8 has no steps).

OO′ C

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

Figure 7

By this bijection, lozenge tilings of F_{n,x} \ ◁_{2}(k) are seen to be equinumerous with families (P_{1}, P_{2}, …, P_{2n}) of non-intersecting lattice paths consisting of unit horizontal and vertical steps in the positive direction, where P_{i} runs from A_{i} = (−i, i) to some point from the set I ∪ {S_{1}, S_{2}}, i = 1, 2, …, 2n, with

I = {(−1, s) : s = 1, 2, …, 2x + 2n},
S_{1} = (−2k − 1, x + n + k),
S_{2} = (−2k − 2, x + n + k + 1),  (4.1)

and the additional condition that S_{1} and S_{2} must be ending points of some paths.

At this point, we need a slight extension of Theorem 3.2 in [34] (which is, in fact, derivable from the minor summation formula of Ishikawa and Wakayama [19, Theorem 2]). The reader should recall that the Pfaffian of a skew-symmetric 2n × 2n matrix A can be defined by (see

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • • •  • • • • • • •  ∘^{A_{1}}^{A_{2}}^{A_{3}}^{A_{4}}^{A_{5}}^{A_{6}}^{A_{7}}^{A_{8}}  ^{S_{1}}^{S_{2}}  ^{P_{1}}^{P_{2}}^{P_{3}}^{P_{4}}^{P_{5}}^{P_{6}}^{P_{7}}^{P_{8}}  ^{O′} _{x}^{y}

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

Figure 8

e.g. [34, p. 102])

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

where M[1, 2, …, 2n] denotes the set of all perfect matchings (1-factors) of (the complete graph on) {1, 2, …, 2n}, and where sgn π = (−1)^{cr(π)}, with cr(π) denoting the number of “crossings” of π, that is, the number of quadruples i < j < k < l such that, under π, i is paired with k, and j is paired with l. It is a well-known fact (see e.g. [34, Prop. 2.2]) that

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

Theorem 5. Let {A_{1}, A_{2}, …, A_{p}, S_{1}, S_{2}, …, S_{q}} and I = {I_{1}, I_{2}, … } be finite sets of lattice points in the integer lattice ℤ^{2}, with p + q even. Then

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

where 𝔖_{p} denotes the symmetric group on {1, 2, …, p}, A_{π} = (A_{π(1)}, A_{π(2)}, …, A_{π(p)}), and P^{nonint}(A_{π} → S ∪ I) is the number of families (P_{1}, P_{2}, …, P_{p}) of non-intersecting lattice paths consisting of unit horizontal and vertical steps in the positive direction, with P_{k} running from 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}. The matrix Q = (Q_{i,j})_{1≤i,j≤p} is defined by

Q_{i,j} = ∑_{1≤s<t} (P(A_{i} → I_{s}) · P(A_{j} → I_{t}) − P(A_{j} → I_{s}) · P(A_{i} → I_{t})),  (4.5)

where P(A → E) denotes the number of lattice paths from A to E, and the matrix H = (H_{i,j})_{1≤i≤p, 1≤j≤q} by

H_{i,j} = P(A_{i} → S_{j}).

In the special case when the starting and ending points satisfy a certain compatibility condition (called D-compatibility in [34]), the only permutation π which contributes to the right-hand side of (4.4) is the identity permutation, and (4.4) reduces to [34, Theorem 3.2]. In our context, the compatibility condition is not satisfied. However, the same arguments that prove [34, Theorem 3.2] can be used to obtain (4.4). (Alternatively, one could use the minor summation formula of Ishikawa and Wakayama [19, Theorem 2]. In it, choose m = p, r = q, and the skew-symmetric matrix B to be B_{i,j} = 1 for i < j — which makes all principal Pfaffian minors of B equal 1 — to expand the Pfaffian on the left-hand side of (4.4) into a sum of minors of a certain matrix. Each minor can then be seen to count certain families of nonintersecting lattice paths by the general form of the Lindström–Gessel–Viennot theorem [26, Lemma 1], [16, Theorem 1], and, altogether, these are the families that are described in the statement of Theorem 5.)

Remark 6. In the case where p > q+|I|, there are more starting points than available ending points. However, Theorem 5 still holds: then the right-hand side of (4.4) is clearly zero, and the Pfaffian on the left-hand side follows to be zero by the above indicated arguments that prove Theorem 5.

We now apply Theorem 5 to our situation, that is, p = 2n, q = 2, A_{i} = (−i, i), for i = 1, 2, …, 2n, and S_{1}, S_{2}, and I are given by (4.1). It is not difficult to convince oneself that, for this choice of starting and ending points, all families of nonintersecting lattice paths counted on the right-hand side of (4.4) give rise to even permutations π. Hence, the right-hand side of (4.4) indeed counts the families of nonintersecting lattice paths that we need to count. By Theorem 5, their number is equal to the negative value of the Pfaffian of

M_{n}(x) := ( \begin{matrix}Q & H \\ −H^{t} & 0 \end{matrix} ) ,  (4.6)

where Q is a (2n) × (2n) skew-symmetric matrix with (i, j)-entry Q_{i,j} given by (4.5), and where H is a (2n) × 2 matrix, in which the (i, j)-entry H_{i,j} is equal to the number of paths from A_{i} to S_{j}, i = 1, 2, …, 2n, j = 1, 2. (It is the negative value of the Pfaffian because of the sign (−1)^{\binom{q}{2}} on the right-hand side of (4.4), as we have q = 2.)

In particular, using the fact that the number of lattice paths on the integer lattice ℤ^{2} between two given lattice points is given by a binomial coefficient, we have

H_{i,1} = \binom{x + n − k − 1}{i − 2k − 1},  (4.7)
H_{i,2} = \binom{x + n − k − 1}{i − 2k − 2}.  (4.8)

On the other hand, substituting A_{i} = (−i, i) and I_{s} = (−1, s) in (4.5), we have

Q_{i,j} = ∑_{1≤s<t≤2x+2n}(P(A_{i} → I_{s}) · P(A_{j} → I_{t}) − P(A_{j} → I_{s}) · P(A_{i} → I_{t}))

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

= ∑_{1≤s≤t≤2x+2n} \binom{s − 1}{i − 1}\binom{t − 1}{j − 1} − ∑_{1≤s≤t≤2x+2n} \binom{s − 1}{j − 1}\binom{t − 1}{i − 1}

= ∑_{1≤t≤2x+2n} \binom{t}{i}\binom{t − 1}{j − 1} − ∑_{1≤t≤2x+2n} \binom{t}{j}\binom{t − 1}{i − 1}  (4.9)

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

where we used the well-known identity

∑_{t=0}^{X} \binom{t}{i − 1} = \binom{X + 1}{i}  (4.11)

to obtain (4.9). We may obtain an alternative expression for Q_{i,j} by replacing \frac{1}{t} \binom{t}{i} = \frac{1}{i} \binom{t−1}{i−1} in the last expression by \frac{1}{i} ∑_{l=0}^{i−1} \binom{t−j}{l}\binom{j−1}{i−l−1}, this equality being true because of the Chu– Vandermonde summation (cf. e.g. [18, Sec. 5.1, (5.27)])

∑_{l=0}^{L} \binom{M}{l}\binom{N}{L − l} = \binom{M + N}{L},  (4.12)

where L is a non-negative integer. Thus, we arrive at

Q_{i,j} = ∑_{l=0}^{i−1} ∑_{t=1}^{2x+2n} \frac{j − i}{i}\binom{t − j}{l}\binom{j − 1}{i − l − 1}\binom{t}{j}

= ∑_{l=0}^{i−1} ∑_{t=1}^{2x+2n} \frac{j − i}{i}\binom{j − 1}{i − l − 1}\binom{l + j}{l}\binom{t}{l + j}

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

the last line again being due to (4.11).

To summarize, we have obtained the following result.

Lemma 6. For all positive integers n, x and nonnegative integers k, we have

M(F_{n,x} \ ◁_{2}(k)) = − Pf M_{n}(x),  (4.14)

where M_{n}(x) is given by (4.6), with Q_{i,j} defined in (4.10) or (4.13), and H_{i,j} defined in (4.7) and (4.8).

5. Proof of Theorem 4

In the sequel, we shall interpret sums by

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

In particular, using this convention, the expression for Q_{i,j} given in (4.10) makes sense for negative integers x also (in which case the upper bound in the sum can be negative) and is actually equal to the expression in (4.13). It is the latter fact that we shall frequently make use of.

Our proof of Theorem 4 involves a sequence of five steps. By Lemma 6, we know that the number that we want to compute is the negative of a Pfaffian. We shall frequently use the fact (4.3) that the square of the Pfaffian of a skew-symmetric matrix is equal to its determinant.

By definition, Pf M_{n}(x) is a polynomial in x. In Step 1 we prove that

det M_{n}(x) = det M_{n}(−2n − x).

With d denoting the degree of Pf M_{n}(x) as a polynomial in x, this implies that

Pf M_{n}(x) = (−1)^{d} Pf M_{n}(−2n − x).  (5.2)

Subsequently, in Step 2 we show that

∏_{s=1}^{n} ; s≠n−k(x + s)_{2n−2s+1}^{2}  (5.3)

divides det M_{n}(x) as a polynomial in x (here, (x+s)_{2n−2s+1}^{2} is the square of the Pochhammer symbol (x + s)_{2n−2s+1}), while in Step 3 we show that

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

divides det M_{n}(x) (where, similarly, (x+s+ \frac{1}{2})_{2n−2s}^{2} is the square of the Pochhammer symbol (x + s + \frac{1}{2})_{2n−2s}). Both combined, this proves that

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

which is a polynomial of degree

∑_{s=1}^{n}(4n − 4s + 1) − (2k + 1) = n(2n − 1) − (2k + 1),

divides Pf M_{n}(x) as a polynomial in x. The computation in Step 4 then shows that the degree of Pf M_{n}(x), as a polynomial in x, is at most 2n^{2} + n − 4k − 3. Altogether, this implies that

− Pf M_{n}(x) = P_{n}(x)_{∏_{s=1}^{n} ; s≠n−k}(x + s)_{2n−2s+1}∏_{s=1}^{n}(x + s + \frac{1}{2})_{2n−2s},  (5.4)

where P_{n}(x) is a polynomial in x of degree at most

2n^{2} + n − 4k − 3 − n(2n − 1) + (2k + 1) = 2n − 2k − 2.

In Step 5, we determine the value of P_{n}(x) at x = 0, −1, …, −n + k + 1 (see (5.30)). The corresponding calculations make use of an auxiliary lemma due to Mehta and Wang [29], see Theorem 7 and Corollary 10 in Section 6. By (5.2), this gives us at the same time the value of P_{n}(x) at x = −2n, −2n + 1, …, −n − k − 1. In total, these are 2n − 2k explicit evaluations of P_{n}(x) at special values of x. Given the fact that the degree of P_{n}(x) is at most 2n − 2k − 2, they determine P_{n}(x) uniquely, and an explicit expression for P_{n}(x) can be written down using Lagrange interpolation. If this is substituted into (5.4), then the evaluation of − Pf M_{n}(x) is complete. After some manipulations, one arrives at the expression in (3.2).

Step 1. det M_{n}(x) = det M_{n}(−2n−x). We prove this claim by transforming, up to sign, M_{n}(x) into M_{n}(−2n−x) by a sequence of elementary row and column operations (which, of course, leave the value of the determinant invariant). To be precise, for i = 2n, 2n − 1, …, 2 (in this order), we add

∑_{a=1}^{i−1} \binom{i − 1}{a − 1} · (row a)

to row i, and then for j = 2n, 2n − 1, …, 2, we add

∑_{b=1}^{j−1} \binom{j − 1}{b − 1} · (column b)

to column j. Let M_{n}^{(1)}(x) denote the matrix which arises after these row and column operations. According to (4.9), the (i, j)-entry in M_{n}^{(1)}(x) is

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

for 1 ≤ i, j ≤ 2n. By (4.7) and (4.8), for 1 ≤ i ≤ 2n and j = 2n + ε, ε = 1, 2, the (i, j)-entry of M_{n}^{(1)}(x) is

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

and, for 1 ≤ j ≤ 2n and i = 2n + ε, ε = 1, 2, it is

− ∑_{b=1}^{j} \binom{j − 1}{b − 1}\binom{x + n − k − 1}{b − 2k − ε}.  (5.7)

By Chu–Vandermonde summation (4.12), we have

∑_{a=1}^{i} \binom{i − 1}{a − 1}\binom{t + γ}{a + η} = ∑_{a=1}^{i} \binom{i − 1}{i − a}\binom{t + γ}{a + η} = \binom{t + i + γ − 1}{i + η},

whence the expression (5.5) simplifies to

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

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

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

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

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

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

Here, we used the identity

\binom{t}{i}\binom{t}{j − 1} − \binom{t}{i − 1}\binom{t}{j} = (\binom{t}{i} + \binom{t}{i − 1}) \binom{t}{j − 1} − \binom{t}{i − 1} (\binom{t}{j} + \binom{t}{j − 1})

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

to obtain (5.8), and our convention (5.1) for sums to obtain (5.9). Comparison with (4.9) shows that this last expression is, up to the sign (−1)^{i+j}, exactly Q_{i,j} with x replaced by −2n − x. In a similar vein, the expression (5.6) simplifies to

\binom{x + n + i − k − 2}{i − 2k − ε} = (−1)^{i+ε}\binom{−x − n − k + 1 − ε}{i − 2k − ε},  (5.11)

while expression (5.7) simplifies to the same expression with i replaced by j. Upon setting ε = 2, this shows that the (i, 2n + 2)-entry in M_{n}^{(1)}(x) is, up to the sign (−1)^{i}, identical with the (i, 2n + 2)-entry in M_{n}(−2n − x), with an analogous statement being true for the (2n + 2, j)-entry of M_{n}^{(1)}(x) and the (2n + 2, j)-entry of M_{n}(−2n − x).

We do one last row and one last column operation: in M_{n}^{(1)}(x), we add the last row to the next-to-last row, and we add the last column to the next-to-last column. Let M_{n}^{(2)}(x) denote the resulting matrix. By (5.11), for i = 1, 2, …, 2n, the (i, 2n + 1)-entry of M_{n}^{(2)}(x) is equal to

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

which is, up to the sign (−1)^{i+1}, exactly the (i, 2n+1)-entry in M_{n}(−2n−x). An analogous statement is true for the (2n + 1, j)-entries of M_{n}^{(2)}(x) and M_{n}(−2n − x).

In summary, as the two by two block in the lower right corner of M_{n}(x) consists of zeros, the computations (5.10)–(5.12) show that the (i, j)-entry of M_{n}^{(2)}(x) is (−1)^{i+j} times the (i, j)-entry of M_{n}(−2n − x). This implies

det M_{n}(x) = det M_{n}^{(2)}(x) = det M_{n}(−2n − x),

as claimed.

Step 2. _{∏_{s=1}^{n} ; s≠n−k}(x + s)_{2n−2s+1}^{2} divides det M_{n}(x). (The reader should recall the remarks

on notation after (5.3).) We begin by observing that the product in the claim can be also rewritten as

∏_{s=1}^{n} ; s≠n−k(x + s)_{2n−2s+1}^{2} = ∏_{s=1}^{n}(x + s)^{2s+2χ(s<n−k)−2} ∏_{s=n+1}^{2n−1}(x + s)^{4n−2s+2χ(s>n+k)−2}, (5.13)

where χ(A) = 1 if A is true and χ(A) = 0 otherwise. In view of Step 1, it suffices to establish that

∏_{s=1}^{n}(x + s)^{2s+2χ(s<n−k)−2}

divides det M_{n}(x).

Now let s, a and b be integers with 1 ≤ s ≤ n and 1 ≤ a ≤ b ≤ 2n. We claim that

∑_{i=a}^{b} \binom{b − a}{i − a}(row i of M_{n}(−s)) = 0,  (5.14)

as long as (A) a − b ≤ 2n − 2s < a, and (B) either b ≤ 2k, or b ≥ 2k + 3 and a − b + k + 1 ≤ n − s < a − k − 1.

Indeed, if we specialize (5.14) to the j-th column, where j ≤ 2n, we obtain, using the expression (4.10) for Q_{i,j},

∑_{i=a}^{b} \binom{b − a}{i − a}Q_{i,j} = ∑_{i=a}^{b} \binom{b − a}{i − a} ∑_{t=1}^{2n−2s} \frac{j − i}{t}\binom{t}{i}\binom{t}{j}

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

= ∑_{t=1}^{2n−2s} (\binom{b − a + t}{b}\binom{t − 1}{j − 1} − \binom{b − a + t − 1}{b − 1}\binom{t}{j}) . (5.15)

Here we used the Chu–Vandermonde summation (4.12) in the last line. Since, for a − b ≤ 2n − 2s < a (which is condition (A)), the binomial coefficients containing the parameter b in expression (5.15) are identically zero throughout the summation range, it is clear that the corresponding sum vanishes.

On the other hand, if we specialize (5.14) to the (2n + 1)-st column, we obtain, again using the Chu–Vandermonde summation (4.12),

∑_{i=a}^{b} \binom{b − a}{i − a}H_{i,1}|_{x=−s} = ∑_{i=a}^{b} \binom{b − a}{b − i}\binom{n − s − k − 1}{i − 2k − 1}

= \binom{b − a + n − s − k − 1}{b − 2k − 1},

which vanishes for b ≤ 2k, and for b ≥ 2k + 2 and 0 ≤ b − a + n − s − k − 1 < b − 2k − 1, the last inequality being equivalent to a − b + k + 1 ≤ n − s < a − k, and if we specialize (5.14) to the (2n + 2)-nd column, we obtain

∑_{i=a}^{b} \binom{b − a}{i − a}H_{i,2}|_{x=−s} = ∑_{i=a}^{b} \binom{b − a}{b − i}\binom{n − s − k − 1}{i − 2k − 2}

= \binom{b − a + n − s − k − 1}{b − 2k − 2},

which vanishes for b ≤ 2k − 1, and for b ≥ 2k + 3 and 0 ≤ b − a + n − s − k − 1 < b − 2k − 2, the last inequality being equivalent to a − b + k + 1 ≤ n − s < a − k − 1. This establishes our claim.

In order to prove that (x + s)^{2s} divides det M_{n}(x) for 1 ≤ s < n − k, we use (5.14) with a = 2n − 2s + 1 and 2n − 2s + 1 ≤ b ≤ 2n. It is not difficult to see that for these choices of s, a and b the conditions (A) and (B) are satisfied, so that we obtain 2s linear combinations of the rows that are linearly independent (as, for our choices of a and b, the coefficients in (5.14) form a triangular array) and vanish when x = −s. This implies divisibility by (x + s)^{2s} (cf. e.g. [24, Lemma in Sec. 2]).

To prove that (x + s)^{2s−2} divides det M_{n}(x) for n − k ≤ s ≤ n, we use (5.14) with a = 2n − 2s + 1 and 2n − 2s + 1 ≤ b ≤ 2k on the one hand, and with a = n + k − s + 2 and 2k + 3 ≤ b ≤ 2n on the other hand. Again, it is not difficult to see that for both types of choices of s, a and b the conditions (A) and (B) are satisfied, so that we obtain (2k + 2s − 2n) + (2n − 2k − 2) = 2s − 2 linear combinations of the rows that are linearly independent and vanish at x = −s. In the same way as before, this implies divisibility by (x + s)^{2s−2}.

Step 3. ∏_{s=1}^{n−1}(x + s + \frac{1}{2})_{2n−2s}^{2} divides det M_{n}(x). (The reader should recall the remarks

on notation after (5.3).) We begin by observing that the product in the claim can be also rewritten as

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

In view of Step 1, it suffices to establish that

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

divides det M_{n}(x).

In order to prove the claim for s < n − k, we shall show that

(n − s − k) · (row (2n − 2s + 1) of M_{n}(−s − \frac{1}{2}))

+ \frac{1}{2}(n − s − k) · (row (2n − 2s) of M_{n}(−s − \frac{1}{2}))

+ ∑_{i=1}^{2n−2s−1} \frac{(−1)^{i}}{2^{2n−2s−i+2}} (row i of M_{n}(−s − \frac{1}{2})) = 0, (5.16)

and that

(row i of M_{n}(−s − \frac{1}{2})) + \frac{2i + 2s − 2n − 2k − 3}{i − 2k − 1} (row (i − 1) of M_{n}(−s − \frac{1}{2}))

+ \frac{(2i + 2s − 2n − 2k − 3)(2i + 2s − 2n − 2k − 5)}{4(i − 2k − 1)(i − 2k − 2)} (row (i − 2) of M_{n}(−s − \frac{1}{2})) = 0 (5.17)

for i = 2n − 2s + 2, 2n − 2s + 3, …, 2n. As these are linearly independent row combinations, the claim will follow.

In order to prove the claim for s ≥ n − k, we shall show that

∑_{i=1}^{2n−2s−1} \frac{(−1)^{i}}{2^{2n−2s−i−1}} (row i of M_{n}(−s − \frac{1}{2})) = 0,  (5.18)

that

(row i of M_{n}(−s − \frac{1}{2})) = 0  (5.19)

for i = 2n − 2s, 2n − 2s + 1, …, 2k, and that

(row i of M_{n}(−s − \frac{1}{2})) + \frac{2i + 2s − 2n − 2k − 3}{i − 2k − 1} (row (i − 1) of M_{n}(−s − \frac{1}{2}))

+ \frac{(2i + 2s − 2n − 2k − 3)(2i + 2s − 2n − 2k − 5)}{4(i − 2k − 1)(i − 2k − 2)} (row (i − 2) of M_{n}(−s − \frac{1}{2})) = 0 (5.20)

for i = 2k + 3, 2k + 4, …, 2n. Again, as these are linearly independent row combinations, the claim will follow.

Let us first suppose s ≥ n − k. We start with the proof of (5.18). Specializing (5.18) to the j-th column, j = 1, 2, …, 2n, by (4.9) we see that we must prove the identity

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

In order to see that this is indeed true, we first extend the sum over i to the range i = 0, 1, …, 2n − 2s − 1, thereby obtaining

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

− \frac{1}{2^{2n−2s−1}} ∑_{t=1}^{2n−2s−1} \binom{t − 1}{j − 1}

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

− \frac{1}{2^{2n−2s−1}} \binom{2n − 2s − 1}{j}

for the left-hand side of (5.21). Next we interchange the sum over i with the sums over t, and subsequently we evaluate the (now inner) sums over i by means of the binomial theorem. In this manner, the left-hand side of (5.21) becomes

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

− \frac{1}{2^{2n−2s−1}} \binom{2n − 2s − 1}{j}

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

as desired.

On the other hand, specializing (5.18) to the j-th column, j = 2n + 1, 2n + 2, by (4.7) and (4.8) we obtain

∑_{i=1}^{2n−2s−1} \frac{(−1)^{i}}{2^{2n−2s−i−1}} \binom{n − k − s − \frac{3}{2}}{i − 2k − ε},

where ε = 1, 2, which is indeed zero since the binomial coefficient always vanishes because of i ≤ 2n − 2s − 1 < 2k + ε, the last inequality being due to our assumption s ≥ n − k.

That (5.19) holds can be easily checked by inspection.

For the proof of (5.20), we observe that we have Q_{i,j}|_{x=−s− \frac{1}{2}} = 0 for all i ≥ 2n − 2s,

because in this case the appearance of the binomial coefficient \binom{t}{i} in the sum in formula (4.10) implies that all summands of this sum vanish. In its turn, this entails that the lefthand side of (5.20) specialized to the j-th column, where 1 ≤ j ≤ 2n, is trivially zero since

i > i − 1 > i − 2 ≥ 2k + 1 ≥ 2n − 2s + 1 > 2n − 2s,

by our assumptions. To see that the left-hand side of (5.20) is as well zero when it is specialized to the (2n + 1)-st or (2n + 2)-nd column amounts to a routine verification using the expressions (4.7) and (4.8) for the corresponding matrix entries.

We now assume that s < n−k and turn our attention to (5.16). The reader should notice that the relations (5.16) and (5.18) are relatively similar, the essential difference being the two extra terms in (5.16) corresponding to the (2n − 2s)-th and the (2n − 2s + 1)-st row, respectively. If 1 ≤ j ≤ 2n, the proof of relation (5.16) specialized to column j is therefore identical with the proof of relation (5.18) specialized to column j, because the entries in the first 2n columns of the (2n − 2s)-th and the (2n − 2s + 1)-st row evaluated at x = −s − \frac{1}{2} are all zero. (The reader should recall formula (4.10).) To show the relation (5.16) specialized to the (2n + 1)-st respectively to the (2n + 2)-nd column requires however more work. We have to prove

(n − s − k) (\binom{n − s − k − \frac{3}{2}}{2n − 2s − 2k − ε + 1} + \frac{1}{2}\binom{n − s − k − \frac{3}{2}}{2n − 2s − 2k − ε})

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

where ε = 1, 2, respectively, after simplification,

\frac{(n − s − k)(ε − 2)}{2} · \frac{(−n + s + k + ε − \frac{1}{2})_{2n−2s−2k−ε}}{(2n − 2s − 2k − ε + 1)!}

+ ∑_{i=1}^{2n−2s−1} \frac{(−1)^{i}}{2^{2n−2s−i+2}} \binom{n − s − k − \frac{3}{2}}{i − 2k − ε} = 0. (5.22)

We reverse the order of summation in the sum over i (that is, we replace i by 2n−2s−i−1), and subsequently we write the (new) sum over i in standard hypergeometric notation

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

Thereby we obtain

\frac{(n − s − k)(ε − 2)}{2} · \frac{(−n + s + k + ε − \frac{1}{2})_{2n−2s−2k−ε}}{(2n − 2s − 2k − ε + 1)!}

− \frac{(−n + k + s + ε + \frac{1}{2})_{2n−2s−2k−ε−1}}{8 (2n − 2s − 2k − ε − 1)!}_{2}F_{1}[ \begin{matrix}1, −2n + 2k + 2s + ε + 1 \\ −n + k + s + ε + \frac{1}{2} \end{matrix} ; \frac{1}{2}] (5.24)

for the left-hand side of (5.22).

If ε = 2, then the_{2}F_{1}-series in (5.24) can be evaluated using Gauß’ second_{2}F_{1}-summation (cf. [33, (1.7.1.9); Appendix (III.6)])

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

As a result, in this case, the expression (5.24) vanishes, whence (5.22) with ε = 2 is satisfied, and thus relation (5.16) specialized to the (2n + 2)-nd column.

If ε = 1, the _{2}F_{1}-series in (5.24) cannot be directly evaluated by means of Gauß’ formula. However, we may in a first stage apply the contiguous relation

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

to transform (5.24) into

− \frac{(n − s − k)}{2} · \frac{(−n + s + k + \frac{1}{2})_{2n−2s−2k−1}}{(2n − 2s − 2k)!}

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

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

Both _{2}F_{1}-series in the last expression can now be evaluated by means of Gauß’ formula (5.25). The first series simply vanishes, while the second series evaluates to a non-zero expression. If this is substituted, after some simplifications we obtain

−\frac{(−n + s + k + \frac{1}{2})_{2n−2s−2k−1}}{4 (2n − 2s − 2k − 1)!} − \frac{(−n + k + s + \frac{3}{2})_{2n−2s−2k−2}}{8 (2n − 2s − 2k − 2)!} = 0.

This shows that for ε = 1 the expression (5.24) vanishes as well, whence (5.22) with ε = 1 is satisfied, and thus also relation (5.16) specialized to the (2n + 1)-st column.

The verification of (5.17) is completely analogous to that of (5.20) and is left to the reader. Step 4. Pf M_{n}(x) is a polynomial in x of degree at most 2n^{2} +n−4k −3. By (4.13), Q_{i,j}

is a polynomial in x of degree i+j. On the other hand, by recalling the definitions (4.7) and (4.8) of H_{i,1} and H_{i,2}, respectively, one sees that the degree of H_{i,1} in x is i − 2k − 1, while the degree of H_{i,2} is i − 2k − 2. It follows that, in the defining expansion of the determinant det M_{n}(x), each nonzero term has degree

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

The Pfaffian being the square root of the determinant (cf. (4.3)), the claim follows.

Step 5. Evaluation of P_{n}(x) at x = 0, −1, …, −n + k + 1. The polynomial P_{n}(x) is defined by means of (5.4). So, what we would like to do is to set x = −σ in (5.4), σ being one of 0, 1, …, n − k − 1, evaluate Pf M_{n}(−σ), divide both sides of (5.4) by the products on the right-hand side of (5.4), and get the evaluation of P_{n}(x) at x = −σ. However, the first product on the right-hand side of (5.4) unfortunately is zero for x = −σ, 1 ≤ σ ≤ n − k − 1. (It is not zero for σ = 0.) Therefore we have to find a way around this difficulty.

Fix an σ with 1 ≤ σ ≤ n − k − 1. Before setting x = −σ in (5.4), we have to cancel (x + σ)^{σ} (see (5.13)) on both sides of (5.4). That is, we should write (5.4) in the form

P_{n}(x) = −\frac{1}{(x + σ)^{σ}} Pf M_{n}(x)

×_{∏_{s=1}^{n−k−1} ; s≠σ}(x + s)^{−s} ∏_{s=n−k+1}^{n}(x + s)^{−s+1} ∏_{s=n+1}^{2n−1}(x + s)^{−2n+s−χ(s>n+k)+1}

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

and subsequently specialize x = −σ. However, in order to be able to perform this step, we need to evaluate

− (\frac{1}{(x + σ)^{σ}} Pf M_{n}(x)) |_{x=−σ}.

In order to accomplish this, we apply Lemma 11 with N = 2n + 2, a = 2n − 2σ, b = 2n, and A = M_{n}(x). Indeed, (x + σ) is a factor of each entry in the i-th row in matrix M_{n}(x), for i = 2n − 2σ + 1, 2n − 2σ + 2, …, 2n. We obtain

− (\frac{1}{(x + σ)^{σ}} Pf M_{n}(x)) |_{x=−σ} = − Pf(Q̃) Pf(S),  (5.27)

where

Q̃ = ( \begin{matrix}\overline{Q} & \overline{H} \\ −\overline{H}^{t} & 0 \end{matrix} ) ,  (5.28)

with \overline{Q} being given by

\overline{Q} = (Q_{i,j}|_{x=−σ})_{1≤i,j≤2n−2σ}

and \overline{H} by

\overline{H} = (H_{i,j}|_{x=−σ})_{1≤i≤2n−2σ, 1≤j≤2} ,

and where

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

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

We must now compute Pf(Q̃) and Pf(S). We start with the evaluation of Pf(S). It follows from (4.13) that the (i, j)-entry of S is given by

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

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

If we write this using hypergeometric notation, we obtain the alternative expression

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

Rewrite this expression as the limit

S_{i,j} = lim_{ε→0} \frac{(−1)^{j+1}(j − i)_{i+2n−2σ}}{(2n − 2σ + j + 1)! (j)_{i−j+2n−2σ+1}}_{3}F_{2}[ \begin{matrix}1 − i − 2n + 2σ, 1 + j + 2n − 2σ, j \\ 1 − i + j, 2 + ε + j + 2n − 2σ \end{matrix}; 1] .

Now we apply one of Thomae’s _{3}F_{2}-transformation formulas (cf. [4, Ex. 7, p. 98])

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

Thus, we obtain

S_{i,j} = lim_{ε→0} \frac{(−1)^{j+1}Γ(2n − 2σ + ε + 1) Γ(2n − 2σ + j + ε + 2) (j − i)_{i+2n−2σ}}{Γ(ε − i + 2) Γ(4n − 4σ + i + j + ε + 1) (2n − 2σ + j + 1)! (j)_{i−j+2n−2σ+1}}

×_{3}F_{2}[ \begin{matrix}1 − i − 2n + 2σ, −i − 2n + 2σ, 1 − i \\ 1 − i + j, 2 + ε − i \end{matrix}; 1] ,

or, in usual sum notation,

S_{i,j} = lim_{ε→0} ∑_{l=0}^{i−1} \frac{(−1)^{j+1} (j − i) Γ(2n − 2σ + ε + 1) Γ(2n − 2σ + j + ε + 2)}{Γ(l − i + ε + 2) Γ(4n − 4σ + i + j + ε + 1)}

· \frac{(1 − i)_{l} (l − i + j + 1)_{2n−2σ+i−l−1} (2n − 2σ + i − l)_{l}}{l! (2n − 2σ + j + 1)! (j)_{2n−2σ+i−j−l+1}} .

a. A lozenge tiling for the degenerate region b. Forced lozenges in case x = 0

Figure 9

Because of the term Γ(l − i + ε + 2) in the denominator, in the limit only the summand for l = i − 1 does not vanish. After simplification, this leads to

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

We must evaluate the Pfaffian

Pf_{1≤i,j≤2σ}(S_{i,j}).

By factoring some terms out of rows and columns, we see that

Pf_{1≤i,j≤2σ}(S_{i,j}) = (−1)^{σ}(2n − 2σ + 1)!^{−σ}

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

This Pfaffian can be evaluated in closed form by Corollary 10 in the next section. The result is that

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

(5.29)

We finally turn to the evaluation of det(Q̃). If we compare (5.28) with (4.6), then we see that Q̃ = M_{n−σ}(0). Hence, using Lemma 6 with n replaced by n − σ and with x = 0, we see that − Pf(Q̃) is equal to M(F_{n−σ,0} \ ◁_{2}(k)). (The reader should recall the definitions of the region F_{n,x} and of the triangular hole ◁_{2}(k) given in the introduction, see again Figure 7.) Figure 9.a shows a typical example where n − σ = 5 and k = 2. Since this region is degenerate, there are many forced lozenges, see Figure 9.b. The enumeration problem therefore reduces to the problem of determining the number of symmetric lozenge tilings of a hexagon with side-lengths 2k, 2k, 2, 2k, 2k, 2. This number is given by formula (3.1) with n = k and x = 1. If we substitute this in (5.27), together with the evaluation (5.29), then, after some manipulation, we obtain

− (\frac{1}{(x + σ)^{σ}} Pf M_{n}(x)) |_{x=−σ} = (−1)^{σ}\binom{4k + 1}{2k}\frac{(2σ)!}{(2n − 2σ + 1)!^{σ} 2^{σ} σ!}

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

Hence, by inserting this in (5.26), we have

P_{n}(−σ) = (−1)^{σ}\binom{4k + 1}{2k}\frac{(2σ)!}{(2n − 2σ + 1)!^{σ} 2^{σ} σ!}

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

×_{∏_{s=1}^{n−k−1} ; s≠σ}(−σ + s)^{−s} ∏_{s=n−k+1}^{n}(−σ + s)^{−s+1} ∏_{s=n+1}^{2n−1}(−σ + s)^{−2n+s−χ(s>n+k)+1}

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

This completes the proof of Theorem 4.

6. An auxiliary determinant evaluation, and an auxiliary Pfaffian factorization

Mehta and Wang proved the following determinant evaluation in [29]. (There is a typo in the formula stated in [29, Eq. (7)] in that the binomial coefficient \binom{n}{k} is missing there.)

Theorem 7 ([29, Eq. (7)]). For all real numbers a, b and positive integers n, we have

det_{0≤i,j≤n−1} ((a + j − i) Γ(b + i + j))

= ( ∏_{i=0}^{n−1} i! Γ(b + i)) ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}((b − a)/2)_{k} ((b + a)/2)_{n−k}, (6.1)

as long as the arguments occurring in the gamma functions avoid their singularities.

The sum on the right-hand side of (6.1) can be alternatively expressed as the coefficient of z^{n}/n! in

(1 + z)^{(a−b)/2}(1 − z)^{(−a−b)/2}.

Therefore, in the case a = 0 we obtain the following simpler determinant evaluation.

Corollary 8. For all real numbers b and positive integers n, we have

det_{0≤i,j≤n−1} ((j − i) Γ(b + i + j)) = χ(n is even)( ∏_{i=0}^{n−1} i! Γ(b + i))\frac{n! (b/2)_{n/2}}{(n/2)!} ,

as long as the arguments occurring in the gamma functions avoid their singularities. Here, as before, χ(A) = 1 if A is true and χ(A) = 0 otherwise.

One can obtain the following slightly (but, for our purposes, essentially) stronger statement. It is stated as Eq. (4) in [29], with the argument how to obtain it hinted at at the bottom of page 231 of [29]. Since, from there, it is not completely obvious how to actually complete the argument, we provide a proof.

Proposition 9. For all real numbers b and positive even integers n, we have

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

as long as the arguments occurring in the gamma functions avoid their singularities.

Proof. Since the Pfaffian of a skew-symmetric matrix equals the square root of its determinant (cf. (4.3)), the formula given by Theorem 8 yields, after a little manipulation, that

Pf_{0≤i,j≤n−1}((j − i) Γ(b + i + j)) = ε ∏_{i=0}^{\frac{n}{2} −1}(2i + 1)! Γ(b + 2i + 1),  (6.3)

where ε = +1 or ε = −1. In order to determine the sign ε, we argue by induction on (even) n. Let us suppose that we have already proved (6.2) up to n − 2. We now multiply both sides of (6.3) by b + 1 and then let b tend to −1. Thus, on the right-hand side we obtain the expression

ε( ∏_{i=0}^{\frac{n}{2} −1}(2i + 1)!)( ∏_{i=1}^{\frac{n}{2} −1} Γ(2i)).  (6.4)

On the other hand, by the definition of the Pfaffian, on the left-hand side we obtain

∑_{π∈M[0,...,n−1]} sgn π lim_{b→−1} ((b + 1)_{∏_{i<j} i,j matched in π}(j − i) Γ(b + i + j))  (6.5)

(with the obvious meaning of M[0, …, n−1]; cf. the sentence containing (4.2)). In this sum, matchings π for which all matched pairs i, j satisfy i + j > 1 do not contribute, because the corresponding summands vanish. However, there is only one possible pair i, j with 0 ≤ i < j for which i + j ≤ 1, namely (i, j) = (0, 1). Therefore, the sum in (6.5) reduces to

∑_{π′∈M[2,...,n−1]} sgn π′( lim_{b→−1}(b + 1)(1 − 0) Γ(b + 1))_{∏_{i<j} i,j matched in π′}(j − i) Γ(i + j − 1)

= Pf_{2≤i,j≤n−1}((j − i) Γ(i + j − 1))

= Pf_{0≤i,j≤n−3}((j − i) Γ(i + j + 3)),

where the next-to-last equality holds by the definition (4.2) of the Pfaffian. Now we can use the induction hypothesis to evaluate the last Pfaffian. Comparison with (6.4) yields that ε = +1. □

By using the reflection formula (cf. [2, Theorem 1.2.1])

Γ(x) Γ(1 − x) = \frac{π}{sin πx}

for the gamma function, and the substitutions i → n − i − 1 and j → n − j − 1, it is not difficult to see that Proposition 9 is equivalent to the following.

Corollary 10. For all positive even integers n, we have

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

We close this section by proving a factorization of a certain specialization of a Pfaffian that we need in Step 5 in Section 5.

Lemma 11. Let N, a, b be positive 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 + σ.

Then

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

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

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

Proof. By the definition (4.2) of the Pfaffian, we have

(\frac{1}{(x + σ)^{(b−a)/2}} Pf A) |_{x=−σ} = (\frac{1}{(x + σ)^{(b−a)/2}} ∑_{π∈M[1,...,N]} sgn π_{∏_{i<j} i,j matched in π}A_{i,j})|_{x=−σ}.

Let M_{1} denote the subset of M[1, …, N] consisting of those matchings that pair all the elements from {a + 1, a + 2, …, b} among themselves (and, hence, all the elements of the complement {1, 2, …, a, b+1, b+2, …, N} among themselves). Let M_{2} be the complement M[1, …, N]\M_{1}. Then

(\frac{1}{(x + σ)^{(b−a)/2}} Pf A) |_{x=−σ} = (\frac{1}{(x + σ)^{(b−a)/2}} ∑_{π∈M_{1}} sgn π_{∏_{i<j} i,j matched in π}A_{i,j})|_{x=−σ}

+ (\frac{1}{(x + σ)^{(b−a)/2}} ∑_{π∈M_{2}} sgn π_{∏_{i<j} i,j matched in π}A_{i,j})|_{x=−σ}. (6.7)

Each term in the sum in the second line of (6.7) vanishes, since the product contains more than (b − a)/2 factors A_{i,j} that are divisible by x + σ. On the other hand, every matching π in M_{1} is the disjoint union of a matching π′ ∈ M[1, 2, …, a, b + 1, b + 2, …, N] and a matching π′′ ∈ M[a+1, a+2, …, b]. If we also use the simple fact that sgn π = sgn π′·sgn π′′ (as there are no crossings between paired elements of π′ and paired elements of π′′), then we obtain

(\frac{1}{(x + σ)^{(b−a)/2}} Pf A)|_{x=−σ}

= (\frac{1}{(x + σ)^{(b−a)/2}}_{∑_{π′∈M[1,...,a,b+1,...,N]} ; π′′∈M[a+1,...,b]} sgn π′ · sgn π′′

·(_{∏_{i<j} i,j matched in π′}A_{i,j})(_{∏_{i<j} i,j matched in π′′}A_{i,j}))|_{x=−σ}

= ∑_{π′∈M[1,...,a,b+1,...,N]} sgn π′_{∏_{i<j} i,j matched in π′}A_{i,j}|_{x=−σ}

· ∑_{π′′∈M[a+1,...,b]} sgn π′′_{∏_{i<j} i,j matched in π′′} (\frac{1}{x + σ} A_{i,j}) |_{x=−σ}.

By the definition (4.2) of the Pfaffian, the last expression is exactly the right-hand side of (6.6). □

7. Proofs of Theorems 1 and 2

In our proofs we make use of the following lemmas.

Lemma 12. Let β be a real number with either β > 0 or β < −1. Then, for fixed positive k and all sequences (β_{n})_{n≥1} with β_{n} → β as n → ∞, we have

lim_{n→∞} \frac{1}{\sqrt{n}} _{5}F_{4}[ \begin{matrix}−2n, \frac{1}{2}, −n + k + 1, −n + k + 1, β_{n}n \\ −2n + \frac{1}{2}, −n − k, −n − k, β_{n}n + 1 \end{matrix} ; 1] = ∫_{0}^{1} \frac{\sqrt{2} (1 − α)^{4k+2}}{(1 + \frac{α}{β}) \sqrt{πα(2 − α)}} dα,

(7.1)

where, on the left-hand side, we used again the standard notation (5.23) for hypergeometric series.

Proof. We write the _{5}F_{4}-series in (7.1) explicitly as a sum over l:

∑_{l=0}^{n−k−1} \frac{Γ(2n + 1) Γ(l + \frac{1}{2}) Γ(2n − l + \frac{1}{2}) Γ(n − k)^{2} Γ(n + k − l + 1)^{2}}{Γ(2n − l + 1) Γ(\frac{1}{2}) Γ(l + 1) Γ(2n + \frac{1}{2}) Γ(n − k − l)^{2} Γ(n + k + 1)^{2}} \frac{β_{n}n}{(β_{n}n + l)}. (7.2)

Let us denote the summand in this sum by F (n, l). We have

\frac{∂}{∂l} F (n, l) = F (n, l)(ψ(l + \frac{1}{2}) − ψ(l + 1) + ψ(2n − l + 1) − ψ(2n − l + \frac{1}{2})

+ 2ψ(n − k − l) − 2ψ(n + k − l + 1) − \frac{1}{β_{n}n + l} ),

where ψ(x) := (\frac{d}{dx}Γ(x))/Γ(x) is the digamma function. Because of the functional equation ψ(x + 1) = ψ(x) + \frac{1}{x} (cf. [2, Eq. (1.2.15) with n = 1]), we have

ψ(l + 1) − ψ(l + \frac{1}{2}) ≥ ψ(2n − l + 1) − ψ(2n − l + \frac{1}{2})

for 0 ≤ l ≤ n. Moreover, since either β > 0 or β < −1, for large enough n we have

ψ(n + k − l + 1) ≥ ψ(n − k − l) + \frac{1}{n + k − l} > ψ(n − k − l) − \frac{1}{β_{n}n + l} .

Altogether, this implies that \frac{∂}{∂l}F (n, l) < 0 for 0 ≤ l ≤ n − k − 1, that is, for fixed large enough n, the summand F (n, l) is monotone decreasing as a function in l. In particular, for 0 ≤ l ≤ n − k − 1 we have

0 < F (n, l) ≤ F (n, 0) = 1.  (7.3)

The sum (7.2) may therefore be approximated by an integral:

∑_{l=0}^{n−k−1} F (n, l) = ∑_{l=0}^{⌊log n⌋−1} F (n, l) + ∑_{l=⌊log n⌋}^{n−k−⌊log n⌋−1} F (n, l) + ∑_{l=n−k−⌊log n⌋}^{n−k−1} F (n, l)

= O(log n) + ∫_{⌊log n⌋−1}^{n−k−⌊log n⌋−1} F (n, l) d l,  as n → ∞.  (7.4)

The next step is to apply Stirling’s approximation

log Γ(z) = (z − \frac{1}{2}) log(z) − z + \frac{1}{2} log(2π) + O (\frac{1}{z})  (7.5)

THE INTERACTION OF A GAP WITH A FREE BOUNDARY IN A DIMER SYSTEM 33

for the gamma function, in the form

log Γ(an + bl + c) = (an + bl + c − \frac{1}{2}) (log (a + b\frac{l}{n}) + log(n) + log (1 + \frac{c}{an+bl}))

− (an + bl + c) + \frac{1}{2} log(2π) + O (\frac{1}{an + bl} )

= (an + bl + c − \frac{1}{2}) (log(a + b\frac{l}{n}) + log(n))

− (an + bl) + \frac{1}{2} log(2π) + O (\frac{1}{an + bl} ) ,

where a, b, c are real numbers with a ≥ 0. If this is used in the defining expression for F (n, l), then after cancellations we obtain

log F (n, l) = \frac{1}{2}log(2) + (4k + 2) log (1 − \frac{l}{n}) − \frac{1}{2}log (2 − \frac{l}{n})

− \frac{1}{2}log (\frac{l}{n}) − \frac{1}{2}log(n) − \frac{1}{2}log(π) − log (1 + \frac{l}{β_{n}n})

+ O (\frac{1}{l}) + O (\frac{1}{n − l} ) + O (\frac{1}{2n − l} ) + O (\frac{1}{n})

= log (\frac{\sqrt{2} (1 − \frac{l}{n})^{4k+2}}{\sqrt{n}(1 + \frac{l}{β_{n}n}) \sqrt{π \frac{l}{n}(2 − \frac{l}{n})}}) + O (\frac{1}{log n}) ,

as long as log n ≤ l ≤ n − k − log n. Substitution of this approximation in (7.4) yields

∑_{l=0}^{n−k−1} F (n, l)

= ( ∫_{⌊log n⌋−1}^{n−k−⌊log n⌋−1} \frac{\sqrt{2} (1 − \frac{l}{n})^{4k+2}}{\sqrt{n}(1 + \frac{l}{β_{n}n}) \sqrt{π \frac{l}{n}(2 − \frac{l}{n})}} d l) (1 + O (\frac{1}{log n})) + O (log n) ,

or, after the substitution l = αn,

∑_{l=0}^{n−k−1} F (n, l)

= \sqrt{n}( ∫_{(⌊log n⌋−1)/n}^{(n−k−⌊log n⌋−1)/n} \frac{\sqrt{2} (1 − α)^{4k+2}}{(1 + \frac{1}{β_{n}} α) \sqrt{πα(2 − α)}} dα) (1 + O (\frac{1}{log n})) + O (log n) .

The assertion of the lemma follows now immediately. □

We can now get an exact formula for the correlation ω_{f}(k; ξ) defined in (2.2).

Lemma 13. For any ξ > 0 and 0 ≤ k ∈ ℤ, we have

ω_{f}(k; ξ) = \frac{1}{π} \binom{4k + 1}{2k} \frac{1}{(1 + ξ)^{4k+2}\sqrt{ξ(2 + ξ)}}

× ((2 + ξ) ∫_{0}^{1} \frac{(1 − α)^{4k+2}}{(1 + \frac{α}{ξ}) \sqrt{α(2 − α)}} dα − ξ ∫_{0}^{1} \frac{(1 − α)^{4k+2}}{(1 − \frac{α}{2+ξ}) \sqrt{α(2 − α)}} dα)

= \frac{1}{π} \binom{4k + 1}{2k} \frac{1}{(1 + ξ)^{4k+2}\sqrt{ξ(2 + ξ)}} ∫_{0}^{1} \frac{2 (1 − α)^{4k+3}}{(1 + \frac{α}{ξ}) (1 − \frac{α}{2+ξ}) \sqrt{α(2 − α)}} dα. (7.6)

Proof. By Theorem 4 and formula (3.1), the ratio between M(F_{n,x} \ ◁_{2}(k)) and M(F_{n,x}) is, when written in hypergeometric notation,

\binom{4k + 1}{2k} \frac{(n + k)! (\frac{1}{2})_{2n}}{(x + n − k)_{2k+1} (x + \frac{1}{2})_{2n}} \frac{(x + 1)_{n−k−1} (x + n + k + 1)_{n−k−1}}{(n − k − 1)!^{2} (n + k + 1)_{n−k}}

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

− x_{5}F_{4}[ \begin{matrix}−2n, \frac{1}{2}, −n + k + 1, −n + k + 1, −2n − x \\ −2n + \frac{1}{2}, −n − k, −n − k, −2n − x + 1 \end{matrix} ; 1] ).

We now substitute x = ξ_{n}n in this expression. Use of Lemma 12 (which applies, as ξ > 0), together with Stirling’s formula (7.5), yields the assertion. □

Lemma 14. For any β ≠ 0 we have

∫_{0}^{1} \frac{(1 − α)^{4k+2}}{(1 + \frac{α}{β}) \sqrt{α(2 − α)}} dα ∼ \sqrt{\frac{π}{8k}} , k → ∞.  (7.7)

Proof. Let I_{β}(k) be the integral on the left-hand side of (7.7). The asymptotics of I_{β}(k) as k → ∞ can be readily found using Laplace’s method as presented for instance in [30]. Conditions (i)–(v) of [30, pp. 121–122] are readily checked. By [30, Theorem 6.1, p. 125], the large z asymptotics of ∫_{a}^{b} e^{−zp(t)}q(t) dt is determined by the quantities λ, μ, p_{0} and q_{0} in the series expansions

p(t) − p(a) = p_{0}(t − a)^{μ} + p_{1}(t − a)^{μ+1} + ⋯

and

q(t) = q_{0}(t − a)^{λ} + q_{1}(t − a)^{λ+1} + · · · .

Namely, under the above assumptions one has

e^{zp(a)} ∫_{a}^{b} e^{−zp(t)}q(t) dt = Γ (\frac{λ}{μ}) \frac{q_{0}/(μp_{0}^{λ/μ})}{z^{λ/μ}} + O (\frac{1}{z^{λ/μ+1}} ) .  (7.8)

In the case of I_{β}(k) we have p(t) = − ln(1 − t), q(t) = \frac{1}{(1−t/β)\sqrt{t(2−t)}}, a = 0, and b = 1.

These yield parameters λ = 1/2, μ = 1, p_{0} = 1, and q_{0} = 1/\sqrt{2}. In addition, p(a) = 0. As in our case z = 4k + 2, under these specializations (7.8) becomes (7.7). □

Proof of Theorem 1. Combine Lemmas 13 (first expression) and 14 with Stirling’s approximation (7.5) for the binomial coefficient \binom{4k+1}{2k} = \frac{Γ(4k+2)}{Γ(2k+1) Γ(2k+2)} in (7.6). □

Proof of Theorem 2. The case ξ ≠ 1 follows directly from Theorem 1.

From now on, let ξ = 1. Set

D_{k} := 3I_{1}(k) − I_{−3}(k),

where I_{β}(k) denotes the integral on the left-hand side of (7.7) with ξ = 1. Using the earlier notation ω_{f}(k) = ω_{f}(k; 1), we have by Lemma 13 that

ω_{f}(k+1)−ω_{f}(k) = \frac{1}{π} \frac{1}{2^{4k+2}\sqrt{3}}\binom{4k + 1}{2k} \{[\frac{(4k + 3)(4k + 5)}{4(2k + 2)(2k + 3)} − 1] D_{k+1} + (D_{k+1} − D_{k})\} ,

and thus

\frac{ω_{f}(k + 1) − ω_{f}(k)}{ω_{f}(k)} = [\frac{(4k + 3)(4k + 5)}{4(2k + 2)(2k + 3)} − 1] \frac{D_{k+1}}{D_{k}} + \frac{D_{k+1} − D_{k}}{D_{k}} .  (7.9)

By two applications of Lemma 14 it follows that

D_{k} ∼ \frac{\sqrt{π}}{\sqrt{2}k} , k → ∞.  (7.10)

Thus D_{k+1}/D_{k} → 1 as k → ∞, and elementary arithmetics implies that the first term on the right-hand side of (7.9) is asymptotically −1/(2k) as k → ∞.

To determine the asymptotics of the second term, write by Lemma 13

D_{k+1} − D_{k} = 3 [I_{1}(k + 1) − I_{1}(k)] − [I_{−3}(k + 1) − I_{−3}(k)] .  (7.11)

As I_{β}(k) is the integral on the left-hand side of (7.7), we have

I_{β}(k + 1) − I_{β}(k) = ∫_{0}^{1} \frac{(1 − α)^{4k+2}}{(1 + \frac{α}{β}) \sqrt{α(2 − α)}} [(1 − α)^{4} − 1] dα.  (7.12)

The asymptotics of the integral in (7.12) follows by Laplace’s method, in the same manner as the proof of Lemma 14. In this case λ = 3/2, μ = 1, and equations (7.8) and (7.12) impliy that

I_{β}(k + 1) − I_{β}(k) ∼ \frac{\sqrt{π}}{4\sqrt{2}k^{3/2}} , k → ∞.  (7.13)

Equations (7.11) and (7.13) determine the asymptotics of D_{k+1} − D_{k}, and combining this with the asymptotics of D_{k} given by (7.10) we obtain that the second term on the right-hand side of (7.9) has asymptotics −1/(2k) as k → ∞. The two terms on the right-hand side of (7.9) thus have a sum that is asymptotically −1/(2k) − 1/(2k) = −1/k, and Theorem 2 is proved. □

8. Lozenge occupation probability for a free boundary

This section contains the results that are relevant for the calculation of the F-field F_{ξ} reported in Section 2. Since the proofs are very similar to those of Theorem 4 and Lemmas 12–14, here we only give a brief outline of how to derive these results.

By a method completely analogous to the one used in the proof of Theorem 4 given in Section 5, one can derive the following theorem. Recall that F_{n,x} is the half hexagon with side-lengths 2n, 2x, 2n and that L(k) is the horizontal lozenge on its symmetry axis at distance k\sqrt{3} from the free boundary.

Theorem 15. For all positive integers n, x and nonnegative integers k ≤ n − 1, we have

M(F_{n,x} \ L(k)) = ∏_{s=1}^{n} \frac{(2x + 2s)_{4n−4s+1}}{(2s)_{4n−4s+1}}

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

The sum in (8.1) can be written as a difference of two hypergeometric series, which turn out to be _{3}F_{2}-series. For the asymptotic analysis of these _{3}F_{2}-series, we need the following counterpart of Lemma 12.

Lemma 16. Let β be a real number with either β > 0 or β < −1. Then, for fixed positive k and all sequences (β_{n})_{n≥1} with β_{n} → β as n → ∞, we have

lim_{n→∞} \frac{1}{\sqrt{n}} _{3}F_{2}[ \begin{matrix}−2n, \frac{1}{2}, β_{n}n \\ −2n + \frac{1}{2}, β_{n}n + 1 \end{matrix} ; 1] = ∫_{0}^{1} \frac{\sqrt{2}}{(1 + \frac{α}{β}) \sqrt{πα(2 − α)}} dα,  (8.2)

where, on the left-hand side, we used again the standard notation (5.23) for hypergeometric series.

Using Stirling’s formula (7.5) and the above lemma, it is straightforward to determine the asymptotics of (8.1) as n and x tend to infinity so that x/n approaches ξ. We obtain the following counterpart of Lemma 13.

Lemma 17. For any ξ > 0, any sequence (ξ_{n})_{n≥1} with lim_{n→∞} ξ_{n} = ξ and ξ_{n}n ∈ ℤ, and 0 ≤ k ∈ ℤ, we have

lim_{n→∞} \frac{M(F_{n,ξ_{n}n} \ L(k))}{M(F_{n,ξ_{n}n})}

= \frac{1}{π\sqrt{ξ(2 + ξ)}}((2 + ξ) ∫_{0}^{1} \frac{dα}{(1 + \frac{α}{ξ}) \sqrt{α(2 − α)}} − ξ ∫_{0}^{1} \frac{dα}{(1 − \frac{α}{2+ξ}) \sqrt{α(2 − α)}})

= \frac{1}{π\sqrt{ξ(2 + ξ)}} ∫_{0}^{1} \frac{2(1 − α)}{(1 + \frac{α}{ξ}) (1 − \frac{α}{2+ξ}) \sqrt{α(2 − α)}} dα.  (8.3)

It is a routine matter to check that

∫ \frac{dα}{(1 + \frac{α}{ξ}) \sqrt{α(2 − α)}} = 2\sqrt{\frac{ξ}{π(2 + ξ)}} arctan \sqrt{\frac{α(2 + ξ)}{(2 − α)ξ}}.  (8.4)

Corollary 18. For any ξ > 0, any sequence (ξ_{n})_{n≥1} with lim_{n→∞} ξ_{n} = ξ and ξ_{n}n ∈ ℤ, and 0 ≤ k ∈ ℤ, we have

lim_{n→∞} \frac{M(F_{n,ξ_{n}n} \ L(k))}{M(F_{n,ξ_{n}n})} = \frac{2}{π} arctan \frac{1}{\sqrt{ξ(2 + ξ)}}.  (8.5)

Proof. From Lemma 17 (first expression) and (8.4), we obtain

lim_{n→∞} \frac{M(F_{n,ξ_{n}n} \ L(k))}{M(F_{n,ξ_{n}n})} = \frac{2}{π} (arctan \sqrt{\frac{2 + ξ}{ξ}} − arctan \sqrt{\frac{ξ}{2 + ξ}} ) .

The expession in (8.5) then follows by standard formulas for the arctangent function. □

Acknowledgement. We are grateful to the referee for a very careful reading of the original manuscript and many helpful suggestions on the presentation of the material.

References

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

2. G. E. Andrews, R. A. Askey and R. Roy, Special functions, Encyclopedia of Math. And Its Applications 71, Cambridge University Press, Cambridge, 1999.

3. J. Baik, T. Kriecherbauer, K. T.-R. McLaughlin, P. D. Miller, Discrete orthogonal polynomials, Asymptotics and applications, Ann. Math. Studies, Princeton University Press, Princeton, NJ, 2007.

4. W. N. Bailey, Generalized hypergeometric series, Cambridge University Press, Cambridge, 1935.

5. M. Ciucu, Rotational invariance of quadromer correlations on the hexagonal lattice, Adv. in Math. 191 (2005), 46–77.

6. M. Ciucu, A random tiling model for two dimensional electrostatics,, Mem. Amer. Math. Soc. 178 (2005), 1–106.

7. M. Ciucu, Dimer packings with gaps and electrostatics, Proc. Natl. Acad. Sci. USA 105 (2008), 2766– 2772.

8. M. Ciucu, The scaling limit of the correlation of holes on the triangular lattice with periodic boundary conditions, Mem. Amer. Math. Soc. 199, no. 935, Providence, R.I., 2009.

9. M. Ciucu, The emergence of the electrostatic field as a Feynman sum in random tilings with holes, Trans. Amer. Math. Soc. 362 (2010), 4921–4954.

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

11. H. Cohn, M. Larsen and J. Propp, The shape of a typical boxed plane partition, New York J. of Math. 4 (1998), 137–165.

12. P. Di Francesco and N. Reshetikhin, Asymptotic shapes with free boundaries, preprint;

http://arχiv.org/abs/0908.1630.

13. R. P. Feynman, The Feynman Lectures on Physics, vol. II, Addison-Wesley, Reading, Massachusetts, 1963.

14. I. Fischer, Another refinement of the Bender–Knuth (ex-)conjecture, European J. Combin. 27 (2006), 290–321.

15. M. E. Fisher and J. Stephenson, Statistical mechanics of dimers on a plane lattice. II. Dimer correlations and monomers, Phys. Rev. (2) 132 (1963), 1411–1431.

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

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

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

18. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

19. M. Ishikawa and M. Wakayama, Minor summation formula for pfaffians, Linear and Multilinear Algebra 39 (1995), 285–305.

20. R. Kenyon, Local statistics of lattice dimers, Ann. Inst. H. Poincaré Probab. Statist. 33 (1997), 591–618.

21. R. Kenyon, The asymptotic determinant of the discrete Laplacian, Acta Math. 185 (2000), 239–286.

22. R. Kenyon, A. Okounkov and S. Sheffield, Dimers and amoebae, Ann. of Math. 163 (2006), 1019–1056.

23. C. Krattenthaler, The major counting of nonintersecting lattice paths and generating functions for tableaux, Mem. Amer. Math. Soc. 115, no. 552, Providence, R. I., 1995.

24. C. Krattenthaler, An alternative evaluation of the Andrews–Burge determinant, 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.

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

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

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

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

29. M. L. Mehta and R. Wang, Calculation of a certain determinant, Commun. Math. Phys. 214 (2000), 227–232.

30. F. W. J. Olver, Asymptotics and special functions, reprint of the 1974 original [Academic Press, New York], A K Peters, Ltd., Wellesley, MA, 1997.

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

32. S. Sheffield, Random surfaces, Astérisque, vol. 304, Soc. Math. France, 2005.

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

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

35. D. Vella and L. Mahadevan, The “Cheerios effect”, Amer. J. Phys. 73 (2005), 817–825.

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

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