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.
@article{10_37236_9966,
author = {Michael Albert and Murray Tannock},
title = {Prolific permutations},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {2},
doi = {10.37236/9966},
zbl = {1461.05004},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9966/}
}
TY - JOUR
AU - Michael Albert
AU - Murray Tannock
TI - Prolific permutations
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9966/
DO - 10.37236/9966
ID - 10_37236_9966
ER -
%0 Journal Article
%A Michael Albert
%A Murray Tannock
%T Prolific permutations
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9966/
%R 10.37236/9966
%F 10_37236_9966
Michael Albert; Murray Tannock. Prolific permutations. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9966
