Pattern avoidance is not P-recursive

2015/05/25 by Scott Garrabrant, Garrabrant, Scott, Igor Pak +1 · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Cellular Automata and Applications #Advanced Combinatorial Mathematics

paper · pdf · doi:10.48550/arxiv.1505.06508

Abstract

Let F ⊂ S_k be a finite set of permutations and let C_n(F) denote the number of permutations σ 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.

Citations

• The undecidability of the domino problem

Cited by

• Most principal permutation classes have nonrational generating functions

Related

• On the enumeration of permutations avoiding chains of patterns
• The Enumeration of Permutations With a Prescribed Number of ``Forbidden'' Patterns
• Permutations Avoiding Certain Partially-ordered Patterns
• Pattern Avoidance in Set Partitions
• On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length