The enumeration of simple permutations.

A simple permutation is one which maps no proper non-singleton interval onto an interval. We consider the enumeration of simple permutations from several aspects. Our results include a straightforward relationship between the ordinary generating function for simple permutations and that for all permutations, that the coe‐cients of this series are not P-recursive, an asymptotic expansion for these coe‐cients, and a number of congruence results for the coe‐cients of the functional inverse of the ordinary generating function for allpermutations.