Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Using homological duality in consecutive pattern avoidance. | Using homological duality in consecutive pattern avoidance Anton Khoroshkin Boris Shapiro Departement Matematik ETH Department of Mathematics CH-8092 Zurich Switzerland and Stockholm University Lab. 170 ITEP Moscow SE-106 91 Stockholm SE RU-117259 Moscow Russia shapiro@ Submitted Sep 30 2010 Accepted May 16 2011 Published May 25 2011 Mathematics Subject Classifications 05A15 05A05 Abstract Using the approach suggested in 2 we present a sufficient condition guaranteeing that two collections of patterns of permutations have the same exponential generating functions for the number of permutations avoiding elements of these collections as consecutive patterns. In short the coincidence of the latter generating functions is guaranteed by a length-preserving bijection of patterns in these collections which is identical on the overlappings of pairs of patterns where the overlappings are considered as unordered sets. Our proof is based on a direct algorithm for the computation of the inverse generating functions. As an application we present a large class of patterns where this algorithm is fast and in particular allows us to obtain a linear ordinary differential equation with polynomial coefficients satisfied by the inverse generating function. 1 Introduction In recent years the theory of consecutive pattern avoidance for permutations has experienced a rapid development since the publication of the important paper 5 . Among the latest publications one should mention 1 9 12 4 where a number of special cases has been treated and the corresponding exponential generating functions explicitly found. The present text is devoted to the same topic and is an extension of the application of homological supported by RFBR 10-01-00836 RFBR-CNRS-10-01-93111 RFBR-CNRS-10-01-93113 and by the Federal Programm of Ministry of Education and Science of the Russian Federation under contract THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2 2011
