The Enumeration of Three Pattern Classes using Monotone Grid Classes

  • Michael Albert
  • Mike Atkinson
  • Robert Brignall
Keywords: permutation, pattern, enumeration


The structure of the three pattern classes defined by the sets of forbidden permutations $\{2143, 4321\}$, $\{2143, 4312\}$ and $\{1324, 4312\}$ is determined using the machinery of monotone grid classes. This allows the permutations in these classes to be described in terms of simple diagrams and regular languages and, using this, the rational generating functions which enumerate these classes are determined.

Author Biographies

Michael Albert, University of Otago
Department of Computer Science
Mike Atkinson, University of Otago
Department of Computer Science
Robert Brignall, The Open University
Department of Mathematics and Statistics
Article Number