%%%%%%%%%%%%%%%%
%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_1<i_2<\dots <i_d\le n$ of letters such that
$\pi(i_1)<\pi(i_2)<\dots <\pi(i_d)$. For example, the
permutation
\[ \left(\matrix{1&2&3&4&5&6&7&8\cr 4&2&8&5&1&3&6&7\cr}\right) \]
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,\dots ,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 \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_1<i_2$, and $k_1<k_2$.  Then there is an ascending subsequence of
$\pi$ 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 \in B_j$.  These
properties determine $\pi$ uniquely, since the $A_j$ cover all of
$\{1,2,...,n/2\}$, so $\phi$ is indeed injective.  For any walk $w$
ending at the origin, denote the permutation determined in this manner
by $\theta(w)$.  We have shown that $w \in \mbox{Im } \phi$ if and only if
$\phi(\theta(w))=w$.

\noindent{\bf 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 $\theta(w)(1)=2$ and $\theta(w)(4)=1$; $A_2 = \{2,3\}$
and $B_2 = \{3,4\}$, so $\theta(w)(2)=4$, $\theta(w)(3)=3$.  As a sequence,
then, $\theta(w)$ = 2,4,3,1---and indeed, $\phi(\theta(w))=w$.

\bigskip
Let $w = a_1,\dots ,a_{n/2} / b_1,\dots ,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, \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<i$, but $\theta(w)(j)<\theta(w)(i)$, contrary to the definition of
$\theta$. We will have $a_i^{\prime} \geq a_i$ when there is an ascending
subsequence of $\theta(w)$ of length $a_i$ ending with the value 
$\theta(w)(i)$; this will happen when $\theta(w)(i)>\theta(w)(j)$ for some
$j<i$ with $a_j=a_i-1$.  But $\theta(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 $\theta(w)(j)$ is the location of the $l_i$th-to-last
negative step in direction $a_i-1$.  Hence $a_i^{\prime}=a_i$ exactly when
the condition in the lemma is satisfied, and the lemma is proven. $\Box$

\bigskip Now we will define a parity-reversing involution $\psi$ on the
set of walks to Toeplitz points excluding those in Im $\phi$.  Given a
walk $w = a_1,\dots ,a_{n/2} / b_1,\dots ,b_{n/2} \not\in \mbox{Im }\phi$,
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 $\psi(w)$ by
keeping $a_1,\dots,a_i$ and $b_j,\dots,b_{n/2}$ fixed, and elsewhere in
$w$ changing all occurrences of $a_i$ to $a_i-1$ and vice-versa.  Letting
$\tau$ be the transposition of $a_i$ and $a_i-1$, we will now show that if
$w$ ends at $T(\sigma)$, $\psi(w)$ ends at $T(\sigma\circ\tau)$, and that
$\psi$ 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,\dots,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 $\psi(w)_{a_i} = w_{a_i-1}+1 = a_i-\sigma(a_i-1)$
and $\psi(w)_{a_i-1} = w_{a_i}-1 = (a_i-1)-\sigma(a_i)$.  Of course
$\psi(w)_j = w_j$ for $j \neq a_i$ and $j \neq a_i-1$, so $\psi(w)$ ends
at $T(\sigma\circ\tau)$, and $\psi$ is parity-reversing as desired. 

Because the steps whose values are changed do not affect the
distinguishing property of the $i$th or earlier steps, applying $\psi$
for a second time switches the the occurrences of $a_i$ and $a_i-1$
back to their original values, and we find that
$\psi(\psi(w))=w$ as desired.$\Box$

\smallskip \noindent{\bf Example 2}: If $a_1>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 $i<j$. We define the
walk $\Psi(w)$ to be the walk with direction array $(c_1,\dots, c_p,
c_{p+1}',\dots,c_n')$, where $(c_{p+1}',\dots,c_n')$ is obtained from 
$(c_{p+1},\dots,c_n)$ by switching $i$'s with $j$'s and switching $-i$'s with
$-j$'s. Then $\Psi$ is clearly an involution. Since $w$ ends at
$U(\sigma)=(d-\sigma(1), d-\sigma(2),\dots, d-\sigma(i),\dots,
d-\sigma(j),\dots,
d-\sigma(d))$, $\Psi(w)$ will end at
$(d-\sigma(1), d-\sigma(2),\dots, d-\sigma(j),\dots, d-\sigma(i),\dots,
d-\sigma(d))=U(\sigma\circ \tau)$, where $\tau$ is the transposition of
$i$ and
$j$. Thus $\Psi$ 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,\dots,n/2\}$ with no ascending subsequence of length greater
than $d$



\subsection{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,\mathbf{0}}$ is the number 
of $n$-step walks from the origin to the origin, then we have that
\begin{eqnarray*}
{2n\choose n}u_n(d)\le
c_{2n,\mathbf{0}}&=&\left[\frac{x^{2n}}{(2n)!}\right]I_0(2x)^d\\
&=&(2n)!\left[x^n\right]I_0(2\sqrt{x})^d.
\end{eqnarray*}
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})\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}