On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length

2012/09/11 by Miklós Bóna, Bona, Miklos
Engineering · Mathematics · #05A15 #05A16 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1209.2404

openalex publication_date 2012/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Numerical evidence suggests that certain permutation patterns of length k are easier to avoid than any other patterns of that same length. We prove that these patterns are avoided by no more than (2.25k²)ⁿ permutations of length n. In light of this, we conjecture that no pattern of length k is avoided by more than that many permutations of length n.

Related

• A probabilistic approach to consecutive pattern avoiding in permutations
• Counting Permutations that Avoid Many Patterns
• Pattern avoidance in compositions and powers of permutations
• Permutations avoiding sets of patterns with long monotone subsequences
• Pattern Avoiding Permutations Enumerated by Inversions