The Open UniversitySkip to content
 

Permutation classes of polynomial growth

Albert, M. H.; Atkinson, M. D. and Brignall, Robert (2007). Permutation classes of polynomial growth. Annals of Combinatorics, 11(3-4) pp. 249–264.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1007/s00026-007-0318-x
Google Scholar: Look up in Google Scholar

Abstract

A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterized as those permutations not involving a particular set of forbidden permutations. A simple collection of necessary and sufficient conditions on sets of forbidden permutations which ensure that the associated pattern class is of polynomial growth is determined. A catalogue of all such sets of forbidden permutations having three or fewer elements is provided together with bounds on the degrees of the associated enumerating polynomials.

Item Type: Journal Article
Copyright Holders: 2007 Birkhäuser Basel
ISSN: 0219-3094
Keywords: restricted permutations; pattern avoidance; growth rate; polynomial growth
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 23470
Depositing User: Robert Brignall
Date Deposited: 22 Nov 2010 15:29
Last Modified: 28 Mar 2014 12:09
URI: http://oro.open.ac.uk/id/eprint/23470
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk