Lattice walks in \({\mathbf Z}^ d\) and permutations with no long ascending subsequences (Q1379124)

Summary: We identify a set of \(d!\) signed points, called 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.