Subclasses of the separable permutations

Michael H. Albert, M. D. Atkinson, Vincent Vatter

Published 2010-07-06Version 1

We prove that all subclasses of the separable permutations not containing Av(231) or a symmetry of this class have rational generating functions. Our principal tools are partial well-order, atomicity, and the theory of strongly rational permutation classes introduced here for the first time.