Nicholas R Beaton ; Andrew R Conway ; Anthony J Guttmann - On consecutive pattern-avoiding permutations of length 4, 5 and beyond

dmtcs:3311 - Discrete Mathematics & Theoretical Computer Science, February 26, 2018, Vol. 19 no. 2, Permutation Patterns 2016 - https://doi.org/10.23638/DMTCS-19-2-8
On consecutive pattern-avoiding permutations of length 4, 5 and beyondArticle

Authors: Nicholas R Beaton ORCID; Andrew R Conway ; Anthony J Guttmann

    We review and extend what is known about the generating functions for consecutive pattern-avoiding permutations of length 4, 5 and beyond, and their asymptotic behaviour. There are respectively, seven length-4 and twenty-five length-5 consecutive-Wilf classes. D-finite differential equations are known for the reciprocal of the exponential generating functions for four of the length-4 and eight of the length-5 classes. We give the solutions of some of these ODEs. An unsolved functional equation is known for one more class of length-4, length-5 and beyond. We give the solution of this functional equation, and use it to show that the solution is not D-finite. For three further length-5 c-Wilf classes we give recurrences for two and a differential-functional equation for a third. For a fourth class we find a new algebraic solution. We give a polynomial-time algorithm to generate the coefficients of the generating functions which is faster than existing algorithms, and use this to (a) calculate the asymptotics for all classes of length 4 and length 5 to significantly greater precision than previously, and (b) use these extended series to search, unsuccessfully, for D-finite solutions for the unsolved classes, leading us to conjecture that the solutions are not D-finite. We have also searched, unsuccessfully, for differentially algebraic solutions.


    Volume: Vol. 19 no. 2, Permutation Patterns 2016
    Section: Permutation Patterns
    Published on: February 26, 2018
    Accepted on: February 14, 2018
    Submitted on: May 5, 2017
    Keywords: Mathematics - Combinatorics,05Exx, 05Axx
    Funding:
      Source : OpenAIRE Graph
    • Discovery Early Career Researcher Award - Grant ID: DE170100186; Funder: Australian Research Council (ARC); Code: DE170100186

    Consultation statistics

    This page has been seen 725 times.
    This article's PDF has been downloaded 438 times.