|Journal of Integer Sequences, Vol. 6 (2003), Article 03.4.4|
Department of Applied Mathematics (KAM)
and Institute for Theoretical Computer Science (ITI)
Malostranské námestí 25
118 00 Praha
Abstract: 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 coefficients of this series are not $P$-recursive, an asymptotic expansion for these coefficients, and a number of congruence results for the coefficients of the functional inverse of the ordinary generating function for all permutations.
(Concerned with sequence A059372.)
Received April 15 2003; revised version received October 30 2003. Published in Journal of Integer Sequences December 13 2003.