A probabilistic approach to consecutive pattern avoiding in permutations

作者：Perarnau Guillem^*

来源：Journal of Combinatorial Theory - Series A, 2013, 120(5): 998-1011.

DOI：10.1016/j.jcta.2013.02.004

• Permutations
• Consecutive pattern avoiding
• Monotone patterns
• CMP conjecture
• Probabilistic method

We present a new approach to the problem of enumerating permutations of length n that avoid a fixed consecutive pattern of length m. We use this approach to give explicit upper and lower bounds on the number of permutations avoiding a consecutive pattern of length m. As a corollary we obtain a simple proof of the CMP conjecture from Elizalde and Noy, regarding the most avoided pattern, recently proved by Elizalde. We also show that most of the patterns behave similarly to the least avoided one.

• 出版日期2013-7