Permutations Containing Many Patterns

2006/09/27 by Michael Albert, M. H. Albert, Micah Coleman +2 · 2 citations
Engineering · Mathematics · #Advanced Combinatorial Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05A16 #msc:05D40

paper · pdf · doi:10.1007/s00026-007-0319-9

published as Annals of Combinatorics, Vol 11 (2007), 265-270

arxiv created 2006/09/27 · openalex publication_date 2007/12/01 · arxiv updated 2012/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It is shown that the maximum number of patterns that can occur in a permutation of length n is asymptotically 2ⁿ. This significantly improves a previous result of Coleman.

Cited by

• Dense Packing of Patterns in a Permutation
• Asymptotic bounds for permutations containing many different patterns