Permutations with exactly one copy of a decreasing pattern of length k

Abstract

We construct an injection from the set of permutations of length $n$ that contain exactly one copy of the decreasing pattern of length $k$ to the set of permutations of length $n+2$ that avoid that pattern. We then prove that the generating function counting the former is not rational, and in the case when $k$ is even and $k\ge 4$, it is not even algebraic. We extend our injection and our nonrationality result to a larger class of patterns.

Nine pages