Séminaire Lotharingien de Combinatoire 52 (2004), Article B52b

NONINTERSECTING LATTICE PATHS ON THE CYLINDER

MARKUS FULMEK

Abstract. We show how a formula concerning “vicious walkers” (which basically are nonintersecting lattice paths) on the cylinder given by P.J. Forrester can be proved and generalized by using the Lindström–Gessel–Viennot method, after having things set up in the right way. We apply the corresponding results to the (thermodynamic limit of the) free energy of the “lock step model of vicious walkers”, thus completing (and in one instance correcting) the work of Forrester. Moreover, we also show how a related formula given by I. Gessel and C. Krattenthaler can be obtained from the same “point of view”.

1. Introduction

In this paper, we consider interesting formulas concerning nonintersecting lattice paths on the cylinder, and show how the well–known Lindström–Gessel–Viennot method provides a common and quite simple framework for proving them.

We also consider the asymptotic behaviour of these formulas (i.e., we determine the thermodynamic limit of the free energy of the “lock step model of vicious walkers”) and correct a small error in the respective formula [3, (2.33)] given by Forrester.

1.1. Forrester’s formula. In his paper [3], Forrester considered the generating function of certain “vicious walkers” [3, Theorem 2.1]. The model of vicious walkers was originally introduced by Fisher [2]. In combinatorial terms, Forrester’s formula simply gives the enumeration of nonintersecting lattice paths on a cylindric lattice, expressed as a determinant of certain sums, but only for the case of an odd number of nonintersecting lattice paths. Forrester proved this formula using a recurrence relation.

1.2. Simple framework for Forrester’s formula: Lindström–Gessel–Viennot. In our paper, we shall show how the Lindström–Gessel–Viennot framework [7, 5] for directed graphs can be effortlessly adapted to the cylindric lattice ℤ × ℤ_{M}. From this point of view, Forrester’s formula literally is “easily seen”.

Moreover, it is almost immediate that in this setting the appropriate generalization of Forrester’s formula also holds for an even number of “vicious walkers”. However, in its “raw” form, the respective formula contains summands with negative sign, and hence is not very useful for enumeration purposes. We overcome this disadvantage by appropriately modifying the weights in the respective generating function (see Theorem 6).

As applications, we give enumeration formulas for the case of r equidistant vicious walkers. While for an odd number r, this formula is already contained in [3, (2.28)], the formula for even r seems to be new. Thus we are able to complete Forrester’s work; in particular, we can now also determine the asymptotics for even r. Finally, we indicate another proof (basically amounting to coefficient extraction in Forrester’s formula) of a formula given by Gessel and Krattenthaler [4].

Research partially supported by European Commission’s IHRP Programme, grant HPRN–CT–2001– 00272, “Algebraic Combinatorics in Europe”.

1.3. Organization of this paper. This paper is organized as follows:

• In Section 2, we present the basic definitions and recall the Lindström–Gessel– Viennot method.

• In Section 3, we explain how the Lindström–Gessel–Viennot method applies to a cylindric lattice.

• In Section 4, we derive explicit enumeration formulas for equidistant vicious walkers. (These are related to a formula obtained by Grabiner [6, (33)]: Our formulas (27) and (28) could be obtained by an appropriate summation of Grabiners formula). Moreover, we give the corresponding asymptotic formulas for the number of paths tending to infinity (and correct a small error in the asymptotic formula [3, (2.33)] given by Forrester). Finally, we indicate how Forrester’s formula and our generalization is related to the main theorem of Gessel and Krattenthaler [4, Proposition 1, Equation (3.5)].

2. Basic Definitions and Presentation of known Formulas

The main purpose of this paper is to present how the right point of view almost immediately gives insight in Forrester’s formula as well as in Gessel and Krattenthaler’s formula. So we make an effort to give a careful explanation of this point of view.

2.1. Nonintersecting paths and generating functions in the lattice ℤ×ℤ. Consider the lattice ℤ × ℤ, i.e., the directed graphs with vertex set ℤ × ℤ and arcs from (m, n) to (m − 1, n + 1) (a “step to the left”) and from (m, n) to (m + 1, n + 1) (a “step to the right”) for all (m, n) ∈ ℤ × ℤ (see Figure 1). To all steps to the right, assign weight 1, and to all steps to the left, assign weight x, i.e., for the edge

e = [(m_{0}, n) → (m_{1}, n + 1)]

we have

w (e) = \begin{cases}1 & if m_{1} = m_{0} + 1, \\ x & if m_{1} = m_{0} − 1. \end{cases}  (1)

A path p of length N is simply a sequence of N adjacent edges (e_{1}, …, e_{N}); i.e., for the sequence (v_{i})_{i=0}^{N} of vertices in the path, we have

e_{i} = [v_{i−1} → v_{i}]

for i = 1, … N. The vertices v_{0} and v_{N} are called the starting point and the end point of p, respectively.

The weight of a lattice path p = (e_{1}, …, e_{N}) of length N is simply defined to be the product of the weights of its edges, i.e.,

w (p) = ∏_{i=1}^{N} w (e_{i}) .  (2)

Figure 1. Illustration of lattice paths in ℤ×ℤ. The picture shows three lattice paths p_{1}, p_{2} and p_{3}; from (3, −2) to (6, 11), from (6, −2) to (11, 11), and from (9, −2) to (10, 11), respectively. Note that p_{1} intersects p_{3} in point (7, 4), but p_{2} does neither intersect p_{1} nor p_{3}, since the “geometric crossings” do not correspond to common lattice points.

Two lattice paths p_{1} and p_{2} are called intersecting, if they have a vertex (i.e., a lattice point) in common. A family of lattice paths p_{1}, …, p_{r} (also called an r–tuple of lattice paths) is called nonintersecting, if no two of its paths are intersecting.

See Figure 1 for an illustration of these simple concepts.

Remark 1. Note that “intersection” refers only to common lattice points: E.g., the “geometric crossings” of path p_{1} and p_{2} in Figure 1 do not constitute intersections in this sense.

It is clear that two paths starting in lattice points (m_{1}, n_{1}) and (m_{2}, n_{2}), respectively, can only be intersecting if (m_{1} − m_{2} + n_{1} − n_{2}) is an even number.

While the following considerations and formulas are valid even if this parity condition is violated, the most interesting case occurs if we consider the “even–numbered” sub– lattice {(x, y) ∈ ℤ × ℤ : x + y ≡ 0 (2)}.

The weight of an arbitrary (not necessarily non–intersecting) r–tuple P = (p_{1}, …, p_{r}) of lattice paths is simply defined to be the product of the weights of the single paths, i.e.,

w (P) = ∏_{i=1}^{r} w (p_{i}) .  (3)

As usual, by the generating function of some set A of weighted objects we understand the sum of the weights of the objects, i.e.,

GF (A) = ∑_{a∈A} w (a) .

2.2. The Lindström–Gessel–Viennot determinant. The enumeration of nonintersecting paths in some directed graph with given starting and end points is given by the Lindström–Gessel–Viennot determinant (see [7, Lemma 1] or [5, Corollary 2]). In order to make clear how this elegant method can be applied to the case of cylindric lattices also, we state this well–known result:

Proposition 1. Let D = (V, A) a directed graph (with vertex set V and arc set A), and let A = (a_{1}, …, a_{r}) and E = (e_{1}, …, e_{r}) be two lists of arbitrary vertices in the D. Then we have:

det_{1≤i,j,≤r} (GF (P (a_{i}, e_{j}))) = ∑_{π∈S_{r}} sgn (π) GF (P^{+} (A, E_{π})) .  (4)

where P (a, e) denotes the set of all paths starting at a and ending at e, and P^{+} (A, E_{π}) denotes the set of all r–tuples of nonintersecting paths, where path i starts at a_{i} and ends at e_{π(i)}.

Remark 2. The “usual application” of Proposition 1 contains the additional assumption, that for 1 ≤ i < j ≤ r and 1 ≤ k < l ≤ r, any path from a_{i} to e_{l} must intersect any path from a_{j} to e_{k}. In this case, there is only one summand on the right–hand side of (4), namely GF (P^{+} (A, E)), which corresponds to the identity permutation.

2.3. Paths and generating functions in the lattice ℤ_{M} × ℤ. For some (arbitrary, but fixed) integer M > 1, consider the mapping

W : ℤ × ℤ → ℝ^{3},
W (m, n) = (cos \frac{2πm}{M}, sin \frac{2πm}{M}, n) .  (5)

Note that the mapping W simply “wraps” the lattice ℤ × ℤ “around the cylinder”. More precisely, view the image im W as a “cylindric lattice”; i.e., a lattice with vertex set {W (q) : q ∈ ℤ_{M} × ℤ}, and edges leading from points

[W (m, n) → W (m + 1, n + 1)] (a “counter–clockwise” step),
[W (m, n) → W (m − 1, n + 1)] (a “clockwise” step).

We shall call this cylindric lattice the M–cylinder. (Figure 2 illustrates this simple concept.)

Clearly, a lattice path p in the M–cylinder can be viewed as the image of an “ordinary” lattice path in ℤ × ℤ under the mapping W. Each path p in the M–cylinder inherits the weight from a corresponding path in ℤ × ℤ, i.e., if p = W \binom{}{p̂}, we set w (p) := w \binom{}{p̂}. (Note that this is well–defined.)

Figure 2. Illustration of the M–cylinder for M = 12. The picture shows a lattice path p of length 4 and weight x, starting in (0, 0) and ending in (2, 4).

A lattice path may “wind around the cylinder several times”, in either positive or negative direction, before reaching its end point: The preimage W^{−1} (P (a, e)) of the set of lattice paths in the M–cylinder, which start at (a, 0) and end in (e, N), consists of lattice paths in ℤ × ℤ, which start at (a + k · M, 0) and end in (e + (k + o) · M, N) for k, o ∈ ℤ, i.e.,

W^{−1} (P (a, e)) = ⋃_{o∈ℤ}(⋃_{k∈ℤ} P̂ (a + k · M, e + (k + o) · M)) .

We shall call the number o the offset of the endpoint of the path p. (See Figure 3 for this concept.)

In the following, we shall restrict ourselves to lattice paths starting at (a, 0) and ending at (e, N), where N is some (arbitrary but fixed) integer. Note that in ℤ × ℤ, a lattice path starting at (a, 0) and ending at (e, N) exists if and only if

N − 2k = e − a  (6)

for some k ∈ ℤ with 0 ≤ k ≤ N (here, k denotes the number of steps to the left). For lattice paths in the M–cylinder, this condition is changed to

N − 2k = (e + o · M) − a  (7)

for arbitrary o ∈ ℤ and some k ∈ ℤ with 0 ≤ k ≤ N (here, o denotes the offset of the endpoint, and k denotes the number of clockwise steps).

So it is easy to see that the generating function q (M, N, a, e) of all lattice paths in the M–cylinder, which start at (a, 0) and end in (e, N), is given by

q (M, N, a, e; x) = ∑_{\begin{matrix}o∈ℤ \\ N−e−o·M+a≡0 (2) \end{matrix}} \binom{N}{\frac{N−e−o·M+a}{2}}x^{\frac{N−e−o·M+a}{2}} .  (8)

Figure 3. Illustration of intersecting lattice paths on the M–cylinder for M = 12. The right picture shows representatives of the preimages of these paths (drawn with thick lines) in the lattice ℤ × ℤ under the mapping defined in (5). The whole preimage consists of an infinite family of horizontally translated paths, indicated by thin lines in the picture.

Forrester gave an equivalent expression (see [3, equation 2.11 and 2.12]) for (8), which is more elegant insofar as it “conceals” the clumsy definition of the range of summation in (8):

q (M, N, a, e; x) = \frac{1}{M} ∑_{l=0}^{M−1} e^{\frac{−2πi(e−a)l}{M}} (xe^{\frac{−2πil}{M}} + e^{\frac{2πil}{M}} )^{N}  (9)

= ∑_{k=0}^{N} \binom{N}{k}x^{k} \frac{1}{M} ∑_{l=0}^{M−1} (e^{^{\frac{2πi}{M}} (N−2k−e+a)})^{l} ,

where i denotes the imaginary unit. (9) is equal to (8), since we have

∑_{l=0}^{M−1} (e^{\frac{2πi}{M} m})^{l} = \begin{cases}M & if m ≡ 0 (M) , \\ 0 & else. \end{cases}  (10)

3. Results and Proofs

It is an obvious observation that the Lindström–Gessel–Viennot method for nonintersecting paths in a directed graph, as described in Proposition 1, applies to the M– cylinder. However, unlike the “usual case” outlined in Remark 2, there appear terms corresponding to other permutations than the identity permutation; which turn out to be cyclic permutations. These permutations may have negative sign if the number of paths, r, is even. So if we are given starting points ((a_{1}, 0) , … (a_{r}, 0)) and end points ((e_{1}, N) , … (e_{r}, N)), we define the signed weight of a family P = (P_{1}, …, P_{r}) of lattice paths, where P_{i} starts in (a_{i}, 0) and ends in (e_{π(i)}, N) for some permutation π ∈ S_{r}, as

w (π, P) = sgn π ∏_{j=1}^{r} w (P_{j}) .  (11)

3.1. A simple generalization of Forrester’s formula. Given this “signed weight” for families of nonintersecting lattice paths, we may derive immediately the following generalization of Forrester’s formula.

Theorem 3. The generating function with signed weights (according to (11)) of all r–tuples of non–intersecting lattice paths in the M–cylinder, starting at the points

((a_{1}, 0) , … (a_{r}, 0))

and ending in any permutation of the points

((e_{1}, N) , … (e_{r}, N)) ,

with 0 ≤ a_{1} < a_{2} < ⋯ < a_{r} < M and 0 ≤ e_{1} < e_{2} < ⋯ < e_{r} < M, where for all 1 ≤ i, j ≤ r we have N − e_{i} + a_{j} ≡ 0 (2), is given by

det (q (M, N, a_{i}, e_{j}; x))_{i,j=1}^{r} .  (12)

Moreover, we have the following expansion for the above determinant:

det (q (M, N, a_{i}, e_{j}; x))_{i,j=1}^{r} = ∑_{i=0}^{r−1} sgn (μ^{i}) GF (P^{+} (A, E_{μ^{i}})) ,  (13)

where μ denotes the permutation mapping 1 to 2, 2 to 3, and so on; i.e., μ = (1, 2, …, r) in cycle notation.

Proof. The assertion of (12) is an immediate consequence of Proposition 1.

For the assertion of (13), consider the preimage of any nonintersecting r–tuple of lattice paths with respect to W: It appears as a periodic configuration of infinitely many nonintersecting lattice paths in ℤ × ℤ, such that each point (a_{i} + s · M, 0) and each point (e_{i} + s · M, N) (for i = 1, …, r and s ∈ ℤ) appears as starting point and as end point, respectively, of some path (see Figure 4 for an illustration).

It is obvious that such a configuration can only correspond to some “shift of the endpoints” in the following sense: Consider the “canonical” starting points (a_{i}, 0), and label the “canonical” endpoints (e_{i}, N) with the numbers 1, 2, …, r. Label the other possible endpoints from left to right with the integers in a consistent way (i.e., (e_{r} − M, N) gets label 0, (e_{r−1} − M, N) gets label −1; (e_{1} + M, N) gets label r + 1, and so on). Then for any nonintersecting r–tuple of lattice paths there is some fixed integer p, such that Figure 4. Illustration of the preimage with respect to W (right picture) of a nonintersecting pair of lattice paths in the 6–cylinder (left picture).

for 1 ≤ i ≤ r, the path starting at (a_{i}, 0) ends in the (i + p)–th endpoint in this labeling. This “shift of the endpoints” clearly corresponds to a cyclic permutation μ^{p}, where μ = (1, 2, …, r). □

Remark 4. Note that under the assumptions of Theorem 3, the case M odd admits only one possible permutation of endpoints, namely the identity permutation, since all such permutations must be of the form (μ^{r})^{2k} = id, according to condition (7).

While the following considerations and formulas are valid also for odd M, the most interesting cases occur if we assume

• M ≡ N ≡ 0 (2),

• a_{i} − a_{j} ≡ e_{i} − e_{j} ≡ 0 (2) ∀1 ≤ i, j ≤ r.

(See also Remark 1.)

The determinantal expression (12) was derived recursively by Forrester only for odd r (see [3, Theorem 2.1, equation 2.10]). In Theorem 3, we easily extended it to the case of even r (thus answering the respective question posed in [3]), just by adopting the right “point of view” (i.e., the Lindström–Gessel–Viennot framework with “signed weights”).

3.2. A more sophisticated generalization of Forrester’s formula. Note that for odd r, all the (cyclic) permutations in (13) have positive sign. If r is even, however, also negative terms appear in the generating function (12): This is a bit of a nuisance, for we cannot simply set x ≡ 1 in order to obtain an enumeration formula.

An easy way out of this difficulty is to modify the definition of the weight of a single path p, so that its “offset of endpoint”, o, is taken into account via a multiplicative factor of y^{o}, i.e.,we replace definition (2) by

w_{y} (p) = y^{o} ∏_{i=1}^{N} w (e_{i}) .  (14)

This amounts to the following modification of (8):

q (M, N, a, e; x, y) = ∑_{\begin{matrix}o∈ℤ \\ N−e−o·M+a≡0 (2) \end{matrix}} \binom{N}{\frac{N−e−o·M+a}{2}}y^{o} · x^{\frac{N−e−o·M+a}{2}} .  (15)

Now, the proof of Theorem 3 (with slight and obvious modifications) immediately yields the following Lemma:

Lemma 5. The generating function with weights according to (14) of all r–tuples of non–intersecting lattice paths in the M–cylinder, starting at the points

((a_{1}, 0) , … (a_{r}, 0))

and ending in some permutation of the points

((e_{1}, N) , … (e_{r}, N)) ,

with 0 ≤ a_{1} < a_{2} < ⋯ < a_{r} < M and 0 ≤ e_{1} < e_{2} < ⋯ < e_{r} < M, where for all 1 ≤ i, j ≤ r we have N − e_{i} + a_{j} ≡ 0 (2), is given by

det (q (M, N, a_{i}, e_{j}; x, y))_{i,j=1}^{r} .  (16)

A simple argument now leads to the desired formula without unwanted negative signs:

Theorem 6. The generating function with unsigned weights (i.e., according to (2)) of all r–tuples of non–intersecting lattice paths in the M–cylinder, starting at the points

((a_{1}, 0) , … (a_{r}, 0))

and ending in some permutation of the points

((e_{1}, N) , … (e_{r}, N)) ,

with 0 ≤ a_{1} < a_{2} < ⋯ < a_{r} < M and 0 ≤ e_{1} < e_{2} < ⋯ < e_{r} < M, where for all 1 ≤ i, j ≤ r we have N − e_{i} + a_{j} ≡ 0 (2), is given by

det (q (M, N, a_{i}, e_{j}; x, (−1)^{r−1}))_{i,j=1}^{r} .  (17)

Proof. For odd r, we clearly have

q (M, N, a, e; x, 1) = q (M, N, a, e; x) ,

whence (17) simply amounts to the assertion of Theorem 3.

For even r, observe that (due to (13)) the sign of the summands in (16) equals (−1)^{n}, where n is the number of paths with odd offset of endpoint in the corresponding r–tuple of paths. So setting y = −1 in (16) properly cancels all the negative signs. □

3.3. Enumeration formulas involving trigonometric functions. It is possible to rewrite the generating function q (M, N, a, e; x, y) in a way similar to (9).

Corollary 7. For M > 0, we have:

q (M, N, a, e; x, y) = \frac{y^{\frac{a−e}{M}}}{M} ∑_{l=0}^{M−1} e^{\frac{−2πi(e−a)l}{M}} (xy^{− \frac{1}{M}} e^{\frac{−2πil}{M}} + y^{\frac{1}{M}} e^{\frac{2πil}{M}} )^{N} .  (18)

Moreover, the generating function (17) of Theorem 6 is equivalently given by

M^{−r} det(e^{\frac{(r−1)πi(a_{i}−e_{j})}{M}} ∑_{l=0}^{M−1} e^{\frac{−2πi(e_{j} −a_{i})l}{M}} (xe^{\frac{−2πi(l+ \frac{r−1}{2})}{M}} + e^{\frac{2πi(l+ \frac{r−1}{2})}{M}} )^{N})_{i,j=1}^{r}. (19)

Proof. Equation (18) follows from the same type of computation as in (9).

\frac{y^{\frac{a−e}{M}}}{M} ∑_{l=0}^{M−1} e^{\frac{−2πi(e−a)l}{M}} (xy^{\frac{−1}{M}} e^{\frac{−2πil}{M}} + y^{\frac{1}{M}} e^{\frac{2πil}{M}} )^{N}

= \frac{y^{\frac{a−e}{M}}}{M} ∑_{l=0}^{M−1} e^{\frac{−2πi(e−a)l}{M}} ∑_{k=0}^{N} \binom{N}{k}x^{k}y^{\frac{N−2k}{M}} e^{\frac{2πi}{M} (N−2k)l}

= ∑_{k=0}^{N} \binom{N}{k}x^{k}y^{\frac{N−e+a−2k}{M}} \frac{1}{M} ∑_{l=0}^{M−1} e^{\frac{2πi}{M} (N−e+a−2k)l}.

Use (10) to see that (18) equals (15) (set k = \frac{N−e+a−o·M}{2} , or, equivalently, o = \frac{N−e+a−2k}{M}). Now set y = (−1)^{r−1} = e^{(r−1)πi} in (18), and insert the result into (17): This immediately yields (19). □

If the starting points a_{i} are equidistant, we can simplify the corresponding expressions even further by a little trick, extending the computation carried out by Forrester [3, equation (3.2)] to the case of even r:

Corollary 8. Consider the case of equidistant starting points, i.e., let a_{i} = (i − 1) · ν and M = r · ν in(16) for some fixed ν ∈ ℕ. In this case, the generating function (17) of Theorem 6 is given by

i^{− \frac{(r)(r−1)}{2}} (ν\sqrt{r})^{−r}

× det (∑_{a=0}^{ν−1} e^{\frac{πi(N−e_{j+1}(2(i+ar)+1))}{rν}} (xe^{\frac{−2πi(i+ar+1)}{rν}} + e^{\frac{2πi(i+ar)}{rν}} )^{N})_{i,j=0}^{r−1} (20)

if r is even, and by

i^{− \frac{(r+2)(r−1)}{2}} (ν\sqrt{r})^{−r} det (∑_{a=0}^{ν−1} e^{\frac{πi(−e_{j+1}(2(i+ar)))}{rν}} (xe^{\frac{−2πi(i+ar)}{rν}} + e^{\frac{2πi(i+ar)}{rν}} )^{N})_{i,j=0}^{r−1} (21)

if r is odd. (Note that — as a matter of convenience — row and column indices range from 0 to (r − 1) here.)

Proof. Note that [(e^{− \frac{2πi}{r} i})^{j} r^{−1/2}]_{i,j=0}^{r−1} is a unitary matrix. This fact, together with the

well–known formula for Vandermonde determinants, yields the determinant evaluations

det (e^{− \frac{2πi}{r} i·j})_{i,j=0}^{r−1} = r^{\frac{r}{2}} i^{\frac{(r+2)(r−1)}{2}} , and det (e^{− \frac{2πi}{r} (i+1/2)·j})_{i,j=0}^{r−1} = r^{\frac{r}{2}} i^{\frac{(r)(r−1)}{2}} .  (22)

The assertions follow by a simple computation, which we shall show for even r only (the case r odd being completely analogous; see Forrester [3, equation (3.2)]). Set y = (−1) = e^{πi} in (18) and insert in (17). Now multiply this with the second determinant from (22); i.e., consider the determinant of the product of the r × r–matrices

[e^{− \frac{2πi}{r} (k+1/2)·m}] × [\frac{e^{πi \frac{N−e_{j+1}+iν}{rν}}}{rν} ∑_{l=0}^{rν−1} e^{\frac{−2πi(e_{j+1}−iν)l}{rν}} (xe^{\frac{−2πi(l+1)}{rν}} + e^{\frac{2πil}{rν}} )^{N}] ,

where the row and column indices i and j range from 0 to (r − 1). The (i, j)–entry of this matrix product is given by

a_{i,j} = ∑_{n=0}^{r−1} (e^{− \frac{2πi}{r} (i+1/2)n} \frac{e^{πi \frac{N−e_{j+1}+nν}{rν}}}{rν} ∑_{l=0}^{rν−1} e^{\frac{−2πi(e_{j+1}−nν)l}{rν}} (xe^{\frac{−2πi(l+1)}{rν}} + e^{\frac{2πil}{rν}} )^{N})

= \frac{1}{rν} ∑_{l=0}^{rν−1} (xe^{\frac{−2πi(l+1)}{rν}} + e^{\frac{2πil}{rν}} )^{N} e^{^{\frac{πi}{rν}} (N−e_{j+1}(2l+1))} ∑_{n=0}^{r−1} e^{− \frac{2πi}{r} (i−l)n}

= \frac{1}{ν} ∑_{a=0}^{ν−1} (xe^{\frac{−2πi(i+ar+1)}{rν}} + e^{\frac{2πi(i+ar)}{rν}} )^{N} e^{\frac{πi}{rν} (N−e_{j+1}(2(i+ar)+1)),}

which immediately gives (20). (The proof of (21) involves multiplication with the first determinant from (22).) □

4. Applications

4.1. An enumeration formula for a special case. Of particular interest is the enumeration formula for the case M = rν with equidistant starting points and end points, a_{i} = e_{i} = (i − 1) ν: This simply amounts to setting M = rν, a_{i} = e_{i} = (i − 1) ν and x = 1 in (17). Since we have the obvious relations

q (M, N, a, e; x, y) = x^{N}q (M, N, e, a; 1/x, 1/y)  (23)

and

q (rν, N, iν, jν; x, y) = y · q (rν, N, iν, (j + r)ν; x, y) ,  (24)

we may concentrate on the numbers

a_{d} := q (rν, N, 0, dν; 1, (−1)^{r−1}) for d = 0, …, r − 1.

So for odd r, we obtain a circulant matrix, the determinant of which we can easily evaluate by the well–known formula (cf. [1, §51, p. 131]):

det (\begin{matrix}a_{0} & a_{1} & … & a_{r−2} & a_{r−1} \\ a_{r−1} & a_{0} & … & a_{r−3} & a_{r−2} \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ a_{1} & a_{2} & … & a_{r−1} & a_{0} \end{matrix}) = ∏_{m=0}^{r−1} (∑_{k=0}^{r−1} (e^{\frac{2mπi}{r}} )^{k} a_{k}) .  (25)

For even r, however, we obtain a “skew–symmetric” circulant matrix (due to (24)), the determinant of which we can evaluate in much the same way as (25). Since this evaluation appears to be not so well–known, we state and prove it in the following lemma:

Lemma 9. For arbitrary variables a_{0} … a_{r−1}, we have

det (\begin{matrix}a_{0} & a_{1} & … & a_{r−2} & a_{r−1} \\ −a_{r−1} & a_{0} & … & a_{r−3} & a_{r−2} \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ −a_{1} & −a_{2} & … & −a_{r−1} & a_{0} \end{matrix}) = ∏_{m=0}^{r−1} (∑_{k=0}^{r−1} (e^{\frac{(2m+1)πi}{r}} )^{k} a_{k}) .  (26)

Proof. Set ω_{m} := e^{\frac{(2m+1)πi}{r}} and consider the r vectors ω⃗_{m} := (ω_{m}^{0}, ω_{m}^{1}, …, ω_{m}^{r−1}) for m = 0, …, r − 1. Note that ω_{m}^{r} = −1 and compute the i–th component in the product A · ω⃗_{m} (where A, of course, denotes the matrix in (26)):

(A · ω⃗_{m})_{i} = −a_{r−i}ω_{m}^{0} − a_{r−i+1}ω_{m}^{1} − ⋯ − a_{r−1}ω_{m}^{i−1} + a_{0}ω_{m}^{i} + a_{1}ω_{m}^{i+1} + … a_{r−i−1}ω_{m}^{r−1}

= a_{0}ω_{m}^{i} + a_{1}ω_{m}^{i+1} + … a_{r−i−1}ω_{m}^{r−1} + a_{r−i}ω_{m}^{r} + a_{r−i+1}ω_{m}^{r+1} + ⋯ + a_{r−1}ω_{m}^{r+i−1}

= ω_{m}^{i} · (∑_{k=0}^{r−1} a_{k}ω_{m}^{k}) .

This shows that ω⃗_{m} is an eigenvector of A to the eigenvalue (∑_{k=0}^{r−1} a_{k}ω_{m}^{k}), which proves the assertion. □

Corollary 10. Denote the number of all r–tuples of non–intersecting lattice paths in the (rν)–cylinder, starting at the points

((0, 0) , … ((r − 1) ν, 0))

and ending in any permutation of the points

((0, N) , … ((r − 1) ν, N)) ,

by Z (N, r, ν). Then we have the following formulas:

Z (N, 2r − 1, ν) = (\frac{2^{N}}{ν} )^{2r−1} ∏_{m=0}^{2r−2} ∑_{l=0}^{ν−1} cos^{N} (2 π (\frac{m}{ν (2r − 1)} + \frac{l}{ν} )) ,  (27)

Z (N, 2r, ν) = (\frac{2^{N}}{ν} )^{2r} ∏_{m=0}^{2r−1} ∑_{l=0}^{ν−1} cos^{N} (2 π (\frac{m + 1/2}{ν (2r)} + \frac{l}{ν} )) .  (28)

Proof. Clearly, (27) will follow by simplifying (25), and (28) will follow by simplifying (26). We shall give the corresponding computation for (28) only, the other case is completely analogous.

Straightforward insertion of

a_{d} := q (rν, N, 0, dν; 1, e^{πi})

into (26) gives the following expression:

∏_{m=0}^{2r−1} ∑_{k=0}^{2r−1} ((e^{\frac{(2m+1)πi}{2r}} )^{k} \frac{e^{\frac{(N−kν)πi}{2νr}}}{2νr} ∑_{l=0}^{2νr−1} e^{− \frac{kνlπi}{νr}} (e^{− \frac{(l+1)πi}{νr}} + e^{\frac{lπi}{νr}} )^{N}) .  (29)

Now write

(e^{− \frac{(l+1)πi}{νr}} + e^{\frac{lπi}{νr}} ) = e^{− \frac{πi}{2νr}} 2 cos (\frac{(l + 1/2) π}{νr} ) ,

pull out appropriate factors, simplify, and interchange summation; in order to obtain

(\frac{2^{N−1}}{νr} )^{2r} ∏_{m=0}^{2r−1} ∑_{l=0}^{2νr−1} cos^{N} (\frac{(l + 1/2) π}{νr} ) ∑_{k=0}^{2r−1} (e^{\frac{2(m−l)πi}{2r}} )^{k} .

Observe that (10) applies to the innermost sum, whence (28) follows. □

Remark 11. Equation (27) is basically the same as Forrester’s formula [3, (2.28)].

4.2. Free energy. In his paper, Forrester considers the dimensionless free energy per unit length on a strip–shaped lattice of infinite width and height N (see [3, (2.30)]):

f_{N} (ν) = − lim_{r→∞} \frac{1}{νr} log (Z (N, r, ν)) .  (30)

We can apply his considerations now also to the case of even r. According to (27) and (28), respectively, we have

− \frac{1}{rν} log (Z (N, r, ν)) =

− \frac{1}{rν} (r (N log 2 − log ν) + ∑_{m=0}^{r−1} log (∑_{l=0}^{ν−1} cos^{N} (2π \frac{l + \frac{m+ϵ(r)}{r}}{ν} ))), (31)

where ϵ (r) = 1/2 if r is even, and ϵ (r) = 0 if r is odd. In both cases, observe that we have Riemann sums, which tend to the same integral in the limit:

−\frac{1}{ν}((N log 2 − log ν) + ∫_{0}^{1} log (∑_{k=0}^{ν−1} cos^{N} (2π \frac{k + t}{ν})) d t).  (32)

(This corresponds to Forresters formula [3, (2.31)].)

Now, following Forrester [3, Section 2.4], we consider the free energy per lattice site in the two–dimensional thermodynamic limit, i.e., the quantitity F_{ν} := lim_{N→∞} \frac{f_{N} (ν)}{N}. Of course, the basic idea for evaluating this limit is “Pull out the dominating term from the sum in (32)”. However, we must be careful in determining this dominating term (there seems to be a small flaw in Forresters formula [3, 2.33] with respect to this):

For even ν, the dominating term is

• cos (\frac{2πt}{ν}) for 0 ≤ t ≤ \frac{1}{2},

• cos (\frac{2π(t+ν−1)}{ν}) = cos (\frac{2π(t−1)}{ν}) for \frac{1}{2} ≤ t ≤ 1, whence we obtain

F_{ν} = −\frac{log 2}{ν}

− lim_{N→∞} \frac{1}{νN} ∫0^{\frac{1}{2}} log (cos (\frac{2πt}{ν})^{N} × ∑_{k=0}^{ν−1} (\begin{matrix}cos & (2π \frac{k+t}{ν}) \\ cos & (\frac{2πt}{ν}) \end{matrix})^{N} ) d t

− lim_{N→∞} \frac{1}{νN} ∫ 1_{\frac{1}{2}} log (cos (\frac{2π (t − 1)}{ν})^{N} × ∑_{k=0}^{ν−1} (\begin{matrix}cos & (2π \frac{k+t}{ν}) \\ cos & (\frac{2π(t−1)}{ν}) \end{matrix})^{N} ) d t

= −\frac{log 2}{ν} − ∫− \frac{1}{2ν}^{\frac{1}{2ν}} log (cos (2πt)) dt.  (33)

(Forresters formula [3, 2.33] looks almost the same, but the range of integration is stated as [0, \frac{1}{ν}] instead of [−\frac{1}{2ν} , \frac{1}{2ν}].)

For odd ν, the dominating term is • cos (\frac{2πt}{ν}) for 0 ≤ t ≤ \frac{1}{4},

• cos (\frac{2π(t+ \frac{ν−1}{2})}{ν}) = − cos (\frac{2π(t− \frac{1}{2})}{ν}) for \frac{1}{4} ≤ t ≤ \frac{3}{4},

• cos (\frac{2π(t−1)}{ν}) for \frac{3}{2} ≤ t ≤ 1,

whence by the same simple computation as above, we obtain

F_{ν} = −\frac{log 2}{ν} − 2 ∫− \frac{1}{4ν}^{\frac{1}{4ν}} log (cos (2πt)) dt.  (34)

4.3. Gessel and Krattenthaler’s formula. Gessel and Krattenthaler [4] consider nonintersecting paths in the lattice ℤ × ℤ, too. However, their lattice paths consist of horizontal and vertical steps, which essentially is equivalent to the situation of lattice paths consisting of diagonal steps in the even–numbered sublattice (see Remark 1).

More precisely, they consider lattice paths which are nonintersecting and, in addition, are also nonintersecting with respect to “shifted copies” of lattice paths; i.e., copies of the original paths which are translated by a fixed (non–vertical and non–horizontal) shift vector S. See Figure 5 for an illustration, where the translation S is indicated by a dotted arrow.

They give a quite general formula [4, Proposition 1, Equation (3.5)] for the generating function of such nonintersecting families, in the form of a multi–sum of certain determinants.

A special case of this formula • with shift vector S = (−m, m),

• with a certain choice of edge–weights,

• and with starting points and end points arranged on downward–sloping lines basically appears as refinement of our formula (16), in the sense that now we are only interested in terms with fixed sum ∑ o = c of offsets of endpoints. So, this amounts to extracting the coefficient of y^{c} in the expansion of (16). The advantage of our formula Figure 5. Illustration of nonintersecting lattice paths with nonintersecting translate. The shift vector S is indicated by the dotted arrow.

(16) is that it consists of a single determinant. Moreover, it does not appear to be easy to obtain it by appropriately summing up Gessel and Krattenthaler’s formula.

In any case, the most natural way of understanding (16) is the direct application of the Lindström–Gessel–Viennot method.

Acknowledgements. I thank Christian Krattenthaler for many helpful hints and discussions.

References

[1] A.C. Aitken. Determinants and Matrices. Oliver and Boyd Ltd., Edinburgh, 1956.

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

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

[4] I. M. Gessel and C. Krattenthaler. Cylindric partitions. Trans. Amer. Math. Soc., 349:429–479, 1997.

[5] I. M. Gessel and X.G. Viennot. Determinants, paths, and plane partitions. preprint, available at

   http://www.cs.brandeis.edu/~ira/papers/pp.pdf, 1989.

[6] David J. Grabiner. Random walk in an alcove of an affine Weyl group, and non–colliding random walks on an interval. J. Combin. Theory Ser. A, 97:285–306, 2002.

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

Institut für Mathematik, Universität Wien, Nordbergstraße 15, A–1090 Wien, Austria

E-mail address: Markus.Fulmek@Univie.Ac.At
WWW: http://www.mat.univie.ac.at/~mfulmek