Prolific permutations (Q2662343)

Summary: 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 \({\mathrm Av}(321)\). We then show a number of interesting properties that arise when studying prolificity in \({\mathrm Av}(321)\), concluding by showing that the class of permutations that are not prolific for any increasing permutation in \({\mathrm Av}(321)\) form a polynomial subclass.