Most principal permutation classes have nonrational generating functions

Miklós Bóna

Published 2019-01-24Version 1

We prove that for any fixed $n$, and for most permutation patterns $q$, the number $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\geq 0} Av_n(q)z^n$ of the sequence $Av_n(q)$ of the numbers of $q$-avoiding permutations is not rational.