Permutation patterns are hard to count

Let ℱ ⊂ S k be a finite set of permutations and let C n ( ℱ ) denote the number of permutations σ ∊ S n avoiding the set of patterns ℱ. We prove that { C n ( ℱ )} cannot be computed in time polynomial in n, unless EXP = ⊕EXP. Our tools also allow us to disprove the Noonan – Zeilberger conjecture which states that the sequence { C n ( ℱ )} is P-recursive.

Authors

• Scott Garrabrant
• Igor Pak

Keywords

No keywords are indexed for this paper.