Geodesic
Lattice walks in \({\mathbf Z}^ d\) and permutations with no long ascending subsequences
The electronic journal of combinatorics, Tome 5 (1998)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/1340
Classification : 05A15, 05A05
Mots-clés : lattice walks, Toeplitz points, permutations, ascending subsequence, generating functions, Schensted algorithm 
@article{10_37236_1340,
     author = {Ira Gessel and Jonathan Weinstein and Herbert S. Wilf},
     title = {Lattice walks in \({\mathbf {Z}^} d\) and permutations with no long ascending subsequences},
     journal = {The electronic journal of combinatorics},
     year = {1998},
     volume = {5},
     doi = {10.37236/1340},
     zbl = {0885.05010},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1340/}
}
TY  - JOUR
AU  - Ira Gessel
AU  - Jonathan Weinstein
AU  - Herbert S. Wilf
TI  - Lattice walks in \({\mathbf Z}^ d\) and permutations with no long ascending subsequences
JO  - The electronic journal of combinatorics
PY  - 1998
VL  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1340/
DO  - 10.37236/1340
ID  - 10_37236_1340
ER  - 
%0 Journal Article
%A Ira Gessel
%A Jonathan Weinstein
%A Herbert S. Wilf
%T Lattice walks in \({\mathbf Z}^ d\) and permutations with no long ascending subsequences
%J The electronic journal of combinatorics
%D 1998
%V 5
%U http://geodesic.mathdoc.fr/articles/10.37236/1340/
%R 10.37236/1340
%F 10_37236_1340
Ira Gessel; Jonathan Weinstein; Herbert S. Wilf. Lattice walks in \({\mathbf Z}^ d\) and permutations with no long ascending subsequences. The electronic journal of combinatorics, Tome 5 (1998). doi: 10.37236/1340

Cité par Sources :