Journal of Integer Sequences, Vol. 6 (2003), Article 03.4.4

The Enumeration of Simple Permutations

M. H. Albert and M. D. Atkinson
Department of Computer Science
University of Otago
Dunedin
New Zealand

M. Klazar
Department of Applied Mathematics (KAM)
and Institute for Theoretical Computer Science (ITI)
Charles University
Malostranské námestí 25
118 00 Praha
Czech Republic

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.