Simple permutations and algebraic generating functions (Q2426423)

This paper deals with simple permutations, that is with permutations that never map a nontrivial contiguous set of indices contiguously. For an arbitrary set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, there is given a framework for enumerating subsets that are restricted by properties belonging to a finite ``query-complete set''. Such properties include being even, being an alternating permutation and avoiding a given generalized (blocked or barred) pattern. The authors prove that the generating functions of these subsets are always algebraic, generalizing some recent results of Albert and Atkinson. These techniques are also applied to enumerate the involutions and cyclic closures.