Prolific structures in combinatorial classes

Abstract

Under what circumstances might every extension of a combinatorial structure contain more copies of another one than the original did? This property, which we call prolificity, holds universally in some cases (e.g., finite linear orders) and only trivially in others (e.g., permutations). Integer compositions, or equivalently layered permutations, provide a middle ground. In that setting, there are prolific compositions for a given pattern if and only if that pattern begins and ends with 1. For each pattern, there are methods that identify conditions that allow classification of the texts that are prolific for the pattern. This notion is also extendable to other combinatorial classes. In the context of permutations that are sums of cycles we can also establish minimal elements for the set of prolific permutations based on the bijective correspondence between these permutations and compositions, with a slightly different containment order. We also take a brief step into the more general world of permutations that avoid the pattern 321 and attempt to establish some preliminary results.