Permutation Classes of Polynomial Growth

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterised 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.
17 pages, 4 figures

Keywords

Combinatorics, 05A15 (Primary), 05A05 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/123409

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0603315
 http://arxiv.org/abs/math/0603315

Collections

arXiv