VICIOUS WALKERS, FRIENDLY WALKERS AND YOUNG TABLEAUX II: WITH A WALL

CHRISTIAN KRATTENTHALER§, ANTHONY J. GUTTMANN†, AND XAVIER G. VIENNOT‡

Abstract. We derive new results for the number of star and watermelon configurations of vicious walkers in the presence of an impenetrable wall by showing that these follow from standard results in the theory of Young tableaux, and combinatorial descriptions of symmetric functions. For the problem of n-friendly walkers, we derive exact asymptotics for the number of stars and watermelons both in the absence of a wall and in the presence of a wall.

1. Introduction

In an earlier paper [12] an expression for the number of star configurations of vicious walkers on a d-dimensional lattice was obtained, and the result for the corresponding number of watermelon configurations was conjectured. Later, in [21] it was shown how certain results from the theory of Young tableaux, and related results in algebraic combinatorics enabled one to readily prove both results.

In this paper, we show how some results from the theory of symmetric functions can be used to prove analogous results for the more difficult case of walkers in the presence of an impenetrable wall. We also give rigorous asymptotic results.

Vicious walkers describes the situation in which two or more walkers arriving at the same lattice site annihilate one another. Accordingly, the only configurations we consider are those in which such contacts are forbidden. Alternatively expressed, we consider mutually self-avoiding networks of lattice walks which also model directed polymer networks. The connection of these vicious walker problems to the 5 and 6 vertex model of statistical mechanics was also discussed in [21].

The problem, together with a number of physical applications, was introduced by Fisher [13]. The general model is one of p random walkers on a d-dimensional lattice who at regular time intervals simultaneously take one step with equal probability in the direction of one of the allowed lattice vectors such that at no time two walkers occupy the same lattice site.

The two standard topologies of interest are that of a star and a watermelon. Consider a directed square lattice, rotated 45^{∘} and augmented by a factor of \sqrt{2}, so that the “unit” vectors on the lattice are (1, 1) and (1, −1). Both configurations consist of p branches of length m (the lattice paths along which the walkers proceed) which start at (0, 0), (0, 2), (0, 4), …, (0, 2p − 2). The watermelon configurations end at (m, k), (m, 2+k), (m, 4+k), …, (m, k+2p−2), for some k. For stars, the end-points of the branches all have x-coordinate equal to m, but the y coordinates are unconstrained, apart from the ordering imposed by the non-crossing condition. Thus if the end-points are (m, e_{1}), (m, e_{2}), (m, e_{3}), ⋯, (m, e_{p}), then e_{1} < e_{2} < e_{3} < ⋯ < e_{p} ≤ 2p − 2 + m.

In the problem considered here, the additional constraint of an impenetrable wall imposes the condition that at no stage may any walker step to a point with negative y-coordinate.

In [12] recurrence relations and the corresponding differential equations for stars and watermelons on the directed square lattice were obtained. In the case of watermelons, a determinantal form was evaluated by standard techniques applied to the determinant. In the case of stars, the results obtained were conjectural, being equivalent to an earlier conjecture [2]. In [21] it was shown how a number of “standard” results in the theory of Young tableaux and partitions lead to a much more intuitive derivation of the above results, and provided a proof of the conjectured results.

In recent months a number of authors [25, 40, 41, 3] have made the fascinating connection between certain properties of two-dimensional vicious walkers and the eigenvalue distribution of certain random matrix ensembles. In [25] a model is introduced which can be considered as a randomly growing Young diagram, or a totally asymmetric one-dimensional exclusion process. (This could be interpreted in the vicious walker model where at each time unit exactly one of the walkers moves. This model occurs already in [13].) It is shown that the appropriately scaled shape fluctuations converge in distribution to the Tracy-Widom distribution of the largest eigenvalue of the Gaussian Unitary Ensemble (GUE). Similarly, in [3] a vicious walker model is considered in which the end-point fluctuations of the top-most walker (in our notation) are considered. In that case the appropriately scaled limiting distribution is that of the largest eigenvalue of another distribution, the Gaussian Orthogonal Ensemble (GOE). Finally in [40, 41] the height distribution of a given point in the substrate of a one-dimensional growth process is considered, and this is generalised to models in the Kardar-Parisi-Zhang (KPZ) universality class [26]. The configurations considered again appear like vicious walkers. Again fluctuations and other properties of the models are found that follow GOE or GUE distributions. Given that Painlevé transcendents underlie the theory of random matrix ensembles, it would be of considerable value, and would undoubtedly add greatly to our understanding of the combinatorial problems we discuss here, if the connection with random matrix theory and Painlevé transcendents could be clarified. An important recent development in this clarification is the the recent paper by Its. et al. [24].

In [22] and [53] two slightly different generalisations of the vicious walker model were introduced, both called the friendly walker model. In [22], the “vicious” constraint is systematically relaxed, so that any two walks (but not more than two) may stay together for up to n lattice sites in a row, but may never swap sides. We refer to this as the n-friendly walker model. In the limit as n → ∞ we obtain the ∞-friendly walker model in which walkers may share an arbitrary number of steps. The Tsuchiya-Katori model [53], by contrast, corresponds to a variant of the ∞-friendly walker model which allows any number of walkers to share any number of bonds, whereas in the Guttmann-Vöge definition [22], only two walkers may share a bond. We subsequently refer to these two models as the TK and GV models respectively. Thus the number of TK friendly walk configurations gives an upper bound on the number of ∞-friendly walk conigurations in the definition of GV. We make use of this observation in subsequent proofs. Any reference to n-friendly walkers assumes the definition given in [22]. Thus, n = 0 corresponds to the vicious walker model described above, and n = 1 to the so-called osculating walker model in which walkers may touch at a vertex, but then must part. (The osculating walker model is an especially intriguing one, as it can be seen as a six-vertex model, cf. [21], and because, with special boundary conditions, it produces famous objects in enumerative combinatorics, alternating sign matrices, cf. [4, 7].)

Only numerical conjectures for exponents were obtained in [22] for the general nfriendly walker model. Here we provide asymptotics for this model, which both prove the earlier conjectures, and makes the earlier results more precise.

In this paper we first re-derive the results of [21] by making use of Schur functions and odd orthogonal characters, which will also be needed in our derivation of the results for watermelons and stars in the presence of a wall. As well as re-deriving results in the absence of a wall, we also develop the asymptotics for the number of such configurations.

We then solve the problem in the presence of a wall, or impenetrable barrier below which the walks may not go. We also give asymptotic results for both stars and watermelons in this case. We then extend these results to m-friendly stars and watermelons in the presence of a wall. The problem of vicious walkers in the presence of a wall has been previously considered by Forrester [14] who set up the determinantal form, but did not reduce it to a product form. We accomplish the reduction by the use of symplectic characters. A recent preprint [5] contains our Theorem 6, with an alternative proof.

The makeup of the paper is as follows. In Appendix A we present and develop the mathematical tools needed for the asymptotics developed in the body of the paper. In Appendix B the two main results on the enumeration of non-intersecting lattice paths are recalled, while Appendix C is devoted to some determinant evaluations. These results will be used throughout the paper. In Section 2 we study stars with fixed endpoints, and in Section 3 stars with arbitrary end-points, in which we develop many of the proofs which will be applied mutatis mutandis in later sections. Sections 4 and 5 cover the same ground as the two preceding sections, but this time in the presence of a wall. In Section 6 we discuss watermelon configurations, and in Section 7 we treat the case of watermelons in the presence of a wall. Section 8 is a short conclusion.

A summary of our results now follows: For the problem of vicious walkers in the absence of a wall we obtain product forms for the number of star configurations with fixed end-points, and also for the total number of stars. For watermelons with given deviation we also derive a product form, but for the total number of watermelons we are only able to find the asymptotic form, and not a product form. By developing the asymptotic form for the total number of vicious stars (and watermelons), as well as that for the total number of ∞-friendly stars (and watermelons) in the TK model we are able to give the asymptotic form for n-friendly stars and watermelons for any n. The number of n-friendly stars is ≍ 2^{mp}m^{−p^{2}/4+p/4} as m (the length of the branches) tends to infinity (see Corollary 5). It must be expected that it is asymptotically c(n)2^{mp}m^{−p^{2}/4+p/4}, where c(n) is a monotonically increasing function of n. Similarly, the number of n-friendly watermelons is ≍ 2^{mp}m^{−p^{2}/2+1/2} as m tends to infinity (see Corollary 13), and it is expected that it is asymptotically f(n)2^{mp}m^{−p^{2}/2+1/2}, where f(n) is a monotonically increasing function of n.

Analogous results for systems of walkers in the presence of a wall are also obtained. For the problem of vicious walkers in the presence of a wall we obtain product forms for the number of star configurations with fixed end-points, and also for the total number of stars. For watermelons with given deviation we also derive a product form, but for the total number of watermelons we are only able to find the asymptotic form, and not a product form. By developing the asymptotic form for the total number of vicious stars (and watermelons) in the presence of a wall, as well as that for the total number of ∞- friendly stars (and watermelons) in the TK model we are able to give the asymptotic form for n-friendly stars and watermelons in the presence of a wall for any n. The number of n-friendly stars in the presence of a wall is ≍ 2^{mp}m^{−p^{2}/2} as m tends to infinity (see Corollary 10), and is expected to be d(n)2^{mp}m^{−p^{2}/2}, where d(n) is a monotonically increasing function of n. Similarly, the number of n-friendly watermelons in the presence of a wall is by ≍ 2^{mp}m^{−3p^{2}/4−p/4+1/2} as m tends to infinity (see Corollary 17), and is expected to be g(n)2^{mp}m^{−3p^{2}/4−p/4+1/2}, where g(n) is a monotonically increasing function of n.

2. Stars with fixed end-points, without a wall.

A typical star configuration is shown in Figure 1. Let e_{1} < e_{2} < ⋯ < e_{p} with e_{i} ≡ m (mod 2), i = 1, 2, …, p. We seek the number of stars with p branches, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), i = 1, 2, …, p. In Figure 1.a an example with p = 4, m = 6, e_{1} = 0, e_{2} = 2, e_{3} = 6, e_{4} = 10 is given.

Theorem 1. The number of such stars is given by:

2^{−\binom{p}{2}} ∏_{i=1}^{p} \frac{(m − i + p)!}{(\frac{m+e_{i}}{2} )! (\frac{m−e_{i}}{2} + p − 1)!} ∏_{1≤i<j≤p}(e_{j} − e_{i}).  (2.1)

Proof. We describe a proof which uses knowledge about Schur functions.

Let λ = (λ_{1}, λ_{2}, …, λ_{m}) be a partition, i.e., a nonincreasing sequence of nonnegative integers. Then the Schur function s_{λ}(x_{1}, x_{2}, …, x_{m}) is defined by (see [35, I, (3.1)] or [16, p. 403, (A.4)])

s_{λ}(x_{1}, x_{2}, …, x_{m}) = \frac{det_{1≤i,j≤m}(x_{j}^{λ_{i}+m−i})}{det_{1≤i,j≤m}(x_{j}^{m−i})}.  (2.2)

It is well-known that a combinatorial description of Schur functions may be given in terms of (semistandard) tableaux. A filling of the cells of the Ferrers diagram of λ with elements of the set {1, 2, … } which is weakly increasing along rows and strictly increasing along columns is called a (semistandard) tableau of shape λ. Figure 1.b shows such a semistandard tableau of shape (4, 3, 2).

The weight x^{T} of a tableau T is defined as

x^{T} := ∏ x_{T_{i,j}},  (2.3)

where the product is over all entries T_{ij} of T. Given this terminology, the Schur function s_{λ}(x_{1}, x_{2}, …, x_{m}) is also given by (see [35, I, (5.12) with μ = ∅]),

s_{λ}(x_{1}, x_{2}, …, x_{m}) = ∑_{T} x^{T} ,  (2.4)

where the sum is over all tableaux T of shape λ with entries ≤ m.

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

• • • • • • •

[figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] •

• • •

•

•

•

•

2 4

5 3

4 6 4

6

6

A_{1}

A_{2}

A_{3}

A_{4}

E_{1} E_{2} E_{3} E_{4}

2 3 4 6 4 4 6 5 6

b. A tableau a. A star

Figure 1

In [21] it was proved that the number of stars with p branches, as described above, can be determined by using a standard bijection between stars and tableaux, see Figure 1. First label down-steps by the x-coordinate of their end point, so that a step from (a − 1, b) to (a, b − 1) is labelled by a, see Figure 1.a. Then, out of the labels of the j-th branch, form the j-th column of the corresponding tableau. The resulting array of numbers is indeed a tableau. This can be readily seen, since the entries are trivially strictly increasing along columns, and they are weakly increasing along rows because the branches do not touch each other.

Thus, given a star with p branches, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), i = 1, 2, …, p, one obtains a tableau with column lengths \frac{m−e_{1}}{2} , \frac{m−e_{2}}{2} …, \frac{m−e_{p}}{2} . The shape (the vector of row lengths) can be easily extracted from the column lengths. This correspondence between stars and tableaux is a bijection between stars with p branches, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), i = 1, 2, …, p, and tableaux with entries at most m and column lengths \frac{m−e_{1}}{2} , \frac{m−e_{2}}{2} …, \frac{m−e_{p}}{2} .

Clearly, the number of these tableaux is given by (2.4) with x_{1} = x_{2} = ⋯ = x_{m} = 1 and λ the partition whose Ferrers diagram has column lengths \frac{m−e_{1}}{2} , \frac{m−e_{2}}{2} …, \frac{m−e_{p}}{2} . On the other hand, it is well-known that (see [35, I, Sec. 3, Ex. 1 and 4], [16, Ex. A.30, (ii)])

s_{λ}(\underbrace{1, 1, …, 1}_{m}) = ∏_{1≤i<j≤m} \frac{λ_{i} − i − λ_{j} + j}{j − i} = ∏_{ρ∈λ} \frac{m + c_{ρ}}{h_{ρ}} ,  (2.5)

where c_{ρ} and h_{ρ} are the content and the hook length of the cell ρ. The content c_{ρ} of a cell ρ = (i, j) is j − i, whereas the hook-length h_{ρ} of a cell ρ is the number of cells in the same row to the right of ρ plus the number of cells in the same column below ρ plus 1. The expression obtained can, with some work, be converted into (2.1).

3. Enumeration of stars with arbitrary end points, without wall restriction

The following result was proved in [21] using the Bender-Knuth formula, but no proof of the Bender-Knuth formula was given. As we require some of the concepts of the proof in subsequent sections, we briefly repeat the proof given in [21] but also review a proof of the Bender-Knuth conjecture.

Theorem 2. The number of stars of length m with p branches equals

∏_{1≤i≤j≤m} \frac{p + i + j − 1}{i + j − 1}.  (3.1)

Proof. Using the correspondence between stars and tableaux described in the proof of Theorem 1, we see that we must count tableaux with entries at most m having at most p columns. This enumeration problem (actually the corresponding “q-enumeration” problem) is known under the name Bender–Knuth conjecture, and was first proved by B. Gordon around 1970 (but appeared only much later as [20]). Since then, many further proofs have been given. See [1], [9, Théoréme 1.1, first identity], [35, I, Sec. 5, Ex. 19], [43, Prop. 7.2], [46], [50, Sec. 7] for a selection. What all these proofs share more or less explicitly is the following identity, which relates Schur functions and odd orthogonal characters of the symmetric group of rectangular shape,

∑_{μ, μ_{1}≤p} s_{μ}(x_{1}, x_{2}, …, x_{m}) = (x_{1}x_{2} ⋯ x_{m})^{p/2} so_{((p/2)^{m})}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1). (3.2)

The odd orthogonal characters so_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1), where x_{1}^{±1} is a shorthand notation for x_{1}, x_{1}^{−1}, etc., and where λ is an m-tuple (λ_{1}, λ_{2}, …, λ_{m}) of integers, or of half-integers, is defined by

so_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1) = \frac{det_{1≤i,j≤m}(x_{j}^{λ_{i}+m−i+1/2} − x_{j}^{−(λ_{i}+m−i+1/2)})}{det_{1≤i,j≤m}(x_{j}^{m−i+1/2} − x_{j}^{−(m−i+1/2)})}.  (3.3)

Recall that the Schur functions s_{λ}(x_{1}, x_{2}, …, x_{m}) are defined by (2.2). While Schur functions are polynomials in x_{1}, x_{2}, …, x_{m} (cf. (2.4)), odd orthogonal characters so_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{m}^{±1}, 1) are polynomials in x_{1}, x_{1}^{−1}, x_{2}, x_{2}^{−1}, …, x_{m}, x_{m}^{−1}, 1. They have a combinatorial descriptions in terms of certain tableaux as well, see [15, Sec. 2], [45, Sec. 6–8], [51, Theorem 2.3].

A variety of different proofs of (3.2) has been given. There are proofs by a combination of combinatorial and manipulatory arguments (cf. [20], [50, Sec. 7, Cor. 7.4.(a)], [39, Theorem 2.3.(1)]), by use of the theory of Hall–Littlewood functions (cf. [35, I, Sec. 5, Ex. 16]), by use of combinatorial descriptions of orthogonal characters coming from algebraic geometry, due to DeConcini, Procesi, Lakshmibai, Musili and Seshadri (cf. [43, Sec. 7], [46, Theorem 3], [31, Proof of (3.8) in the case p = 0, stated separately as (3.12)]). Eventually, a completely elementary proof was found by Bressoud [6].

However, what we now require is the evaluation of the left-hand side of (3.2) at x_{1} = x_{2} = ⋯ = x_{m} = 1, because this yields, in view of (2.4), exactly the number of tableaux under consideration here. In order to evaluate the right-hand side of (3.2) for x_{1} = x_{2} = ⋯ = x_{m} = 1, we may use well-known formulae for the evaluation of odd orthogonal characters at these values of the x_{i}’s, namely (see [16, (24.29)], [51, Theorem 4.5.(2)]),

so_{λ}(1, 1, …, 1) = ∏_{1≤i<j≤m} \frac{λ_{i} − i − λ_{j} + j}{j − i} ∏_{1≤i≤j≤m} \frac{λ_{i} + λ_{j} + 2m + 1 − i − j}{2m + 1 − i − j}

= ∏_{ρ∈λ} \frac{2m + 1 + e_{ρ}}{h_{ρ}} , (3.4)

where, again, h_{ρ} is the hook length of cell ρ, and e_{ρ} is given by

e_{ρ} = e_{(i,j)} = \begin{cases}λ_{i} + λ_{j} − i − j & i ≤ j, \\ i + j − λ′_{i} − λ′_{j} − 2 & i > j. \end{cases}

Here, λ′ denotes the partition conjugate to λ (see [35, p. 2] for the definition of conjugate partition).

Using this formula for λ = ((p/2)^{n}) in (3.2) with x_{1} = x_{2} = ⋯ = x_{n} = 1, finally leads to (3.1).

Theorem 3. The number of stars with p branches of length m is asymptotically

2^{mp+p^{2}/4}m^{−p^{2}/4+p/4}π^{−p/4}( ∏_{ℓ=1}^{p/2}(2ℓ − 2)!)(1 + O(m^{−1}))  if p is even,

2^{mp+p^{2}/4−1/4}m^{−p^{2}/4+p/4}π^{−p/4+1/4}( ∏_{ℓ=1}^{(p−1)/2}(2ℓ − 1)!)(1 + O(m^{−1})) if p is odd,

(3.5)

as m tends to infinity.

Proof. We know that the number of stars with p branches of length m is given by the product formula

∏_{1≤i≤j≤m} \frac{p + i + j − 1}{i + j − 1}.  (3.6)

Therefore, proving (3.5) amounts to appropriately rewriting (3.6) and then applying Stirling’s formula.

For convenience, let us introduce the notations H(n) := ∏_{ℓ=1}^{n}(i − 1)! = ∏_{ℓ=1}^{n}(n − i)! and H_{2}(n) := ∏_{ℓ=1}^{⌊n/2⌋}(n − 2i)!. Then the product (3.6) can be rewritten as follows,

∏_{1≤i≤j≤m} \frac{p + i + j − 1}{i + j − 1} = ∏_{i=1}^{m} \frac{(p + i + m − 1)! (2i − 2)!}{(p + 2i − 2)! (i + m − 1)!}

= \frac{H(p + 2m) H_{2}(p) H_{2}(2m) H(m)}{H(p + m) H_{2}(p + 2m) H_{2}(0) H(2m)}.  (3.7)

Our aim is to write this as a product whose range depends only on p. To do so, we need to distinguish between the cases of p being even or odd.

If p is even, then (3.7) can be written as

∏_{ℓ=1}^{p/2} \frac{(2ℓ − 2)!}{(2m + 2ℓ − 2)!} ∏_{ℓ=1}^{p} \frac{(2m + ℓ − 1)!}{(m + ℓ − 1)!}.

Application of Stirling’s formula, and some simplification, yields the first line of (3.5). If p is odd, then (3.7) can be written as

\frac{(p + 2m − 1)!!}{(p − 1)!!} ∏_{ℓ=1}^{(p+1)/2} \frac{(2ℓ − 2)!}{(2m + 2ℓ − 2)!} ∏_{ℓ=1}^{p} \frac{(2m + ℓ − 1)!}{(m + ℓ − 1)!}.

Renewed application of Stirling’s formula, and some simplification, yields the second line of (3.5).

Next we consider the ∞-friendly model for stars.

Theorem 4. The number of ∞-friendly stars in the TK model with p branches of length m is asymptotically

\begin{cases}2^{mp+3p^{2}/4−p/2}m^{−p^{2}/4+p/4}π^{−p/4}( ∏_{ℓ=1}^{p/2}(2ℓ − 2)!)(1 + O(m^{−1})) & if p is even, \\ 2^{mp+3p^{2}/4−p/2−1/4}m^{−p^{2}/4+p/4}π^{−p/4+1/4} \\ ×( ∏_{ℓ=1}^{(p−1)/2}(2ℓ − 1)!)(1 + O(m^{−1})) & if p is odd, \end{cases} (3.8)

as m tends to infinity.

Proof. The situation is more difficult here, as we do not have a nice closed product formula (such as (3.6)) for ∞-friendly stars. For simplicity, we treat the case of even m only, the case of odd m being completely analogous.

Consider an ∞-friendly star with p branches of length m. It consists of a family (P_{1}, P_{2}, …, P_{p}) of non-crossing lattice paths, P_{i} running from A_{i} = (0, 2(i − 1)) to some point on the line x = m, i = 1, 2, …, p. Figure 2.a displays an example for p = 4 and m = 6.

Shifting the i-th path, P_{i}, by 2(i − 1) units up, we obtain a family (P̃_{1}, P̃_{2}, …, P̃_{p}) of non-intersecting paths, P̃_{i} running from (0, 4(i − 1)) to some point on the line x = m, i = 1, 2, …, p, see Figure 2.b. Clearly, this correspondence is a bijection.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{1}; A_{2}; A_{3}; A_{4}; E_{1}; E_{2} = E_{3}; E_{4}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; Ã_{1}; Ã_{2}; Ã_{3}; Ã_{4}; Ẽ_{1}; Ẽ_{2}; Ẽ_{3}; Ẽ_{4}]

a. An ∞-friendly star b. A corresponding family of non-intersecting lattice paths

Figure 2

The standard way to find the number of these families of non-intersecting lattice paths is to resort to Proposition A3 and thus obtain a Pfaffian for this number. However, it seems difficult to derive asymptotic estimates from this Pfaffian, in particular since Gordon’s reductions ([19, implicitly in Sec. 4, 5], see also [50, proof of Theorem 7.1]) do not seem to apply. Therefore we choose a different path.

For fixed e_{1}, e_{2}, …, e_{p}, the number of families (P̃_{1}, P̃_{2}, …, P̃_{p}) of non-intersecting lattice paths, P̃_{i} running from (0, 4(i − 1)) to (m, 2e_{i}) is given by the corresponding Lindström–Gessel-Viennot determinant (see Proposition A2),

det_{1≤i,j≤p} (\binom{m}{\frac{m}{2} + 2j − e_{i} − 2}) .  (3.9)

We have to sum (3.9) over all −m/2 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ m/2, and approximate the sum as m tends to infinity. (It is here where we use the assumption that m is even. For, any path from a point (0, 4(i − 1)) reaches the vertical line x = m in a point with even y-coordinate.) We content ourselves to give a rough outline, as our approach is very much in the spirit of Regev’s asymptotic computation [47] for Young diagrams in a strip, and as the proof of Theorem 11 contains a detailed computation of the same kind, showing all the essentials in the simpler case of the estimation of a one-fold sum (as opposed to a p-fold sum that we are considering here). As in Regev’s computation, the expression to be estimated is transformed until an integral is obtained, which then can be evaluated by a limit case of Selberg’s famous integral [49].

To begin with, we bring the determinant (3.9) into a more convenient form, by taking out some common factors,

det_{1≤i,j≤p} (\binom{m}{\frac{m}{2} + 2j − e_{i} − 2})

= ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m}{2} + e_{i})! (\frac{m}{2} − e_{i} + 2p − 2)!} det_{1≤i,j≤p} ((\frac{m}{2} +e_{i}−2j+3)_{2j−2} (\frac{m}{2} −e_{i}+2j−1)_{2p−2j}), (3.10)

where (a)_{k} denotes the standard shifted factorial, (a)_{k} := a(a+1) ⋯ (a+k −1), k ≥ 1, (a)_{0} := 1.

The determinant is a polynomial in m and the e_{i}’s. It suffices to extract the leading term, because the contributions of the lower terms to the overall asymptotics are negligible. In order to do so, we observe that, more precisely, the determinant in (3.10) is a polynomial in m and the e_{i}’s of degree 2p^{2} − 2p which is divisible by ∏_{1≤i<j≤p}(e_{j} − e_{i}).

The leading term is

det_{1≤i,j≤p} ((\frac{m}{2} + e_{i})^{2j−2}(\frac{m}{2} − e_{i})^{2p−2j})

= ∏_{i=1}^{p}(\frac{m}{2} − e_{i})^{2p−2} det_{1≤i,j≤p} (( \frac{\frac{m}{2} + e_{i}}{\frac{m}{2} − e_{i}} )^{2j−2})

= ∏_{i=1}^{p}(\frac{m}{2} − e_{i})^{2p−2} ∏_{1≤i<j≤p} (( \frac{\frac{m}{2} + e_{j}}{\frac{m}{2} − e_{j}} )^{2} − ( \frac{\frac{m}{2} + e_{i}}{\frac{m}{2} − e_{i}} )^{2})

= ∏_{1≤i<j≤p} (m(e_{j} − e_{i})(\frac{m^{2}}{2} − 2e_{i}e_{j})).

Here we used the Vandermonde determinant evaluation to evaluate the determinant in the second line. On ignoring again terms whose contribution to the overall asymptotics are negligible, we obtain

m^{3\binom{p}{2}}2^{−\binom{p}{2}} ∏_{1≤i<j≤p}(e_{j} − e_{i})  (3.11)

as the dominant term in the determinant in (3.10). Now we have to multiply this expression by the product on the right-hand side of (3.10), and then sum the resulting expression over all −m/2 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ m/2. In fact, we may extend the range of summation and sum over all −m/2 ≤ e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{p} ≤ m/2, because the expression (3.11) is zero if any two e_{i}’s should be the same.

For each e_{i} separately, the sum over e_{i} is estimated in the way as it is done in the proof of Theorem 11 for the sum over k, now using Lemma A1 also for b other than 0. The result is that we obtain

m^{3\binom{p}{2}}2^{−\binom{p}{2}} ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m}{2})! (\frac{m}{2} + 2p − 2)!}

× ∫_{y_{1}≤y_{2}≤···≤y_{p}} ( ∏_{1≤i<j≤p}(y_{j} − y_{i}))e^{− \frac{2}{m} ∑_{ℓ=1}^{p} y_{i}^{2}} dy_{1} … dy_{p}

as an estimation for the number of stars under consideration. In the integral we perform the substitution y_{i} → x_{i}\sqrt{m}/2. This gives

m^{3\binom{p}{2}}2^{−\binom{p}{2}} ∏_{ℓ=1}^{p} (\frac{m!}{(\frac{m}{2})! (\frac{m}{2} + 2p − 2)!})

× (\frac{\sqrt{m}}{2})^{\binom{p+1}{2}} ∫_{x_{1}≤x_{2}≤···≤x_{p}} ( ∏_{1≤i<j≤p} |x_{j} − x_{i}|)e^{− \frac{1}{2} ∑_{ℓ=1}^{p} x_{i}^{2}} dx_{1} … dx_{p} . (3.12)

At this point, the absolute values in the integrands are superfluous. However, with the absolute values, the integrand is invariant under permutations of the x_{i}’s. Hence, the integral equals

\frac{1}{p!} ∫_{−∞}^{∞} ⋯ ∫_{−∞}^{∞} ( ∏_{1≤i<j≤p} |x_{j} − x_{i}|)e^{− \frac{1}{2} ∑_{ℓ=1}^{p} x_{i}^{2}} dx_{1} … dx_{p} .

This integral is the special case k = 1/2 of Mehta’s integral (see [34, (4.1)])

∫_{−∞}^{∞} ⋯ ∫_{−∞}^{∞} ( ∏_{1≤i<j≤p} |x_{j} − x_{i}|^{2k})e^{− \frac{1}{2} ∑_{ℓ=1}^{p} x_{i}^{2}} dx_{1} … dx_{p} = (2π)^{p/2} ∏_{ℓ=1}^{p} \frac{(ℓk)!}{k!},

where k! means Γ(k +1) even if k is not an integer. Substitution of this into (3.12) and application of Stirling’s formula to the factorials in the product in (3.12) yields (3.8) after some simplification.

Since the expressions (3.5) and (3.8) are identical except for a multiplicative constant, we obtain as a consequence the following result for n-friendly models.

Corollary 5. As m tends to infinity, n-friendly stars with p branches of length m have, up to a multiplicative constant, the same asymptotic behaviour, for the GV as well as for the TK model. More precisely, the number of n-friendly stars with p branches of length m is ≍ 2^{mp}m^{−p^{2}/4+p/4}, i.e., there are positive constants c_{1} and c_{2} such that for large enough m this number is between c_{1}2^{mp}m^{−p^{2}/4+p/4} and c_{2}2^{mp}m^{−p^{2}/4+p/4}. Under the assumption that there is a constant c(n) such that this number is asymptotically exactly equal to c(n)2^{mp}m^{−p^{2}/4+p/4}, then we must have c(0) < c(1) < c(2) < ⋯, i.e., for any n there are, asymptotically, strictly less n-friendly stars with p branches of length m than (n + 1)-friendly stars with p branches of length m.

Proof. The first assertion follows immediately from Theorems 3 and 4 since the number of n-friendly stars is bounded below by the number of “genuine” stars, and is bounded above by the number of ∞-friendly stars in the TK model. So, explicitly, we may choose

c_{1} = \begin{cases}2^{p^{2}/4}π^{−p/4}( ∏_{ℓ=1}^{p/2}(2ℓ − 2)!) & if p is even, \\ 2^{p^{2}/4−1/4}π^{−p/4+1/4}( ∏_{ℓ=1}^{(p−1)/2}(2ℓ − 1)!) & if p is odd, \end{cases}

and

c_{2} = \begin{cases}2^{3p^{2}/4−p/2}π^{−p/4}( ∏_{ℓ=1}^{p/2}(2ℓ − 2)!) & if p is even, \\ 2^{3p^{2}/4−p/2−1/4}π^{−p/4+1/4}( ∏_{ℓ=1}^{(p−1)/2}(2ℓ − 1)!) & if p is odd. \end{cases}

The second assertion can be proved as follows. Clearly, for any n we have c(n) ≤ c(n + 1). To see that in fact strict inequality holds, we identify a set of (n + 1)- friendly stars which are not n-friendly stars, with the property that its cardinality is ≍ (2^{mp}m^{−p^{2}/4+1/4}) (as is the cardinality of n-friendly stars). As this set of (n + 1)- friendly stars we may choose families (P_{1}, P_{2}, …, P_{p}) of paths, such that P_{i} runs from (0, 2(i − 1)) through (2 ⌊n/2⌋ + 4, 2(i − 1)) to the line x = m, i = 1, 2, …, p, and P_{1} and P_{2} touch each other along n+1 consecutive edges. (This is indeed possible. Let P_{1} start with an up-step and P_{2} start with a down step, then let P_{1} and P_{2} go up and down in parallel for 2 ⌊n/2⌋ + 2 steps, then let P_{1} continue with a down-step, thus reaching (2 ⌊n/2⌋ + 4, 0), and P_{2} continue with an up-step, thus reaching (2 ⌊n/2⌋ + 4, 2). As 2 ⌊n/2⌋ + 2 ≥ n + 1, such paths P_{1} and P_{2} do indeed touch each other along n + 1 consecutive edges.)

If we disregard the portion of the paths between x = 0 and x = 2 ⌊n/2⌋ + 4, then what remains is an (n + 1)-friendly star with p branches of length m − 2 ⌊n/2⌋ − 4. The cardinality of these is at least the cardinality of “genuine” stars with p branches of length m − 2 ⌊n/2⌋ − 4, which, asymptotically, is given by (3.5) with m replaced by m − 2 ⌊n/2⌋ − 4. Up to some constant, this is

2^{mp−2⌊n/2⌋p−4p}m^{−p^{2}/4+1/4}(1 − (2 ⌊n/2⌋ + 4)/m)^{−p^{2}/4+1/4}(1 + O(m^{−1}),

which is ≍ (2^{mp}m^{−p^{2}/4+1/4}), as desired.

Clearly, there is abundant evidence that for any fixed p there exist such constants c(0), c(1), etc. By Theorems 3 and 4 we have computed c(0) and c(∞). It appears to be a challenging problem to determine the other constants, and even just c(1). However, for p = 2 we can calculate c(k) from the data given in [22], and find c(k) = \frac{4}{(1+2^{−k})\sqrt{π}}. This result supports our assertion regarding the existence of this increasing sequence of constants.

4. Enumeration of stars with fixed end points, with wall restriction

For vicious walkers, the previous sections re-derive known results, by techniques from algebraic combinatorics. We now show how these techniques may be used to derive new results, for the case of vicious walkers in the presence of a wall.

Theorem 6. Let e_{1} < e_{2} < ⋯ < e_{p} with e_{i} ≡ m (mod 2), i = 1, 2, …, p. The number of stars with p branches, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), i = 1, 2, …, p, and never going below the x-axis, equals

2^{−p^{2}+p} ∏_{i=1}^{p} \frac{(e_{i} + 1) (m + 2i − 2)!}{(\frac{m+e_{i}}{2} + p)! (\frac{m−e_{i}}{2} + p − 1)!} ∏_{1≤i<j≤p}(e_{j} − e_{i})(e_{i} + e_{j} + 2).  (4.1)

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{1}; A_{2}; A_{3}; A_{4}; E_{1}; E_{2}; E_{3}; E_{4}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A′_{1}; A′_{2}; A′_{3}; A′_{4}; E_{1}; E_{2}; E_{3}; E_{4}]

a. A star b. Star with attached “up-pieces”

Figure 3

Proof. (1) By first principles. As in [21], we could directly use the main theorem of non-intersecting lattice paths (see Proposition A2), to write the number of stars in question in the form

det_{1≤i,j≤p} ( |P^{+}(A_{j} → E_{i})| ),  (4.2)

where P^{+}(A → E) denotes the set of all lattice paths from A to E that do not go below the x-axis. By the “reflection principle” (see e.g. [8, p. 22]), each path number |P^{+}(A_{j} → E_{i})| could then be written as a difference of two binomials. It was shown in [30, Proof of Theorem 7], how to evaluate the resulting determinant (actually, a q-analogue was evaluated there). The evaluation relies on the determinant lemma [30, Lemma 34].

However, since we are only interested in plain enumeration there is a simpler way. As a first step, we may freely attach 2i − 2 up-steps at the beginning of the i-th branch, i = 1, 2, …, p, (see Figure 3). It is obvious that the number of stars with starting points A′_{i} = (−2i+2, 0) (instead of A_{i} = (0, 2i−2)) and end points as in the statement of the theorem, each branch not going below the x-axis (see Figure 3.b), is exactly the same as the number of stars in the statement of the theorem (see Figure 3.a).

If we apply the main theorem of non-intersecting lattice paths now, then we again obtain a determinant for the number in question, namely the determinant (4.2) with A_{j} replaced by A′_{j},

det_{1≤i,j≤p} ( |P^{+}(A′_{j} → E_{i})| ),  (4.3)

P^{+}(A → E) denoting the set of all lattice paths from A to E that do not go below the x-axis.

Again, by reflection principle, the path number |P^{+}(A′_{j} → E_{i})| can be easily computed, so that the determinant (4.3) equals

det_{1≤i,j≤p} (\frac{e_{i} + 1}{m + 2j − 1}\binom{m + 2j − 1}{\frac{m−e_{i}}{2} + j − 1}) .

Now we remove as many factors from the determinant as possible. In that way we obtain

(−1)^{\binom{p}{2}} ∏_{i=1}^{p} \frac{(e_{i} + 1) (m + 2i − 2)!}{(\frac{m+e_{i}}{2} + p)! (\frac{m−e_{i}}{2} + p − 1)!}

× det_{1≤i,j≤p} ((\frac{−m + e_{i}}{2} − p + 1) ⋯ (\frac{−m + e_{i}}{2} − j)(\frac{m + e_{i}}{2} + p) ⋯ (\frac{m + e_{i}}{2} + j − 1)).

(4.4)

The determinant in (4.4) can clearly be rewritten as

det_{1≤i,j≤p} ((\frac{e_{i} + 1}{2} − \frac{m − 1}{2} − p) ⋯ (\frac{e_{i} + 1}{2} − \frac{m − 1}{2} − j − 1)

· (\frac{e_{i} + 1}{2} + \frac{m − 1}{2} + p) ⋯ (\frac{e_{i} + 1}{2} − \frac{m − 1}{2} + j + 1))

= det_{1≤i,j≤p} (((\frac{e_{i} + 1}{2})^{2} − (\frac{m − 1}{2} − p)^{2}) ⋯ ((\frac{e_{i} + 1}{2})^{2} − (\frac{m − 1}{2} − j − 1)^{2})) .

This determinant can be reduced by elementary row manipulations to

det_{1≤i,j≤p} ((\frac{e_{i} + 1}{2})^{2(p−j)}) ,

which is apparently a Vandermonde determinant and therefore equals

∏_{1≤i<j≤p} ((\frac{e_{i} + 1}{2})^{2} − (\frac{e_{j} + 1}{2})^{2}) = 2^{−p^{2}+p} ∏_{1≤i<j≤p}(e_{i} − e_{j})(e_{i} + e_{j} + 2).

Substituting this in (4.4) gives (4.1).

(2) Using knowledge about symplectic characters. The (even) symplectic character sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) is defined by (see [16, (24.18)])

sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) = \frac{det_{1≤i,j≤n}(x_{j}^{λ_{i}+n−i+1} − x_{j}^{−(λ_{i}+n−i+1)})}{det_{1≤i,j≤n}(x_{j}^{n−i+1} − x_{j}^{−(n−i+1)})}.  (4.5)

Proctor [42] also defined odd symplectic characters sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1), which are for example defined by

sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1)

= \frac{1}{2} det_{1≤i,j≤n} (h_{λ_{i}−i+j}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1) + h_{λ_{i}−i−j+2}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1)), (4.6)

where h_{k}(z_{1}, z_{2}, …, z_{r}) = ∑_{1≤i_{1}≤···≤i_{m}≤r} z_{i_{1}} ⋯ z_{i_{k}} denotes the k-th complete homogeneous symmetric function.

It is well-known that a combinatorial description of symplectic characters is given in terms of symplectic tableaux. Let λ be a partition. A symplectic tableau of shape λ is a semistandard tableau of shape λ with the additional property that

entries in row i are at least 2i − 1.  (4.7)

It is obvious that because of weak increase along rows this condition may be restricted to the entries in the first column.

Let n be fixed, and let T be a symplectic tableau with entries at most 2n + 1. The weight x^{T} of the symplectic tableau T is defined by

x^{T} = ∏_{l=1}^{n} x_{l}^{|{T_{i,j}=2l−1}|−|{T_{i,j}=2l}|}.  (4.8)

where T_{ij} denotes the entry in cell (i, j) of T. Note that entries 2n + 1 do not contribute to the weight. Given this terminology, the (even) symplectic character sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) is also given by (see [51, Theorem 2.3], [45, Theorem 4.2]),

sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}) = ∑_{T} x^{T} ,  (4.9)

where the sum is over all symplectic tableaux T of shape λ with entries ≤ 2n, whereas the odd symplectic character sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1) is also given by (see [45, Theorem 4.2]),

sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …, x_{n}^{±1}, 1) = ∑_{T} x^{T} ,  (4.10)

where the sum is over all symplectic tableaux T of shape λ with entries ≤ 2n + 1.

The formula for symplectic characters needed here is (see [10, (3.27)], [51, Theorem 4.5.(1)] and [42, Prop. 3.2])

sp_{λ}(\underbrace{1, 1, …, 1}_{m}) = ∏_{1≤i<j≤m} \frac{λ_{i} − i − λ_{j} + j}{j − i} ∏_{1≤i≤j≤m} \frac{λ_{i} + λ_{j} + m − i − j + 2}{m + 2 − i − j}

= ∏_{ρ∈λ} \frac{m − f_{ρ}}{h_{ρ}} , (4.11)

where m may be even or odd, where, again, h_{ρ} is the hook length of cell ρ, and f_{ρ} is given by

f_{ρ} = f_{(i,j)} = \begin{cases}λ′_{i} + λ′_{j} − i − j & i ≤ j, \\ i + j − λ_{i} − λ_{j} − 2 & i > j. \end{cases}

Here again, λ′ denotes the partition conjugate to λ.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 2; 4; 5; 3; 4; 6; 4; 6; 6; A_{1}; A_{2}; A_{3}; A_{4}; E_{1}; E_{2}; E_{3}; E_{4}; ^{2 3 4 6 4 4 6 5 6 1 ≤ 3 ≤ 5 ≤}]

a. A star with a wall b. A symplectic tableau

Figure 4

Now we use a slight variant of the correspondence described in the proof of Theorem 1. Given a star, we label down-steps by the x-coordinate of their starting point, i.e., a step from (a, b) to (a + 1, b − 1) is labelled by a, see Figure 4.a. Then, again, from the labels of the j-th branch, we form the j-th column of the corresponding tableau. It is evident that the condition that the branches do not go below the x-axis under this correspondence translates exactly into condition (4.7). Therefore, in that manner we obtain a bijection between stars with p branches, the i-th branch running from A_{i} = (0, 2i − 2) to E_{i} = (m, e_{i}), i = 1, 2, …, p, and never going below the xaxis, with symplectic tableaux with entries at most m − 1 and with column lengths \frac{m−e_{1}}{2} , \frac{m−e_{2}}{2} …, \frac{m−e_{p}}{2} . So, formula (4.11) solves this enumeration problem and gives (4.1) upon some manipulation.

5. Enumeration of stars with arbitrary end points, with wall restriction

Theorem 7. The number of stars of length m with p branches which do not go below the x-axis, and whose end points have y-coordinates at least s, s ≡ m (mod 2), equals

∏_{i=1}^{p} ∏_{j=1}^{(m+s)/2} ∏_{k=1}^{(m−s)/2} \frac{i + j + k − 1}{i + j + k − 2}.  (5.1)

Proof. Using the correspondence between stars restricted by a wall and symplectic tableaux described in the second proof of Theorem 6, we see that we want to count symplectic tableaux with entries at most m − 1 having at most (m − s)/2 rows and at most p columns. This problem was encountered before by Proctor [44]. (He was actually interested in enumerating plane partitions of trapezoidal shape. However, he demonstrates in [44] that these are in bijection with the symplectic tableaux we are considering here.) The solution of the problem lies in the following identity which relates symplectic characters and Schur functions of rectangular shape:

s_{(c^{r})}(\underbrace{1, 1, …, 1}_{N+1}) = ∑_{ν⊆(c^{r})} sp_{ν}(\underbrace{1, 1, …, 1}_{N}).  (5.2)

Here (c^{r}) is short for (c, c, …, c), with r occurrences of c. Recall, that in the argument of a symplectic character sp_{λ}(x_{1}^{±1}, x_{2}^{±1}, …) the term x_{i}^{±1} denotes the two arguments x_{i}, x_{i}^{−1}.

Actually, an identity for “universal” characters is true, see [31, (3.1) summed over all p]. This underlying “universal” character identity is proved by a combinatorial rule due to Littlewood [33], see [44, Proof of Lemma 4] and [31, Sec. 4].

Clearly, the formula (2.5), used in (5.2) with c = p, r = (m − s)/2, N = m − 1, immediately gives what we want. With some work the resulting expression can be transformed into (5.1).

Formula (5.2) also implies that there should be a bijection between symplectic tableaux with entries at most m having at most s rows and at most p columns, on the one hand, and (ordinary) tableaux with entries at most m + 1 having s rows and p columns, on the other hand. Such a bijection has been constructed by Haiman [23, Prop. 8.11], it is based on Schützenberger’s [48] jeu de taquin. Actually, his bijection is between tableaux of trapezoidal shape (which however are in bijection with symplectic tableaux as shown by Proctor) and tableaux of rectangular shape. This bijection could easily be converted into a bijection between stars of length m with p branches which do not go below the x-axis, and whose end points have y-coordinates at least m − s and watermelons of length m with p branches of deviation s.

Theorem 8. The number of stars with p branches of length m which do not go below the x-axis, and whose end points have y-coordinates at least s, s ≡ m (mod 2), is asymptotically

2^{mp+p^{2}−p/2}m^{−p^{2}/2}π^{−p/2}( ∏_{ℓ=1}^{p}(ℓ − 1)!)(1 + O(1/m))  (5.3)

as m tends to infinity.

Proof. We know that the number of stars with p branches of length m which do not go below the x-axis, and whose end points have y-coordinates at least s, s ≡ m (mod 2), is given by the product formula

∏_{ℓ=1}^{p} ∏_{i=1}^{(m+s)/2} ∏_{j=1}^{(m−s)/2} \frac{i + j + ℓ − 1}{i + j + ℓ − 2} = ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (m + ℓ − 1)!}{(\frac{m+s}{2} + ℓ − 1)! (\frac{m−s}{2} + ℓ − 1)!}.  (5.4)

Application of Stirling’s formula yields (5.3) after a short calculation.

Theorem 9. The number of ∞-friendly stars in the TK model with p branches of length m which do not go below the x-axis, and whose end points have y-coordinates at least s, s ≡ m (mod 2), is asymptotically

2^{mp+p^{2}−3p/2}m^{−p^{2}/2}π^{−p/2}( ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (2ℓ − 2)! (4ℓ − 2)!}{(ℓ + p − 1)!^{2}})(1 + O(m^{−1/2} log^{3} m)) (5.5)

as m tends to infinity.

Proof. Again, the situation is more difficult here, as we do not have a nice closed product formula (such as (5.3)) for ∞-friendly stars. We shall follow very closely the line of arguments of the proof of Theorem 4. Again, for simplicity, we treat the case of even m and s = 0 only, other cases being completely analogous.

As in the proof of Theorem 4, we begin by transforming ∞-friendly stars into families of non-intersecting lattice paths by shifting the i-th path up by 2(i − 1) units. Thus, ∞-friendly stars with p branches of length m which do not go below the x-axis are in bijection with families (P_{1}, P_{2}, …, P_{p}) of non-intersecting lattice paths, P_{i} running from (0, 4(i − 1)) to (m, 2e_{i}), i = 1, 2, …, p, for some integers e_{1}, e_{2}, …, e_{p} with 0 ≤ e_{1} < e_{2} < ⋯ < e_{p}. For fixed e_{1}, e_{2}, …, e_{p}, the number of such families of non-intersecting lattice paths is given by the corresponding Lindström–Gessel-Viennot determinant (see Proposition A2, and cf. also the arguments in the first proof of Theorem 6, particularly the application of the reflection principle),

det_{1≤i,j≤p} (\binom{m}{\frac{m}{2} + 2j − e_{i} − 2} − \binom{m}{\frac{m}{2} + 2j + e_{i} − 1}) .  (5.6)

We have to sum (5.6) over all 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ m/2, and approximate the sum as m tends to infinity. As in the proof of Theorem 4, the expression to be estimated is transformed until an integral is obtained, which then can be evaluated by a limit case of Selberg’s famous integral [49]. It is, however, a different limit case that we need here.

To begin with, we bring the determinant (5.6) into a more convenient form, by taking out some common factors,

det_{1≤i,j≤p} (\binom{m}{\frac{m}{2} + 2j − e_{i} − 2} − \binom{m}{\frac{m}{2} + 2j + e_{i} − 1})

= ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m}{2} + e_{i} + 2p − 1)! (\frac{m}{2} − e_{i} + 2p − 2)!}

× det_{1≤i,j≤p} ((\frac{m}{2} + e_{i} − 2j + 3)_{2p+2j−3} (\frac{m}{2} − e_{i} + 2j − 1)_{2p−2j}

− (\frac{m}{2} + e_{i} + 2j)_{2p−2j} (\frac{m}{2} − e_{i} − 2j + 2)_{2p+2j−3}), (5.7)

where, as before, (a)_{k} denotes the standard shifted factorial, (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, (a)_{0} := 1.

The determinant is a polynomial in m and the e_{i}’s. It suffices to extract the leading term, because the contributions of the lower terms to the overall asymptotics are negligible. In order to do so, we consider the more general determinant

det_{1≤i,j≤p} ((\frac{m}{2} + X_{i} − 2j + \frac{5}{2})_{2p+2j−3} (\frac{m}{2} − X_{i} + 2j − \frac{1}{2})_{2p−2j}

− (\frac{m}{2} + X_{i} + 2j − \frac{1}{2})_{2p−2j} (\frac{m}{2} − X_{i} − 2j + \frac{5}{2})_{2p+2j−3}). (5.8)

Clearly, we regain the determinant in (5.7) for X_{i} = e_{i} + 1/2.

The determinant in (5.8) is a polynomial in m and the X_{i}’s of degree p(4p − 3). It is divisible by ∏_{1≤i<j≤p}(X_{j}^{2} − X_{i}^{2}) ∏_{i=1}^{p} X_{i}.

The leading term of (5.8) is

det_{1≤i,j≤p} ((\frac{m}{2} + X_{i})^{2p+2j−3}(\frac{m}{2} − X_{i})^{2p−2j} − (\frac{m}{2} + X_{i})^{2p−2j}(\frac{m}{2} − X_{i})^{2p+2j−3})

= ∏_{i=1}^{p}(\frac{m}{2} + X_{i})^{2p−3/2}(\frac{m}{2} − X_{i})^{2p−3/2} det_{1≤i,j≤p} (( \frac{\frac{m}{2} + X_{i}}{\frac{m}{2} − X_{i}} )^{2j−3/2} − ( \frac{\frac{m}{2} + X_{i}}{\frac{m}{2} − X_{i}} )^{−2j+3/2})

= ∏_{i=1}^{p}(\frac{m}{2} + X_{i})^{p−1}(\frac{m}{2} − X_{i})^{3p−2} ∏_{i=1}^{p} (( \frac{\frac{m}{2} + X_{i}}{\frac{m}{2} − X_{i}} ) − 1)

× ∏_{1≤i<j≤p} (( \frac{\frac{m}{2} + X_{i}}{\frac{m}{2} − X_{i}} ) − ( \frac{\frac{m}{2} + X_{j}}{\frac{m}{2} − X_{j}} )) (1 − (\frac{(\frac{m}{2} + X_{i})}{(\frac{m}{2} − X_{i})} \frac{(\frac{m}{2} + X_{j})}{(\frac{m}{2} − X_{j})}))

× so_{(p−1,p−2,...,1,0)} (( \frac{\frac{m}{2} +X_{1}}{\frac{m}{2} −X_{1}} )^{±1} , …, ( \frac{\frac{m}{2} +X_{p}}{\frac{m}{2} −X_{p}} )^{±1} , 1)

= ∏_{1≤i<j≤p} (((\frac{m}{2} + X_{j})(\frac{m}{2} − X_{i}) − (\frac{m}{2} + X_{i})(\frac{m}{2} − X_{j}))

· ((\frac{m}{2} + X_{j})(\frac{m}{2} + X_{i}) − (\frac{m}{2} − X_{i})(\frac{m}{2} − X_{j}))) ∏_{i=1}^{p} ((\frac{m}{2} + X_{i}) − (\frac{m}{2} − X_{i}))

× ∏_{i=1}^{p}(\frac{m}{2} + X_{i})^{p−1}(\frac{m}{2} − X_{i})^{p−1} so_{(p−1,p−2,...,1,0)} (( \frac{\frac{m}{2} +X_{1}}{\frac{m}{2} −X_{1}} )^{±1} , …, ( \frac{\frac{m}{2} +X_{p}}{\frac{m}{2} −X_{p}} )^{±1} , 1) .

Here we used (C.4) to evaluate the determinant in the second line. Now we recall the observation (see the paragraph containing (3.4)) that the odd orthogonal character is a certain Laurent polynomial in its variables. In the present context it implies that the very last line in our computation is a polynomial in the quantities (m/2 + X_{i}), (m/2 − X_{i}), i = 1, 2, …, p, consisting of a sum of exactly so_{(p−1,...,1,0)}(1, 1, …, 1) monomials, the evaluation of the orthogonal character at all 1’s being given by (3.4) itself.

Hence, the determinant (5.8) equals

( ∏_{1≤i<j≤p} m(X_{j} − X_{i})m(X_{j} + X_{i}))( ∏_{i=1}^{p} 2X_{i})

× 2^{−p}( ∏_{ℓ=1}^{p} \frac{(2ℓ − 2)! (4ℓ − 2)!}{(ℓ + p − 1)!^{2}}) ((\frac{m}{2})^{2p^{2}−2p} + ⋯) . (5.9)

The leading term of the determinant in (5.7) is obtained from this expression under the substitution of X_{i} = e_{i} + 1/2, i = 1, 2, …, p. This substitution turns (5.9) into

m^{3p^{2}−3p}2^{−2p^{2}+2p} ∏_{1≤i<j≤p}(e_{j} − e_{i})(e_{j} + e_{i} + 1) ∏_{ℓ=1}^{p}(e_{i} + \frac{1}{2}) ∏_{ℓ=1}^{p} \frac{(2ℓ − 2)! (4ℓ − 4)!}{(ℓ + p − 1)!^{2}}

+ lower terms. (5.10)

Now we have to multiply this expression by the product on the right-hand side of (5.7), and then sum the resulting expression over all 0 ≤ e_{1} < e_{2} < ⋯ < e_{p} ≤ m/2. In fact, we may extend the range of summation and sum over all 0 ≤ e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{p} ≤ m/2, because the expression (5.10) is zero if any two e_{i}’s should be the same.

For each e_{i} separately, the sum over e_{i} is estimated in the way as it is done in the proof of Theorem 11 for the sum over k, now using Lemma A1 also for b other than 0. The result is that we obtain

m^{3p^{2}−3p}2^{−2p^{2}+2p} ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m}{2} + 2p − 2)! (\frac{m}{2} + 2p − 1)!} \frac{(2ℓ − 2)! (4ℓ − 4)!}{(ℓ + p − 1)!^{2}}

× ∫_{0≤y_{1}≤y_{2}≤···≤y_{p}} ( ∏_{1≤i<j≤p}(y_{j} − y_{i})(y_{j} + y_{i} + 1) ∏_{ℓ=1}^{p}(y_{i} + \frac{1}{2}))e^{− \frac{2}{m} ∑_{ℓ=1}^{p} y_{i}^{2}} dy_{1} … dy_{p}

as an estimation for the number of stars under consideration. In the integral we perform the substitution y_{i} → x_{i}\sqrt{m}/2. After dropping terms which are asymptotically negligible, we obtain

m^{3p^{2}−3p}2^{−2p^{2}+2p} ∏_{ℓ=1}^{p} (\frac{m!}{(\frac{m}{2} + 2p − 2)! (\frac{m}{2} + 2p − 1)!} \frac{(2ℓ − 2)! (4ℓ − 4)!}{(ℓ + p − 1)!^{2}})

× (\frac{m}{4})^{\binom{p+1}{2}} ∫_{0≤x_{1}≤x_{2}≤···≤x_{p}} ( ∏_{1≤i<j≤p} |x_{j}^{2} − x_{i}^{2}| ∏_{ℓ=1}^{p} |x_{i}|)e^{− \frac{1}{2} ∑_{ℓ=1}^{p} x_{i}^{2}} dx_{1} … dx_{p} . (5.11)

At this point, the absolute values in the integrands are superfluous. However, with the absolute values, the integrand is invariant under permutations of the x_{i}’s, and under sign changes of the x_{i}’s. Hence, the integral equals

\frac{1}{2^{p}p!} ∫_{−∞}^{∞} ⋯ ∫_{−∞}^{∞} ( ∏_{1≤i<j≤p} |x_{j}^{2} − x_{i}^{2}| ∏_{ℓ=1}^{p} |x_{i}|)e^{− \frac{1}{2} ∑_{ℓ=1}^{p} x_{i}^{2}} dx_{1} … dx_{p} .

This integral is the special case k_{1} + k_{3} = 1, k_{2} = 1 of the integral (see [34, Conj. 6.1, Case (a)])

∫_{−∞}^{∞} ⋯ ∫_{−∞}^{∞} ( ∏_{1≤i<j≤p} |x_{j}^{2} − x_{i}^{2}|^{k_{2}} ∏_{ℓ=1}^{p} |x_{i}|^{k_{1}+k_{3}})e^{− \frac{1}{2} ∑_{ℓ=1}^{p} x_{i}^{2}} dx_{1} … dx_{p}

= (2^{1−k_{1}−k_{3}}π)^{p/2} ∏_{ℓ=1}^{p} \frac{(\frac{1}{2}ℓk_{2})! (k_{1} + k_{3} + (ℓ − 1)k_{2})!}{(\frac{1}{2}k_{2})! (\frac{1}{2}(k_{1} + k_{3} + (ℓ − 1)k_{2}))!}.

Substitution of this into (5.11) and application of Stirling’s formula to the factorials in the product in (5.11) yields (5.5) after some simplification.

Corollary 10. As m tends to infinity, n-friendly stars with p branches of length m which do not go below the x-axis have, up to a multiplicative constant, the same asymptotic behaviour, for the GV as well as for the TK model. More precisely, the number of n-friendly stars with p branches of length m which do not go below the x-axis and whose end points have y-coordinates at least s, s ≡ m (mod 2), is ≍ 2^{mp}m^{−p^{2}/2}, i.e., there are positive constants d_{1} and d_{2} such that for large enough m this number is between d_{1}2^{mp}m^{−p^{2}/2} and d_{2}2^{mp}m^{−p^{2}/2}. Under the assumption that there is a constant d(n) such that this number is asymptotically exactly equal to d(n)2^{mp}m^{−p^{2}/2}, then we must have d(0) < d(1) < d(2) < ⋯, i.e., for any n there are, asymptotically, strictly less n-friendly stars with p branches of length m than (n + 1)-friendly stars with p branches of length m.

This follows without difficulty from Theorems 8 and 9, in the same way as Corollary 5 follows from Theorems 3 and 4.

Clearly, there is abundant evidence that for any fixed p there exist such constants d(0), d(1), etc. By Theorems 3 and 4 we have computed d(0) and d(∞). It appears to be a challenging problem to determine the other constants, and even just d(1).

6. Enumeration of watermelons without wall restriction

As discussed in the introduction, watermelons are a proper subset of stars, their end points being (m, k), (m, k +2), (m, k +4), ⋯, (m, k +2p−2). The parameter k we refer to as the deviation.

In [12] it was shown that the number of watermelons of length m with p branches and deviation k (where k ≡ m (mod 2)) is given by (this also follows from Theorem 1 with e_{i} = k + 2i − 2, i = 1, 2, …, p)

∏_{ℓ=1}^{p} ∏_{i=1}^{(m+k)/2} ∏_{j=1}^{(m−k)/2} \frac{i + j + ℓ − 1}{i + j + ℓ − 2} = ∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(\frac{m+k}{2} + ℓ − 1)! (\frac{m−k}{2} + ℓ − 1)!}.  (6.1)

We are not able to give a closed form expression for the total number of such watermelons (it is very unlikely that a closed form expression exists in general), but we can give an asymptotic result.

Theorem 11. The number of watermelons with p branches of length m (and arbitrary deviation) is asymptotically

2^{mp+p^{2}−p/2−1/2}m^{−p^{2}/2+1/2}π^{−p/2+1/2}p^{−1/2}( ∏_{ℓ=1}^{p}(ℓ − 1)!)(1 + O(m^{−1/2} log^{3} m)) (6.2)

as m tends to infinity.

Proof. We know that the number of watermelons with p branches of length m and with deviation k (where k ≡ m (mod 2)) is given by (6.1). Therefore our task is to estimate the sum

∑_{k≡m (mod 2)} ∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(\frac{m+k}{2} + ℓ − 1)! (\frac{m−k}{2} + ℓ − 1)!}.  (6.3)

We follow the standard way of carrying out such estimations, as described in [37, Ex. 5.4].

The dominant terms in the sum on the right-hand side are those corresponding to k’s which are near 0. Consequently, we split the sum into three parts, the terms with “small” k, the terms with “large” k, and the terms with k ∼ 0. Let S(k) denote the summand on the right-hand side of (6.3),

S(k) = ∏_{ℓ=1}^{p} \frac{Γ(m + ℓ) Γ(ℓ)}{Γ(\frac{m+k}{2} + ℓ) Γ(\frac{m−k}{2} + ℓ)}.

Then the precise way we split the sum in (6.3) is

∑_{−m≤k≤m} S(k) = ∑_{−m≤k≤−\sqrt{m} log m} S(k) + ∑_{\sqrt{m} log m≤k≤m} S(k) + ∑_{|k|<\sqrt{m} log m} S(k), (6.4)

where it is understood without saying that all sums are only over those k which are of the same parity as m. We will show that the contributions of the first and second term in (6.4) are negligible, and we will compute the contribution which the third term provides.

To see that the first term in (6.4) is negligible, it is enough to observe that every summand S(k) with −m ≤ k ≤ −\sqrt{m} log m is bounded above by S(−\sqrt{m} log m), and to compute the asymptotics of S(−\sqrt{m} log m) by means of Stirling’s formula,

S(−\sqrt{m} log m) = (1 + O(1/m)) ∏_{ℓ=1}^{p} Γ(ℓ)\frac{(\frac{m}{e})^{m} m^{ℓ−1}\sqrt{2πm}}{(\frac{m+\sqrt{m} log m}{2e})\frac{1}{2} (m+\sqrt{m} log m) (\frac{m+\sqrt{m} log m}{2})ℓ−1}

· \frac{1}{(\frac{m−\sqrt{m} log m}{2e})^{\frac{1}{2} (m−\sqrt{m} log m)} (\frac{m−\sqrt{m} log m}{2})^{ℓ−1} \sqrt{\frac{1}{2}π^{2}(m^{2} − m log^{2} m)}}

= (1 + O(log^{2} m/m)) ∏_{ℓ=1}^{p}(ℓ − 1)!\frac{2^{m+2ℓ−1}}{m^{ℓ−1}\sqrt{πm}}

· \frac{1}{(1 + \frac{log m}{\sqrt{m}})^{\frac{1}{2} (m+\sqrt{m} log m)+ℓ−1} (1 − \frac{log m}{\sqrt{m}})^{\frac{1}{2} (m−\sqrt{m} log m)+ℓ−1}}

= (1 + O(log^{2} m/m)) ∏_{ℓ=1}^{p}(ℓ − 1)!\frac{2^{m+2ℓ−1}}{m^{ℓ−1}\sqrt{πm}}

· \frac{1}{exp ((\frac{log m}{\sqrt{m}} − \frac{log^{2} m}{2m} + O (\frac{log^{3} m}{m\sqrt{m}})) (\frac{1}{2}(m + \sqrt{m} log m) + ℓ − 1))}

· \frac{1}{exp ((−\frac{log m}{\sqrt{m}} − \frac{log^{2} m}{2m} + O (\frac{log^{3} m}{m\sqrt{m}})) (\frac{1}{2}(m − \sqrt{m} log m) + ℓ − 1))}

= (1 + O(log^{3} m/\sqrt{m})) ∏_{ℓ=1}^{p}(ℓ − 1)!\frac{2^{m+2ℓ−1}}{m^{ℓ−1}\sqrt{πm}}e^{− \frac{1}{2} log^{2} m}

= (1 + O(log^{3} m/\sqrt{m}))\frac{2^{pm+p^{2}}}{m^{p^{2}/2}π^{p/2}} m^{− \frac{p}{2} log m} ∏_{ℓ=1}^{p}(ℓ − 1)!

= O(1/m^{3}),

because the term m^{\frac{1}{2} p log m} which appears in the denominator of the expression in the next-to-last line grows super exponentially. Therefore, the first term in (6.4) is

O(\frac{1}{2}(m − \sqrt{m} log m)/m^{3}) = O(1/m).

The second term in (6.4) is equal to the first term, hence has the same order of magnitude.

Now we turn to the third term in (6.4). To carry out our computations, we would have to distinguish between two cases, depending on whether m is even or odd. The computations in both cases are however rather similar. Therefore we carry them out in detail just for the case that m is even and leave it to the reader to complete the computations for the other case.

In the case that m is even, the third term in (6.4), after replacement of k by 2k, becomes

∑_{|k|≤ \frac{1}{2} \sqrt{m} log m} ∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(m/2 + k + ℓ − 1)! (m/2 − k + ℓ − 1)!}.  (6.5)

For nonnegative k, we may rewrite the summand as

∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(\frac{m}{2} + ℓ − 1)!^{2}} · \frac{(\frac{m}{2} − k + ℓ)(\frac{m}{2} − k + ℓ + 1) · (\frac{m}{2} + ℓ − 1)}{(\frac{m}{2} + ℓ)(\frac{m}{2} + ℓ + 1) · (\frac{m}{2} + k + ℓ − 1)}

= ∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(\frac{m}{2} + ℓ − 1)!^{2}} · \frac{(1 + \frac{−k+ℓ}{m/2})(1 + \frac{−k+ℓ+1}{m/2}) · (1 + \frac{ℓ−1}{m/2})}{(1 + \frac{ℓ}{m/2})(1 + \frac{ℓ+1}{m/2}) · (1 + \frac{k+ℓ−1}{m/2})}

= ∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(\frac{m}{2} + ℓ − 1)!^{2}} · e^{− \frac{2}{m} k^{2}+O(k^{3}/m^{2})}.  (6.6)

For nonpositive k there is a similar computation which leads to the same result.

We have to sum the expression (6.6) over k between −\frac{1}{2} \sqrt{m} log m and \frac{1}{2} \sqrt{m} log m. In that range, the O(.) term is at worst O(m^{−1/2} log^{3} m). Thus, the sum (6.5) turns into

( ∑_{|k|≤ \frac{1}{2} \sqrt{m} log m} e^{− \frac{2p}{m} k^{2}})(1 + O(m^{−1/2} log^{3} m)) ∏_{ℓ=1}^{p} \frac{(m + ℓ − 1)! (ℓ − 1)!}{(\frac{m}{2} + ℓ − 1)!^{2}}.  (6.7)

If we extend the sum to run over all integers k then we make an error which is bounded by O(1/m). The complete sum ∑_{k=−∞}^{∞} e^{− \frac{2p}{m} k^{2}} can be approximated by Lemma A1 with b = 0, N = 0 and α = −2p/m. The asymptotics of the product in (6.7) is easily determined by using Stirling’s formula. Thus we obtain (6.2).

Theorem 12. The number of ∞-friendly watermelons in the TK model with p branches of length m (and arbitrary deviation) is asymptotically

2^{mp+2p^{2}−3p/2−1/2}m^{−p^{2}/2+1/2}π^{−p/2+1/2}p^{−1/2}( ∏_{ℓ=1}^{p}(ℓ − 1)!)(1 + O(m^{−1/2} log^{3} m)) (6.8)

as m tends to infinity.

Proof. The first step is the same as in the proof of Theorem 4. We transform ∞- friendly watermelons into families of non-intersecting lattice paths by shifting the i-th path up by 2(i − 1) units. Thus, ∞-friendly watermelons with p branches of length m and deviation k are in bijection with families (P_{1}, P_{2}, …, P_{p}) of non-intersecting lattice paths, P_{i} running from (0, 4(i − 1)) to (m, k + 4(i − 1)), i = 1, 2, …, p. The number of such families of non-intersecting lattice paths is given by the corresponding Lindström–Gessel-Viennot determinant (see Proposition A2),

det_{1≤i,j≤p} (\binom{m}{\frac{m+k}{2} + 2i − 2j}) .  (6.9)

Consequently, our task is to sum (6.9) over all k ≡ m (mod 2), −m ≤ k ≤ m, and approximate the sum as m tends to infinity. The procedure is quite similar to the proof of Theorem 11, with the complication that (6.9) cannot be written in closed form.

To begin with, we bring the determinant (6.9) into a more convenient form, by taking out some factors,

det_{1≤i,j≤p} (\binom{m}{\frac{m+k}{2} + 2i − 2j}) = ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m+k}{2} + 2ℓ − 2)! (\frac{m−k}{2} − 2ℓ + 2p)!}

× det_{1≤i,j≤p} ((\frac{m+k}{2} + 2i − 2j + 1)_{2j−2} (\frac{m−k}{2} − 2i + 2j + 1)_{2p−2j}). (6.10)

The determinant in (6.10) is a polynomial in m and k, of degree at most 4\binom{p}{2},

det_{1≤i,j≤p} ((\frac{m+k}{2} + 2i − 2j + 1)_{2j−2} (\frac{m−k}{2} − 2i + 2j + 1)_{2p−2j}) = ∑_{0≤s+t≤4\binom{p}{2}} A(s, t)m^{s}k^{t} (6.11)

say. We claim that, for our asymptotic considerations, it is sufficient to just consider the leading terms on the right-hand side of (6.11). For, consider a single term A(s, t)m^{s}k^{t} on the right-hand side of (6.11). It has to be multiplied by the product on the righthand side of (6.10), and the resulting expression is summed over all k ≡ m (mod 2), −m ≤ k ≤ m, so that one obtains

∑_{k≡m (mod 2)} A(s, t)m^{s}k^{t} ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m+k}{2} + 2ℓ − 2)! (\frac{m−k}{2} − 2ℓ + 2p)}.

This is now handled in the same way as the sum (6.3). In essence, it is the expression (compare (6.7))

∑_{k} A(s, t)m^{s}(2k)^{t}e^{− \frac{2p}{m} k^{2}} ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m}{2} + 2ℓ − 2)! (\frac{m}{2} − 2ℓ + 2p)}

that needs to be estimated. By (A.1) with b = 0, N = t and α = 2p/m, this is

A(s, t)m^{s+t/2+1/2}2^{t/2−3/2}p^{−t/2−1/2}Γ(\frac{t}{2} + \frac{1}{2})(1 + O(m^{−1/2} log^{3} m))

× ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m}{2} + 2ℓ − 2)! (\frac{m}{2} − 2ℓ + 2p)}. (6.12)

Obviously, the larger s and t are, the larger will be the contribution of the corresponding term, the largest coming from those for which s + t/2 is maximal.

As it turns out, the actual degree in m and k of the leading terms of the determinant in (6.11) is significantly smaller than 4\binom{p}{2}. To see what it is, and what the leading terms are, we consider a more general determinant,

det_{1≤i,j≤p} ((\frac{m}{2} + X_{i} − 2j + 1)_{2j−2} (\frac{m}{2} − X_{i} + 2j + 1)_{2p−2j}).  (6.13)

Clearly, we regain the determinant in (6.11) for X_{i} = 2i + k/2.

The determinant in (6.13) is a polynomial in m and the X_{i}’s of degree 4\binom{p}{2}. It is divisible by ∏_{1≤i<j≤p}(X_{j} − X_{i}). Therefore the degree in m and k, after substitution of X_{i} = 2i + k/2, i = 1, 2, …, p, of the determinant in (6.11) is at most 3\binom{p}{2}.

The leading term of (6.13) is

det_{1≤i,j≤p}((\frac{m}{2} + X_{i})^{2j−2} (\frac{m}{2} − X_{i})^{2p−2j}) = (\frac{m}{2} − X_{i})^{p(2p−2)} det_{1≤i,j≤p} (( \frac{\frac{m}{2} + X_{i}}{\frac{m}{2} − X_{i}} )^{2j−2})

= ∏_{1≤i<j≤p} ((\frac{m}{2} + X_{j})^{2}(\frac{m}{2} − X_{i})^{2} − (\frac{m}{2} + X_{i})^{2}(\frac{m}{2} − X_{j})^{2})

= ∏_{1≤i<j≤p}(X_{j} − X_{i}) m ((\frac{m}{2} + X_{j})(\frac{m}{2} − X_{i}) + (\frac{m}{2} + X_{i})(\frac{m}{2} − X_{j})) .

(Clearly, the determinant evaluation used to get from the first to the second line is the Vandermonde determinant evaluation.) The leading term of the determinant in (6.11) is this expression under the substitution of X_{i} = 2i + k/2, i = 1, 2, …, p, which equals

∏_{1≤i<j≤p}(2j − 2i) m (\frac{m^{2}}{2} − \frac{k^{2}}{2} − 2ik − 2jk − 4ij) = m^{3\binom{p}{2}} ∏_{ℓ=1}^{p}(ℓ − 1)!(1 + O(k^{2}/m^{2})).

Hence, in order to compute the asymptotics of the sum of (6.9) over all k ≡ m (mod 2), it suffices to determine the asymptotics of the sum over all k ≡ m (mod 2) of (recall (6.10) and the remark after (6.12))

m^{3\binom{p}{2}} ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! m!}{(\frac{m+k}{2} + 2ℓ − 2)! (\frac{m−k}{2} − 2ℓ + 2p)}.

As the considerations leading to (6.12) showed, this can be handled completely analogously to the computation of the asymptotics of the sum (6.3). The result is exactly (6.8).

Since the expressions (6.2) and (6.8) are identical except for a multiplicative constant of 2^{p^{2}−p}, we obtain as a consequence the following result for n-friendly models.

Corollary 13. As m tends to infinity, n-friendly watermelons with p branches of length m (and arbitrary deviation) have, up to a multiplicative constant, the same asymptotic behaviour, for the GV as well as for the TK model. More precisely, the number of n-friendly watermelons with p branches of length m is ≍ 2^{mp}m^{−p^{2}/2+1/2}, i.e., there are positive constants f_{1} and f_{2} such that for large enough m this number is between f_{1}2^{mp}m^{−p^{2}/2+1/2} and f_{2}2^{mp}m^{−p^{2}/2+1/2}. Under the assumption that there is a constant f(n) such that this number is asymptotically exactly equal to f(n)2^{mp}m^{−p^{2}/2+1/2}, then we must have f(0) < f(1) < f(2) < ⋯, i.e., for any n there are, asymptotically, strictly less n-friendly watermelons with p branches of length m than (n+1)-friendly watermelons with p branches of length m.

This follows without difficulty from Theorems 11 and 12, in the same way as Corollary 5 follows from Theorems 3 and 4.

Clearly, there is abundant evidence that for any fixed p there exist such constants f(0), f(1), etc. By Theorems 11 and 12 we have computed f(0) and f(∞). It appears to be a challenging problem to determine the other constants, and even just f(1). However, for p = 2 we can calculate f(k) from the data given in [22], and find f(k) = \frac{16}{(1+2^{−k})^{2}\sqrt{π}}. This result supports our assertion regarding the existence of this increasing sequence of constants.

7. Enumeration of watermelons with given deviation, with wall restriction

The number of such watermelons follows immediately from Theorem 6 upon setting m = n and e_{i} = k + 2(i − 1). After a little simplification we arrive at

Corollary 14. The number of watermelons of length m with p branches which do not go below the x-axis, and with deviation k ≥ 0 equals

∏_{i=0}^{\frac{p}{2} −1} \frac{(k + 2p − 1 − 2i)!}{(k + 2i)!} ∏_{j=0}^{p−1} \frac{(m + 2j)!j!}{(\frac{m−k}{2} + j)!(\frac{m+k}{2} + j + p)!}.  (7.1)

An alternative expression follows by elementary manipulation of the above expression, and is

∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (k + 2ℓ − 1)_{p−ℓ+1} (m + 2ℓ − 2)!}{(\frac{m+k}{2} + ℓ + p − 1)! (\frac{m−k}{2} + ℓ − 1)!}.  (7.2)

From this second expression we can derive the following theorem for the asymptotic number of such watermelons, viz.

Theorem 15. The number of watermelons with p branches of length m (and arbitrary deviation) which do not go below the x-axis is asymptotically

2^{mp+9p^{2}/4−p/4−3/2}m^{−3p^{2}/4−p/4+1/2}π^{−p/2}p^{−p^{2}/4−p/4−1/2}

× Γ (\frac{p^{2}}{4} + \frac{p}{4} + \frac{1}{2}) ( ∏_{ℓ=1}^{p}(ℓ − 1)!)(1 + O(m^{−1/2} log^{3} m)) (7.3)

as m tends to infinity.

Proof. The number of watermelons with p branches of length m and with deviation k (where k ≡ m (mod 2)) which do not go below the x-axis is given by (7.2). We wish to sum this expression over all k ≥ 0 with k ≡ m (mod 2) and then approximate it. This is done completely analogously to the proof of Theorem 11. The only difference is that here the sum does not extend to negative k. Again, the dominant terms are those for k ∼ 0. Therefore we concentrate on the terms for 0 ≤ k ≤ \sqrt{m} log m. The other terms are negligible, as is seen in the same way as in the proof of Theorem 11. For carrying out the computations, we would again have to distinguish between the two cases of m being even or odd. Also here, the computations are rather parallel. So let us assume in the following that m is even.

If we carry out the computations parallel to those leading from (6.5) to (6.7), then we see that the sum over all even k ≥ 0 of (7.2) is asymptotically

( ∑_{k=0}^{∞} e^{− \frac{2p}{m} k^{2}} ∏_{ℓ=1}^{p}(2k + 2ℓ − 1)_{p−ℓ+1}) ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (m + 2ℓ − 2)!}{(\frac{m}{2} + ℓ + p − 1)! (\frac{m}{2} + ℓ − 1)!}

× (1 + O(m^{−1/2} log^{3} m)). (7.4)

The sum in this expression can be split into a linear combination of sums of the form ∑_{k=0}^{∞} k^{N}e^{− \frac{2p}{m} k^{2}}. The asymptotics of the latter are given by Lemma A1. It implies particularly that the largest contribution would come from the term where the exponent N of k is maximal. This term is

∑_{k=0}^{∞} 2^{\binom{p+1}{2}}k^{\binom{p+1}{2}}e^{− \frac{2p}{m} k^{2}},

which by (A.1) gives a contribution of \frac{1}{2}(m/2p)^{p^{2}/4+p/4+1/2}Γ(p^{2}/4 + p/4 + 1/2). The asymptotics of the product in (7.4) is easily determined by using Stirling’s formula. Putting everything together we obtain (7.3).

Next we consider the ∞-friendly model for watermelons with wall restriction.

Theorem 16. The number of ∞-friendly watermelons in the TK model with p branches of length m (and arbitrary deviation) which do not go below the x-axis is asymptotically

2^{mp+9p^{2}/4−9p/4−3/2}m^{−3p^{2}/4−p/4+1/2}π^{−p/2}p^{−p^{2}/4−p/4−1/2}

× Γ (\frac{p^{2}}{4} + \frac{p}{4} + \frac{1}{2}) ( ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (2ℓ − 2)! (4ℓ − 2)!}{(ℓ + p − 1)!^{2}})(1 + O(m^{−1/2} log^{3} m)) (7.5)

as m tends to infinity.

Proof. As we have already seen, in the context of ∞-friendly models the situation is more difficult, because we do not have a nice closed product formula (such as (7.2)) for the number of ∞-friendly watermelons.

The first step is the same as in the proof of Theorem 4. We transform ∞-friendly watermelon into families of nonintersecting lattice paths by shifting the i-th path up by 2(i−1) units. Thus, ∞-friendly watermelons with p branches of length m and deviation k which do not go below the x-axis are in bijection with families (P_{1}, P_{2}, …, P_{p}) of nonintersecting lattice paths which do not go below the x-axis, P_{i} running from A_{i} = (0, 4(i − 1)) to E_{i} = (m, k + 4(i − 1)), i = 1, 2, …, p.

The number of these families of nonintersecting lattice paths is given by the Lindström–Gessel–Viennot determinant (see Proposition A2),

det_{1≤i,j≤p} ( |P^{+}(A_{j} → E_{i})| ),  (7.6)

where P^{+}(A → E) denotes the set of all lattice paths from A to E that do not go below the x-axis. By the “reflection principle” (see e.g. [8, p. 22]), each path number |P^{+}(A_{j} → E_{i})| can then be written as a difference of two binomials. Thus we obtain the determinant

det_{1≤i,j≤p} (\binom{m}{\frac{m−k}{2} + 2j − 2i} − \binom{m}{\frac{m+k}{2} + 2j + 2i − 3})  (7.7)

for the number of watermelons under consideration.

We have to sum (7.7) over all k ≡ m (mod 2), −m ≤ k ≤ m, and approximate the sum as m tends to infinity. Having carried out many similar proofs before, in particular the proof of Theorem 12, we have seen how to approach this problem. As in the proof of Theorem 12, we need to determine the leading terms of (7.7).

Once more, we bring the determinant (7.7) into a more convenient form, by taking out some factors,

det_{1≤i,j≤p} (\binom{m}{\frac{m−k}{2} + 2j − 2i} − \binom{m}{\frac{m+k}{2} + 2j + 2i − 3})

= ∏_{ℓ=1}^{p} \frac{m!}{(\frac{m+k}{2} + 2ℓ + 2p − 3)! (\frac{m−k}{2} − 2ℓ + 2p)!}

× det_{1≤i,j≤p} ((\frac{m+k}{2} + 2i − 2j + 1)_{2p+2j−3} (\frac{m−k}{2} − 2i + 2j + 1)_{2p−2j}

− (\frac{m+k}{2} + 2i + 2j − 2)_{2p−2j} (\frac{m−k}{2} − 2i − 2j + 4)_{2p+2j−3}). (7.8)

This determinant is exactly the determinant (5.8) with X_{i} = 2i + k/2 − 3/2. Thus, the leading term of the determinant in (7.8) is obtained from (5.9) under the substitution of X_{i} = 2i + k/2 − 3/2, i = 1, 2, …, p. This substitution turns (5.9) into

m^{3p^{2}−3p}2^{−p^{2}+p} ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (2ℓ − 2)! (4ℓ − 4)!}{(ℓ + p − 1)!^{2}} ∏_{ℓ=1}^{p}(2ℓ + \frac{k}{2} − \frac{1}{2})_{p−ℓ} ∏_{ℓ=1}^{p}(2ℓ + \frac{k}{2} − \frac{3}{2})

+ lower terms.

When expanded, the term in this expression which will give the largest contribution is

k^{\binom{p+1}{2}}m^{3p^{2}−3p}2^{−3p^{2}/2+p/2} ∏_{ℓ=1}^{p} \frac{(ℓ − 1)! (2ℓ − 2)! (4ℓ − 4)!}{(ℓ + p − 1)!^{2}}.

What remains to do is to multiply this expression by the product on the right-hand side of (7.8), then sum the resulting expression over all k ≥ 0 with k ≡ m mod 2, manipulate the summand in a way analogous to the manipulations in (6.6), and finally estimate the result using Lemma A1. After simplification, the final result is (7.5).

Again, since the expressions (7.3) and (7.5) are identical except for a multiplicative constant, we obtain as a consequence the following result for n-friendly models.

Corollary 17. As m tends to infinity, n-friendly watermelons with p branches of length m (and arbitrary deviation) which do not go below the x-axis have, up to a multiplicative constant, the same asymptotic behaviour, for the GV as well as for the TK model. More precisely, the number of n-friendly watermelons with p branches of length m which do not go below the x-axis is ≍ 2^{mp}m^{−3p^{2}/4−p/4+1/2}, i.e., there are positive constants g_{1} and g_{2} such that for large enough m this number is between g_{1}2^{mp}m^{−3p^{2}/4−p/4+1/2} and g_{2}2^{mp}m^{−3p^{2}/4−p/4+1/2}. Under the assumption that there is a constant g(n) such that this number is asymptotically exactly equal to g(n)2^{mp}m^{−3p^{2}/4−p/4+1/2}, then we must have g(0) < g(1) < g(2) < ⋯, i.e., for any n there are, asymptotically, strictly less n-friendly watermelons with p branches of length m which do not go below the x-axis than (n + 1)-friendly watermelons with p branches of length m which do not go below the x-axis.

This follows without difficulty from Theorems 15 and 16, in the same way as Corollary 5 follows from Theorems 3 and 4.

Clearly, there is abundant evidence that for any fixed p there exist such constants g(0), g(1), etc. By Theorems 15 and 16 we have computed g(0) and g(∞). It appears to be a challenging problem to determine the other constants, and even just g(1).

8. Conclusion

We have derived new results for the number of star and watermelon configurations of vicious walkers both in the absence and in the presence of an impenetrable wall by showing how these results follow from standard results in the theory of Young tableaux, and combinatorial descriptions of symmetric functions. We present the theory of asymptotic expansions of determinants, and apply this to obtain asymptotic expressions for the above quantities. We then apply these asymptotic methods to the broader question of n-friendly walkers, both in the presence and in the absence of a wall, and give asymptotic expansions for stars and watermelons in all cases.

Acknowledgements

We are particularly grateful to John Essam for pointing out problems in proofs and definitions in an earlier version of the paper. We would like to thank Richard Brak and Peter Forrester for comments on the manuscript. One of us (AJG) wishes to acknowledge the financial support of the Australian Research Council. Another, (XGV) is grateful to the Department of Mathematics and Statistics at The University of Melbourne, where some of this work was carried out. Finally, (CK) acknowledges the financial support of the Austrian Science Foundation FWF, grants P12094-MAT and P13190-MAT.

Appendix

In this appendix we collect together the tools used in the analysis carried out in the body of the paper. These comprise certain basic asymptotic results, the determinantal and Pfaffian formulae for the enumeration of nonintersecting lattice paths with fixed and with arbitrary endpoints, and the evaluation of certain determinants and Pfaffians.

Appendix A. Asymptotics

Aside from Stirling’s formula, the approximation that we use extensively throughout is the following:

Lemma A1. Let N and b be nonnegative integers. Then, as α tends to 0^{+},

∑_{k=b}^{∞} k^{N}e^{−αk^{2}} = ∫_{b}^{∞} y^{N}e^{−αy^{2}} dy + O(1) = \frac{Γ (\frac{N}{2} + \frac{1}{2})}{2 α^{N/2+1/2}} + O(1),  (A.1)

where the constant in the error term O(1) can be chosen so that it is independent of b.

Proof. We first prove (A.1) for b = 0. The Poisson summation theorem (see [37, (5.75) with a = 0], [52, (2.8.1)]) says that

∑_{k=−∞}^{∞} f(k) = ∑_{m=−∞}^{∞} ∫_{−∞}^{∞} f(y)e^{−2πimy} dy,  (A.2)

for suitable functions f. It is for example valid for continuous, absolutely integrable functions f of bounded variation. The choice of f(x) = e^{−αx^{2}} in (A.2) gives (A.1) for N = 0 upon little manipulation. From now on let N ≥ 1. In (A.2) we choose

f(x) = \begin{cases}x^{N} · e^{−αx^{2}} & x ≥ 0, \\ 0 & x < 0. \end{cases}  (A.3)

This function does satisfy the above mentioned requirements. Thus we obtain

∑_{k=0}^{∞} k^{N}e^{−αk^{2}} = ∑_{m=−∞}^{∞} e^{−π^{2}m^{2}/α} ∫_{0}^{∞} y^{N}e^{−α(y+πim/α)^{2}} dy

= ∫_{0}^{∞} y^{N}e^{−αy^{2}} dy + ∑_{m=1}^{∞} e^{−π^{2}m^{2}/α} ∫_{−∞}^{∞} |y|^{N}e^{−α(y+πim/α)^{2}} dy

= ∫_{0}^{∞} y^{N}e^{−αy^{2}} dy + ∑_{m=1}^{∞} e^{−π^{2}m^{2}/α} ∫_{−∞}^{∞} |y − \frac{πim}{α} |^{N} e^{−αy^{2}} dy.  (A.4)

(To justify that we may take the latter integral over real y instead of over y with imaginary part πim/α, it suffices to observe that the contour integral of the integrand along the rectangle connecting the extremal points −M − πim/α, M − πim/α, M + πim/α, −M + πim/α vanishes, and that the integrals along the vertical sides of the rectangle tend to zero as M approaches infinity.) Next we approximate the integral which appears in the sum. We split the integral into two parts,

∫_{−∞}^{∞} |y − \frac{πim}{α} |^{N} e^{−αy^{2}} dy = ∫_{|y|≥ \frac{πm}{α\sqrt{3}}} |y − \frac{πim}{α} |^{N} e^{−αy^{2}} dy + ∫_{|y|< \frac{πm}{α\sqrt{3}}} |y − \frac{πim}{α} |^{N} e^{−αy^{2}} dy.

For the first part, i.e., for |y| ≥ \frac{πm}{α\sqrt{3}} and y real, we have |y − \frac{πim}{α} | ≤ 2 |y|. For the second part, i.e., for |y| < \frac{πm}{α\sqrt{3}} and y real, we have |y − \frac{πim}{α} | ≤ \frac{2πm}{α\sqrt{3}}. Thus we obtain

∫_{−∞}^{∞} |y − \frac{πim}{α} |^{N} e^{−αy^{2}} dy ≤ ∫_{|y|≥ \frac{πm}{α\sqrt{3}}} (2 |y|)^{N}e^{−αy^{2}} dy + ∫_{|y|< \frac{πm}{α\sqrt{3}}} (\frac{2πm}{α\sqrt{3}})^{N} e^{−αy^{2}} dy

≤ 2^{N} ∫_{−∞}^{∞} |y|^{N} e^{−αy^{2}} dy + (\frac{2πm}{α\sqrt{3}})^{N} ∫_{−∞}^{∞} e^{−αy^{2}} dy.

The integrals in the last line are easily evaluated by recalling one of the definitions of the gamma function (see [11, 1.1(1)]),

Γ(x) = ∫_{0}^{∞} t^{x−1}e^{−t} dt.  (A.5)

For, substitution of −αy^{2} for t and replacement of x by (N + 1)/2 yields

∫_{0}^{∞} y^{N}e^{−αy^{2}} dy = \frac{Γ (\frac{N}{2} + \frac{1}{2})}{2 α^{N/2+1/2}}.

Combining all this and substituting back into (A.4), we get

∑_{k=0}^{∞} k^{N}e^{−αk^{2}} = \frac{Γ (\frac{N}{2} + \frac{1}{2})}{2 α^{N/2+1/2}} + O (∑_{m=1}^{∞} e^{−π^{2}m^{2}/α} (2^{N+1} \frac{Γ (\frac{N}{2} + \frac{1}{2})}{2 α^{N/2+1/2}} + (\frac{2πm}{α\sqrt{3}})^{N} \begin{matrix}√ & \overline{π} \\ √ & \overline{α} \end{matrix})) .

The appearance of the exponential e^{−π^{2}m^{2}/α} makes the O(.) term “arbitrarily” small. Thus, (A.1) with b = 0 follows immediately.

To establish (A.1) in full generality, one would proceed in the same way. One would apply the Poisson summation theorem (A.2) with g(x)f(x) instead of f(x), with f(x) given by (A.3) as before, and g(x) some suitably “nice” function with g(x) = 0 for x ≤ b − ε and g(x) = 1 for x ≥ b, ε ≥ 0. Everything else is completely analogous. The result is then obtained by letting ε → 0.

Appendix B. The enumeration of nonintersecting lattice paths

If one wants to enumerate nonintersecting lattice paths with given starting and end points, then the solution is given by the Lindström–Gessel–Viennot determinant [32, Lemma 1], [18, Corollary 2] (cf. also [28] and [27] for continuous and probabilistic versions of the same problem),

Proposition A2. Let A_{1}, A_{2}, …, A_{p} and E_{1}, E_{2}, …, E_{p} be lattice points, with the property that if 1 ≤ i < j ≤ p and 1 ≤ k < l ≤ p, then any path from A_{i} to E_{l} must intersect any path from A_{j} to E_{k}. Then the number of families (P_{1}, P_{2}, …, P_{p}) of nonintersecting lattice paths, where P_{i} runs from A_{i} to E_{i}, i = 1, 2, …, p, is given by

det_{1≤i,j≤p} ( |P (A_{j} → E_{i})| ),  (B.1)

where P (A → E) denotes the set of all lattice paths from A to E.

If, however, we want to enumerate nonintersecting lattice paths with given starting points, but where the end points may be any points from a given set of points, then the solution can be given in terms of a Pfaffian, as was shown by Okada [38, Theorem 3] and Stembridge [50, Theorem 3.1].

Proposition A3. Let p be even. Let A_{1}, A_{2}, …, A_{p} be lattice points, and let E = {E_{i} : i ∈ I} be a set of lattice points, where I is a linearly ordered set of indices, with the property that if 1 ≤ i < j ≤ p and k, l ∈ I, k < l, then any path from A_{i} to E_{l} must intersect any path from A_{j} to E_{k}. Then the number of families (P_{1}, P_{2}, …, P_{p}) of nonintersecting lattice paths, where P_{i} runs from A_{i} to some point in the set I, is given by

Pf_{1≤i<j≤p}(Q_{E}(A_{i}, A_{j})),  (B.2)

where Q_{E}(A_{i}, A_{j}) is the number of all pairs of nonintersecting lattice paths, one connecting A_{i} to E, the other connecting A_{j} to E.

Appendix C. Some determinants

In our computations we need the following determinant evaluations. All of them are readily proved by the standard argument that proves Vandermonde-type determinant evaluations.

Lemma A4. Let N by a nonnegative integer. Then

det_{1≤i,j≤N} (x_{i}^{j} + x_{i}^{1−j}) = (x_{1}x_{2} ⋯ x_{N})^{1−N} ∏_{1≤i<j≤N}(x_{i} − x_{j})(1 − x_{i}x_{j}) ∏_{i=1}^{N}(x_{i} + 1), (C.1)

det_{1≤i,j≤N} (x_{i}^{j} − x_{i}^{−j}) = (x_{1}x_{2} ⋯ x_{N})^{−N} ∏_{1≤i<j≤N}(x_{i} − x_{j})(1 − x_{i}x_{j}) ∏_{i=1}^{N}(x_{i}^{2} − 1) (C.2)

det_{1≤i,j≤N} (x_{i}^{j−1/2} − x_{i}^{−j+1/2}) = (x_{1}x_{2} ⋯ x_{N})^{−N+1/2} ∏_{1≤i<j≤N}(x_{i} − x_{j})(1 − x_{i}x_{j}) ∏_{i=1}^{N}(x_{i} − 1). (C.3)

In the proof of Theorem 16 we need to express another, very similar determinant in terms of odd orthogonal characters. The latter are defined by (3.3). A combination of (3.3) with λ = (N − 1, N − 2, …, 1, 0) and (C.3) gives

det_{1≤i,j≤N} (x_{i}^{2j−3/2} − x_{i}^{−2j+3/2}) = det_{1≤i,j≤N} (x_{i}^{j−1/2} − x_{i}^{−j+1/2})

× so_{(N−1,N−2,...,1,0)}(x_{1}^{±1}, x_{2}^{±1}, …, x_{N}^{±1}, 1)

= (x_{1}x_{2} ⋯ x_{N})^{−N+1/2} ∏_{1≤i<j≤N}(x_{i} − x_{j})(1 − x_{i}x_{j}) ∏_{i=1}^{N}(x_{i} − 1)

× so_{(N−1,N−2,...,1,0)}(x_{1}^{±1}, x_{2}^{±1}, …, x_{N}^{±1}, 1). (C.4)

References

[1] G. E. Andrews, Plane partitions (II): The equivalence of the Bender–Knuth and the MacMahon conjectures, Pacific J. Math. 72 (1977), 283–291.

[2] D. K. Arrowsmith, P. Mason and J. W. Essam, Vicious walkers, flows and directed percolation. Current problems in statistical mechanics, Physica A 177 (1991), 267–272.

[3] J. Baik, Random vicious walks and random matrices, math.PR/0001022 and Commun. Pure Appl. Math. (to appear).

[4] M. Bousquet–Mélou and L. Habsieger, Sur les matrices à signes alternants, Discrete Math. 139 (1995), 57–72.

[5] R. Brak and J. W. Essam, Contact polynomials for non-intersecting paths above a surface, (preprint).

[6] D. M. Bressoud, Elementary proof of MacMahon’s conjecture, J. Alg. Combin. 7 (1998), 253–257.

[7] D. M. Bressoud, Proofs and confirmations — The story of the alternating sign matrix conjecture, Cambridge University Press, Cambridge, 1999.

[8] L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, Holland, 1974.

[9] J. Désarménien, La démonstration des identités de Gordon et MacMahon et de deux identités nouvelles, in: Actes de 15^{e} Séminaire Lotharingien, I. R. M. A. Strasbourg, 1987, 39–49.

[10] N. El-Samra and R. C. King, Dimensions of irreducible representations of the classical Lie groups, J. Phys. A: Math. Gen. 12 (1979), 2317–2328.

[11] A. Erdélyi, V. Magnus, F. Oberhettinger and F. Tricomi, Higher transcendental functions, McGraw–Hill, New York, 1953.

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

[13] M. E. Fisher, Walks, walls, wetting, and melting, J. Stat. Phys. 34 (1984), 667–729.

[14] P. J. Forrester, Probability of survival for vicious walkers near a cliff, J. Phys. A 22 (1989), L609–L613.

[15] M. Fulmek and C. Krattenthaler, Lattice path proofs for determinant formulas for symplectic and orthogonal characters, J. Combin. Theory Ser. A 77 (1998), 3–50.

[16] W. Fulton and J. Harris, Representation Theory, Springer–Verlag, New York, 1991.

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

[18] I. M. Gessel and X. G. Viennot, Determinants, paths, and plane partitions, preprint, 1989.

[19] B. Gordon, Notes on plane partitions V, J. Combin. Theory 11 (1971), 157–168.

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

[21] A. J. Guttmann, A. L. Owczarek and X. G. Viennot, Vicious walkers and Young tableaux. I. Without walls, J. Phys. A, 31, (1998), 8123–8135.

[22] A. J. Guttmann and M. Vöge, Lattice paths: vicious walkers and friendly walkers, J. Statistical Plann. Inf. (to appear).

[23] M. Haiman, On mixed insertion, symmetry, and shifted Young tableaux, J. Combin. Theory Ser. A 50 (1989), 196–225.

[24] A. R. Its, C. A. Tracy and H. Widom, Random Words, Toeplitz Determinants and Integrable Systems, II, arXiv:nlin.SI/0004018, (2000).

[25] K. Johansson, Shape fluctuations and random matrices, Commun. Math. Phys. 209 (2) (2000), 437–476.

[26] M. Kardar, G. Parisi and Y.-Z. Zhang, Dynamic scaling of growing interfaces, Phys Rev. Letts. 56 (1986), 889–892.

[27] S. Karlin, Coincident probabilities and applications in combinatorics, J. Appl. Probab. 25A (1988), 185–200.

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

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

[30] 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.

[31] C. Krattenthaler, Identities for classical group characters of nearly rectangular shape, J. Algebra 209 (1998), 1–64.

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

[33] D. E. Littlewood, The theory of group characters and matrix representations of groups, Oxford University Press, Oxford, 1940.

[34] I. G. Macdonald, Some conjectures for root systems, SIAM J. Math. Anal. 13 (1982), 988-1007.

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

[36] S. G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

[37] A. M. Odlyzko, Asymptotic enumeration methods, in: Handbook of Combinatorics, vol. II, R. L. Graham, M. Grötschel, L. Lovász, eds., The M.I.T. Press, Cambridge, Massachusetts, 1995.

[38] S. Okada, On the generating functions for certain classes of plane partitions, J. Combin. Theory Ser. A 51 (1989), 1–23.

[39] S. Okada, Applications of minor summation formulas to rectangular-shaped representations of classical groups, J. Algebra 205 (1998), 337–368.

[40] M. Prähofer and H. Spohn, Statistical Self-similarity of One-dimensional Growth Processes, cond-mat/9910273 and Physica A (to appear).

[41] M. Prähofer and H. Spohn, Universal distributions for Growth Processes in 1+1 dimensions and

    random matrices, cond-mat/9912264.

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

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

[44] R. A. Proctor, Shifted plane partitions of trapezoidal shape, Proc. Amer. Math. Soc. 89 (1983), 553–559.

[45] R. A. Proctor, Young tableaux, Gelfand patterns, and branching rules for classical groups, J. Algebra 164 (1994), 299–360.

[46] R. A. Proctor, New symmetric plane partition identities from invariant theory work of DeConcini and Procesi, Europ. J. Combin. 11 (1990), 289–300.

[47] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), 115–136.

[48] M.-P. Schützenberger, La correspondance de Robinson, in: “Combinatoire et Représentation du Groupe Symétrique”, Lecture Notes in Math., vol. 579, Springer–Verlag, Berlin–Heidelberg–New York, 1977, 59–113.

[49] A. Selberg, Bemerkninger om et multiplet integral, Norsk Mat. Tidsskr. 26 (1944), 71–79.

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

[51] S. Sundaram, Tableaux in the representation theory of the classical Lie groups, in: “Invariant theory and tableaux”, D. Stanton, ed., The IMA Volumes in Math. And Its Appl., Vol. 19, Springer–Verlag, New York, Berlin, Heidelberg, 1989, 191–225.

[52] E. C. Titchmarsh, Introduction to the theory of Fourier integrals, Oxford University Press, Oxford, 1937.

[53] T. Tsuchiya and M. Katori, Chiral Potts models, Friendly Walkers and Directed Percolation Problem J. Phys. Soc. Japan, 67 (1988), 1655-66.

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

†Department of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia

‡LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France.