Simple Cayley permutations

Abstract

We propose a notion of simplicity for Cayley permutations that is compatible with inflation. We prove that Cayley permutations admit a substitution decomposition analogous to that of permutations and use it to enumerate simple Cayley permutations, primitive simple Cayley permutations, and simple restricted growth functions. We also prove that every hereditary Cayley permutation class with finitely many simple members has a finite basis and an algebraic generating function.