Rationality for subclasses of 321-avoiding permutations

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)44-72
JournalEuropean Journal of Combinatorics
Volume78
Early online date6 Feb 2019
DOIs
Publication statusPublished - May 2019

Fingerprint

Dive into the research topics of 'Rationality for subclasses of 321-avoiding permutations'. Together they form a unique fingerprint.

Cite this