%%%%%%%%%%%%%%%%
%A LaTeX2e file
\documentclass[12pt]{article}
\usepackage{latexsym}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%macros for Young tableaux
\newdimen\squaresize \squaresize=20pt
\newdimen\thickness \thickness=.4pt
\def\Square#1{\hbox{\vrule width \thickness
\vbox to \squaresize{\hrule height \thickness\vss
\hbox to \squaresize{\hss#1\hss}
\vss\hrule height\thickness}%
\vrule width \thickness}
\kern-\thickness}
\def\vsquare#1{\vbox{\Square{$#1$}}\kern-\thickness}
\def\blank{\omit\hskip\squaresize}
\def\young#1{
\vbox{\smallskip\offinterlineskip
\halign{&\vsquare{##}\cr #1}}}
%
%end of macros for young tableaux
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 5 (1998), \#R2\hfill}
\thispagestyle{empty}
\textwidth 6.5 in
\hoffset -.5in
\begin{document}
\title{Lattice walks in ${\mathbf{Z}}^d$ and permutations with no long
ascending subsequences}
\author{Ira Gessel\thanks{Supported in part by the National Science
Foundation.}\\Brandeis University\and
Jonathan Weinstein\thanks{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.}\\Harvard University\and
Herbert S. Wilf\hspace{2pt}\thanks{Supported in part by the Office of Naval
Research.}\\University of Pennsylvania}
\date{}
\maketitle
\begin{abstract}
We identify a set of $d!$ signed points, called \textit{Toeplitz points},
in ${\mathbf{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 ${n\choose n/2}$ times the number
of permutations of $\{1,2,\dots ,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.
\end{abstract}
\smallskip
\centerline{Submitted: September 27, 1996; Accepted: November 17, 1997}
\smallskip
\section{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.
An ascending subsequence of length $d$ of a permutation $\pi$ of the
letters $\{1,2,\dots ,n\}$ is a set
$1\le i_1d$, 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 \cite{Re}. An explicit generating
function of the sequence has been found
by Gessel \cite{Ge}, in the form
\begin{equation}
\label{eq:ges}
\sum_{n\ge
0}\frac{u_n(d)}{n!^2}x^{2n}=\det{\bigl(I_{|r-s|}(2x)\bigr)_{r,s=1,\dots ,d}}.
\end{equation}
in which the $I_{\nu}$'s are the Bessel functions of imaginary argument.
We will use the result (\ref{eq:ges}) in section \ref{sec:gf} to establish our
correspondence
with lattice walks. Interestingly, however, by providing a combinatorial
proof of this correspondence, in section \ref{sec:comb} below,
\textit{we will be giving an independent and purely combinatorial proof of
the theorem (\ref{eq:ges})}.
As an open problem, we mention that it would be of interest to
illuminate the connection between Theorem \ref{th:one} below and the result of
\cite{Wi}, which, at least superficially, have striking similarities of
form.
\section{The generating function approach}
\label{sec:gf}
\subsection{Generating functions for lattice walks}
Let $c_{n,\mathbf{k}}$ denote the number of walks of $n$ steps from the
origin to the
point $\mathbf{k}=(k_1,\dots ,k_d)\in\mathbf{Z}^d$, where each step is a
change of $\pm 1$
in one coordinate. If $d=1$ it is clear that
$c_{n,k}={n\choose \frac{n+k}{2}}$, from which we have the exponential
generating function
\[\sum_{n\ge 0}\frac{c_{n,k}}{n!}x^n=\sum_{n\ge
0}\frac{x^n}{(\frac{n+k}{2})!(\frac{n-k}{2})!}=\sum_{n\ge
0}\frac{x^{2n+k}}{n!(n+k)!}=I_k(2x),\]
where $I_k(t)$ is the Bessel function of imaginary argument.
Since in $\mathbf{Z}^d$ all walks of $n$ steps from the origin to
$\mathbf{k}$ are
shuffles of independent 1-dimensional walks to the coordinates of
$\mathbf{k}$, we have the $d$-dimensional exponential generating
function
\begin{equation}
\label{eq:gf}
\sum_{n\ge 0}\frac{c_{n,\mathbf{k}}}{n!}x^n=\prod_{\nu=1}^dI_{k_{\nu}}(2x).
\end{equation}
\subsection{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
(\ref{eq:ges}) with the generating function (\ref{eq:gf}).
Notice that the determinant on the right side of (\ref{eq:ges}) is a sum of
$d!$ terms, each of which
is a product of $d$ Bessel functions. Products of $d$ Bessel functions,
according to (\ref{eq:gf}) 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. (\ref{eq:gf}) above, with appropriate signs,
with
appropriate values of the terminal point $\mathbf{k}$, and thereby relate
such
permutations to lattice walks.
For each permutation $\sigma$ of
$\{1,\dots,d\}$, the \textit{Toeplitz point} $T(\sigma)$ is the point
$(1-\sigma(1), 2-\sigma(2),\dots, d-\sigma(d))\in
{\mathbf{Z}}^d$. The number of Toeplitz points in
${\mathbf{Z}}^d$ is obviously $d!$.
The \textit{sign} of $T(\sigma)$ is the parity ($=\pm 1$) of $\sigma$.
For example, the six Toeplitz points in ${\mathbf{Z}}^3$, together with
their signs, are
\begin{eqnarray}
\label{eq:tpts}
\mathrm{sign}=+1:\ &&(0,0,0),(-1,-1,2),(-2,1,1)\\
\mathrm{sign}=-1:\ && (0,-1,1),(-1,1,0),(-2,0,2).\nonumber
\end{eqnarray}
\subsection{Walks and permutations}
On the right side of eq. (\ref{eq:gf}) above, successively replace the
point $\mathbf{k}$ by
each of the Toeplitz points in ${\mathbf{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
(\ref{eq:ges}), and
therefore it will be equal to the power series on the left side of
(\ref{eq:ges}).
On the other hand, the coefficient of $x^n$ on the left side of
(\ref{eq:gf}), 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.
\begin{theorem}
\label{th:one}
Fix integers $d\ge 1$ and $n\ge 0$. The signed sum of the numbers of
lattice walks in ${\mathbf{Z}}^d$ from the origin
to the Toeplitz points is 0 if $n$ is odd, and is ${n\choose n/2}$ times
the number of permutations of $n/2$ letters that have no ascending
subsequence of length $>d$, if $n$ is even.
\end{theorem}
As an example we will work out the case $n=6$, $d=3$. The six Toeplitz
points are shown in (\ref{eq:tpts}) 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 ${6\choose 3}=20$ times the number of
permutations (namely 6) of three letters that have no ascending subsequence
of length $>3$.
\section{A combinatorial approach}
\label{sec:comb}
In this section we will provide a combinatorial proof of Theorem
\ref{th:one}.
We will first show how the walks can be divided into classes of
${n\choose 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 \ref{lem:fxp}
below)
of those classes of
walks that are the images of some permutation without long ascending
subsequences.
\subsection{Second proof of Theorem \ref{th:one}}
Assume $n$ is even. By the \textit{direction array} of a walk $w$ of $n$ steps
we mean the array of length $n$ whose $i$th entry is $r$ (resp. $-r$) if
the $i$th step
of the walk $w$ is parallel (resp. antiparallel) to the $r$th coordinate
axis.
Since the sum of the
coordinates of the Toeplitz point $T(\sigma)$ is $\sum i - \sum \sigma(i)
=0$, every walk to a Toeplitz point will have equally many positive and
negative entries in its
direction array. Call two walks \textit{equivalent} if the subsequences of
their
$n/2$ positive direction array entries are identical, as are their negative
subsequences. There will
be ${n\choose 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,\dots ,a_{n/2} / b_1,\dots ,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 $j$th coordinate of the endpoint of walk $w$.
Now, given a permutation $\pi$ of $\{1,2,...,n/2\}$ with no
ascending subsequence of length greater than $d$, we create an $n$-step
walk $\phi(\pi)$ = $a_1,\dots ,a_{n/2} / b_1,\dots ,b_{n/2}$ by
letting $a_i$ be the length of the longest ascending subsequence of
$\pi$ ending with the value $\pi(i)$, and $b_i$ be the length of
the longest ascending subsequence of $\pi$ ending at the value $i$.
Since the $b_i$ are a rearrangement of the $a_i$, $\phi(\pi)$ ends
at the origin.
We now show that $\phi$ is injective. Let $w = a_1,\dots ,a_{n/2} /
b_1,\dots ,b_{n/2}$ be a walk ending at the origin. For each $j$ such
that $1 \leq j \leq d$, let $A_j=\{i:a_i=j\}$ and $B_j=\{i:b_i=j\}$.
We observe from the definition of $\phi$ that $w=\phi(\pi)$ implies
$b_{\pi(i)}=a_i$ for each $i$, so $\pi(A_j)=B_j$. Furthermore,
the restriction of $\pi$ to $A_j \stackrel{\pi}{\rightarrow} B_j$
must be
order reversing---for suppose to the contrary that $\pi(i_1)=k_1$ and
$\pi(i_2)=k_2$, with $i_1,i_2 \in A_j$, $k_1,k_2 \in B_j$,
$i_11$, let $k_i$ and $l_i$
be the numbers of occurrences of $a_i$ and $a_i-1$, respectively, in
$a_1, \dots,a_i$. We then have the following result, which
characterizes the walks that correspond to permutations.
\begin{lemma}
\label{lem:fxp}
$w \in \mbox{Im } \phi$ 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$.
\end{lemma}
\smallskip
\noindent{\bf Proof}:
First, suppose $w$ does not end at the origin, so $w \not\in \mbox{Im } \phi$.
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} \leq 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
$\phi(\theta(w))=w$ is equivalent to the condition that $w$ and
$\phi(\theta(w))$ agree in just their positive steps, by the stipulation
in the construction of $\theta(w)$ that $\pi(A_j)=B_j$. Suppose the
two walks agree in all positive steps before the $i$th, and let
$\phi(\theta(w))$ in its $i$th step go in direction $a_i^{\prime}$. We
will never have $a_i^{\prime}>a_i$; for then let $j$ be the location of
the $a_i$th term of an ascending subsequence of $\theta(w)$ of length
$a_i^{\prime}$ ending with the value $\theta(w)(i)$. Then $a_j=a_i$,
$j*\theta(w)(j)$ for some
$j**1$, then $l_1=0$, and so $i=1$
violates the conditions of the lemma. $\psi(w)$ is then given by
replacing $a_1$ with $a_1-1$ and vice-versa everywhere but the first step.
\noindent{\bf 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 $\psi(w)$=$1,2,2,3/2,1,1,3$ which
ends at $(-1,1,0)=T(\tau)=T(e\circ\tau)$ where $\tau$ is the
transposition of 1 and 2 and $e$ is the identity permutation.
\smallskip 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:
\begin{eqnarray}
{1, 4, 3, 2}&& {1, 2, 2, 2/ 1, 2, 2, 2}\nonumber\\
{2, 1, 4, 3}&& {1, 1, 2, 2/ 1, 1, 2, 2}\nonumber\\
{2, 4, 1, 3}&& {1, 2, 1, 2/ 1, 1, 2, 2}\nonumber\\
{2, 4, 3, 1}&& {1, 2, 2, 1/ 1, 1, 2, 2}\nonumber\\
{3, 1, 4, 2}&& {1, 1, 2, 2/ 1, 2, 1, 2}\nonumber\\
{3, 2, 1, 4}&& {1, 1, 1, 2/ 1, 1, 1, 2}\nonumber\\
{3, 2, 4, 1}&& {1, 1, 2, 1/ 1, 1, 1, 2}\nonumber\\
{3, 4, 1, 2}&& {1, 2, 1, 2/ 1, 2, 1, 2}\nonumber\\
{3, 4, 2, 1}&& {1, 2, 1, 1/ 1, 1, 1, 2}\nonumber\\
{4, 1, 3, 2}&& {1, 1, 2, 2/ 1, 2, 2, 1}\nonumber\\
{4, 2, 1, 3}&& {1, 1, 1, 2/ 1, 1, 2, 1}\nonumber\\
{4, 2, 3, 1}&& {1, 1, 2, 1/ 1, 1, 2, 1}\nonumber\\
{4, 3, 1, 2}&& {1, 1, 1, 2/ 1, 2, 1, 1}\nonumber\\
{4, 3, 2, 1}&& {1, 1, 1, 1/ 1, 1, 1, 1}\nonumber
\end{eqnarray}
\section{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 \textit{standard tableau} of shape
$\lambda=(\lambda_1,\dots,\lambda_k)$, where
$\lambda_1\ge\cdots\ge\lambda_k\ge0$,
is an arrangement of the integers from 1 to $\lambda_1+\cdots+\lambda_k$ in a
Young diagram of shape $\lambda$ such that the numbers increase in every row
and and column. For example,
$$\young{1&3&4&7\cr 2&5&6\cr}$$
is a standard tableau of shape $(4,3)$.
Schensted [7] gave a bijection from permutations
of $\{1,2,\dots,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 ${n\choose 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 ${\bf Z}^d$, starting at the origin, with unit steps in the positive
coordinate directions, that stay in the region
$x_1\ge x_2\ge \cdots\ge x_d$: given such a tableau with entries $1,
2,\dots, m$, let
$a_i$ be the row in which $i$ appears. Then $(a_1,\dots, a_m)$ is the
direction array of the corresponding walk. Moreover, if the tableau has shape
$(\lambda_1,\dots,\lambda_d)$ (where some of the $\lambda_i$ may be 0), then
the corresponding walk ends at the point $(\lambda_1,\dots,\lambda_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 $\pi$ of $\{1,2,\dots,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,\dots, a_{n/2})$ and
$(b_1,\dots, 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,\dots, a_{n/2}, -b_{n/2}, -b_{{n/2}-1},\dots -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\ge x_2\ge
\cdots\ge x_d$. Moreover, this correspondence is a bijection from permutations
of $\{1,2,\dots,{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 parity-reversing 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\ge x_2\ge\cdots\ge x_d$.
The parity-reversing involution is described most easily if we translate
the walks to start at $(d-1,d-2,\dots, 0)$ rather than $(0,0,\dots,0)$; the
walks to be counted are then restricted to the region $x_1>\cdots>x_d$.
For each permutation $\sigma$ of
$\{1,2,\dots,d\}$, let $U(\sigma)$ be the point $(d-\sigma(1), d-\sigma(2),
\dots, d-\sigma(d))$. Then for the identity permutation $e$ we have
$U(e)=(d-1,d-2,\dots,0)$, and thus $U(\sigma)-U(e)=T(\sigma).$
Let $R$ be the region $\{\,(x_1,x_2,\dots,x_d) \mid x_1>x_2>\cdots>x_d\,\}$.
Let
$W$ be the set of walks of length $n$ from $U(e)$ to any $U(\sigma)$, 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(\sigma)$ is
defined to
be the same as the parity of $\sigma$.
Let $w$ be a walk in $N$ from $U(e)$ to $U(\sigma)$ with direction array
$(c_1,\dots, c_n)$. Then there is a shortest initial segment $w_0$ of $w$,
with
direction array $(c_1,\dots, c_p)$, that ends outside of $R$. The
restrictions on
the steps of $w$ imply that the endpoint $(k_1,\dots, k_d)$ of $w_0$ has
$k_i=k_j$
for exactly one pair $(i,j)$ of coordinate indices with $i0$.
{From} the known asymptotic behavior of the Bessel function, viz.
$I_0(2\sqrt{x})\sim Cx^{-1/4}e^{2\sqrt{x}}$,
we obtain by taking $x:=(n/d)^2$, the estimate
\[u_n(d)\le 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 \cite{Ha}, being the $d$th 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 \cite{Re}, and it is
\[u_n(d) \sim \frac{d^{2n + d^2 /2} \prod\limits_{j=1}^{d-1} j!}
{(2 \pi)^{(d-1)/2} 2^{(d^2 -1)/2} n^{(d^2 -1)/2}} \qquad
(n \to \infty) ~.\]
We can also get a \textit{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 $\mathbf{a}/\mathbf{b}$. An entry
$b_i$ of the array $\mathbf{b}$ is the length of the longest
ascending subsequence that ends at the position $i$. It follows that as
we scan the array $\mathbf{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 $\mathbf{b}$ is a \textit{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 ($i$th 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
$\mathbf{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
$\sum_{i=1}^d{n\brace i}$, where ${n\brace i}$ 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.
\subsection{Connections}
Schensted's algorithms gives other information about this bijection.
In his algorithm, whereby a permutation $\pi$ is
inserted into a tableau, the $k$th \textit{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 $k$th element of the first
row (though they may not end up there).
Now, if the permutation $\pi$ is given as a sequence, then our $a_i$
is the index of the basic subsequence to which
$\pi (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 $k$th 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.
\newpage
\vspace{25pt}
\begin{thebibliography}{aaa}
\bibitem{Ge} Ira Gessel, Symmetric functions and $P$-recursiveness,
\textit{J. Comb. Theory A}, \textbf{53} (1990), 257--285.
\bibitem{GZ} Ira M. Gessel and Doron Zeilberger, Random walk in a Weyl
chamber, \textit{Proc. Amer. Math. Soc.} \textbf{115} (1992), no. 1, 27--31.
\bibitem{GM} David J. Grabiner and Peter Magyar, Random walks in Weyl
chambers and the decomposition of tensor powers, \textit{J. Algebraic
Combin.} \textbf{2} (1993), no. 3, 239--260.
\bibitem{Ha} W. K. Hayman, A generalisation of Stirling's formula,
\textit{J. Reine Angew. Math.} \textbf{196}, 67--95.
\bibitem{LaB} Jacques Labelle, Paths in the cartesian, triangular and
hexagonal lattices,
\textit{Bull. Inst. Combinatorics Appl.} \textbf{17} (1996), 47--61.
\bibitem{Re} A. Regev, Asymptotic values for degrees associated with
strips of Young diagrams, \textit{Advances in Math.} \textbf{41},
115--136.
\bibitem{Sc} C. Schensted, Longest increasing and decreasing subsequences,
\textit{Canad. J. Math.} \textbf{13} (1961),
179--191.
\bibitem{Wi} Herbert Wilf, Ascending subsequences of permutations and the
shapes of tableaux,
\textit{J. Combinatorial Theory, Ser. A} \textbf{60} (1992), 155--157.
\end{thebibliography}
\vspace{.5in}
\noindent\texttt{gessel@math.brandeis.edu}\\
\texttt{jlweinst@husc.harvard.edu}\\
\texttt{wilf@math.upenn.edu}
\end{document}
*