Prolific Permutations

Abstract

The concept of prolificity was previously introduced by the authors in the context of compositions of integers. We give a general interpretation of prolificity that applies across a range of relational structures defined in terms of counting embeddings. We then proceed to classify prolificity in permutation classes with bases consisting of permutations of length 2, or 3; completely classifying all such classes except ${\rm Av}(321)$. We then show a number of interesting properties that arise when studying prolificity in ${\rm Av}(321)$, concluding by showing that the class of permutations that are not prolific for any increasing permutation in ${\rm Av}(321)$ form a polynomial subclass.