tailieunhanh - Báo cáo toán học: "Multiple pattern avoidance with respect to fixed points and excedances"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Multiple pattern avoidance with respect to fixed points and excedances. | Multiple pattern avoidance with respect to fixed points and excedances Sergi Elizalde Department of Mathematics MIT Cambridge MA 02139 sergi@ Submitted Oct 22 2003 Accepted Jul 25 2004 Published Jul 29 2004 Mathematics Subject Classifications 05A15 05A05 Abstract We study the distribution of the statistics number of fixed points and number of excedances in permutations avoiding subsets of patterns of length 3. We solve all the cases of simultaneous avoidance of more than one pattern giving generating functions enumerating these two statistics. Some cases are generalized to patterns of arbitrary length. For avoidance of one single pattern we give partial results. We also describe the distribution of these statistics in involutions avoiding any subset of patterns of length 3. The main technique is to use bijections between pattern-avoiding permutations and certain kinds of Dyck paths in such a way that the statistics in permutations that we study correspond to statistics on Dyck paths that are easy to enumerate. 1 Introduction The problem of enumerating pattern-avoiding permutations also known as restricted permutations has generated a lot of research over the last few decades. One of the most referenced papers on this topic is 18 which contains a systematic enumeration of permutations avoiding any subset of patterns of length 3. However the study of statistics in pattern-avoiding permutations started developing very recently and the interest in this topic is currently growing. Two of the most studied permutation statistics have been the number of fixed points and the number of excedances of a restricted permutation. For example in 16 6 8 it is shown the surprising fact that the joint distribution of these two statistics is the same in 132- and in 321-avoiding permutations. In 5 involutions avoiding any single pattern of length 3 are studied with respect to the number of fixed points. Another paper 14 deals with the enumeration of permutations with a .