Grid classes and the Fibonacci dichotomy for restricted permutations (Q2500973)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Grid classes and the Fibonacci dichotomy for restricted permutations
scientific article

    Statements

    Grid classes and the Fibonacci dichotomy for restricted permutations (English)
    0 references
    0 references
    0 references
    30 August 2006
    0 references
    Summary: We introduce and characterise grid classes, which are natural generalisations of other well-studied permutation classes. This characterisation allows us to give a new, short proof of the Fibonacci dichotomy: the number of permutations of length \(n\) in a permutation class is either at least as large as the \(n\)th Fibonacci number or is eventually polynomial.
    0 references
    0 references
    0 references
    0 references
    0 references
    permutation classes
    0 references
    Fibonacci number
    0 references
    0 references