A probabilistic approach to consecutive pattern avoiding in permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Perarnau, Guillem

关键词: Permutations;    Consecutive pattern avoiding;    Monotone patterns;    CMP conjecture;    Probabilistic method;   

DOI  :  10.1016/j.jcta.2013.02.004

来源: Elsevier

【 摘 要 】

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. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free