Statistics On Permutations And Matchings And Partially Directed Self-avoiding Walks | Posted on:2012-09-04 | Degree:Master | Type:Thesis | Country:China | Candidate:J X Xie | Full Text:PDF | GTID:2120330335465678 | Subject:Operational Research and Cybernetics | Abstract/Summary: | PDF Full Text Request | Self-avoiding walks are lattice walks in the plane that do not pass a point more than once. They play an important role in the theory of random walks. In this paper we study symmetric partially directed self-avoiding walks (sPDSAWs) and asymmetric partially directed self-avoiding walks (asPDSAWs). These two classes of walks are closely related to matchings and permutations, respectively, and have drawn a lot of attention in enumerative combinatorics during recent years.The main results of this paper are two bijections,χ1 andχ2, between permutations and as-PDSAWs.χ1 provides the equi-distribution properties of seven pairs of statistics of permutations and asPDSAWs:the inversions of a permutation correspond to the squares enclosed by the walk and the line y=-x, the ascents of a permutation correspond to the corners of the walk, etc.χ2 provides the equi-distribution property between major indices of permutations and squares enclosed by asPDSAWs and the line y =-x. From these two bijections we obtain a new proof that the two statistics of permutations, inversion and major index, are equi-distributed.For sPDSAWs, we also give a bijection that provides one-to-one correspondences between four pairs of statistics on matchings and sPDSAWs. Finally we present three questions on sPDSAWs for future study.
| Keywords/Search Tags: | Permutation, Matching, PDSAW, Inversion, Major Index, Stirling permutation | PDF Full Text Request | Related items |
| |
|