Geodesic
On consecutive pattern-avoiding permutations of length 4, 5 and beyond
Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2018_19_2_a6,
     author = {Beaton, Nicholas R and Conway, Andrew R and Guttmann, Anthony J},
     title = {On consecutive pattern-avoiding permutations of length 4, 5 and beyond},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-2-8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-8/}
}
TY  - JOUR
AU  - Beaton, Nicholas R
AU  - Conway, Andrew R
AU  - Guttmann, Anthony J
TI  - On consecutive pattern-avoiding permutations of length 4, 5 and beyond
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-8/
DO  - 10.23638/DMTCS-19-2-8
LA  - en
ID  - DMTCS_2018_19_2_a6
ER  - 
%0 Journal Article
%A Beaton, Nicholas R
%A Conway, Andrew R
%A Guttmann, Anthony J
%T On consecutive pattern-avoiding permutations of length 4, 5 and beyond
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-8/
%R 10.23638/DMTCS-19-2-8
%G en
%F DMTCS_2018_19_2_a6
Beaton, Nicholas R; Conway, Andrew R; Guttmann, Anthony J. On consecutive pattern-avoiding permutations of length 4, 5 and beyond. Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2. doi : 10.23638/DMTCS-19-2-8. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-8/

Cité par Sources :