Most principal permutation classes, and t-stack sortable permutations, have nonrational generating functions

Main Article Content

Miklós Bóna

Abstract

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.

Article Details

How to Cite
Bóna, M. (2019). Most principal permutation classes, and t-stack sortable permutations, have nonrational generating functions. Acta Mathematica Universitatis Comenianae, 88(3), 481-487. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1204/684
Section
EUROCOMB 2019