Pattern avoidance is not P-recursive

Abstract

Let $F\subset S_k$ be a finite set of permutations and let $C_n(F)$ denote the number of permutations $\sigma$ in $S_n$ avoiding the set of patterns $F$. The Noonan-Zeilberger conjecture states that the sequence $C_n(F)$ is P-recursive. We use Computability Theory to disprove this conjecture.

19 pages

References in corpus (4)

• The enumeration of simple permutations
• Overview of some general results in combinatorial enumeration
• Problems and Conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7-11, 2005
• Words in Linear Groups, Random Walks, Automata and P-Recursiveness