Affordable Access

Publisher Website

A probabilistic approach to consecutive pattern avoiding in permutations

Authors
Journal
Journal of Combinatorial Theory Series A
0097-3165
Publisher
Elsevier
Volume
120
Issue
5
Identifiers
DOI: 10.1016/j.jcta.2013.02.004
Keywords
  • Permutations
  • Consecutive Pattern Avoiding
  • Monotone Patterns
  • Cmp Conjecture
  • Probabilistic Method

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.