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 (6)

• An aperiodic hexagonal tile
• 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
• Pattern-Avoiding Involutions: Exact and Asymptotic Enumeration
• Words in Linear Groups, Random Walks, Automata and P-Recursiveness

Cited by in corpus (6)

• Gröbner methods for representations of combinatorial categories
• Complexity problems in enumerative combinatorics
• The undecidability of joint embedding and joint homomorphism for hereditary graph classes
• Most principal permutation classes have nonrational generating functions
• Long increasing subsequences and non-algebraicity
• The undecidability of joint embedding for 3-dimensional permutation classes