Most principal permutation classes have nonrational generating functions

Publication date: 24 January 2019

Abstract: We prove that for any fixed

n

, and for most permutation patterns

q

, the number

e x t u p {A v}_{n, e l l} (q)

of

q

-avoiding permutations of length

n

that consist of

e l l

skew blocks is a monotone decreasing function of

e l l

. We then show that this implies that for most patterns

q

, the generating function

s u m_{n g e q 0} e x t u p {A v}_{n} (q) z^{n}

of the sequence

e x t u p {A v}_{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.

This page was built for publication: Most principal permutation classes have nonrational generating functions