The Open UniversitySkip to content
 

Rationality for subclasses of 321-avoiding permutations

Albert, Michael; Brignall, Robert; Ruskuc, Nik and Vatter, Vincent (2019). Rationality for subclasses of 321-avoiding permutations. European Journal of Combinatorics, 78 pp. 44–72.

Full text available as:
Full text not publicly available (Accepted Manuscript)
Due to publisher licensing restrictions, this file is not available for public download until 5 February 2020
Click here to request a copy from the OU Author.
DOI (Digital Object Identifier) Link: https://doi.org/10.1016/j.ejc.2019.01.001
Google Scholar: Look up in Google Scholar

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.

Item Type: Journal Item
Copyright Holders: 2019 Elsevier
ISSN: 0195-6698
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 59056
Depositing User: Robert Brignall
Date Deposited: 11 Feb 2019 08:48
Last Modified: 08 Dec 2019 01:27
URI: http://oro.open.ac.uk/id/eprint/59056
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU