# Prolific permutations and permuted packings: downsets containing many large patterns

Research output: Research - peer-review › Article

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.

Original language | English |
---|---|

Pages (from-to) | 98-121 |

Number of pages | 24 |

Journal | Journal of Combinatorial Theory Series A |

Volume | 153 |

Early online date | 1 Sep 2017 |

DOIs | |

State | Published - 31 Jan 2018 |

- permutation, pattern, pattern poset, downset, prolific permutation, packing, permuted packing