Noonan–Zeilberger conjecture on P-recursiveness of pattern-avoidance sequences

Let $S_k$ be the symmetric group on $k$ letters. For a fixed finite set of patterns $\subset S_k$, let $C_n(\mathcal{F})$ be the number of permutations in $S_n$ avoiding every pattern in $\mathcal{F}$. An integer sequence $\{a_n\}$ is P-recursive if it satisfies a nontrivial linear recurrence with polynomial coefficients, namely

$$q_0(n)a_n+q_1(n)a_{n-1}+\cdots+q_k(n)a_{n-k}=0$$

for some $q_i(x)\in\mathbb Z[x]$. Noonan–Zeilberger conjecture. For every fixed finite set of patterns $\mathcal{F}\subset S_k$, the sequence $\{C_n(\mathcal{F})\}$ is P-recursive. This was a longstanding conjecture supported by many positive results for special pattern sets, but the paper disproves it.