Lattice walks in Z^{d} and permutations with no long ascending subsequences

Ira Gessel^{∗} Brandeis University Jonathan Weinstein^{†} Harvard University

Herbert S. Wilf^{‡} University of Pennsylvania

Abstract

We identify a set of d! signed points, called Toeplitz points, in Z^{d}, with the following property: for every n > 0, the excess of the number of lattice walks of n steps, from the origin to all positive Toeplitz points, over the number to all negative Toeplitz points, is equal to \binom{n}{n/2} times the number of permutations of \{1, 2, …, n\} that contain no ascending subsequence of length > d. We prove this first by generating functions, using a determinantal theorem of Gessel. We give a second proof by direct construction of an appropriate involution. The latter provides a purely combinatorial proof of Gessel’s theorem by interpreting it in terms of lattice walks. Finally we give a proof that uses the Schensted algorithm.

Submitted: September 27, 1996; Accepted: November 17, 1997

1 Introduction

The subject of walks on the lattice in Euclidean space is one of the most important areas of combinatorics. Another subject that has been investigated by many researchers in recent years is that of permutations without long ascending subsequences. In this paper we find a link between the counting functions of these two families of combinatorial objects.

∗Supported in part by the National Science Foundation.

†This work was done during the 1996 Research Experience for Undergraduates at the University of Minnesota, Duluth, directed by Joseph Gallian and sponsored by the National Science Foundation and the National Security Agency.

‡Supported in part by the Office of Naval Research.

An ascending subsequence of length d of a permutation π of the letters {1, 2, …, n} is a set 1 ≤ i_{1} < i_{2} < … < i_{d} ≤ n of letters such that π(i_{1}) < π(i_{2}) < … < π(i_{d}). For example, the permutation

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 2 & 8 & 5 & 1 & 3 & 6 & 7 \end{matrix} )

has an ascending subsequence of length 3 at positions 1,4,8 since the values 4,5,7 are in ascending order.

If u_{n}(d) is the number of permutations of {1, 2, …, n} that have no ascending subsequence of length > d, then, for example, {u_{n}(2)} are well known to be the Catalan numbers. Regarding u_{n}(d), a great deal is known. The asymptotic behavior of the sequence has been determined by Regev [6]. An explicit generating function of the sequence has been found by Gessel [1], in the form

∑_{n≥0} \frac{u_{n}(d)}{n!^{2}}x^{2n} = det (I_{|r−s|}(2x))_{r,s=1,...,d}.  (1)

in which the I_{ν}’s are the Bessel functions of imaginary argument. We will use the result (1) in section 2 to establish our correspondence with lattice walks. Interestingly, however, by providing a combinatorial proof of this correspondence, in section 3 below, we will be giving an independent and purely combinatorial proof of the theorem (1).

As an open problem, we mention that it would be of interest to illuminate the connection between Theorem 1 below and the result of [8], which, at least superficially, have striking similarities of form.

2 The generating function approach

2.1 Generating functions for lattice walks

Let c_{n,k} denote the number of walks of n steps from the origin to the point k = (k_{1}, …, k_{d}) ∈ Z^{d}, where each step is a change of ±1 in one coordinate. If d = 1 it is clear that c_{n,k} = \binom{n}{\frac{n+k}{2}}, from which we have the exponential generating function

∑_{n≥0} \frac{c_{n,k}}{n!} x^{n} = ∑_{n≥0} \frac{x^{n}}{(\frac{n+k}{2})!(\frac{n−k}{2})!} = ∑_{n≥0} \frac{x^{2n+k}}{n!(n + k)!} = I_{k}(2x),

where I_{k}(t) is the Bessel function of imaginary argument.

Since in Z^{d} all walks of n steps from the origin to k are shuffles of independent 1dimensional walks to the coordinates of k, we have the d-dimensional exponential generating function

∑_{n≥0} \frac{c_{n,k}}{n!} x^{n} = ∏_{ν=1}^{d} I_{k_{ν}}(2x).  (2)

2.2 Connection with permutations without long ascending subsequences

The connection between lattice walks and the class of permutations that we are studying here is obtained by comparing Gessel’s determinant in (1) with the generating function (2). Notice that the determinant on the right side of (1) is a sum of d! terms, each of which is a product of d Bessel functions. Products of d Bessel functions, according to (2) above, count lattice walks in d-space that begin at the origin and end at the lattice point whose coordinates are the subscripts of the Bessel functions that occur in the product. Consequently, the determinant above is an alternating sum of generating functions each of which counts lattice walks that end at a certain point.

To quantify this, we sum eq. (2) above, with appropriate signs, with appropriate values of the terminal point k, and thereby relate such permutations to lattice walks.

For each permutation σ of {1, …, d}, the Toeplitz point T (σ) is the point (1 − σ(1), 2 − σ(2), …, d − σ(d)) ∈ Z^{d}. The number of Toeplitz points in Z^{d} is obviously d!. The sign of T (σ) is the parity (= ±1) of σ.

For example, the six Toeplitz points in Z^{3}, together with their signs, are

sign = +1 : (0, 0, 0), (−1, −1, 2), (−2, 1, 1)  (3)
sign = −1 : (0, −1, 1), (−1, 1, 0), (−2, 0, 2).

2.3 Walks and permutations

On the right side of eq. (2) above, successively replace the point k by each of the Toeplitz points in Z^{d}, multiply by the sign of that point, and sum over all such points. Then the sum will obviously be the same as the right side of (1), and therefore it will be equal to the power series on the left side of (1).

On the other hand, the coefficient of x^{n} on the left side of (2), after this sequence of signed replacements and summation, will be 1/n! times the signed sum of the numbers of lattice walks of n steps from the origin to all Toeplitz points.

If we match coefficients of like powers of x on both sides, we obtain the following result.

Theorem 1 Fix integers d ≥ 1 and n ≥ 0. The signed sum of the numbers of lattice walks in Z^{d} from the origin to the Toeplitz points is 0 if n is odd, and is \binom{n}{n/2} times the number of permutations of n/2 letters that have no ascending subsequence of length > d, if n is even.

As an example we will work out the case n = 6, d = 3. The six Toeplitz points are shown in (3) above. The signed numbers of lattice walks from the origin to each of them in turn, are 1860, 480, 480, −1200, −1200, −300. The signed sum is therefore 1860 + 480 + 480 − 1200−1200−300 = 120. This is indeed \binom{6}{3} = 20 times the number of permutations (namely 6) of three letters that have no ascending subsequence of length > 3.

3 A combinatorial approach

In this section we will provide a combinatorial proof of Theorem 1.

We will first show how the walks can be divided into classes of \binom{n}{n/2} walks. Then we will give an injection from the permutations without long ascending subsequences to walks that end at the origin (which is the even Toeplitz point corresponding to the identity permutation), and a parity-reversing involution which acts on all the walks not in the range of this injection. In the process of doing this we also give an internal description (cf. Lemma 1 below) of those classes of walks that are the images of some permutation without long ascending subsequences.

3.1 Second proof of Theorem 1

Assume n is even. By the direction array of a walk w of n steps we mean the array of length n whose ith entry is r (resp. −r) if the ith step of the walk w is parallel (resp. antiparallel) to the rth coordinate axis.

Since the sum of the coordinates of the Toeplitz point T (σ) is ∑ i − ∑ σ(i) = 0, every walk to a Toeplitz point will have equally many positive and negative entries in its direction array. Call two walks equivalent if the subsequences of their n/2 positive direction array entries are identical, as are their negative subsequences. There will be \binom{n}{n/2} walks in each equivalence class. Henceforth we will restrict our attention to the representative of each equivalence class in which all of the positive steps precede the negative. We will denote such a walk by w = a_{1}, …, a_{n/2}/b_{1}, …, b_{n/2}, where the a_{i}’s (resp. b_{i}’s) are the absolute values of the positive (resp. negative) entries in the direction array. Also, we will use w_{j} to denote the jth coordinate of the endpoint of walk w.

Now, given a permutation π of {1, 2, ..., n/2} with no ascending subsequence of length greater than d, we create an n-step walk ϕ(π) = a_{1}, …, a_{n/2}/b_{1}, …, b_{n/2} by letting a_{i} be the length of the longest ascending subsequence of π ending with the value π(i), and b_{i} be the length of the longest ascending subsequence of π ending at the value i. Since the b_{i} are a rearrangement of the a_{i}, ϕ(π) ends at the origin.

We now show that ϕ is injective. Let w = a_{1}, …, a_{n/2}/b_{1}, …, b_{n/2} be a walk ending at the origin. For each j such that 1 ≤ j ≤ d, let A_{j} = {i : a_{i} = j} and B_{j} = {i : b_{i} = j}. We observe from the definition of ϕ that w = ϕ(π) implies b_{π(i)} = a_{i} for each i, so π(A_{j}) = B_{j}. Furthermore, the restriction of π to A_{j} →^{π} B_{j} must be order reversing—for suppose to the contrary that π(i_{1}) = k_{1} and π(i_{2}) = k_{2}, with i_{1}, i_{2} ∈ A_{j}, k_{1}, k_{2} ∈ B_{j}, i_{1} < i_{2}, and k_{1} < k_{2}. Then there is an ascending subsequence of π of length j ending in the value k_{1}. Appending k_{2}, we have an ascending subsequence of length j + 1 ending in the value k_{2}, contradicting k_{2} ∈ B_{j}. These properties determine π uniquely, since the A_{j} cover all of {1, 2, ..., n/2}, so ϕ is indeed injective. For any walk w ending at the origin, denote the permutation determined in this manner by θ(w). We have shown that w ∈ Im ϕ if and only if ϕ(θ(w)) = w. Example 1: Let n = 8, d = 2, and w = 1, 2, 2, 1/1, 1, 2, 2. Then A_{1} = {1, 4}, and B_{1} = {1, 2}, so θ(w)(1) = 2 and θ(w)(4) = 1; A_{2} = {2, 3} and B_{2} = {3, 4}, so θ(w)(2) = 4, θ(w)(3) = 3. As a sequence, then, θ(w) = 2,4,3,1—and indeed, ϕ(θ(w)) = w.

Let w = a_{1}, …, a_{n/2}/b_{1}, …, b_{n/2} be a walk to any Toeplitz point. For each i for which a_{i} > 1, let k_{i} and l_{i} be the numbers of occurrences of a_{i} and a_{i} − 1, respectively, in a_{1}, …, a_{i}. We then have the following result, which characterizes the walks that correspond to permutations.

Lemma 1 w ∈ Im ϕ if and only if for every i such that a_{i} > 1, l_{i} > 0 and the l_{i}th-to-last negative step in direction a_{i} − 1, if it exists, comes before the k_{i}th-to-last negative step in direction a_{i}.

Proof: First, suppose w does not end at the origin, so w ∉ Im ϕ. Let j be the smallest integer for which w_{j} > 0; j > 1 since all our Toeplitz points have non-positive first coordinate. Let i be the greatest value such that a_{i} = j. There will be fewer than k_{i} occurrences of j among the b_{i}, and at least l_{i} occurrences of j − 1 among the b_{i}, since w_{j−1} ≤ 0—hence i does not satisfy the condition in the lemma.

Now we consider walks w which do end at the origin. First note that ϕ(θ(w)) = w is equivalent to the condition that w and ϕ(θ(w)) agree in just their positive steps, by the stipulation in the construction of θ(w) that π(A_{j}) = B_{j}. Suppose the two walks agree in all positive steps before the ith, and let ϕ(θ(w)) in its ith step go in direction a′_{i}. We will never have a′_{i} > a_{i}; for then let j be the location of the a_{i}th term of an ascending subsequence of θ(w) of length a′_{i} ending with the value θ(w)(i). Then a_{j} = a_{i}, j < i, but θ(w)(j) < θ(w)(i), contrary to the definition of θ. We will have a′_{i} ≥ a_{i} when there is an ascending subsequence of θ(w) of length a_{i} ending with the value θ(w)(i); this will happen when θ(w)(i) > θ(w)(j) for some j < i with a_{j} = a_{i} − 1. But θ(w)(i) is just the location of the k_{i}th-to-last negative step in direction a_{i}, and the smallest possible value of θ(w)(j) is the location of the l_{i}th-to-last negative step in direction a_{i} −1. Hence a′_{i} = a_{i} exactly when the condition in the lemma is satisfied, and the lemma is proven. □

Now we will define a parity-reversing involution ψ on the set of walks to Toeplitz points excluding those in Im ϕ. Given a walk w = a_{1}, …, a_{n/2}/b_{1}, …, b_{n/2} ∉ Im ϕ, take the smallest i not satisfying the condition in the lemma. Now let j be the index of the l_{i}th-to-last occurrence of a_{i} − 1 among the negative steps (if l_{i} = 0, let j = n/2 + 1). We create ψ(w) by keeping a_{1}, …, a_{i} and b_{j}, …, b_{n/2} fixed, and elsewhere in w changing all occurrences of a_{i} to a_{i} − 1 and vice-versa. Letting τ be the transposition of a_{i} and a_{i} − 1, we will now show that if w ends at T (σ), ψ(w) ends at T (σ ∘ τ), and that ψ is an involution, which will complete our proof.

From the definition of i we know that the number of occurrences of a_{i} in b_{j}, …, b_{n/2} is less than k_{i}. It must equal k_{i} −1, else the location of (k −1)st occurrence of a_{i} would provide a smaller value of i violating the condition of the lemma. We now know that there is one net positive step in the a_{i} direction, and zero net steps in the a_{i} − 1 direction, in the portion of the walk which remains fixed. This allows us to calculate ψ(w)_{a_{i}} = w_{a_{i}−1} +1 = a_{i} −σ(a_{i} −1) and ψ(w)_{a_{i}−1} = w_{a_{i}} − 1 = (a_{i} − 1) − σ(a_{i}). Of course ψ(w)_{j} = w_{j} for j ≠ a_{i} and j ≠ a_{i} − 1, so ψ(w) ends at T (σ ∘ τ), and ψ is parity-reversing as desired.

Because the steps whose values are changed do not affect the distinguishing property of the ith or earlier steps, applying ψ for a second time switches the the occurrences of a_{i} and a_{i} − 1 back to their original values, and we find that ψ(ψ(w)) = w as desired.□ Example 2: If a_{1} > 1, then l_{1} = 0, and so i = 1 violates the conditions of the lemma. ψ(w) is then given by replacing a_{1} with a_{1} − 1 and vice-versa everywhere but the first step. Example 3: Let n = 8, d = 3, and w = 1, 2, 1, 3/1, 2, 1, 3, so w ends at the origin, or T (e). Then i = 2 is the smallest value violating the conditions of the lemma, and we find ψ(w)=1, 2, 2, 3/2, 1, 1, 3 which ends at (−1, 1, 0) = T (τ) = T (e ∘ τ) where τ is the transposition of 1 and 2 and e is the identity permutation.

Here are the 14 permutations of {1, 2, 3, 4} that have no ascending subsequence of length > 2, and their associated encodings as the representatives a_{1}, a_{2}, a_{3}, a_{4}/b_{1}, b_{2}, b_{3}, b_{4} of equivalence classes of lattice walks of 8 steps in the plane:

1, 4, 3, 2 1, 2, 2, 2/1, 2, 2, 2
2, 1, 4, 3 1, 1, 2, 2/1, 1, 2, 2
2, 4, 1, 3 1, 2, 1, 2/1, 1, 2, 2

2, 4, 3, 1 1, 2, 2, 1/1, 1, 2, 2
3, 1, 4, 2 1, 1, 2, 2/1, 2, 1, 2
3, 2, 1, 4 1, 1, 1, 2/1, 1, 1, 2
3, 2, 4, 1 1, 1, 2, 1/1, 1, 1, 2
3, 4, 1, 2 1, 2, 1, 2/1, 2, 1, 2
3, 4, 2, 1 1, 2, 1, 1/1, 1, 1, 2
4, 1, 3, 2 1, 1, 2, 2/1, 2, 2, 1
4, 2, 1, 3 1, 1, 1, 2/1, 1, 2, 1
4, 2, 3, 1 1, 1, 2, 1/1, 1, 2, 1
4, 3, 1, 2 1, 1, 1, 2/1, 2, 1, 1
4, 3, 2, 1 1, 1, 1, 1/1, 1, 1, 1

4 A proof via Schensted’s algorithm

We can use some of the properties of Schensted’s algorithm [7] to give another proof of Theorem 1.

Recall that a standard tableau of shape λ = (λ_{1}, …, λ_{k}), where λ_{1} ≥ ⋯ ≥ λ_{k} ≥ 0, is an arrangement of the integers from 1 to λ_{1} + ⋯ + λ_{k} in a Young diagram of shape λ such that the numbers increase in every row and and column. For example,

1 3 4 7 2 5 6

is a standard tableau of shape (4, 3).

Schensted [7] gave a bijection from permutations of {1, 2, …, n} with no ascending subsequence of length greater than d to ordered pairs of standard tableaux of the same shape, with entries from 1 to n and with first row of length at most d. By transposing the tableaux, we may replace the condition that the first row has length at most d with the condition that the first column has length at most d; i.e., that there are at most d rows. We shall prove formula (1), or equivalently, Theorem 1, by showing that the signed sum of Theorem 1 for n even is \binom{n}{n/2} times the number of pairs of standard tableaux of the same shape with at most d rows, and entries from 1 to n/2,

There is a simple bijection from standard tableaux with at most d rows to walks in Z^{d}, starting at the origin, with unit steps in the positive coordinate directions, that stay in the region x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{d}: given such a tableau with entries 1, 2, …, m, let a_{i} be the row in which i appears. Then (a_{1}, …, a_{m}) is the direction array of the corresponding walk. Moreover, if the tableau has shape (λ_{1}, …, λ_{d}) (where some of the λ_{i} may be 0), then the corresponding walk ends at the point (λ_{1}, …, λ_{d}). For example, the standard tableau shown above corresponds to the walk with direction array (1, 2, 1, 1, 2, 2, 1).

From a permutation π of {1, 2, …, n/2} with no ascending subsequence of length greater than d, Schensted’s algorithm gives a pair of standard tableaux of the same shape, with at most d columns. Transposing these two tableaux and applying the bijection just described gives a pair of walks with direction arrays (a_{1}, …, a_{n/2}) and (b_{1}, …, b_{n/2}) that correspond to them. The condition that these tableaux have the same shape implies that the two walks end at the same point, so the walk consisting of the first walk followed by the reverse of the second, whose direction array is (a_{1}, …, a_{n/2}, −b_{n/2}, −b_{n/2−1}, … − b_{1}), is a walk of length n from the origin to itself with unit steps in the coordinate directions, all positive steps preceding all negative steps, and staying within the region x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{d}. Moreover, this correspondence is a bijection from permutations of {1, 2, …, n/2} with no ascending subsequence of length greater than d to such walks.

We shall show that the number of such walks is equal to the coefficient of x^{n}/(n/2)!^{2} in (1) by using the reflection principle, in a manner similar to [2] and [3], to construct a parityreversing involution on all walks of length n, from the origin to the Toeplitz points, with unit steps in the positive or negative coordinate directions, and all positive steps preceding all negative steps, that do not stay within the region x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{d}.

The parity-reversing involution is described most easily if we translate the walks to start at (d − 1, d − 2, …, 0) rather than (0, 0, …, 0); the walks to be counted are then restricted to the region x_{1} > ⋯ > x_{d}. For each permutation σ of {1, 2, …, d}, let U(σ) be the point (d − σ(1), d − σ(2), …, d − σ(d)). Then for the identity permutation e we have U(e) = (d − 1, d − 2, …, 0), and thus U(σ) − U(e) = T (σ).

Let R be the region { (x_{1}, x_{2}, …, x_{d}) | x_{1} > x_{2} > ⋯ > x_{d} }. Let W be the set of walks of length n from U(e) to any U(σ), with all positive steps before all negative steps, and let N be the set of walks in W that do not lie entirely within R. Note that walks in W − N must end at U(e), since U(e) is the only possible endpoint in R. To complete the proof we need only construct a parity-reversing involution on N, where the parity of a walk ending at U(σ) is defined to be the same as the parity of σ.

Let w be a walk in N from U(e) to U(σ) with direction array (c_{1}, …, c_{n}). Then there is a shortest initial segment w_{0} of w, with direction array (c_{1}, …, c_{p}), that ends outside of R. The restrictions on the steps of w imply that the endpoint (k_{1}, …, k_{d}) of w_{0} has k_{i} = k_{j} for exactly one pair (i, j) of coordinate indices with i < j. We define the walk Ψ(w) to be the walk with direction array (c_{1}, …, c_{p}, c′_{p+1}, …, c′_{n}), where (c′_{p+1}, …, c′_{n}) is obtained from (c_{p+1}, …, c_{n}) by switching i’s with j’s and switching −i’s with −j’s. Then Ψ is clearly an involution. Since w ends at U(σ) = (d−σ(1), d−σ(2), …, d−σ(i), …, d−σ(j), …, d−σ(d)), Ψ(w) will end at (d − σ(1), d − σ(2), …, d − σ(j), …, d − σ(i), …, d − σ(d)) = U(σ ∘ τ), where τ is the transposition of i and j. Thus Ψ is parity-reversing.

It follows that in the signed sum of walks in W all terms corresponding to walks in N cancel, leaving only the walks that correspond to permutations of {1, 2, …, n/2} with no ascending subsequence of length greater than d

4.1 Asymptotic estimates

Since the permutations correspond with a subset of the lattice walks from the origin to the origin, their number is bounded above by the total number of such walks. Thus, if c_{n,0} is the number of n-step walks from the origin to the origin, then we have that

\binom{2n}{n}u_{n}(d) ≤ c_{2n,0} = [\frac{x^{2n}}{(2n)!}] I_{0}(2x)^{d}
= (2n)! [x^{n}] I_{0}(2\sqrt{x})^{d}.

To estimate this coefficient of x^{n}, we can make a crude estimate by just using Cauchy’s inequality, which states that the coefficient is at most I_{0}(2\sqrt{x})^{d}/x^{n}, for every x > 0. From the known asymptotic behavior of the Bessel function, viz. I_{0}(2\sqrt{x}) ∼ Cx^{−1/4}e^{2\sqrt{x}}, we obtain by taking x := (n/d)^{2}, the estimate

u_{n}(d) ≤ K(d)n^{−(d/2−1)}d^{2n}.

If we take a little more care with the estimate, and use the fact that I_{0}(2\sqrt{x})^{d} is Hayman admissible [4], being the dth power of an entire function of order 1/2 whose zeros are all negative and real, then we get an extra factor of n^{.5} in the denominator of the above estimate, which however is still not sharp. The correct first term of the asymptotics has been found by Regev [6], and it is

u_{n}(d) ∼ \frac{d^{2n+d^{2}/2} ∏_{j=1}^{d−1} j!}{(2π)^{(d−1)/2}2^{(d^{2}−1)/2}n^{(d^{2}−1)/2}} (n → ∞) .

We can also get a lower bound on the number of permutations, but this is even less sharp. The walks that correspond to these permutations are, as we have seen, encoded by certain pairs a/b. An entry b_{i} of the array b is the length of the longest ascending subsequence that ends at the position i. It follows that as we scan the array b from left to right, whenever we see a new value for the first time, it can be only 1 unit greater than the previous largest value scanned. Thus b is a restricted growth function.

Evidently there is a 1-1 correspondence between restricted growth functions of length m whose largest entry is k and partitions of a set of m elements into k classes (ith member of the sequence is the class to which i belongs). It is easy to see, by construction, that every restricted growth function of length n/2 whose largest entry is at most d occurs as the b sequence of at least one permutation of n/2 letters with no ascending subsequence of length > d. It follows that u_{n}(d) is bounded from below by ∑_{i=1}^{d} \left\{{n \atop i}\right\}, where \left\{{n \atop i}\right\} is the Stirling number of the second kind. The dominant feature of the asymptotics of this sum, for large n and d fixed, is d^{n}, which is too small by a factor of 2^{n}, so the lower bound is much less satisfactory than the upper bound.

4.2 Connections

Schensted’s algorithms gives other information about this bijection. In his algorithm, whereby a permutation π is inserted into a tableau, the kth basic subsequence that corresponds to this insertion is defined to be the subsequence of those elements of the permutation that are first inserted as the kth element of the first row (though they may not end up there).

Now, if the permutation π is given as a sequence, then our a_{i} is the index of the basic subsequence to which π(i) belongs, and our b_{i} is the index of the basic subsequence to which i belongs. Hence the condition that characterizes the walks that correspond to permutations can be stated as follows: every element of the kth basic subsequence must be greater than the most recent element of the (k − 1)st basic subsequence.

Our thanks go to Noam Elkies for some discussions that helped to clarify our ideas about the relationship of this work to reflection principles in Weyl chambers.

References

[1] Ira Gessel, Symmetric functions and P -recursiveness, J. Comb. Theory A, 53 (1990), 257–285.

[2] Ira M. Gessel and Doron Zeilberger, Random walk in a Weyl chamber, Proc. Amer. Math. Soc. 115 (1992), no. 1, 27–31.

[3] David J. Grabiner and Peter Magyar, Random walks in Weyl chambers and the decomposition of tensor powers, J. Algebraic Combin. 2 (1993), no. 3, 239–260.

[4] W. K. Hayman, A generalisation of Stirling’s formula, J. Reine Angew. Math. 196, 67–95.

[5] Jacques Labelle, Paths in the cartesian, triangular and hexagonal lattices, Bull. Inst. Combinatorics Appl. 17 (1996), 47–61.

[6] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Advances in Math. 41, 115–136.

[7] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179–191.

[8] Herbert Wilf, Ascending subsequences of permutations and the shapes of tableaux, J. Combinatorial Theory, Ser. A 60 (1992), 155–157.

gessel@math.brandeis.edu
jlweinst@husc.harvard.edu
wilf@math.upenn.edu