Small configurations in simple permutations


European Journal of Combinatorics, 31 (2010), 1781–1784.

We prove that every entry in a simple permutation of length at least 4 is contained in a copy of 2413 or 3412 or plays the role of the '3' in a copy of 25314 or 41352. This allows us to give a short proof that the number of permutations with at most r copies of 132 has an algebraic generating function for any integer r.

Note: the abstract of this article contains a mistake. Every entry in a simple permutation of length at least 4 is contained in a copy of 2413 or 3142 (not 3412) or plays the role the '3' in a copy of 25314 or 41352. (Thanks to Dominque Rossin for spotting this.)

Download the paper: