Geodesic
Pattern-avoiding ascent sequences of length 3
Andrew R. Conway1 ; Miles Conway1 ; Andrew Elvey Price2 ; Anthony J. Guttmann3
1Fairfield, Victoria, Australia
2Université de Tours, France
3The University of Melbourne
The electronic journal of combinatorics, Tome 29 (2022) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Pattern-avoiding ascent sequences have recently been related to set-partition problems and stack-sorting problems. While the generating functions for several length-3 pattern-avoiding ascent sequences are known, those avoiding 000, 100, 110, 120 are not known. We have generated extensive series expansions for these four cases, and analysed them in order to conjecture the asymptotic behaviour. We provide polynomial time algorithms for the $000$ and $110$ cases, and exponential time algorithms for the $100$ and $120$ cases. We also describe how the $000$ polynomial time algorithm was detected somewhat mechanically given an exponential time algorithm. For 120-avoiding ascent sequences we find that the generating function has stretched-exponential behaviour and prove that the growth constant is the same as that for 201-avoiding ascent sequences, which is known. The other three generating functions have zero radius of convergence, which we also prove. For 000-avoiding ascent sequences we give what we believe to be the exact growth constant. We give the conjectured asymptotic behaviour for all four cases.
DOI : 10.37236/11266
Classification : 05A18, 05A05, 05A15, 68R10, 68P10, 11B83, 90C39
Mots-clés : generating function, dynamic programming algorithm

Andrew R. Conway  1   ; Miles Conway  1   ; Andrew Elvey Price  2   ; Anthony J. Guttmann  3

1 Fairfield, Victoria, Australia
2 Université de Tours, France
3 The University of Melbourne 
@article{10_37236_11266,
     author = {Andrew R. Conway and Miles Conway and Andrew  Elvey Price and Anthony J. Guttmann},
     title = {Pattern-avoiding ascent sequences of length 3},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {4},
     doi = {10.37236/11266},
     zbl = {1502.05017},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11266/}
}
TY  - JOUR
AU  - Andrew R. Conway
AU  - Miles Conway
AU  - Andrew  Elvey Price
AU  - Anthony J. Guttmann
TI  - Pattern-avoiding ascent sequences of length 3
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11266/
DO  - 10.37236/11266
ID  - 10_37236_11266
ER  - 
%0 Journal Article
%A Andrew R. Conway
%A Miles Conway
%A Andrew  Elvey Price
%A Anthony J. Guttmann
%T Pattern-avoiding ascent sequences of length 3
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11266/
%R 10.37236/11266
%F 10_37236_11266
Andrew R. Conway; Miles Conway; Andrew  Elvey Price; Anthony J. Guttmann. Pattern-avoiding ascent sequences of length 3. The electronic journal of combinatorics, Tome 29 (2022) no. 4. doi: 10.37236/11266

Cité par Sources :