Rationality for subclasses of 321-avoiding permutations

M.H. Albert; R. Brignall; Nik Ruskuc; V. Vatter

doi:10.1016/j.ejc.2019.01.001

Rationality for subclasses of 321-avoiding permutations

M.H. Albert, R. Brignall, Nik Ruskuc, V. Vatter

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well-quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.

Original language	English
Pages (from-to)	44-72
Journal	European Journal of Combinatorics
Volume	78
Early online date	6 Feb 2019
DOIs	https://doi.org/10.1016/j.ejc.2019.01.001
Publication status	Published - May 2019

Access to Document

10.1016/j.ejc.2019.01.001

av321
Copyright © 2019 Elsevier Ltd. All rights reserved. This work has been made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1016/j.ejc.2019.01.001
Accepted author manuscript, 528 KBLicence: CC BY-NC-ND

https://www.sciencedirect.com/science/article/pii/S0195669819300010

Cite this

@article{92d8ff3f58ab45f799df580733e6c4da,

title = "Rationality for subclasses of 321-avoiding permutations",

abstract = "We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well-quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.",

author = "M.H. Albert and R. Brignall and Nik Ruskuc and V. Vatter",

year = "2019",

month = may,

doi = "10.1016/j.ejc.2019.01.001",

language = "English",

volume = "78",

pages = "44--72",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - Rationality for subclasses of 321-avoiding permutations

AU - Albert, M.H.

AU - Brignall, R.

AU - Ruskuc, Nik

AU - Vatter, V.

PY - 2019/5

Y1 - 2019/5

N2 - We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well-quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.

AB - We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well-quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.

UR - https://arxiv.org/abs/1602.00672

U2 - 10.1016/j.ejc.2019.01.001

DO - 10.1016/j.ejc.2019.01.001

M3 - Article

SN - 0195-6698

VL - 78

SP - 44

EP - 72

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Rationality for subclasses of 321-avoiding permutations

Abstract

Access to Document

Other files and links

Fingerprint

The Structure of Permutation Classes: The Structure of Permutation Classes

Cite this

Rationality for subclasses of 321-avoiding permutations

Abstract

Access to Document

Other files and links

Fingerprint

Projects

The Structure of Permutation Classes: The Structure of Permutation Classes

Cite this