\magnification =1200\nopagenumbers\noindent                    
{\bf Ira Gessel, Jonathan Weinstein, Herbert S. Wilf} 
\medskip\noindent
{\bf Lattice walks in $Z^d$ and permutations with no long
ascending subsequences}
\vskip.5cm
We identify a set of $d!$ signed points, called {\sl 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 ${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