Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Lattice walks in Zd and permutations with no long ascending subsequences"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Lattice walks in Zd and permutations with no long ascending subsequences. | Lattice walks in Zd and permutations with no long ascending subsequences Ira Gessel Jonathan Weinstein Brandeis University Harvard University Herbert S. Wilft University of Pennsylvania Abstract We identify a set of d signed points called Toeplitz points in Zd 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 2 times the number of permutations of 1 2 . ng 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. Submitted September 27 1996 Accepted November 17 1997 1 Introduction The subject of walks on the lattice in Euclidean space is one of the most important areas of combinatorics. Another subject that has been investigated by many researchers in recent Supported in part by the National Science Foundation. This work was done during the 1996 Research Experience for Undergraduates at the University of Minnesota Duluth directed by Joseph Gallian and sponsored by the National Science Foundation and the National Security Agency. Supported in part by the Office of Naval Research. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 5 1998 R2 2 years is that of permutations without long ascending subsequences. In this paper we hnd a link between the counting functions of these two families of combinatorial objects. An ascending subsequence of length d of a permutation K of the letters 1 2 . n is a set 1 Ó i2 . id n of letters such that t ó ff i2 . T id . For example the permutation 1 2 3 4 5 6 7 8 u 2 8 5 1 3 6 77 has an ascending subsequence of length 3 at positions 1 4 8 since the values 4 5 7 are in .