Watermelon configurations with wall

interaction: exact and asymptotic results

C. Krattenthaler^{†‡}

Institut Camille Jordan, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France.

            WWW: http://igd.univ-lyon1.fr/~kratt

Dedicated to Tony Guttmann

Abstract. We perform an exact and asymptotic analysis of the model of n vicious walkers interacting with a wall via contact potentials, a model introduced by Brak, Essam and Owczarek. More specifically, we study the partition function of watermelon configurations which start on the wall, but may end at arbitrary height, and their mean number of contacts with the wall. We improve and extend the earlier (partially nonrigorous) results by Brak, Essam and Owczarek, providing new exact results, and more precise and more general asymptotic results, in particular full asymptotic expansions for the partition function and the mean number of contacts. Furthermore, we relate this circle of problems to earlier results in the combinatorial and statistical literature.

1. Introduction. The problem of vicious walkers was introduced by Fisher [18], who also gave a number of physical applications of the model, such as, for example, to modelling wetting and melting. The general model is one of n random walkers on a d-dimensional lattice who at regular time intervals simultaneously take one step in the direction of one of the allowed lattice vectors such that at no time two walkers occupy the same lattice site.

Numerous papers have been written on the subject since then. Most of them analyse the model of vicious walkers in a continuum limit (such as for example [10, 18, 21, 22, 23, 24, 37, 38, 39, 40, 50, 51], with the foundation paper being [18]). It has been realized only recently that in fact there are many interesting cases in which even exact results in form of nice closed product formulas are available (see for example [1,

2000 Mathematics Subject Classification. Primary 82B20; Secondary 05A15 05A16 60G50 82B23 82B26 82B41 82B43.

Key words and phrases. vicious walkers, watermelon configurations, non-intersecting lattice paths, touchings, reflection principle, hypergeometric series, singularity analysis.

†Research partially supported by the Austrian Science Foundation FWF, grants P12094-MAT and P13190-MAT, as well as grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory,” and by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”

‡Current address: Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria.

7, 8, 9, 16, 32, 46, 52, 56]), and that asymptotic analysis can be performed directly on the model, without taking recourse to continuum limits, thus obtaining more precise estimates (see for example [8, 16, 46, 52, 56]).

In this paper we consider n vicious walkers (the “vicious” constraint demanding that at no time two walkers occupy the same site) in the plane integer lattice with allowed steps of the form (1, 1) (up-step) and (1, −1) (down-step), which in addition do not run below the x-axis (the wall). Given integer vectors a = (a_{1}, a_{2}, …, a_{n}) and e = (e_{1}, e_{2}, …, e_{n}), where all a_{i}’s are of the same parity and all e_{i}’s are of the same parity, we study the partition function Z_{t}^{(n)}(a → e; κ) := ∑_{P} κ^{c(P)}, where the sum is over all families P = (P_{1}, P_{2}, …, P_{n}) of n vicious walkers as above, the ith walker P_{i} starting at (0, a_{i}) and ending at (t, e_{i}), i = 1, 2, …, n, and with c(P) denoting the total number of contacts of the walkers with the wall. (Because of the “vicious” constraint, it is only the lowest of the walkers who can have contacts with the wall.) An example of such a family of vicious walkers with n = 4, a = (0, 2, 4, 6), e = (0, 2, 4, 6), t = 8 is shown in Figure 1.a, whereas Figure 1.b shows a family of vicious walkers with n = 5, a = (0, 2, 4, 6, 8), e = (2, 4, 6, 8, 10), t = 12. The number of contacts with the wall (the x-axis) is 3 in Figure 1.a, and it is 4 in Figure 1.b.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; u_{1}; u_{2}; u_{3}; u_{4}; v_{1}; v_{2}; v_{3}; v_{4}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; u_{1}; u_{2}; u_{3}; u_{4}; u_{5}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}]

a. b. Vicious walkers

Figure 1

The special topology of vicious walkers that we shall be mostly concerned with in this paper is watermelon configurations (watermelons for short), which are families of vicious walkers in which the y-coordinates of neighbouring starting points differ by 2, the same being true for the end points. The y-coordinate of the end point of the lowest walker is called the deviation of the watermelon configuration. Thus, both vicious walker families in Figure 1 are in fact watermelon configurations, the one in Figure 1.a has deviation 0, the one in Figure 1.b has deviation 2.

The above described vicious walker model with contact interaction has been introduced by Owczarek, Essam and Brak in [52]. They obtained a determinantal formula for the partition function, and undertook a (partially non-rigorous^{1}) study of its asymptotic properties as the length t of the walks tends to infinity in the case of watermelon configurations starting and ending on the wall. (By definition, these arise if a = e = (0, 2, 4, …, 2n − 2).) This study was crucially based on recurrence relations for the partition function. It revealed a critical value of the parameter κ at κ = 2, and they also provided a scaling analysis around this critical value. However, the use of recurrence relations intrinsically makes it only possible to obtain the order of magnitude of the partition function, but not the multiplicative constant, not to mention any error terms. This paper was followed by the articles [6, 7] by Brak and Essam, in which exact results for the partition function for watermelons which start on the wall and end at some fixed deviation y not necessarily equal to 0 are obtained. On the other hand, the latter three papers do not contain any asymptotic results for this more general situation.

The purpose of our paper is three-fold. First, we relate this circle of problems to earlier results in the combinatorial and statistical literature. In particular, we show that the determinantal formulas in [9] and [52] follow directly from a (now) classical result on non-intersecting path families in acyclic graphs due to Lindström [47], which was rediscovered by Gessel and Viennot [26, 27]. (In fact, all determinantal formulas for vicious walkers follow from that result.) Furthermore, we outline that the results in [8] and [52] on the partition function of a single walker are well-known in nonparametric statistics. Second, we derive a new exact formula for the partition function

Z_{t}^{(n)}(y; κ) := Z_{t}^{(n)}((0, 2, …, 2n − 2) → (y, y + 2, …, y + 2n − 2); κ)  (1.1)

for watermelon configurations which start on the wall and end at deviation y (see Theorem 8), which expresses Z_{t}^{(n)}(y; κ) in terms of a double sum. This is the central result of our paper, from which all other results are derived. Not only does it allow us to rederive, in a uniform manner, all previously obtained exact results [6, 7, 8, 12, 46, 52] on the partition function Z_{t}^{(n)}(y; κ) in the literature (see Corollary 5, Theorem 9, Corollary 10, Theorem 11), it also enables us to extend these in two cases to significantly larger domains of the parameter κ (see Corollary 5 and Theorem 11). Third, we improve and extend the asymptotic results by Owczarek, Essam and Brak [52]. Not only do we show how to rigorously find the asymptotic form of the partition function for watermelon configurations which start on the wall and end at an arbitrary (fixed, or non-fixed) deviation as the length of the walks tends to infinity, our approach allows to even derive full asymptotic expansions. In particular, our results confirm the phase transition at κ = 2 predicted by Owczarek, Essam and Brak. Moreover, we provide new exact and asymptotic results for the (normalized) mean number of contacts of the watermelons with the wall. These results show that, for the length of the walks being large, the normalized mean number of contacts is (asymptotically) proportional to a constant if κ is less than the critical value 2, it is proportional to the square root of the length of the walks if κ is equal to the critical value, and it is proportional to the length of the walks if κ is greater than 2. Again, all these results are made possible by our double sum formula for the partition function given in Theorem 8.

1Their approach could probably be made rigorous by applying the Birkhoff–Trjitzinsky theory [3, 4] of determining the asymptotics of solutions to difference equations, surveyed in [64].

The techniques that we employ to prove our results are (1) combinatorial: path manipulation, Lindström–Gessel–Viennot theorem on non-intersecting lattice paths, tableau combinatorics (in particular: jeu de taquin); (2) algebraic-manipulatory: hypergeometric series identities;^{2} and for the asymptotic calculations (3) analytic: singularity analysis. In particular, our approach clearly shows how the various results that have been obtained earlier are connected.

Our paper is organised as follows. In the next section we address the analysis of a single walker with wall interaction, and relate it to the statistical literature, in particular to papers by Engelberg [15] and Mohanty [48]. Then, in Section 3, we address the case of several walkers. We recall the Lindström–Gessel–Viennot theorem and demonstrate how it directly implies the determinantal formula [9] by Brak, Essam and Owczarek. In addition, in Proposition 3, we also deduce a slightly different determinantal formula for the partition function for watermelon configurations which start on the wall, which will be more convenient for our subsequent computations. In Section 4 we restrict our attention to the exact enumeration of watermelon configurations which start and end on the wall. We provide a new, short proof for a result by Brak and Essam [6, Theorem 6], which expresses the partition function in form of a single sum. This proof shows in particular that guessing the result is sufficient to prove it, the details being filled in by the computer (see Theorem 4 and its proof). Moreover, we reprove and extend an alternative expression for the partition function found earlier by Owczarek, Essam and Brak [52, Eq. (4.65)] (see Corollary 5). Section 5 begins the analysis of watermelon configurations which start on the wall and end at some fixed deviation y not necessarily equal to 0. The main purpose of the section is to find a manageable expression for the number of these watermelons with a fixed number of contacts with the wall. This is accomplished by showing that these are equinumerous with another set of vicious walker families (see Proposition 6), a result that has been previously obtained by Brak and Essam [6, Cor. 1]. Our proof however is bijective, being based on a modified jeu de taquin, thus solving a problem posed in [6]. (We remark that since the first version of the present article was written, Rubey [57] has found a completely different bijection, which, in fact, works in a much more general setting.) This result is then used in Section 6 to find an exact expression in form of a double sum for the partition function Z_{t}^{(n)}(y; κ) for watermelons which start on the wall and end at some arbitrary fixed deviation (see Theorem 8), which is new and the central result of this paper. By the use of hypergeometric summation and transformation formulas we are able to rederive, respectively extend, previously obtained alternative expressions due to Brak and Essam (private communication) (see Theorems 9 and 11). By the same techniques we are also able to rederive earlier closed form results by the author, Guttmann and Viennot [46] in the case that κ = 1, and by Owczarek, Essam and Brak [52] and Ciucu and the author [12] in the case that κ = 2, see Corollary 10. Section 7 is devoted to the asymptotic analysis of the partition function Z_{t}^{(n)}(y; κ). Our starting point is the double sum formula for Z_{t}^{(n)}(y; κ) provided by Theorem 8, which, when combined with the technique of singularity analysis, yields full asymptotic expansions for Z_{t}^{(n)}(y; κ) as the length t of the walks tends to infinity (see Theorem 12). Thus we confirm the predictions by Owczarek, Essam and Brak [52], making them more precise at the same time. The final Section 8 is devoted to the study of the mean number of contacts. In the same special cases as above, namely for κ = 1 and κ = 2, we are able to obtain simple closed formulas, see Theorems 13 and 14. Singularity analysis again allows us to obtain full asymptotic expansions for the mean number of contacts, which is the contents of Theorem 15.

2All the hypergeometric calculations in this paper were carried out using the author’s Mathematica package HYP, which is designed for a convenient handling of hypergeometric series, and is available from http://www.mat.univie.ac.at/~kratt.

2. The combinatorics of a single walker. In this section we consider a single walker with wall interaction. What we aim at is the computation of the partition function ∑_{P} κ^{c(P)}, where the sum is over all walks P from (0, a) to (t, e) which never run below the x-axis (the wall), and where c(P) denotes the number of contacts of the walk with the wall. Slightly deviating from the notation introduced in the Introduction, we denote this partition function by Z_{t}^{(1)}(a → e; κ).

As we are going to develop, this type of question is classical in the literature on nonparametric statistics. We summarize what is known in the proposition below. It gives an explicit formula for the partition function Z_{t}^{(1)}(a → e; κ), and, as a simple corollary, an algebraic expression for the corresponding generating function. This is an old result due to Engelberg [15, Cor. 3.2] (for the case where the starting point is on the x-axis) and Mohanty [48, Cor. 1 (iv)] (for the general case). It has recently been rediscovered by Brak, Essam and Owczarek in [8, Eq. (3.11)]. There is an elegant combinatorial proof, the origin of which is difficult to track down (see for example [34, proof of Lemma 1] for an occurrence of that idea^{3}). Since it is apparently less well-known than it should be, we reproduce it below.

Proposition 1. Let a and e be non-negative integers with a + e ≡ t mod 2. Then the partition function Z_{t}^{(1)}(a → e; κ) of a single vicious walker starting at (0, a) and ending at (t, e) and never running below the x-axis is given by

3The original inspiration for that idea may be due to Csáki and Vincze [14, p. 100]. There it appears in a slightly modified form, and is used there to solve a slightly modified problem, namely to find the number of walks which cross the x-axis a given number of times.

\binom{t}{(t + a − e)/2} − \binom{t}{(t − a − e)/2}

+ ∑_{ℓ≥1} (\binom{t − ℓ}{(t + a + e − 2)/2} − \binom{t − ℓ}{(t + a + e)/2}) κ^{ℓ}. (2.1)

The generating function, the coefficients of which are these partition functions, is equal to

∑_{t≥0} ; t≡a+e (mod 2)Z_{t}^{(1)}(a → e; κ)z^{t} = \frac{1}{\sqrt{1 − 4z^{2}}} (\frac{1 − \sqrt{1 − 4z^{2}}}{2z} )^{|e−a|}

− \frac{1}{\sqrt{1 − 4z^{2}}} (\frac{1 − \sqrt{1 − 4z^{2}}}{2z} )^{e+a} (1 − \frac{\sqrt[\frac{2κ}{2−κ}]{1 − 4z^{2}}}{1 + \frac{κ}{2−κ} \sqrt{1 − 4z^{2}}} ) . (2.2)

Proof. Let for the moment a and e be at least 1. The coefficient of κ^{0} in Z_{t}^{(1)}(a → e; κ) counts the walks from (0, a) to (t, e) which do not touch the x-axis. As is classical, this number can be obtained from the reflection principle (see e.g. [13, p. 22]). It is equal to

\binom{t}{(t + a − e)/2} − \binom{t}{(t − a − e)/2},  (2.3)

which explains the first line in (2.1).

On the other hand, for ℓ ≥ 1 the coefficient of z^{ℓ} counts the walks from (0, a) to (t, e) which do not cross the x-axis and touch it exactly ℓ times. Let us consider such a walk, see Figure 2 for an example in which t = 17, a = 3, e = 2, ℓ = 3.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; (0, a); (t, e)]

A walk touching the x-axis ℓ times

Figure 2

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; •; •; ∘; ∘; ∘; (0, a); (t − ℓ, e + ℓ); y = 1]

After deletion of steps

Figure 3

Such a walk is now transformed into a walk from (0, a) to (t − ℓ, e + ℓ) by deleting all the steps immediately preceding a touching point from the original walk and gluing the walk pieces together. In our example in Figure 2, these steps are indicated by thick line segments. Figure 3 shows the result after deletion of these steps. The circles should be ignored at this point.

We claim that this mapping is indeed a bijection between walks from (0, a) to (t, e) which do not cross the x-axis and touch it exactly ℓ times and walks from (0, a) to (t − ℓ, e + ℓ) which do not run below the horizontal line y = 1 but touch y = 1 at least once. For establishing the claim we have to explain how we can reconstruct the original walk from one of the walks of the second type. In order to accomplish this, we just have to find the points in the walk where steps had been deleted. Indeed, as is straight-forward to see, for each j, 1 ≤ j ≤ ℓ, the right-most point on the walk which is on the horizontal line y = j is such a point, and these are in fact all of them. In our example in Figure 3 these points are circled.

Hence, the number that we want to find is equal to the number of walks from (0, a) to (t−ℓ, e+ℓ) which do not run below the line y = 1 minus the number of walks from (0, a) to (t − ℓ, e + ℓ) which do not run below the line y = 2. By another application of the reflection principle, this is

(\binom{t − ℓ}{(t + a − e − 2ℓ)/2} − \binom{t − ℓ}{(t − a − e − 2ℓ)/2})

− (\binom{t − ℓ}{(t + a − e − 2ℓ)/2} − \binom{t − ℓ}{(t − a − e − 2ℓ + 2)/2}) ,

which, after cancellation, gives exactly the expression which appears as the coefficient of κ^{ℓ}, ℓ ≥ 1, in (2.1).

The above considerations establish (2.1) for a, e ≥ 1. If a = 0 and e ≥ 1, then we argue that the partition function Z_{t}^{(1)}(0 → e; κ) is equal to κZ_{t−1}^{(1)}(1 → e; κ) because the first step in a walk that starts at (0, 0) must necessarily be an up-step, the additional factor κ taking into account the touching of the original walk at (0, 0). Now we may apply formula (2.1) with a = 1. It is just a matter of simple manipulations to convert the obtained expression to (2.1) with a = 0. If a ≥ 1 and e = 0, respectively if a = e = 0, one argues similarly. We leave the details to the reader.

In order to establish the second assertion of the proposition, we must compute the generating function

∑_{t≥0} ; t≡a+e (mod 2) (\binom{t}{(t + a − e)/2} − \binom{t}{(t − a − e)/2}) z^{t}  (2.4)

on the one hand, and

∑_{t≥0} ; t≡a+e (mod 2)( ∑_{ℓ≥1} (\binom{t − ℓ}{(t + a + e − 2)/2} − \binom{t − ℓ}{(t + a + e)/2}) κ^{ℓ})z^{t}  (2.5)

on the other.

We may concentrate on the case where e ≥ a, because it is combinatorially obvious that an interchange of a and e gives the same result. Therefore, from now on we assume e ≥ a.

In order to compute the series (2.4), we write it in a telescoping form as

∑_{j=0}^{a−1}_{∑_{t≥0} ; t≡a+e (mod 2)} (\binom{t}{(t + a − e − 2j)/2} − \binom{t}{(t + a − e − 2j − 2)/2}) z^{t}

= ∑_{j=0}^{a−1} ∑_{r≥0} (\binom{2r + 2j + e − a}{r} − \binom{2r + 2j + e − a}{r − 1}) z^{2r+2j+e−a}, (2.6)

where in the next-to-last line we performed the index transformation t → 2r+2j+e−a.

Now we appeal to the well-known fact (see e.g. [49, displayed line before (1.21) with μ = 1], in combination with [49, (1.19)]) that

∑_{r=0}^{∞} \frac{m + 1}{r + m + 1}\binom{2r + m}{r}x^{r} = ∑_{r=0}^{∞} (\binom{2r + m}{r} − \binom{2r + m}{r − 1}) x^{r} = C(x)^{m+1}, (2.7)

where C(x) is the generating function for the Catalan numbers,

C(x) = ∑_{r=0}^{∞} \frac{1}{r + 1}\binom{2r}{r}x^{r} = ∑_{r=0}^{∞} (\binom{2r}{r} − \binom{2r}{r − 1}) x^{r} = \frac{1 − \sqrt{1 − 4x}}{2x}. (2.8)

If we use this in (2.6), then we find that the series (2.4) is equal to

∑_{j=0}^{a−1} z^{2j+e−a}C(z^{2})^{2j+e−a+1} = \frac{z^{e−a}C(z^{2})^{e−a+1} − z^{e+a}C(z^{2})^{e+a+1}}{1 − z^{2}C(z^{2})^{2}}

= \frac{1}{\sqrt{1 − 4z^{2}}} ((\frac{1 − \sqrt{1 − 4z^{2}}}{2z} )^{e−a} − (\frac{1 − \sqrt{1 − 4z^{2}}}{2z} )^{e+a}) , (2.9)

the last line being due to the easily verified fact that

1 − xC(x)^{2} = C(x)\sqrt{1 − 4x}.  (2.10)

For the computation of the series (2.5) we proceed in a similar fashion. Here, we first interchange summations and then replace the index t of the (now) inner summation by 2r + 2ℓ + a + e − 2 to transform the series to

∑_{ℓ≥1} ∑_{r≥0} (\binom{2r + ℓ + a + e − 2}{r} − \binom{2r + ℓ + a + e − 2}{r − 1}) z^{2r+2ℓ+a+e−2}κ^{ℓ}.

Now we apply (2.7) to the inner summation and obtain

∑_{ℓ≥1} z^{2ℓ+a+e−2}C(z^{2})^{ℓ+a+e−1}κ^{ℓ} = \frac{κ z^{a+e}C(z^{2})^{a+e}}{1 − κz^{2}C(z^{2})}

= \frac{1}{\sqrt{1 − 4z^{2}}} (\frac{1 − \sqrt{1 − 4z^{2}}}{2z} )^{e+a} \frac{\sqrt[\frac{2κ}{2−κ}]{1 − 4z^{2}}}{1 + \frac{κ}{2−κ} \sqrt{1 − 4z^{2}}} . (2.11)

Summing the expressions (2.9) and (2.11) gives exactly (2.2). □

3. The combinatorics of n vicious walkers. In this section we recall Lindström’s classical result [47, Lemma 1] on the enumeration of families of vicious walkers (non-intersecting paths)^{4} in directed graphs (directed networks), and apply it to obtain determinantal formulae for our partition function Z_{t}^{(n)}(a → e; κ).

Let G = (V, E) be a directed acyclic graph with vertices V and directed edges E. Furthermore, we are given a function w which assigns a weight w(x) to every vertex or edge x. Let us define the weight w(P) of a walk P in the graph by ∏_{e} w(e) ∏_{v} w(v), where the first product is over all edges e of the walk P and the second product is over all vertices v of P. We denote the set of all walks in G from u to v by P(u → v), and the set of all families (P_{1}, P_{2}, …, P_{n}) of walks, where P_{i} runs from u_{i} to v_{i}, i = 1, 2, …, n, by P(u → v), with u = (u_{1}, u_{2}, …, u_{n}) and v = (v_{1}, v_{2}, …, v_{n}). The symbol P^{+}(u → v) stands for the set of all families (P_{1}, P_{2}, …, P_{n}) in P(u → v) with the additional property that no two walks share a vertex. We call such families of walk(er)s “vicious walkers” or, alternatively, “non-intersecting lattice paths”. The weight w(P) of a family P = (P_{1}, P_{2}, …, P_{n}) of walks is defined as the product ∏_{i=1}^{n} w(P_{i}) of all the weights of the walks in the family. Finally, given a set M with weight function w, we write GF(M; w) for the generating function ∑_{x∈M} w(x).

We need two further notations before we are able to state the Lindström–Gessel– Viennot theorem.^{5} The symbol S_{n} denotes the symmetric group of order n. Given a permutation σ ∈ S_{n}, we write u_{σ} for (u_{σ(1)}, u_{σ(2)}, …, u_{σ(n)}). Then

∑_{σ∈S_{n}}(sgn σ) · GF(P^{+}(u_{σ} → v); w) = det_{1≤i,j≤n} ( GF(P(u_{j} → v_{i}); w)).  (3.1)

4Lindström used the term “pairwise node disjoint paths”. The term “non-intersecting,” which is most often used nowadays in combinatorial literature, was coined by Gessel and Viennot [26].

5By a curious coincidence, Lindström’s result (the motivation of which was matroid theory!) was rediscovered in the 1980s at about the same time in three different communities, not knowing from

Most often, this theorem is applied in the case where the only permutation σ for which vicious walks exist is the identity permutation, so that the sum on the lefthand side reduces to a single term which counts all families (P_{1}, P_{2}, …, P_{n}) of vicious walks, the i-th walk P_{i} running from A_{i} to E_{i}, i = 1, 2, …, n. This case occurs for example if for any pair of walks (P, Q) with P running from u_{a} to v_{d} and Q running from u_{b} to v_{c}, a < b and c < d, it is true that P and Q must have a common vertex. Explicitly, in that case we have

GF(P^{+}(u → v); w) = det_{1≤i,j≤n} ( GF(P(u_{j} → v_{i}); w)).  (3.2)

This is also the case which we encounter in this paper.^{6}

Proposition 2. Let a = (a_{1}, a_{2}, …, a_{n}) and e = (e_{1}, e_{2}, …, e_{n}) be n-tuples of non-negative integers with 0 ≤ a_{1} < a_{2} < ⋯ < a_{n}, 0 ≤ e_{1} < e_{2} < ⋯ < e_{n}, all a_{i}’s of the same parity, all e_{i}’s of the same parity, such that a_{i} + e_{i} ≡ t (mod 2) for all i. As before, let Z_{t}^{(n)}(a → e; κ) denote the partition function for families of n vicious walkers, the i-th starting at (0, a_{i}) and ending at (t, e_{i}), none of them running below the x-axis, where the weight of a walker configuration P is defined as κ^{c(P)} with c(P) denoting the number of contacts of the walkers with the x-axis. Then

Z_{t}^{(n)}(a → e; κ) = det_{1≤i,j≤n} (Z_{t}^{(1)}(a_{j} → e_{i}; κ)) ,  (3.3)

where Z_{t}^{(1)}(a → e; κ) is given by (2.1).

Proof. We apply (3.2) for G the graph with vertices the points (x, y) in the plane integer lattice with y ≥ 0 and with directed edges (x, y) → (x + 1, y − 1), y ≥ 1, and (x, y) → (x + 1, y + 1), y ≥ 0. As the weight w we choose the function which assigns 1 to every edge and to every vertex (x, y) with y > 0, and which assigns κ to every vertex on the x-axis. If we now choose u_{i} = (0, a_{i}) and v_{i} = (t, e_{i}) in the Lindström–Gessel– Viennot theorem (3.2), then the generating function on the left-hand side is exactly the partition function Z_{t}^{(n)}(a → e; κ) for n vicious walkers, whereas the generating function which gives the (i, j)-entry of the determinant on the right-hand side is the partition function Z_{t}^{(1)}(a_{j} → e_{i}; κ) for a single walker from (0, a_{j}) to (t, e_{i}), the latter being given explicitly by Proposition 1. □

each other at that time: in statistical physics by Fisher [18, Sec. 5.3] in order to apply it to the analysis of vicious walkers as a model of wetting and melting, in combinatorial chemistry by John and Sachs [33] and Gronau, Just, Schade, Scheffler and Wojciechowski [31] in order to compute Pauling’s bond order in benzenoid hydrocarbon molecules, and in enumerative combinatorics by Gessel and Viennot [26, 27] in order to count tableaux and plane partitions. Since only Gessel and Viennot rediscovered it in its most general form, I propose to call this theorem the “Lindström– Gessel–Viennot theorem.” It must however be mentioned that in fact the same idea appeared even earlier in work by Karlin and McGregor [35, 36] in a probabilistic framework, as well as that the so-called “Slater determinant” in quantum mechanics (cf. [59] and [60, Ch. 11]) may qualify as an “ancestor” of the Lindström–Gessel–Viennot determinant.

6There exist however also several interesting applications of the general form of the Lindström– Gessel–Viennot theorem in the literature, see [11, 17, 62].

This result has also been obtained by Brak, Essam and Owczarek in [9, Eqs. (22), (23)] (using the Bethe Ansatz method; their derivation is much more complicated, but it is on the other hand a method which is more widely applicable that they use).

In this paper we will primarily analyse the case of watermelon configurations which start on the wall. To be precise, this is the case where the starting point u_{i} is (0, 2i−2) and the end point v_{i} is (t, y + 2i − 2), i = 1, 2, …, n, for some non-negative integer y. In our analysis of this particular case we shall in fact use two variants of the above formula, which are also corollaries of the Lindström–Gessel–Viennot theorem.

Proposition 3. Let t and y be non-negative integers with t ≡ y (mod 2). As in the Introduction, let Z_{t}^{(n)}(y; κ) denote the partition function for families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, where the weight of a walker configuration P is defined as κ^{c(P)} with c(P) denoting the number of contacts of the walkers with the x-axis. Then

Z_{t}^{(n)}(y; κ) = \frac{1}{κ^{n−1}} det_{0≤i,j≤n−1}(B_{i,j}(t, y; κ)),  (3.4)

where

B_{i,j}(t, y; κ) = ∑_{ℓ≥1} (\binom{t + 2j − ℓ}{\frac{t+y}{2} + i + j − 1} − \binom{t + 2j − ℓ}{\frac{t+y}{2} + i + j}) κ^{ℓ}

= ∑_{ℓ≥1} \frac{y + 2i + ℓ − 1}{\frac{t+y}{2} + i + j}\binom{t + 2j − ℓ}{\frac{t+y}{2} + i + j − 1}κ^{ℓ}.  (3.5)

Furthermore, let Z_{2r}^{(n)}(κ) denote the partition function for families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (2r, 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, with the same weight of walker configurations. Then

Z_{2r}^{(n)}(κ) = \frac{1}{κ^{2n−2}} det_{0≤i,j≤n−1}(C(r + i + j; κ)),  (3.6)

where

C(r; κ) = ∑_{ℓ=2}^{r+1} (\binom{2r − ℓ}{r − 1} − \binom{2r − ℓ}{r}) κ^{ℓ} = ∑_{ℓ=2}^{r+1} \frac{ℓ − 1}{r}\binom{2r − ℓ}{r − 1}κ^{ℓ}.  (3.7)

Proof. We start by proving the first claim. Given a family of vicious walkers as in the first statement of the proposition, we may freely attach 2i − 2 up-steps at the beginning of the i-th walk, i = 1, 2, …, n, see Figure 4 for the resulting walks if we do this with the watermelon configuration in Figure 1.b.

It is obvious that the number of families of vicious walkers with starting points u′_{i} = (−2i + 2, 0) (instead of u_{i} = (0, 2i − 2)) and end points v_{i} = (t, y + 2i − 2), i = 1, 2, …, n, each walker not running below the x-axis (see Figure 4), is exactly the same as the number of families of vicious walkers in the first statement of the proposition

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; u′_{1}; u′_{2}; u′_{3}; u′_{4}; u′_{5}; v_{1}; v_{2}; v_{3}; v_{4}; v_{5}]

Watermelon configuration with attached walk pieces at the beginning

Figure 4

(compare Figure 1). Clearly, by attaching these walk pieces at the beginning, we introduced n − 1 further contacts of the first walk with the x-axis (namely in the points u′_{n}, u′_{n−1}, …, u′_{2}).

If we now apply (3.2) with u_{i} replaced by u′_{i}, then we obtain that the partition function for the latter families of walkers is given by

det_{1≤i,j≤n} ( GF(P((−2j + 2, 0) → (t, y + 2i − 2)); w)),

where w is our contact weight. By definition, the generating function

GF(P((−2j + 2, 0) → (t, y + 2i − 2)); w)

is equal to Z_{t+2j−2}^{(1)}(0 → y + 2i − 2; κ), which by Proposition 1 is exactly the same as B_{i−1,j−1}(t, y; κ). Since our operation of adding walk pieces introduced n−1 additional contacts with the x-axis, we must divide the above determinant by κ^{n−1}, and we obtain the final result (3.4) after replacing i by i + 1 and j by j + 1.

The proof of formula (3.6) is completely analogous. Here, one has to also attach 2i − 2 down-steps at the end of the i-th walk. We leave the details to the reader. □

4. Exact results for the partition function for watermelons of deviation 0. In this section we address the exact evaluation of the partition function of watermelon configurations which start and end on the wall. To be precise, we consider the partition function Z_{2r}^{(n)}(κ) = ∑_{P} κ^{c(P)}, where the sum is over all families P = (P_{1}, P_{2}, …, P_{n}) of n vicious walkers never running below the x-axis, the i-th walker P_{i} starting at (0, 2i − 2) and ending at (2r, 2i − 2), i = 1, 2, …, n, and with c(P) denoting the total number of contacts of the walkers with the wall. It should be noted that Z_{2r}^{(n)}(κ) = Z_{2r}^{(n)}((0, 2, 4, …, 2n − 2) → (0, 2, 4, …, 2n − 2); κ) in the notation of the Introduction and of Proposition 2.

The theorem below provides an expression for the partition function Z_{2r}^{(n)}(κ) in terms of a single sum, by finding a product formula for the number of the above watermelon configurations with exactly ℓ contacts with the wall. This result was first obtained by Brak and Essam [6, Theorem 6] by clever determinant manipulations, which allowed them to find a recurrence for the partition function. Our proof is completely different. It demonstrates that, once we have a guess for the formula (which can be found completely automatically using the Mathematica program Rate^{7}, respectively its Maple equivalent GUESS^{8}), it is already proved, as the validity of the formula can be established in a completely automatic fashion, by making use of what is known under the name of “Dodgson’s condensation method” and the Gosper– Zeilberger algorithm. A more general result will be obtained later in Theorem 8, however using completely different (non-automatic) methods.

Theorem 4. The partition function Z_{2r}^{(n)}(κ) is equal to

\frac{(r − 1)! ∏_{i=0}^{n−1}(2i + 1)! ∏_{i=0}^{n−2}(2r + 2i)!}{∏_{i=0}^{2n−2}(r + i)!} ∑_{ℓ=0}^{r−1} \binom{2r − ℓ − 2}{r − 1}\binom{ℓ + 2n − 1}{ℓ}κ^{ℓ+2}. (4.1)

In particular, the number of walker configurations with exactly ℓ contacts with the x-axis is equal to

\frac{(r − 1)! ∏_{i=0}^{n−1}(2i + 1)! ∏_{i=0}^{n−2}(2r + 2i)!}{∏_{i=0}^{2n−2}(r + i)!}\binom{2r − ℓ}{r − 1}\binom{ℓ + 2n − 3}{ℓ − 2}.

Proof. “Dodgson’s condensation method” (cf. [45, Sec. 2.3]) is based on the following determinant identity due to Desnanot and Jacobi. Let A be an n × n matrix. Denote the submatrix of A in which rows i_{1}, i_{2}, …, i_{k} and columns j_{1}, j_{2}, …, j_{k} are omitted by A_{i_{1},i_{2},...,i_{k}}^{j_{1},j_{2},...,j_{k}}. Then there holds

det A · det A_{1,n}^{1,n} = det A_{1}^{1} · det A_{n}^{n} − det A_{1}^{n} · det A_{n}^{1}.  (4.2)

If n = 2, then det A_{1,n}^{1,n}, the determinant of a 0 × 0 matrix, has to be interpreted as 1.

Because of Proposition 3, Z_{2r}^{(n)}(κ) is essentially equal to a determinant. We now apply the above determinant identity with A equal to the determinant in (3.6). Thus we obtain

Z_{2r}^{(n)}(κ)Z_{2r+4}^{(n−2)}(κ) = Z_{2r+4}^{(n−1)}(κ)Z_{2r}^{(n−1)}(κ) − (Z_{2r+2}^{(n−1)}(κ))^{2} .  (4.3)

7written by the author; available from http://www.mat.univie.ac.at/~kratt.

8written  by  François  Béraud  and  Bruno  Gauthier;  available  from http://www-igm.univ-mlv.fr/~gauthier.

This relation enables us to prove the theorem by induction on n. It is clearly true for n = 1, thanks to Proposition 1. Equation (4.3) allows to perform the induction step. We only have to check that (4.3) is true with Z_{2r}^{(n)}(κ) as asserted in the statement of the theorem.

Let first n = 2. Then the term Z_{2r+4}^{(0)}(κ) appears in (4.3), which by virtue of (3.6) is κ^{2} times the determinant of a 0×0 matrix. Since, according to our earlier convention, the latter determinant should be interpreted as 1, we should let Z_{2r}^{(0)}(κ) := κ^{2}. Thus, for n = 2 Equation (4.3) becomes

\frac{(2r)!}{r (r + 1)! (r + 2)!} ∑_{ℓ=0}^{r−1} \binom{2r − ℓ − 2}{r − 1}(ℓ + 1)(ℓ + 2)(ℓ + 3)κ^{ℓ+4}

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

− (∑_{ℓ=0}^{r} \frac{ℓ + 1}{r + 1}\binom{2r − ℓ}{r}κ^{ℓ+2})^{2} .

By comparison of coefficients of κ^{e+4} on both sides, this is seen to be equivalent to verifying that

(e + 1)(e + 2)(e + 3)\binom{2r − e − 2}{r − 1}

= ∑_{ℓ=0}^{e} (\frac{ℓ + 1}{r + 2}\binom{2r − ℓ + 2}{r + 1}\frac{e − ℓ + 1}{r}\binom{2r − e + ℓ − 2}{r − 1}

− \frac{ℓ + 1}{r + 1}\binom{2r − ℓ}{r}\frac{e − ℓ + 1}{r + 1}\binom{2r − e + ℓ}{r}).

This identity is easily proved once one observes that the summand of the sum on the right-hand side is equal to G(e, ℓ + 1) − G(e, ℓ), where

G(e, ℓ) = \frac{(2r − ℓ + 1)! (2r − e + ℓ − 2)!}{(r + 1)! (r + 2)! (r − ℓ + 1)! (r − e + ℓ − 1)!}

× (−6 − 8e − 2e^{2} + 9ℓ + 6eℓ + e^{2}ℓ − ℓ^{2} + 2eℓ^{2} + e^{2}ℓ^{2} − 3ℓ^{3} − 2eℓ^{3}

+ ℓ^{4} − 6er − 2e^{2}r − 3ℓr − 4eℓr − e^{2}ℓr + 3ℓ^{2}r + eℓ^{2}r + 6r^{2} + 2er^{2}),

since then the sum on the right-hand side is equal to G(e, e + 1) − G(e, 0), which can be seen to be equal to the left-hand side upon some simplification. (Clearly, Gosper’s algorithm [28], [30, §5.7], [54, §II.5] was used to find G(e, ℓ). The particular implementation that we used is the Mathematica implementation by Paule and Schorn [53].)

Now let n > 2. In this case, substitution of the claimed expression for Z_{2r}^{(n)}(κ) in (4.3) and comparison of coefficients of κ^{e+4} on both sides yields, after some manipulation, that we have to verify the summation

∑_{ℓ=0}^{e} (\begin{matrix}(n − 1) & (2n − 1) & (r + 1) \\ (2n + r − 2) & (2r + 1) \end{matrix}\binom{2r − ℓ − 2}{r − 1}\binom{2n + ℓ − 1}{ℓ}

· \binom{2r − e + ℓ + 2}{r + 1}\binom{2n + e − ℓ − 5}{e − ℓ}

− \begin{matrix}(r + 1) & (n + r − 1) & (2n + 2r − 3) \\ (2n + r − 2) & (2r + 1) \end{matrix}\binom{2r − ℓ + 2}{r + 1}\binom{2n + ℓ − 3}{ℓ}

· \binom{2r − e + ℓ − 2}{r − 1}\binom{2n + e − ℓ − 3}{e − ℓ}

+ r\binom{2r − ℓ}{r}\binom{2n + ℓ − 3}{ℓ}\binom{2r − e + ℓ}{r}\binom{2n + e − ℓ − 3}{e − ℓ}) = 0. (4.4)

The most straight-forward way to do this is to feed the sum into the Gosper–Zeilberger algorithm [54, 65, 66] (again we used the Mathematica implementation by Paule and Schorn [53]). If S(n) denotes the sum on the left-hand side of (4.4), then the output of the algorithm is the recurrence

(n − 1) (2n − 1) (e + 4n − 5) (2n + r − 1) (2n + r) S(n + 1) − (e + 4n − 1) (e + 2n − r − 2) (e + 2n − r − 1) (n + r) (2n + 2r − 1) S(n) = 0. (4.5)

Now, it is straight-forward to check that S(1) = 0, thus proving (4.4) for n = 1. The validity of (4.4) for arbitrary n then follows upon induction on n from the recurrence (4.5).

Thus, the proof of the theorem is complete. □

If we reverse the order of summation in the sum in (4.1) (i.e., if we replace ℓ by r − 1 − ℓ) and then rewrite it using the 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} ,

where the Pochhammer symbol (α)_{m} is defined by (α)_{m} := α(α + 1) ⋯ (α + m − 1), m ≥ 1, (α)_{0} := 1, then we obtain

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

or, more precisely (the above _{2}F_{1}-series is actually ill-defined because of the denominator parameter 2 − 2n − r which is a negative integer),

lim_{ε→0} κ^{1+r} \frac{(2n)_{r−1}}{(r − 1)!}_{2}F_{1}[ \begin{matrix}r, 1 − r \\ 2 − 2n − r + ε \end{matrix}; \frac{1}{κ}] .  (4.6)

In view of the fact that there are numerous _{2}F_{1}-transformation formulae, we can obtain numerous equivalent expressions for this sum and, hence, for (4.1) itself.

A particular such expression has been given by Owczarek, Essam and Brak in [52, Eq. (4.65)], with proof provided by Brak and Essam in [7], and was the starting point for their scaling analysis of the partition function Z_{2r}^{(n)}(κ) in [52]. This expression provides an expansion of (4.1) as an (infinite) power series in (κ−1)/κ^{2}. It is however only valid for κ ≤ 2. In the corollary below, we show how the expression of Owczarek, Essam and Brak can be readily derived by applying appropriate _{2}F_{1}-transformation formulas to (4.6). Moreover, this technique yields also an expression which is valid for κ > 2. In the case n = 1 the latter expansion was, for example, previously observed by Brak and Essam [5, Eq. (25)].

Corollary 5. Let κ > 2(\sqrt{2} − 1). Then the partition function Z_{2r}^{(n)}(κ) is equal to

\frac{∏_{i=0}^{n−1}(2i + 1)! (2r + 2i)!}{∏_{i=0}^{2n−1}(r + i)!}(\frac{1}{κ^{2n−2}} ∑_{h=0}^{∞} \binom{n + h − 1}{h}\frac{(2r + 2n − 1)_{2h}}{(r + n)_{h} (r + 2n)_{h}} (\frac{κ − 1}{κ^{2}})^{h}

+ χ(κ > 2)\frac{(κ − 2)κ^{2r+2n−1}}{(κ − 1)^{r+2n−1}} \frac{(r + 2n − 1)!}{(2n − 1)! (r + n − 1)!}

· ∑_{h=0}^{n−1} \binom{n − 1}{h}\frac{(r + n − h − 1)! (r + 2n − h − 2)!}{(2r + 2n − 2h − 2)!} (\frac{1 − κ}{κ^{2}})^{h} ), (4.7)

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

Proof. First let κ ≤ 2. We write the sum in (4.1) in the form (4.6) and apply the transformation formula (cf. [61, (1.8.10), terminating form])

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

where N is a non-negative integer. Now the limit ε → 0 can be safely performed, and we obtain

κ^{1+r} \frac{(2n + r)_{r−1}}{(1)_{r−1}}_{2}F_{1}[ \begin{matrix}1 − r, r \\ 2n + r \end{matrix}; 1 − \frac{1}{κ}]

for the sum in (4.1). Next we apply the quadratic transformation formula (see [55, (3.31), reversed])

2F_{1}[ \begin{matrix}a, 1 − a \\ c \end{matrix}; z] = (1 − z)^{c−1}_{2}F_{1}[ \begin{matrix}\frac{c}{2} − \frac{a}{2}, \frac{a}{2} + \frac{c}{2} − \frac{1}{2} \\ c \end{matrix} ; 4z (1 − z)] ,  (4.8)

which holds when Re z < 1/2, as well as if z = 1/2, and substitute the result back in (4.1). After some manipulation, we obtain the expression in the first line of (4.7), which, taking into account the condition under which (4.8) is true and the latter series converges, holds for 2(\sqrt{2} − 1) < κ ≤ 2.

If on the other hand κ > 2, then we proceed differently. We start with the expression

lim_{ε→0} κ^{1+r} \frac{(2n)_{r−1}}{(r − 1)!}_{2}F_{1}[ \begin{matrix}r − ε, 1 − r + ε \\ 2 − 2n − r + ε \end{matrix}; \frac{1}{κ}]

= lim_{ε→0} κ^{1+r} \frac{(2n)_{r−1}}{(r − 1)!} ∑_{k=0}^{∞} \frac{(r − ε)_{k} (1 − r + ε)_{k}}{(2 − 2n − r + ε)_{k} k!} κ^{−k}, (4.9)

which is clearly equivalent to (4.6). The reader should however note the differences to (4.6) in placing the ε. We split the sum over k into the three ranges 0 ≤ k ≤ r − 1, r ≤ k ≤ r + 2n − 2, and r + 2n − 1 ≤ k, and then we perform the limit ε → 0. Thereby each summand in the range r ≤ k ≤ r + 2n − 2 vanishes identically. Thus, upon writing the sum over the range r + 2n − 1 ≤ k in hypergeometric notation, the expression (4.9) becomes

κ^{1+r} \frac{(2n)_{r−1}}{(r − 1)!} ∑_{k=0}^{r−1} \frac{(r)_{k} (1 − r)_{k}}{(2 − 2n − r)_{k} k!}κ^{−k} − \frac{(r)_{r+2n−1}}{κ^{2n−2} (r + 2n − 1)!}_{2}F_{1}[ \begin{matrix}2n, 2r + 2n − 1 \\ 2n + r \end{matrix}; \frac{1}{κ}] .

(4.10)

The first sum in this expression is exactly the sum in (4.1) (which is most easily seen from the equivalent expression (4.6)). Therefore, if we equate (4.9) and (4.10), we see that the sum in (4.1) is equal to

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

+ lim_{ε→0} κ^{1+r} \frac{(2n)_{r−1}}{(r − 1)!}_{2}F_{1}[ \begin{matrix}r − ε, 1 − r + ε \\ 2 − 2n − r + ε \end{matrix}; \frac{1}{κ}] .

To the first _{2}F_{1}-series we apply the quadratic transformation formula (cf. [2, Ex. 4.(iii), p. 97, reversed])

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

which is valid for Re z < 1/2, while to the second _{2}F_{1}-series we apply the quadratic transformation formula (4.8), and subsequently the transformation (cf. [61, (1.3.15)])

2F_{1}[ \begin{matrix}a, b \\ c \end{matrix}; z] = (1 − z)^{c−a−b}_{2}F_{1}[ \begin{matrix}c − a, c − b \\ c \end{matrix}; z] .

If the resulting expression is simplified and then substituted back in (4.1), we obtain eventually the expression (4.7) for κ > 2. □

Remark. (1) Other alternative expression for (4.1) will be obtained later (in greater generality) in Theorems 9 and 11.

(2) The sum in (4.1) does not simplify in general. However, there are two cases where it does, namely if κ = 1 and if κ = 2. We state these results (again in greater generality) in Corollary 10.

5. Vicious walkers, semistandard tableaux, and jeu de taquin. The purpose of this section is to show that the number of watermelon configurations which start on the wall, end at some deviation y, and have a given number of contacts with the x-axis is equinumerous to another family of vicious walkers which do not run below the x-axis, but have no restriction on the number of contacts with the x-axis. The upshot of this is that the latter number of watermelons can now be written in form of a single determinant by applying the Lindström-Gessel–Viennot determinant (3.2). The result has been originally found by Brak and Essam [6, Cor. 1]. They derived it by manipulating (a variant of) the Lindström–Gessel–Viennot determinant (3.4). Since the result itself is purely combinatorial, they posed the problem of finding a bijective proof. We resolve this problem here. The bijective proof that we shall give below is based on the fact that vicious walker configurations are in bijection with semistandard tableaux (see [32, 46]) and on a modified jeu de taquin for semistandard tableaux that occurred earlier in bijective proofs [42, 43, 44] of Stanley’s hook-content formula for the number of semistandard tableaux of a given shape with bounded entries, and which goes back to [29].

Proposition 6. The number of families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, and where the first walk has ℓ + 1 contacts with the x-axis (including its starting point (0, 0)) is the same as the number of families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n − 1, the n-th walker running from (0, 2n − 2) to (t − ℓ − 1, y + 2n + ℓ − 3), none of them running below the x-axis.

Remark. The statement of the proposition deviates slightly from the one in [6, Cor. 1]. The equivalence of both statements can be seen by observing that in the formulation of Brak and Essam there are forced walk portions at the beginning and at the end of the walks, which can hence be omitted. There is also a typo there: the definition of v′_{n}^{f} must be (t − m, y + 2(n − 1) + m).

Proof of Proposition. It is well-known that configurations of vicious walkers are in bijection with so-called semistandard tableaux. By definition, a semistandard tableau is an array of integers in which entries are weakly increasing along rows and strictly increasing along columns. Figure 5 shows three examples.

To explain the bijection, let us first consider the watermelon configurations in the statement of the proposition (this is the first set of families of vicious walkers in the statement of the proposition). An example for n = 4, t = 12, y = 2, and ℓ = 3 is shown in the Figure 6.a. Now label down-steps by the x-coordinate of their starting point, so that a step from (a, b) to (a+1, b−1) is labelled by a, see Figure 6. Then, out of the labels of the i-th walk, form the i-th column of the corresponding tableau. If this procedure is applied to the family of vicious walkers in Figure 6.a then the tableau in Figure 5.a is obtained. It is not difficult to see that the resulting array of numbers is always a semistandard tableau. In fact, the entries are trivially strictly increasing along columns, and they are weakly increasing along rows because the walks do not touch each other. Moreover, the restriction that no walker may run below the x-axis translates into the condition that the entries in the i-th row of the corresponding

1 2 2 6 4 6 6 7 6 7 7 8 7 8 9 10 9 9 11 11  3 3 5 6 4 6 6 7 6 7 9 9 10 11 10 12 12  2 2 4 5 3 5 5 6 5 6 8 8 9 10 9 11 11

a.  b.  c.

Semistandard tableaux

Figure 5

tableau are at least 2i − 1. Finally, any contact of the first walker with the x-axis (except the one in (0, 0)) produces an entry in the first column which is exactly equal to its lower bound. (In the tableau in the Figure 5.a these are the entries 1, 7 and 9.)

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 1; 4; 6; 7; 9; 2; 6; 7; 8; 9; 2; 6; 7; 9; 11; 6; 7; 8; 10; 11; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 2; 3; 5; 8; 9; 2; 5; 6; 9; 11; 4; 5; 8; 10; 11; 5; 6]

a. b.

Corresponding vicious walkers

Figure 6

Thus, the first set of families of vicious walkers in the statement of the proposition is in bijection with semistandard tableaux with n columns of length (t − y)/2, with the entries in row i at least 2i − 1 and at most t − 1, i = 1, 2, …, (t − y)/2, and with exactly ℓ entries in the first column which are equal to their respective lower bound.

If we apply this same translation to the second set of families of vicious walkers in the statement of the proposition, then we see that these are in bijection with semistandard tableaux with n columns, the first n − 1 of them of length (t − y)/2, the last of length (t − y − 2ℓ)/2, with the entries in row i being at least 2i − 1 and at most t − 1, i = 1, 2, …, (t − y)/2, and with the entries in the last column being at most t − ℓ − 2. Figure 5.c shows the result when this translation is applied to the family of vicious walkers in Figure 6.b.

It is now our task to construct a bijection between the latter two sets of tableaux. We start with a tableau from the first set (of which an example is shown in Figure 5.a). The construction makes use of a modified form of jeu de taquin from [29, 42, 43, 44]. We start with the bottom-most entry in the first column which is equal to its lower bound. (In Figure 5.a this is the entry 9 in the first column.) Let us call it the “special entry,” and denote it by s. Now we move s to the right/bottom by the following procedure, denoted by (JT):

(JT) Compare the special entry s with its right neighbour, x say (if there is no right neighbour, then, by convention, we set x = ∞), and its bottom neighbour, y say (if there is no bottom neighbour, then, by convention, we set y = ∞), see (5.1). If there is no right or bottom neighbour, then stop.

If not, then we have the following situation,

\begin{matrix}s & x \\ y \end{matrix} ,  (5.1)

where at least on of x and y is not ∞. If x ≥ y − 1 then do the move

\begin{matrix}y − 1 & x \\ s \end{matrix} .  (5.2)

If x + 1 < y then do the move

\begin{matrix}x + 1 & s \\ y \end{matrix} .  (5.3)

Repeat (JT).

For example, if we apply this algorithm to the tableau in Figure 5.a, the special entry being the 9 in the first column, then we obtain the tableau in Figure 7. (In this case it is only movements of type (5.3) that are applied.) Clearly, after this algorithm has terminated, the special entry will have ended up in the bottom-right corner (as it does in this example). We now remove the special entry (the 9 in the bottom-right corner in our example).

Next, the same algorithm is applied to the (now) bottom-most entry in the first column which is equal to its lower bound. (In Figure 7 this is the entry 7 in the first column.) Since successive jeu de taquin paths cannot cross each other (see [44, Fig. 9] and the accompanying explanations for a detailed argument), this entry must again

1 2 2 6 4 6 6 7 6 7 7 8 7 8 9 10 10 12 12 9_{Figure 7}

end up in the bottom of the last column. Subsequently, we remove it. This procedure is repeated until there is no entry in the first column which is equal to its lower bound. (The final result when this procedure is applied to the tableau in Figure 5.a is the tableau in Figure 5.b.)

Now, what do we obtain in the end? It is easy to see that after each movement of type (5.2) or (5.3) the entries are weakly increasing along rows and strictly increasing along columns, if we ignore the special entry. Thus, we will have obtained a semistandard tableau with n columns, out of which all of them have length (t − y)/2 except for the last, which will be by ℓ shorter. Furthermore, all entries will be at most t (this is due to the fact that at most once 1 is added to an entry by performing a movement of type (5.3)), and all entries in the i-th row will now be strictly larger than 2i − 1. Finally, since originally the entry in row i in the last column is at most (t+y+2i−2)/2 due to strict increase of entries along columns, and since whenever an entry (other than the special entry) is moved upward (which is only possible through a movement of type (5.2)) it shrinks by 1, the entries in the last column will in the end be at most t−ℓ−1. Clearly, if we subtract 1 from all the entries of such a tableau, we obtain a tableau from the second set of tableaux. (In our running example, after subtracting 1 from all the entries in the tableau in Figure 5.b we obtain the tableau in Figure 5.c.)

We claim that this is a bijection between the sets of tableaux under consideration. In order to see this, we have to construct the inverse mapping. In fact, every single step can be inverted. We would start with a tableau from the second set, add 1 to all the entries, place an entry s (whose value will be determined later) immediately below the bottom-most entry in the last column of the tableau, and then apply the following “inverse” jeu de taquin, denoted by (JT*):

(JT*) Call s the special entry.

If the special entry s is located in the first row and column, then stop.

If not, then we have the following situation,

\begin{aligned}& y \\ x & s \end{aligned} ,

where one of x or y could also be absent. (If y is actually not there, then by convention we set y = −∞.) We denote the number of the row in which s is located by i.

If x is actually not there and y + 1 ≤ 2i − 1, then stop. Otherwise, and also if x ≤ y + 1, then do the move

\begin{aligned}& s \\ x & y + 1 \end{aligned} .  (5.4)

If x − 1 > y then do the move

\begin{aligned}& y \\ s & x − 1 \end{aligned} .  (5.5)

Repeat (JT*).

Suppose that the special entry ended up in row i. Then we now set s = 2i − 1. Subsequently, this procedure is repeated until the complete ((t − y)/2) × n rectangle is filled. We leave it to the reader to check that this yields indeed the desired inverse mapping. □

Remark. Brak and Essam have also a variant of Proposition 6 in [6, Cor. 2]. It states that the number of families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, and where ℓ of the contacts of the first walk with the x-axis (excluding (0, 0)) are marked, is the same as the number of families of n vicious walkers, the i-th starting at (0, 2i−2) and ending at (t, y+2i−2), i = 1, 2, …, n−1, the n-th walk running from (0, 2n − 2) to (t, y + 2n + 2ℓ − 2), none of them running below the x-axis. Again, they prove it by determinant manipulations and pose the problem of finding a bijective proof. Such a bijective proof can be provided in the same manner as the one that we found for Proposition 6. First, one translates both sets of walk families into sets of semistandard tableaux in the same manner as before. The first set translates into semistandard tableaux with n columns of length (t−y)/2, with the entries in row i at least 2i − 1 and at most t − 1, i = 1, 2, …, (t − y)/2, and with exactly ℓ entries in the first column which are equal to its lower bound and which are marked. The second set translates into semistandard tableaux with n columns, the first n − 1 of them of length (t − y)/2, the last of length (t − y − 2ℓ)/2, with the entries in row i being at least 2i − 1 and at most t − 1, i = 1, 2, …, (t − y)/2. The bijection of the proof of Proposition 6 then becomes a bijection between the latter two sets of tableaux when one replaces the modified jeu de taquin (JT) and (JT*) by ordinary jeu de taquin (as for example explained in [58]; i.e., nothing is subtracted from or added to x and y in (5.2), (5.3), (5.4), (5.5); furthermore the condition x ≤ y + 1 has to be replaced by x ≤ y everywhere, and x − 1 > y has to be replaced by x > y everywhere, as well as the stopping rule in (JT*) has to be modified to the extent that y + 1 ≤ 2i − 1 has to be replaced by y < 2i − 1).

6. Exact formulas for the partition function for watermelons of arbitrary deviation. This section is devoted to the derivation of exact formulas for the partition function Z_{t}^{(n)}(y; κ) for families of n vicious walkers, the i-th starting at (0, 2i−2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, as defined in (1.1). The main result is Theorem 8, which expresses the partition function in terms of a double sum. It extends Theorem 4 to watermelon configurations of an arbitrary (but fixed) deviation. By applying hypergeometric summation and transformation formulas to this double sum, we are also able to provide alternative expressions for Z_{t}^{(n)}(y; κ), special cases of which having been given earlier by Brak and Essam (private communication).

Our starting point is Proposition 6. We apply the Lindström–Gessel–Viennot formula (3.2) to the second set of vicious walkers in the proposition in order to obtain a determinant for the number of watermelons of deviation y and exactly ℓ + 1 contacts with the x-axis. The most useful determinant is obtained if we first prepend 2i − 2 up-steps to the i-th walk (analogously to what we did in the proof of Proposition 3), so that we obtain families of n vicious walkers, the i-th starting at (−2i + 2, 0) and ending at (t, y + 2i − 2), i = 1, 2, …, n − 1, the n-th walker running from (−2n + 2, 0) to (t − ℓ − 1, y + 2n + ℓ − 3), none of them running below the x-axis. Again, it is clear that the prepended walk portions are forced, and, hence, the number of the latter families of walkers are the same as the number of families in the second set of walkers in Proposition 6. If we apply the Lindström–Gessel–Viennot formula to the modified families of walkers, then we obtain

det_{1≤i,j≤n} ( \begin{matrix}\frac{y+2i−1}{\frac{t+y}{2} +i+j−1} \binom{t+2j−2}{\frac{t+y}{2} +i+j−2} & 1 ≤ i ≤ n − 1 \\ \frac{y+2n+ℓ−2}{\frac{t+y}{2} +n+j−2} \binom{t+2j−ℓ−3}{\frac{t+y}{2} +n+j−3} & i = n \end{matrix} ) ,  (6.1)

where we used (2.3) to compute the number of walks with given starting and end point, which do not pass below the x-axis.

As it turns out, this determinant can be simplified to a single sum. We state the corresponding result in the lemma below.

Lemma 7. Let t and y be non-negative integers with t ≡ y (mod 2). Then the number of families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, and where the first walk has ℓ + 1 contacts with the x-axis (including its starting point (0, 0)) is equal to

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

× ∑_{k=0}^{n−1}(−1)^{n−k−1} \frac{(y + 2n + ℓ − 2) (t + 2k − ℓ − 1)! (\frac{t−y}{2} + k)!}{(t + 2k)! (\frac{t−y}{2} + k − n − ℓ + 1)! k! (n − k − 1)!}. (6.2)

Proof. We expand the determinant (6.1) along the last row. Thus we obtain

∑_{k=1}^{n}(−1)^{n+k} \frac{y + 2n + ℓ − 2}{\frac{t+y}{2} + n + k − 2}\binom{t + 2k − ℓ − 3}{\frac{t+y}{2} + n + k − 3}M_{k},

where M_{k} is the minor of (6.1) where the last row and the k-th column has been deleted. This minor is easily evaluated by means of [45, Theorem 26, (3.13)] with A = 1 − y, B = 2, and L_{i} = i + χ(i ≥ k) + \frac{t+y}{2} − 1, where χ(A) = 1 if A is true and χ(A) = 0 otherwise. After some simplification, and after replacing k by k + 1, one obtains (6.2). □

The preceding lemma provides us with a workable expression for the number of watermelon configurations with a given number of contacts with the x-axis. We will use it now to derive several expressions for the partition function Z_{t}^{(n)}(y; κ). The first of those will be the one which is most suited for studying the asymptotic behaviour of the partition function, and for the mean number of contacts, which we will do in Sections 7 and 8, respectively.

Theorem 8. Let t and y be non-negative integers with t ≡ y (mod 2). The partition function Z_{t}^{(n)}(y; κ) for families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, where the weight of a walker configuration P is defined as κ^{c(P)} with c(P) denoting the number of contacts of the walkers with the x-axis, is given by

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

× ∑_{ℓ=0}^{(t−y)/2} ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}\binom{y + 2k − 2}{2k}\binom{t − ℓ − 1}{\frac{t−y}{2} − ℓ − k}

· \binom{y + ℓ + 2n − 2}{2n − 2k − 1}\frac{(\frac{t+y}{2} )_{k} (2n − 2k − 1)! (2k)!}{(\frac{t−y}{2} + n − k)_{k}}κ^{ℓ+1}. (6.3)

Remark. In the case n = 1 the product in (6.3) is empty and has to be interpreted as 1. Moreover, because of the binomial coefficient \binom{n−1}{k} in the summand, the sum over k collapses to just one term, the term for k = 0.

Proof. Clearly, the partition function Z_{t}^{(n)}(y; κ) is equal to

∑_{ℓ=0}^{(t−y)/2} N_{t}^{(n)}(y; ℓ)κ^{ℓ+1},  (6.4)

where N_{t}^{(n)}(y; ℓ) is the expression in (6.2). We write the sum in (6.2) in hypergeometric notation, thus obtaining

(−1)^{n+1} \frac{(y + 2n + ℓ − 2) (t − ℓ − 1)! (\frac{t−y}{2} )!}{(n − 1)! t! (\frac{t−y}{2} − n − ℓ + 1)!}

×_{4}F_{3}[ \begin{matrix}1 + \frac{t}{2} − \frac{y}{2} , −\frac{ℓ}{2} + \frac{t}{2}, \frac{1}{2} − \frac{ℓ}{2} + \frac{t}{2}, 1 − n \\ 1 + \frac{t}{2}, \frac{1}{2} + \frac{t}{2}, 2 − ℓ − n + \frac{t}{2} − \frac{y}{2} \end{matrix} ; 1] .

To the _{4}F_{3}-series we apply one of the balanced (which, by definition, means that the sum of the denominator parameters exceeds the sum of the numerator parameters by 1) _{4}F_{3} transformation formulas due to Whipple (cf. [25, Appendix (III.16), q ↑ 1])

4F_{3}[ \begin{matrix}a, b, c, −N \\ e, f, 1 + a + b + c − e − f − N \end{matrix} ; 1]

= \frac{(a)_{N} (−a − b + e + f)_{N} (−a − c + e + f)_{N}}{(e)_{N} (f)_{N} (−a − b − c + e + f)_{N}}

×_{4}F_{3}[ \begin{matrix}−N, −a + e, −a + f, −a − b − c + e + f \\ −a − b + e + f, −a − c + e + f, 1 − a − N \end{matrix} ; 1] , (6.5)

where N is a non-negative integer. Thus we obtain

\frac{(y + 2n + ℓ − 2) (n)_{t−n−ℓ} (t + 2n − 1)_{1−n− \frac{t}{2} − \frac{y}{2}} (y + ℓ)_{2n−2}}{(\frac{t−y}{2} − ℓ)!}

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

for the sum in (6.2). If we substitute this back in (6.4), then we obtain the claimed expression after some manipulation. □

Remark. This theorem generalizes Theorem 4 to watermelon configurations of arbitrary (fixed) deviation. Indeed, if we set y = 0 in Theorem 8, then, because of the binomial coefficient \binom{y+2k−2}{2k} appearing in the summand in (6.3), the only summands which are nonzero in (6.3) are the ones with k = 0.

As corollaries of Lemma 7 (which via (6.5) is equivalent to Theorem 8), we are able to derive remarkable simple alternative expressions for the partition function Z_{t}^{(n)}(y; κ) in terms of single sums. (These expressions however seem to be less suited for asymptotic considerations.) We start with an expansion of the partition function around κ = 1.

Theorem 9. With the same assumptions as in Theorem 8, the partition function Z_{t}^{(n)}(y; κ) is equal to

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

× ∑_{h=0}^{(t−y)/2} \binom{n + h − 1}{n − 1}\frac{(y + 2n + 2h − 1) (y + 2n + h − 2)!}{(y + n + h − 1)! (\frac{t+y}{2} + 2n + h − 1)! (\frac{t−y}{2} − h)!}κ(κ − 1)^{h}. (6.6)

Proof. Again, by Lemma 7, the partition function Z_{t}^{(n)}(y; κ) is equal to (6.4), with N_{t}^{(n)}(y; ℓ) the expression in (6.2). We write κ^{ℓ+1} = κ ∑_{h=0}^{ℓ} \binom{ℓ}{h}(κ − 1)^{h}, and substitute this in (6.4). Thus we obtain

Π_{t}^{(n)}(y) ∑_{ℓ=0}^{(t−y)/2} ∑_{k=0}^{n−1}(−1)^{n−k−1} \frac{(y + 2n + ℓ − 2) (t + 2k − ℓ − 1)! (\frac{t−y}{2} + k)!}{(t + 2k)! (\frac{t−y}{2} + k − n − ℓ + 1)! k! (n − k − 1)!}

· κ ∑_{h=0}^{ℓ} \binom{ℓ}{h}(κ − 1)^{h},

where Π_{t}^{(n)}(y) is the product in the first line of (6.2). Now we interchange summations, so that the sum over ℓ becomes the inner-most sum and the sum over h becomes the outer-most sum, and we convert the sum over ℓ to hypergeometric notation. This yields

Π_{t}^{(n)}(y)\frac{κ}{(n − 1)!} ∑_{h=0}^{(t−y)/2} ∑_{k=0}^{n−1}(−1)^{n−k−1}\binom{n − 1}{k}

· \frac{(t + 2k − h − 1)! (\frac{t−y}{2} + k)!}{(t + 2k)! (\frac{t−y}{2} + k − n − h + 1)!}(κ − 1)^{h}

· ((y + 2n − 3)_{2}F_{1}[ \begin{matrix}h + 1, −\frac{t}{2} + \frac{y}{2} − k + n + h − 1 \\ −t − 2k + h + 1 \end{matrix} ; 1]

+ (h + 1)_{2}F_{1}[ \begin{matrix}h + 2, −\frac{t}{2} + \frac{y}{2} − k + n + h − 1 \\ −t − 2k + h + 1 \end{matrix} ; 1] ).

Both _{2}F_{1}-series can be evaluated by means of the Chu–Vandermonde summation formula (cf. [61, (1.7.7); Appendix (III.4)])

2F_{1}[ \begin{matrix}a, −N \\ c \end{matrix} ; 1] = \frac{(c − a)_{N}}{(c)_{N}} ,  (6.7)

where N is a non-negative integer. The result is simplified, and the sum over k is written in hypergeometric notation. This gives the expression

Π_{t}^{(n)}(y)\frac{κ}{(n − 1)!} ∑_{h=0}^{(t−y)/2}(−1)^{n−1} \frac{(y + 2n + 2h − 1) (\frac{t+y}{2} + n − 1)! (\frac{t−y}{2} )!}{(\frac{t+y}{2} + n + h)! (\frac{t−y}{2} − n − h + 1)!}(κ − 1)^{h}

·_{3}F_{2}[ \begin{matrix}\frac{t}{2} + \frac{y}{2} + n, \frac{t}{2} − \frac{y}{2} + 1, 1 − n \\ \frac{t}{2} + \frac{y}{2} + n + h + 1, \frac{t}{2} − \frac{y}{2} − n − h + 2 \end{matrix} ; 1] .

The _{3}F_{2}-series is balanced and can therefore be evaluated by means of the Pfaff– Saalschütz summation formula (cf. [61, (2.3.1.3); Appendix (III.2)])

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

where N is a non-negative integer. Subsequent simplification then leads to the claimed expression (6.6). □

Remarks. (1) The coefficient of κ(κ − 1)^{h} in (6.6) has a combinatorial interpretation in terms of watermelon configurations, the i-th walker of the configuration running from (0, 2i − 2) to (t, y + 2i − 2), i = 1, 2, …, n, but never below the xaxis, where contacts with the x-axis other than (0, 0) can be marked or not. It is an immediate result of the comparison of (6.6) with the definition of Z_{t}^{(n)}(y; κ). In this definition, we replaced κ^{ℓ+1} by κ ∑_{h=0}^{ℓ} \binom{ℓ}{h}(κ − 1)^{h}. Hence, the coefficient of κ(κ−1)^{h} in (6.6) counts watermelon configurations as above where exactly h contacts other than (0, 0) are marked.

(2) It is also possible to prove Theorem 9 in the same (automated) fashion as Theorem 4, i.e., by starting with the Lindström–Gessel–Viennot determinant (3.4), and then arguing by induction, which one would base on the condensation formula (4.2), the verification of the binomial summations that one has to establish on the way being accomplished by the Gosper–Zeilberger algorithm.

The sum in (6.6) does not simplify in general. In fact, when written in hypergeometric terms, it turns out to be a _{4}F_{3}-series,

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

(6.8)

This is a balanced _{4}F_{3}-series, and there are many identities known for balanced _{4}F_{3}- series, but there is no summation formula available that would apply in full generality. However, there are two cases where summation formulas are available, namely if κ = 1 (trivially), and if κ = 2. The result corresponding to κ = 1, giving the total number of the watermelon configurations that we consider in this section (and the subsequent ones), has been previously obtained by the author, Guttmann and Viennot in [46, Theorem 6]. In fact, in Theorem 6 of [46] it is shown how to derive a more general result which is valid for star configurations.^{9} The result corresponding to κ = 2 has been previously obtained by Ciucu and the author in [12, Theorem 1.4] in an equivalent form,^{10} and, in the case y = 0, independently by Owczarek, Essam and Brak in [52, Eq. (4.45)]. The proof that we give below is independent from the proofs in the papers mentioned.

Corollary 10. Let t and y be non-negative integers with t ≡ y (mod 2). Then the total number Z_{t}^{(n)}(y; 1) of families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis, is equal to

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

already in [41, Theorem 7]. multiplicative constant.

9What is shown in [46] is that the result for star configurations is, in equivalent form, part of the folklore of combinatorics and representation theory of symplectic groups. A weighted generalization of this result, in which each path configuration is assigned a certain q-weight, had been proven

10The combinatorial objects that are studied in [12] are rhombus tilings of regions composed of equilateral unit triangles. There is a standard bijection between such tilings and families of nonintersecting lattice paths, which is, for example, explained in Section 2 of [12], see Figures 2.1, 2.2, 2.3(a) in that paper. In the particular case addressed by Theorem 1.4 of [12], a 45^{∘} rotation turns these non-intersecting lattice paths into our vicious walkers. Under these transformations, the weight for rhombus tilings defined in [12] becomes our contact weight for vicious walkers, up to a

The partition function Z_{t}^{(n)}(y; 2) for these families of vicious walkers is equal to

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

Proof. The claim (6.9) is immediately obvious once we set κ = 1 in (6.6).

For proving the second claim, we set κ = 2 in (6.6) and write the sum in (6.6) in hypergeometric notation (equivalently, we set κ = 2 in (6.8)). Thus we see that this sum is equal to

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

The_{4}F_{3}-series can be evaluated by means of the summation formula (cf. [61, (2.3.4.6); Appendix (III.10)])

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

Substitution of the result in (6.6) then leads to the claimed expression after some simplification. □

Our next result provides an alternative expression for Z_{t}^{(n)}(y; κ) in form of an infinite series, which resembles the one in Corollary 5 for the y = 0 case. Again, the corresponding formula is only valid for κ < 2. As we are going to show, it follows readily from the formula in Theorem 9 by applying another well-known hypergeometric transformation formula. Moreover, by the same techniques we can also obtain a similar expression which is valid for κ > 2. We presume that, in analogy to the analysis in [52], these expressions will be the right starting point in order to carry out a scaling analysis of Z_{t}^{(n)}(y; κ) near the critical point κ = 2.

Theorem 11. Under the assumptions of Theorem 8, the partition function Z_{t}^{(n)}(y; κ) is equal to

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

× \frac{(2 − κ)}{κ^{2n+y−1}} ∑_{h=0}^{∞} \frac{(y + 2n + 2h − 1)! (\frac{t+y}{2} + n + h − 1)!}{h! (y + n + h − 1)! (\frac{t+y}{2} + 2n + h − 1)!} (\frac{κ − 1}{κ^{2}})^{h} (6.11)

if 2(\sqrt{2} − 1) < κ < 2, and it is equal to

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

× (\frac{1}{κ^{2n+y−1}} ∑_{h=0}^{∞} \frac{(y + 2n + 2h − 1)! (\frac{t+y}{2} + n + h − 1)!}{(\frac{t+y}{2} + 2n + h − 1)! (y + n + h − 1)! h!} (\frac{κ − 1}{κ^{2}})^{h}

+ \frac{κ^{2n+t−1}}{(κ − 1)^{\frac{t+y}{2} +2n−1}} ∑_{h=0}^{n−1} \frac{(\frac{t+y}{2} + 2n − h − 2)! (\frac{t−y}{2} + n − h − 1)!}{h! (n − h − 1)! (t + 2n − 2h − 2)!} (\frac{1 − κ}{κ^{2}})^{h} )

(6.12)

if κ > 2.

Proof. We work with the expression (6.6) for the partition function Z_{t}^{(n)}(y; κ). In hypergeometric notation, the sum in (6.6) is equal to (6.8).

Now let first κ < 2. Then to the _{4}F_{3}-series in (6.8) we apply the quadratic transformation formula (cf. [2, Ex. 6, p. 97, reversed])

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

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

which is valid provided |z| < 1 and |4z/(1 − z)^{2}| < 1. Thus, as long as 2(\sqrt{2} − 1) < κ < 2, the sum in (6.6) is equal to

\frac{(2 − κ)}{κ^{y+2n−1}} \frac{(y + 2n − 1)!}{(\frac{t−y}{2} )! (\frac{t+y}{2} + 2n − 1)! (y + n − 1)!}

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

This expression is now substituted back in (6.6). Some simplification then yields the expression (6.11).

Next we address the case κ > 2. Clearly, we cannot follow the same line of argument because we would not be allowed to apply (6.13) because of |1 − κ| > 1. Instead, we start with the expression

lim_{ε_{1}→0}_{ε_{2}→0} \frac{κ (κ − 1)^{(t−y)/2} (n)_{(t−y)/2} (2n + t − 1)_{(y−t)/2}}{(\frac{t−y}{2} )! (\frac{t+y}{2} + n − 1)!}

×_{4}F_{3}[ \begin{matrix}1 − 2n − t, \frac{3}{2} − n − \frac{t}{2}, 1 − n − \frac{t}{2} − \frac{y}{2} + ε_{2}, −\frac{t}{2} + \frac{y}{2} + ε_{1} \\ \frac{1}{2} − n − \frac{t}{2}, 1 − n − \frac{t}{2} + \frac{y}{2} − ε_{2}, 2 − 2n − \frac{t}{2} − \frac{y}{2} − ε_{1} \end{matrix} ; \frac{1}{1 − κ}]

= lim_{ε_{1}→0}_{ε_{2}→0} \frac{κ (κ − 1)^{(t−y)/2} (n)_{(t−y)/2} (2n + t − 1)_{(y−t)/2}}{(\frac{t−y}{2} )! (\frac{t+y}{2} + n − 1)!}

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

· \frac{(1 − n − \frac{t}{2} − \frac{y}{2} + ε_{2})_{k} (−\frac{t}{2} + \frac{y}{2} + ε_{1})_{k}}{(1 − n − \frac{t}{2} + \frac{y}{2} − ε_{2})_{k} (2 − 2n − \frac{t}{2} − \frac{y}{2} − ε_{1})_{k}} (\frac{1}{1 − κ})^{k} . (6.14)

We split the sum over k into the three ranges 0 ≤ k ≤ \frac{t−y}{2} , \frac{t−y}{2} +1 ≤ k ≤ \frac{t+y}{2} +2n−2, and \frac{t+y}{2} + 2n − 1 ≤ k, and then we perform the limit ε_{1} → 0. Thereby each summand in the range \frac{t−y}{2} + 1 ≤ k ≤ \frac{t+y}{2} + 2n − 2 vanishes identically. Thus, upon writing the sum over the range \frac{t+y}{2} + 2n − 1 ≤ k in hypergeometric notation, the expression (6.14) becomes, after also performing the limit ε_{2} → 0,

\frac{κ (κ − 1)^{(t−y)/2} (n)_{(t−y)/2} (2n + t − 1)_{(y−t)/2}}{(\frac{t−y}{2} )! (\frac{t+y}{2} + n − 1)!} ∑_{k=0}^{(t−y)/2} \frac{(1 − 2n − t + 2k)}{(1 − 2n − t)}

· \frac{(1 − 2n − t)_{k} (1 − n − \frac{t}{2} − \frac{y}{2} )_{k} (−\frac{t}{2} + \frac{y}{2} )_{k}}{k! (1 − n − \frac{t}{2} + \frac{y}{2} )_{k} (2 − 2n − \frac{t}{2} − \frac{y}{2} )_{k}} (\frac{1}{1 − κ})^{k}

− \frac{κ}{(κ − 1)^{y+2n−1}} \frac{(\frac{t−y}{2} + 1)_{y+2n−2} (\frac{t+y}{2} + 2n − 1)_{1− \frac{t}{2} + \frac{y}{2}}}{(\frac{t+y}{2} + 2n − 1)! (y + n − 1)!}

×_{4}F_{3}[ \begin{matrix}−1 + 2n + y, \frac{1}{2} + n + \frac{y}{2} , n, −\frac{t}{2} + \frac{y}{2} \\ −\frac{1}{2} + n + \frac{y}{2} , n + y, 2n + \frac{t}{2} + \frac{y}{2} \end{matrix} ; \frac{1}{1 − κ}] . (6.15)

As it turns out, the first sum in this expression is exactly the sum in (6.6) (which is seen by replacing h by \frac{t−y}{2} − k in the sum in (6.6)). Therefore, if we equate (6.14) and (6.15), we see that the sum in (6.6) is equal to

\frac{κ}{(κ − 1)^{y+2n−1}} \frac{(y + 2n − 1)!}{(\frac{t−y}{2} )! (\frac{t+y}{2} + 2n − 1)! (y + n − 1)!}

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

+ lim_{ε_{1}→0}_{ε_{2}→0} \frac{κ (κ − 1)^{(t−y)/2} (n)_{(t−y)/2} (2n + t − 1)_{(y−t)/2}}{(\frac{t−y}{2} )! (\frac{t+y}{2} + n − 1)!}

×_{4}F_{3}[ \begin{matrix}1 − 2n − t, \frac{3}{2} − n − \frac{t}{2}, 1 − n − \frac{t}{2} − \frac{y}{2} + ε_{2}, −\frac{t}{2} + \frac{y}{2} + ε_{1} \\ \frac{1}{2} − n − \frac{t}{2}, 1 − n − \frac{t}{2} + \frac{y}{2} − ε_{2}, 2 − 2n − \frac{t}{2} − \frac{y}{2} − ε_{1} \end{matrix} ; \frac{1}{1 − κ}] .

Now we apply the transformation formula (6.13) to both _{4}F_{3}-series. Subsequently we perform the limit in the second term, and we simplify the resulting expressions. After this is substituted back in (6.6), this yields exactly the expression (6.12). □

7. Asymptotic formulas for the partition function for watermelons of arbitrary, but fixed deviation. In this section we embark on the asymptotic analysis of the partition function Z_{t}^{(n)}(y; κ) for families of n vicious walkers, the i-th starting at (0, 2i − 2) and ending at (t, y + 2i − 2), i = 1, 2, …, n, none of them running below the x-axis. Our starting point is the double sum formula for Z_{t}^{(n)}(y; κ) in Theorem 8. It enables us to compute (in principle) full asymptotic expansions for all κ > 0 (see the Remark after the proof). The technique which we employ is singularity analysis. Our analysis reveals a phase transition at κ = 2. We present the first term in the corresponding asymptotic expansions in Theorem 12 below. Previous asymptotic results for y = 0 were found by Owczarek, Essam and Brak in [52, Eq. (4.58)], who gave predictions for the order of magnitude of the partition function Z_{2r}^{(n)}(0; κ) as r tends to ∞. Our results confirm their predictions, but make them at the same time more precise, as we are also able to provide the multiplicative constants and, as we already mentioned, in fact, full asymptotic expansions.

Theorem 12. Let y be a fixed non-negative integer. As t tends to ∞, the partition function Z_{t}^{(n)}(y; κ) is asymptotically

2^{nt}t^{−n(2n+1)/2}2^{2n^{2}− \frac{n}{2} +1}κ π^{−n/2} (2n − 1)! ∏_{i=0}^{n−2} \frac{i! (y + n + i − 1)!}{(y + 2i)!}

× ( ∑_{h=0}^{n} \begin{matrix}\binom{n}{h} & \binom{y+h−2}{h} \\ ( & {2n \atop h} & ) \end{matrix} \frac{1}{(2 − κ)^{2n−h}} ) (1 + O(t^{−1})) , if κ < 2, (7.1)

it is

2^{nt}t^{−n(2n−1)/2}2^{2n^{2}− \frac{3}{2} n+1}π^{−n/2} ∏_{i=0}^{n−1} \frac{i! (y + n + i − 1)!}{(y + 2i)!} (1 + O(t^{−1})) , if κ = 2,

(7.2)

and it is

(\frac{2^{n−1}κ}{\sqrt{κ − 1}})^{t} t^{−(n−1)(2n−1)/2} \frac{2^{(n−1)(4n−5)/2}κ(κ − 2)^{2n−1}}{π^{(n−1)/2}(κ − 1)^{\frac{y}{2} +2n−1}}

× ∏_{i=0}^{n−2} \frac{i! (y + n + i − 1)!}{(y + 2i)!} (1 + O(t^{−1})) , if κ > 2. (7.3)

Remark. This result shows different asymptotic behaviour for κ < 2, for κ = 2, and for κ > 2. For κ < 2 the order of magnitude of the partition function is 2^{nt}t^{−n(2n+1)/2} (i.e., the growth rate is 2^{n}, and the critical exponent is n(2n + 1)/2), for κ = 2 it is 2^{nt}t^{−n(2n−1)/2}, and for κ > 2 it is (\frac{2^{n−1}κ}{\sqrt{κ−1}})^{t} t^{−(n−1)(2n−1)/2} (i.e., now the growth rate is not constant anymore, but grows with κ), everything else is constants.

Proof. We want to determine the asymptotic behaviour of (6.3). Clearly, for the product in front of the summation we just have to apply Stirling’s formula. The result is that

\frac{(\frac{t+y}{2} − 1)!}{(\frac{t+y}{2} + 2n − 2)!} ∏_{i=0}^{n−2} \frac{(t + 2i)! i! (y + n + i − 1)!}{(\frac{t+y}{2} + n + i − 1)! (\frac{t−y}{2} + i)! (y + 2i)!}
∼ 2^{(n−1)t}t^{−((n+1)(2n−1))/2}2^{2n^{2}− \frac{5}{2} n+ \frac{3}{2}} π^{(1−n)/2}

× ∏_{i=0}^{n−2} \frac{i! (y + n + i − 1)!}{(y + 2i)!} (1 + O(t^{−1})) (7.4)

as t tends to ∞.

From now on we concentrate on the double sum in (6.3). Let us write t = 2r + y in the sequel. Since y is fixed and the summation index k comes from a bounded range, we may use the estimation

\frac{(\frac{t+y}{2} )k}{(\frac{t−y}{2} + n − k)_{k}} = \frac{(r + y)_{k}}{(r + n − k)_{k}} = 1 + O(r^{−1})  (7.5)

to approximate the double sum by

( ∑_{ℓ=0}^{r} ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}\binom{y + 2k − 2}{2k}\binom{2r + y − ℓ − 1}{r − ℓ − k}

· \binom{y + ℓ + 2n − 2}{2n − 2k − 1} (2n − 2k − 1)! (2k)! κ^{ℓ+1})(1 + O(r^{−1})).

As is well-known, the most convenient method for determining the asymptotic behaviour of a sequence of numbers is singularity analysis as developed by Flajolet and Odlyzko [19] (see [20] for an introduction to that method). This method requires the generating function for the sequence of numbers to be known as a starting point. In our case, this means that we need a compact expression for

∑_{r=0}^{∞} z^{2r+y} ∑_{ℓ=0}^{r} ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}\binom{y + 2k − 2}{2k}\binom{2r + y − ℓ − 1}{r − ℓ − k}

· \binom{y + ℓ + 2n − 2}{2n − 2k − 1} (2n − 2k − 1)! (2k)! κ^{ℓ+1}. (7.6)

We shall make use of the fact that

∑_{r=0}^{∞} \binom{2r + m}{r}x^{r} = \frac{C(x)^{m+1}}{1 − x C(x)^{2}} ,  (7.7)

where C(x) is the generating function (2.8) for Catalan numbers. This identity follows readily from (2.7) by writing the left-hand side of (7.7) as

∑_{r=0}^{∞} \binom{2r + m}{r}x^{r}

= ∑_{r=0}^{∞} (\binom{2r + m}{r} − \binom{2r + m}{r − 1} + \binom{2r + m}{r − 1} − \binom{2r + m}{r − 2} + − ⋯) x^{r}

= C(x)^{m+1} + xC(x)^{m+3} + x^{2}C(x)^{m+5} + · · · .

If we interchange summations in (7.6) so that the sum over r becomes the inner-most sum, and then apply (7.7), then we obtain the expression

∑_{ℓ=0}^{∞} ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}\binom{y + 2k − 2}{2k}\binom{y + ℓ + 2n − 2}{2n − 2k − 1}

· (2n − 2k − 1)! (2k)!\frac{z^{y+2k+2ℓ}C(z^{2})^{y+2k+ℓ}}{1 − z^{2} C(z^{2})^{2}} κ^{ℓ+1}.

Now we write

\binom{y + ℓ + 2n − 2}{2n − 2k − 1} = ∑_{h=0}^{2n−2k−1} \binom{ℓ + h}{h}\binom{y + 2n − h − 3}{2n − 2k − h − 1}  (7.8)

(which follows from the Chu–Vandermonde summation formula (6.7)) and interchange summations so that the sum over ℓ becomes the inner-most sum. Using the binomial theorem and (2.10), we end up with the expression

∑_{k=0}^{n−1} ∑_{h=0}^{2n−2k−1}(−1)^{k}\binom{n − 1}{k}\binom{2n − 2k − 1}{h}\binom{y + 2n − h − 3}{2n − h − 1}

· h! (2n − h − 1)! \frac{2^{h+1}κ}{(2 − κ)^{h+1}} \frac{z^{y+2k}C(z^{2})^{y+2k−1}}{\sqrt{1 − 4z^{2}} (1 + \frac{κ}{2−κ} \sqrt{1 − 4z^{2}})^{h+1}} (7.9)

for the generating function (7.6).

Singularity analysis now allows us to extract the asymptotic behaviour of the coefficient of z^{2r+y} as r tends to ∞ out of the behaviour of the function in z at its singular points. We have to distinguish between three cases: κ < 2, κ = 2, and κ > 2.

Let first κ < 2. Then, in the disk |z| ≤ 1/2, the only singularity of the expression (7.9) is at z = 1/2. For z close to 1/2 we have the singular expansion

\frac{C(z^{2})^{y+2k−1}}{\sqrt{1 − 4z^{2}} (1 + \frac{κ}{2−κ} \sqrt{1 − 4z^{2}})^{h+1}} ∼ (1 − 4z^{2})^{−1/2}2^{y+2k−1} + D + O ((1 − 4z^{2})^{1/2}) ,

(7.10) where D is an explicit constant independent of z, whose value is however without relevance here. The coefficient of x^{m} in (1−4x)^{−1/2} behaves like (4^{m}/\sqrt{πm})(1+O(m^{−1})) as m → ∞. The transfer theorems [20, Theorems 5.4 and 5.5] then imply that the coefficient of z^{2r−2k} in the left-hand side of (7.10) (which is what we need when we want to consider the coefficient of z^{2r+y} in (7.9)) behaves like (2^{2r+y−1}/\sqrt{πr})(1 + O(r^{−1})) as r → ∞. If we substitute this in (7.9), then we obtain that the coefficient of z^{2r+y} in (7.9) is

∑_{k=0}^{n−1} ∑_{h=0}^{2n−2k−1}(−1)^{k}\binom{n − 1}{k}\binom{2n − 2k − 1}{h}\binom{y + 2n − h − 3}{2n − h − 1}

· h! (2n − h − 1)! \frac{2^{2r+y+h}κ}{\sqrt{πr} (2 − κ)^{h+1}} (1 + O(r^{−1}))

as r tends to infinity. We interchange sums and write the (now) inner sum over k in hypergeometric notation. This gives

∑_{h=0}^{2n−1} \binom{2n − 1}{h}\binom{y + 2n − h − 3}{2n − h − 1}

· h! (2n − h − 1)! \frac{2^{2r+y+h}κ}{\sqrt{πr} (2 − κ)^{h+1}}_{2}F_{1} [ \begin{matrix}\frac{1}{2} + \frac{h}{2} − n, 1 + \frac{h}{2} − n \\ \frac{1}{2} − n \end{matrix}; 1] (1 + O(r^{−1})) .

Clearly, the _{2}F_{1}-series can be evaluated by means of the Chu–Vandermonde summation (6.7). As it turns out, it is only non-zero for h ≥ n − 1. After substitution of the result of the evaluation in the above expression, after replacement of h by 2n − h − 1, after taking into account that t = 2r + y, and finally combining the result with (7.4), the claimed result (7.1) follows upon little rearrangement.

If κ = 2, then it suffices to apply Stirling’s formula to the closed form expression (6.10).

Finally let κ > 2. Then, in the disk |z| ≤ 1/2, the “dominant” singularity (i.e., the singularity with least modulus; cf. [20]) is z = \sqrt{κ − 1}/κ. For z → \sqrt{κ − 1}/κ we have

\frac{C(z^{2})^{y+2k−1}}{\sqrt{1 − 4z^{2}} (1 + \frac{κ}{2−κ} \sqrt{1 − 4z^{2}})^{h+1}} ∼ \frac{κ−2}{κ} (−\frac{2(κ−1)}{(κ−2)^{2}})^{h+1} (1 − z^{2} \frac{κ^{2}}{κ−1})^{h+1}^{(\frac{κ}{κ−1})y+2k−1}

∼ \frac{(−1)^{h+1}κ^{y+2k}(κ − 2)^{2h+1}}{2^{h+1} (κ − 1)^{y+2k+h} (1 − z^{2} \frac{κ^{2}}{κ−1})^{h+1}} .(7.11)

The transfer theorems [20, Theorems 5.2, 5.4 and 5.5] imply that the coefficient of z^{2r−2k} in the left-hand side of (7.11) behaves like

(−1)^{h+1} \frac{κ^{y+2k}(κ − 2)^{2h+1}}{2^{h+1} (κ − 1)^{y+2k+h}} (\frac{κ^{2}}{κ − 1})^{r−k} \frac{r^{h}}{h!} (1 + O(r^{−1})) .

Hence, the asymptotically dominating terms result from the summands in (7.9) where h is maximal, i.e., where h = 2n − 1, which, because of the binomial coefficient \binom{2n−2k−1}{h} occurring in (7.9), in turn forces k to be zero. If this is combined with (7.4), and if we again take into account that t = 2r + y, then the claimed result (7.3) follows upon little simplification.

This completes the proof of the theorem. □

Remark. Since Stirling’s formula (see [63, Sec. 12.33]) does in fact provide a full asymptotic expansion for factorials, as well as do the transfer theorems [20, Theorems 5.2, 5.4 and 5.5] provide full asymptotic expansions, the above approach does in fact allow to compute full asymptotic expansions for the partition function Z_{2r}^{(n)}(y; κ) in all three different regions, if needed. The reader should note that, if we want to compute more terms in the asymptotic expansion, we will have to extend the asymptotic expansion (7.5). The most convenient way to do that (for the subsequent generating function computations) is in the form

\frac{(\frac{t+y}{2} )k}{(\frac{t−y}{2} + n − k)_{k}} = \frac{(r + y)_{k}}{(r + n − k)_{k}}

= 1 + \frac{k(y − n + k)}{r + y + k} + \frac{C_{2}}{(r + y + k)_{2}} + ⋯ + \frac{C_{N}}{(r + y + k)_{N}} + O (r^{−N−1}) , (7.12)

with the C_{i}’s appropriate constants independent of r.

8. Exact and asymptotic results for the number of contacts of n vicious walkers. By definition, the mean number of contacts with the wall for families of n vicious walkers, the i-th starting at (0, a_{i}) and ending at (t, e_{i}), none of them running below the x-axis (the wall), is

M_{t}^{(n)}(a → e; κ) := ∑_{ℓ≥1} N_{t}^{(n)}(a → e; ℓ) ℓ κ^{ℓ},

where N_{t}^{(n)}(a → e; ℓ) is the number of these families of vicious walkers with exactly ℓ contacts with the wall. Clearly, we have

M_{t}^{(n)}(a → e; κ) = κ\frac{d}{dκ}Z_{t}^{(n)}(a → e; κ),  (8.1)

with Z_{t}^{(n)}(a → e; κ) the partition function for these vicious walkers as defined in the Introduction. In addition, the normalized mean number of contacts with the wall is defined by

\frac{M_{t}^{(n)}(a → e; κ)}{Z_{t}^{(n)}(a → e; κ)}.  (8.2)

In this section we shall again concentrate on watermelon configurations which start on the wall and have deviation y, i.e., n vicious walkers as above with a = (0, 2, 4, …, 2n − 2) and e = (y, y + 2, y + 4, …, y + 2n − 2), and analyse their (normalized) mean number of contacts. Specializing (8.2) to the above choices of a and e, the quantity that we want to study is

\frac{κ\frac{d}{dκ}Z_{t}^{(n)}(y; κ)}{Z_{t}^{(n)}(y; κ)},  (8.3)

where, as before, Z_{t}^{(n)}(y; κ) denotes the partition function for these watermelon configurations. Let us denote the normalized mean in (8.3) by M̄_{t}^{(n)}(y; κ). We could use any of our formulas for the partition function Z_{t}^{(n)}(y; κ) (such as (6.3) or (6.6)) to find explicit representations of M̄_{t}^{(n)}(y; κ) as a quotient of two sums (double sums in the case of (6.3)).

As was the case for the partition function, also these formulae for the mean number of contacts do not simplify in general, while they do for κ = 1, and if y = 0 also for κ = 2.

Theorem 13. For κ = 1, the normalized mean number of contacts, M̄_{t}^{(n)}(y; 1), is equal to

1 + \frac{n(y + 2n + 1)(t − y)}{(y + n)(t + y + 4n)}.

Proof. The value of the partition function at κ = 1, Z_{t}^{(n)}(y; 1), was already determined in (6.9). For computing the numerator in (8.3), we make use of the formula (6.6). If this formula is differentiated with respect to κ, and subsequently κ is set equal to 1, then it is only two terms in the sum which survive. Some simplification then leads to the claimed formula. □

Whereas there does not seem to exist a “nice” formula for the mean number of contacts for κ = 2 for arbitrary y, there is one if y = 0.

Theorem 14. For y = 0 and κ = 2, the normalized mean number of contacts, M̄_{2r}^{(n)}(0; 2), is equal to

\frac{2^{2r−1}n\binom{2n}{n}}{\binom{2r+2n−2}{r+n−1}} − 2(n − 1).

Proof. Using the representation of the partition function Z_{2r}^{(n)}(0; κ) = Z_{2r}^{(n)}(κ) as given in (4.1), the normalized mean number of contacts is

M̄_{2r}^{(n)}(0; 2) = 2 + \frac{∑_{ℓ=0}^{r−1} \binom{2r−ℓ−2}{r−1}\binom{ℓ+2n−1}{ℓ} ℓ 2^{ℓ+2}}{∑_{ℓ=0}^{r−1} \binom{2r−ℓ−2}{r−1}\binom{ℓ+2n−1}{ℓ}2^{ℓ+2}} .

A comparison of (4.1) and (6.10) shows that we already evaluated (implicitly) the denominator of this expression. Hence, the evaluation of (8.3) will be accomplished once we have evaluated the sum in the numerator. We begin by converting it to hypergeometric notation, and obtain

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

Next we reverse the order of summation and obtain

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

for the numerator. We now apply the contiguous relation

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

Thus, the _{2}F_{1}-series becomes the sum of the two terms

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

Both of the _{2}F_{1}-series can be summed by means of Bailey’s summation formula (cf. [61, (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})}.  (8.4)

Some simplification then yields the claimed formula. □

We now embark on determining the asymptotic behaviour of the normalized mean number of contacts. Predictions on the order of magnitude in the case of two walkers have been already made earlier by Brak, Essam and Owczarek in [8, Sec. 4.4.2]. The next theorem solves the problem for an arbitrary number of walkers, thereby confirming these predictions and, at the same time, making them more precise. Again, our method allows in fact to obtain full asymptotic expansions (see the Remark after the proof of Theorem 12).

Theorem 15. As t tends to ∞, the normalized mean number of contacts M̄_{t}^{(n)}(y; κ) is asymptotically

1 + C + O(t^{−1}), if κ < 2,  (8.5)

where C is the quotient

κ( ∑_{h=0}^{n} \frac{(2n − h)\binom{n}{h}\binom{y+h−2}{h}}{\binom{2n}{h}} \frac{1}{(2 − κ)^{2n−h+1}} )/( ∑_{h=0}^{n} \begin{matrix}\binom{n}{h} & \binom{y+h−2}{h} \\ ( & {2n \atop h} & ) \end{matrix} \frac{1}{(2 − κ)^{2n−h}} ),

(8.6) it is

2^{\frac{1}{2} −2n}n\binom{2n}{n}\sqrt{πt} − 2n − y + 2 + O(t^{−1/2}), if κ = 2,  (8.7)

and it is

\frac{(κ − 2)}{(κ − 1)} \frac{t}{2} + \frac{κ((2 − κ)y + 4n − 2)}{2(κ − 1)(κ − 2)} + 1 + O (t^{−1}) , if κ > 2.

Remark. Thus, for the length of the walks being large, the normalized mean number of contacts is proportional to a constant if κ < 2, it is proportional to the square root of the length of the walks if κ = 2, and it is proportional to the length of the walks if κ > 2.

Proof. We start by observing that Theorem 8 implies that the normalized mean number of contacts M̄_{t}^{(n)}(y; κ) can be rewritten as

M̄_{t}^{(n)}(y; κ) = 1 + \frac{U_{t}^{(n)}(y; κ)}{V_{t}^{(n)}(y; κ)},  (8.8)

where V_{t}^{(n)}(y; κ) is the double sum in (6.3), and where

U_{t}^{(n)}(y; κ) = ∑_{ℓ=0}^{(t−y)/2} ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}\binom{y + 2k − 2}{2k}\binom{t − ℓ − 1}{\frac{t−y}{2} − ℓ − k}

· \binom{y + ℓ + 2n − 2}{2n − 2k − 1}\frac{(\frac{t+y}{2} )_{k} (2n − 2k − 1)! (2k)!}{(\frac{t−y}{2} + n − k)_{k}}ℓ κ^{ℓ+1}.

We already determined the asymptotic behaviour of the denominator of the fraction in (8.8) in the proof of Theorem 12. What we still need is the asymptotic behaviour of the numerator. We attack this problem in the same way as the corresponding problem for the denominator. Here we will also have to use singularity analysis in the case that κ = 2, because there is no closed form result available for the normalized mean number of contacts in that case (as opposed to for the partition function, which allowed us to do the asymptotics for κ = 2 in Theorem 12 by just making use of Stirling’s formula).

Since for the cases κ = 2 and κ > 2 we aim at computing an additional term (beyond the leading term) in the asymptotic expansion, we will have to use the estimation (7.12), with N = 1, as a first step. After the substitution of this in the numerator of the fraction in (8.8), we compute the generating function with the coefficient of z^{t} being the sum in the numerator. To be precise, again writing t = 2r + y, we want to find a compact expression for

∑_{r=0}^{∞} z^{2r+y} ∑_{ℓ=0}^{r} ∑_{k=0}^{n−1}(−1)^{k}\binom{n − 1}{k}\binom{y + 2k − 2}{2k}\binom{2r + y − ℓ − 1}{r − ℓ − k}

· \binom{y + ℓ + 2n − 2}{2n − 2k − 1}(2n − 2k − 1)! (2k)! (1 + \frac{k(y − n + k)}{r + y + k}) ℓ κ^{ℓ+1}. (8.9)

Now we perform the same steps as in the proof of Theorem 12: we interchange summations so that the sum over r becomes the inner-most sum, then sum over r using (7.7) (respectively (2.7) for the additional term), next use (7.8), then interchange summations so that the sum over ℓ becomes the inner sum, and finally evaluate the remaining sum over ℓ by means of the binomial theorem. The result is that our generating function (8.9) turns into

∑_{k=0}^{n−1} ∑_{h=0}^{2n−2k−1}(−1)^{k}\binom{n − 1}{k}\binom{2n − 2k − 1}{h}\binom{y + 2n − h − 3}{2n − h − 1}

· (h + 1)! (2n − h − 1)! \frac{2^{h+2}κ^{2}}{(2 − κ)^{h+2}} \frac{z^{y+2k+2}C(z^{2})^{y+2k}}{\sqrt{1 − 4z^{2}} (1 + \frac{κ}{2−κ} \sqrt{1 − 4z^{2}})^{h+2}} ,

plus a similar term resulting from the fraction k(y − n + k)/(r + y + k) occurring in (8.9).

Now we apply singularity analysis to the function on the right-hand side. The considerations are entirely analogous to the corresponding ones in the proof of Theorem 12, except that here we have to consider one more term in the singular expansion. As it turns out in the end, the additional term k(y − n + k)/(r + y + k) does in fact produce smaller terms as we need. We leave the details to the reader.

If, finally, the obtained results are combined with the corresponding ones for the sum in the denominator of the fraction on right-hand side of (8.8) which were found in the proof of Theorem 12, then after little simplification the claimed asymptotic expressions are obtained. □

Remark. The sums which appear in (8.5) in the case that κ < 2 can be expressed in terms of hypergeometric _{2}F_{1}-series. (The sum in the denominator is a _{2}F_{1}-series, while the sum in the numerator can be written as a sum of two _{2}F_{1}-series.) From there we see that they cannot be simplified, with the exception of a few special cases where _{2}F_{1}-summation formulas are available (such as, for example, (6.7) and (8.4)). For instance, if κ = 1, then the Chu–Vandermonde summation formula (6.7) is applicable. However, in that case it would have been easier to do the asymptotics directly from the closed form expression in Theorem 13.

References

1. D. K. Arrowsmith, P. Mason and J. W. Essam, Vicious walkers, flows and directed percolation, Physica A 177 (1991), 267–272.

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

3. G. D. Birkhoff, Formal theory of irregular difference equations, Acta Math. 54 (1930), 205–246.

4. G. D. Birkhoff and W. J. Trjitzinsky, Analytic theory of singular difference equations, Acta Math. 60 (1932), 1–89.

5. R. Brak and J. W. Essam, Directed compact percolation near a wall: III. Exact results for the mean length and number of contacts, J. Phys. A: Math. Gen. 32 (1999), 355–367.

6. R. Brak and J. W. Essam, Return polynomials for non-intersecting paths above a surface on the directed square lattice, J. Phys. A: Math. Gen. 34 (2001), 10763–10782.

7. R. Brak and J. W. Essam, Bicoloured Dyck paths and the contact polynomial for n non-inter-secting paths in a half-plane lattice, Electron. J. Combin. 10(1) (2003), Article #R35, 18 pages.

8. R. Brak, J. W. Essam and A. L. Owczarek, New results for directed vesicles and chains near an attractive wall, J. Statist. Phys. 93 (1998), 155–192.

9. R. Brak, J. W. Essam and A. L. Owczarek, Exact solution of N directed non-intersecting walks interacting with one or two boundaries, J. Phys. A: Math. Gen. 32 (1999), 2921–2929.

10. A. J. Bray and K. Winkler, Vicious walkers in a potential, J. Phys. A – Math. Gen. 37 (2004), 5493–5501.

11. 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.

12. M. Ciucu and C. Krattenthaler, Enumeration of lozenge tilings of hexagons with cut off corners, J. Combin. Theory Ser. A 100 (2002), 201–231.

13. L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

14. E. Csáki and I. Vincze, On some problems connected with the Galton test, Publ. Math. Inst. Hung. Acad. Sci. 6 (1961), 97–109.

15. O. Engelberg, On some problems concerning a restricted random walk, J. Appl. Probab. 2 (1965), 396–404.

16. J. W. Essam and A. J. Guttmann, Vicious walkers and directed polymer networks in general dimensions, Phys. Review E 52 (1995), 5849–5862.

17. 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.

18. M. E. Fisher, Walks, walls, wetting, and melting, J. Statist. Phys. 34 (1984), 667–729.

19. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), 216–240.

20. P. Flajolet and R. Sedgewick, The average analysis of algorithms: Complex asymptotics and generating functions, Chapters 4 and 5 in the book project “Analytic Combinatorics”, INRIA Res.

Rep. #2026, 1993, available at http://algo.inria.fr/flajolet/Publications/books.html.

21. P. J. Forrester, Probability of survival for vicious walkers near a cliff, J. Phys. A: Math. Gen. 22 (1989), L609–L613.

22. P. J. Forrester, Exact solution of the lock step model of vicious walkers, J. Phys. A: Math. Gen. 23 (1990), 1259–1273.

23. P. J. Forrester, Exact results for vicious walker models of domain walls, J. Phys. A: Math. Gen. 24 (1991), 203–218.

24. P. J. Forrester and T. Nagao, Vicious random walkers and a discretization of Gaussian random matrix ensembles, Nuclear Phys. 620 (2002), 551–585.

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

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

27. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint, 1989, available

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

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

29. I. Goulden and C. Greene, A new tableau representation for supersymmetric Schur functions, J. Algebra 170 (1994), 687–703.

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

31. H.-D. O. F. Gronau, W. Just, W. Schade, P. Scheffler and J. Wojciechowski, Path systems in acyclic directed graphs, Zastos. Mat. 19 (1988), 399–411.

32. A. J. Guttmann, A. L. Owczarek and X. G. Viennot, Vicious walkers and Young tableaux I: Without walls, J. Phys. A – Math. Gen. 31 (1998), 8123–8135.

33. P. John and H. Sachs, Wegesysteme und Linearfaktoren in hexagonalen und quadratischen Systemen, Graphs in research and teaching (Kiel, 1985), Franzbecker, Bad Salzdetfurth, 1985, pp. 85–101.

34. Kanwar Sen, J. L. Jain and J. M. Gupta, Lattice path approach to transient solution of M/M/1 with (0, k) control policy, J. Statist. Plann. Inference 34 (1993), 259–267.

35. S. Karlin and J. L. McGregor, Coincidence properties of birth-and-death processes, Pacific J. Math. 9 (1959), 1109–1140.

36. S. Karlin and J. L. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141–1164.

37. M. Katori and H. Tanemura, Scaling limit of vicious walks and two-matrix model, Phys. Review E 66 (2002), Article 011105, 12 pages.

38. M. Katori and H. Tanemura, Functional central limit theorems for vicious walkers, Stoch. Rep. 75 (2003), 369–390.

39. M. Katori and H. Tanemura, Nonintersecting paths, noncolliding diffusion processes and representation theory, RIMS Kokyuroku 1438 (2005), 83–102.

40. M. Katori, H. Tanemura, T. Nagao and N. Komatsuda, Vicious walk with a wall, noncolliding meanders, and chiral and Bogoliubov–de Gennes random matrices, Phys. Review E 68 (2003), Article 021112.

41. 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.

42. C. Krattenthaler, A bijective proof of the hook-content formula for super Schur functions and a modified jeu de taquin, Electron. J. Combin. 3 (no. 2, “The Foata Festschrift”) (1996), #R14, 24 pp.

43. C. Krattenthaler, An involution principle-free bijective proof of Stanley’s hook-content formula, Discrete Math. Theor. Computer Science 3 (1998), 011–032.

44. C. Krattenthaler, Another involution principle-free bijective proof of Stanley’s hook-content formula, J. Combin. Theory Ser. A 88 (1999), 66–92.

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

46. C. Krattenthaler, A. J. Guttmann and X. G. Viennot, Vicious walkers, friendly walkers and Young tableaux II: with a wall, J. Phys. A: Math. Gen. 33 (2000), 8835–8866.

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

48. S. G. Mohanty, On some generalization of a restricted random walk, Stud. Sci. Math. Hungarica 3 (1968), 225–241.

49. S. G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

50. S. Mukherji and S. M. Bhattacharjee, Reunion and survival of interacting walkers, Phys. Rev. E 48 (1993), 3427–3440, Erratum: Phys. Rev. E 52 (1995), 3301.

51. S. Mukherji and S. M. Bhattacharjee, Reunion of vicious walkers: results from ϵ-expansion, J. Phys. A: Math. Gen. 26 (1993), L1139–L1144.

52. A. L. Owczarek, J. W. Essam and R. Brak, Scaling analysis for the adsorption transition in a watermelon network of n directed non-intersecting walks, J. Statist. Phys. 102 (2001), 997–1017.

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

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

55. M. Rahman and A. Verma, Quadratic transformation formulas for basic hypergeometric series, Trans. Amer. Math. Soc. 335 (1993), 277–302.

56. M. Rubey, Asymptotic analysis of vicious walkers with arbitrary endpoints, preprint, 2002.

57. M. Rubey, Bijections for lattice paths in an arbitrary region, in preparation.

58. B. E. Sagan, The symmetric group, 2nd edition, Graduate Texts in Math., vol. 203, Springer–Verlag, New York, 2001.

59. J. C. Slater, The theory of complex spectra, Phys. Rev. 34 (1929), 1293–1322.

60. J. C. Slater, Quantum theory of matter, 2nd ed., McGraw–Hill, New York, 1968.

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

62. R. A. Sulanke, A determinant for q-counting lattice paths, Discrete Math. 81 (1990), 91–96.

63. E. T. Whittaker and G. N. Watson, A Course of Modern Analysis, 4th edition, Cambridge University Press, Cambridge, 1965.

64. J. Wimp and D. Zeilberger, Resurrecting the asymptotics of linear recurrences, J. Math. Anal. Appl. 111 (1985), 162–176.

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

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

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France.