### Abstract

Language | English |
---|---|

Pages | 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 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Combinatorial Theory Series A*,

*153*, 98-121. DOI: 10.1016/j.jcta.2017.08.006

}

*Journal of Combinatorial Theory Series A*, vol. 153, pp. 98-121. DOI: 10.1016/j.jcta.2017.08.006

**Prolific permutations and permuted packings : downsets containing many large patterns.** / Bevan, David; Homberger, Cheyne; Tenner, Bridget Eileen.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Prolific permutations and permuted packings

T2 - Journal of Combinatorial Theory Series A

AU - Bevan,David

AU - Homberger,Cheyne

AU - Tenner,Bridget Eileen

PY - 2018/1/31

Y1 - 2018/1/31

N2 - 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.

AB - 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.

KW - permutation

KW - pattern

KW - pattern poset

KW - downset

KW - prolific permutation

KW - packing

KW - permuted packing

UR - http://www.sciencedirect.com/science/journal/00973165

U2 - 10.1016/j.jcta.2017.08.006

DO - 10.1016/j.jcta.2017.08.006

M3 - Article

VL - 153

SP - 98

EP - 121

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

ER -