Permutations with a fixed number of occurrences of a monotone pattern

Abstract

We bound the number of permutations with a fixed number $r$ of $321\ominus p_0$ patterns by a constant times the number of permutations which avoid $321\ominus p_0$. We use this new upper bound to show that the ordinary generating function for permutations with $r$ copies of $k(k-1)...1$ is not rational for odd $k\ge 3$ and not algebraic for even $k\ge 3$.

13 pages, 8 figures, Revision: new results and changed title