Most principal permutation classes, and t-stack sortable permutations, have nonrational generating functions
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 481-487
Citer cet article
Voir la notice de l'article provenant de la source Comenius University
We prove that for any fixed $n$, and for most permutation patterns $q$, the number $\textup{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} \textup{Av}_n(q)z^n$ of the sequence $\textup{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.