A permutation of n letters is k-prolific if each (n - k)-subset of the letters in its one-line notation forms a unique pattern. We present a complete characterization of k-prolific permutations for each k, proving that k-prolific permutations of m letters exist for every m >= k^2/2+2k+1, and that none exist of smaller size. Key to these results is a natural bijection between k-prolific permutations and certain "permuted" packings of diamonds.
- pattern poset
- prolific permutation
- permuted packing
Bevan, D., Homberger, C., & Tenner, B. E. (2018). Prolific permutations and permuted packings: downsets containing many large patterns. Journal of Combinatorial Theory Series A , 153, 98-121. https://doi.org/10.1016/j.jcta.2017.08.006