Most principal permutation classes have nonrational generating functions

Abstract

We prove that for any fixed $n$, and for most permutation patterns $q$, the number ${\text{Av}}_{n,\ell }(q)$ of $q$-avoiding permutations of length $n$ that consist of $\ell$ skew blocks is a monotone decreasing function of $\ell$. We then show that this implies that for most patterns $q$, the generating function ${\sum }_{n\ge 0}{\text{Av}}_n(q)z^n$ of the sequence ${\text{Av}}_n(q)$ of the numbers of $q$-avoiding permutations is not rational. Placing our results in a broader context, we show that for rational power series $F(z)$ and $G(z)$ with nonnegative real coefficients, the relation $F(z)=1/(1-G(z))$ is supercritical, while for most permutation patterns $q$, the corresponding relation is not supercritical.

11 pages

References in corpus (1)

• Pattern avoidance is not P-recursive