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


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.

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions