tailieunhanh - Báo cáo toán học: "Pattern avoidance in partial permutations"

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: Pattern avoidance in partial permutations. | Pattern avoidance in partial permutations Anders Claesson Department of Computer and Information Sciences University of Strathclyde Glasgow G1 1XH UK Vit Jelinek Fakultat fur Mathematik Universitat Wien Garnisongasse 3 1090 Wien Austria jelinek@ Eva Jelinkovi Department of Applied Mathematics Charles University in Prague Malostranske nám. 25 118 00 Praha 1 Czech Republic eva@ Sergey Kitaev School of Computer Science Reykjavik University Menntavegi 1 101 Reykjavik Iceland and Department of Computer and Information Sciences University of Strathclyde Glasgow G1 1XH UK sergey@ Submitted May 12 2010 Accepted Jan 17 2011 Published Jan 26 2011 Mathematics Subject Classification 05A15 Abstract Motivated by the concept of partial words we introduce an analogous concept of partial permutations. A partial permutation of length n with k holes is a sequence of symbols n n1n2 nn in which each of the symbols from the set 1 2 . n k appears exactly once while the remaining k symbols of n are holes . A. Claesson V. Jelinek and S. Kitaev were supported by the Icelandic Research Fund grant no. 090038011. Supported by project 1M0021620838 of the Czech Ministry of Education. The research was conducted while E. Jelinkova was visiting ICE-TCS Reykjavik University Iceland. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P25 1 We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length k correspond to a Wilf-type equivalence class with respect to partial permutations with k 2 holes. Lastly we enumerate the partial permutations of length n with k holes avoiding a given pattern of length at most four for each n k 1. Keywords partial permutation pattern avoidance Wilf-equivalence bijection generating function Baxter