2012/08/27 by Guillem Perarnau, Perarnau, Guillem
Mathematics · Engineering · Computer Science · #Advanced Combinatorial Mathematics #graph theory and CDMA systems #Bayesian Methods and Mixture Models
paper · pdf · doi:10.48550/arxiv.1208.5366
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 idea to give explicit upper and lower bounds on the number of permutations avoiding a pattern of length m. As a corollary, we obtain a simple proof of the CMP conjecture, regarding the most avoided pattern, recently shown by Elizalde. Finally, we also show that most of the patterns behave similar to the least avoided one.