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

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 ${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.