Lattice walks in Z^ d and permutations with no long ascending subsequences
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.
- Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods
- On extremal permutations avoiding _N=NN-1 1
- Stieltjes moment sequences for pattern-avoiding permutations
- Counting signed vexillary permutations
- Exact solution of some quarter plane walks with interacting boundaries
- Decreasing subsequences in permutations and Wilf equivalence for involutions
- On the distribution of the length of the longest increasing subsequence of random permutations
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Enumerating \(r\)c-invariant permutations with no long decreasing subsequences
- Avoidance of partitions of a three-element set
- Riordan matrices and higher-dimensional lattice walks
This page was built for publication: Lattice walks in \({\mathbf Z}^ d\) and permutations with no long ascending subsequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1379124)
