Avoidance of boxed mesh patterns on permutations |
| |
Authors: | Sergey Avgustinovich Sergey Kitaev Alexandr Valyuzhenich |
| |
Affiliation: | 1. Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave, 630090 Novosibirsk, Russia;2. Department of Computer and Information Sciences, University of Strathclyde, Livingstone Tower, 26 Richmond Street, Glasgow G1 1XH, United Kingdom;3. Novosibirsk State University, 2 Pirogova Street, 630090 Novosibirsk, Russia |
| |
Abstract: | We introduce the notion of a boxed mesh pattern and study avoidance of these patterns on permutations. We prove that the celebrated former Stanley–Wilf conjecture is not true for all but eleven boxed mesh patterns; for seven out of the eleven patterns the former conjecture is true, while we do not know the answer for the remaining four (length-four) patterns. Moreover, we prove that an analogue of a well-known theorem of Erd?s and Szekeres does not hold for boxed mesh patterns of lengths larger than 2. Finally, we discuss enumeration of permutations avoiding simultaneously two or more length-three boxed mesh patterns, where we meet generalized Catalan numbers. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|