Murray Tannock ; Michael Albert - Prolific Compositions

dmtcs:5373 - Discrete Mathematics & Theoretical Computer Science, December 13, 2019, Vol. 21 no. 2, Permutation Patters 2018 - https://doi.org/10.23638/DMTCS-21-2-10
Prolific CompositionsArticle

Authors: Murray Tannock ; Michael Albert

    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 is an easily constructed automaton that recognises prolific compositions for that pattern. Some instances where there is a unique minimal prolific composition for a pattern are classified.


    Volume: Vol. 21 no. 2, Permutation Patters 2018
    Section: Permutation Patterns
    Published on: December 13, 2019
    Accepted on: November 13, 2019
    Submitted on: April 12, 2019
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1225 times.
    This article's PDF has been downloaded 194 times.