On the Number of Permutations Avoiding a Given Pattern

Noga Alon, Ehud Friedgut

Research output: Contribution to journalArticle

29 Scopus citations

Abstract

Let σ∈Sk and τ∈Sn be permutations. We say τ contains σ if there exist 1≤x1<x2<...<xk≤n such that τ(xi)<τ(xj) if and only if σ(i)<σ(j). If τ does not contain σ we say τ avoids σ. Let F(n, σ)=(τ∈Snτavoidsσ). Stanley and Wilf conjectured that for any σ∈Sk there exists a constant c=c(σ) such that F(n, σ)≤cn for all n. Here we prove the following weaker statement: For every fixed σ∈Sk, F(n, σ)≤cnγ*(n), where c=c(σ) and γ*(n) is an extremely slow growing function, related to the Ackermann hierarchy.

Original languageEnglish (US)
Pages (from-to)133-140
Number of pages8
JournalJournal of Combinatorial Theory. Series A
Volume89
Issue number1
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On the Number of Permutations Avoiding a Given Pattern'. Together they form a unique fingerprint.

  • Cite this