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:
Google Scholar: Look up in Google Scholar


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
Share this page:


Scopus Citations

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340