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.

DOI: https://doi.org/10.1016/j.ejc.2019.01.001

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.