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: https://doi.org/10.1007/s00026-007-0318-x

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 23470
• Item Type
• Journal Item
• ISSN
• 0219-3094
• Keywords
• restricted permutations; pattern avoidance; growth rate; polynomial growth
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2007 Birkhäuser Basel
• Depositing User
• Robert Brignall