Statistics On Permutations And Matchings And Partially Directed Self-avoiding Walks

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.