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 Item
Copyright Holders: 2007 Birkhäuser Basel
ISSN: 0219-3094
Keywords: restricted permutations; pattern avoidance; growth rate; polynomial growth
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 23470
Depositing User: Robert Brignall
Date Deposited: 22 Nov 2010 15:29
Last Modified: 07 Dec 2018 09:40
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU