pith. sign in

arxiv: 1505.06508 · v1 · pith:SOZA44L6new · submitted 2015-05-25 · 🧮 math.CO · cs.CC· cs.FL

Pattern avoidance is not P-recursive

Scott Garrabrant , Igor Pak This is my paper
classification 🧮 math.CO cs.CCcs.FL
keywords conjecturep-recursivepermutationsavoidanceavoidingcomputabilitydenotedisprove
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Uncountably many enumerations of well-quasi-ordered permutation classes

    math.CO 2022-11 unverdicted novelty 8.0

    Constructs an uncountable family of well-quasi-ordered permutation classes with pairwise distinct enumeration sequences, disproving the conjecture that all such classes have algebraic generating functions.