Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Completing the enume ...
Article

Completing the enumeration of inversion sequences avoiding triples of relations

Nathan Britt ORCID (1), Nicholas Beaton ORCID (1)
(1) The University of Melbourne
Download article
Open on arXiv
Submitted on
December 29, 2025
Accepted on
October 7, 2026
Published on
October 23, 2026
Last modified on
October 23, 2026
Special issue 28
vol. 28:1, Permutation Patterns 2025
Special issues
DOI
10.46298/dmtcs.17203
License
arXiv.org - Non-exclusive license to distribute
Indicators
153
Views
180
Downloads

Completing the enumeration of inversion sequences avoiding triples of relations

Nathan Britt ORCID (1), Nicholas Beaton ORCID (1)
(1) The University of Melbourne
Abstract
An inversion sequence of length $n$ is an integer sequence $(a_1, \ldots, a_n)$ such that $0 \le a_i < i$ for all $i$. The study of pattern-avoiding inversion sequences was initiated in 2015 by Mansour and Shattuck and in 2016 by Corteel, Martinez, Savage and Weselcouch. Martinez and Savage later defined a new type of pattern, a triple of binary relations, of which there are currently 14 uncounted avoidance classes. We complete the enumeration for all of these classes using generating tree methods "growing on the left" and "growing on the right". For many of these classes we are able to find algebraic generating functions. We also discuss the asymptotic behaviour of the counting sequences.
Keywords
  • Combinatorics
  • 05A05, 05A15, 05A16
Preview
Loading PDF preview...
References
  1. A. Asinowski and M. A. Polley. Patterns in rectangulations. Part I: ⊤-like patterns, inversion se- quence classes i(010, 101, 120, 201) and i(011, 201), and rushed dyck paths. Discrete Mathematics & Theoretical Computer Science, 27(1):15118, 2025. doi:10.46298/dmtcs.15118. Permutation Pat- terns 2024.

    DOI : 10.46298/dmtcs.15118
  2. N. R. Beaton, M. Bouvel, V. Guerrini, and S. Rinaldi. Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers. Theoretical Computer Science, 777:69-92, 2019. doi:10.1016/j.tcs.2019.02.003.

    DOI : 10.1016/j.tcs.2019.02.003
  3. C. M. Bender and S. A. Orszag. Advanced Mathematical Methods for Scientists and Engineers I. Springer New York, 1999.

    DOI : 10.1007/978-1-4757-3069-2
  4. D. Bevan, R. Brignall, A. Elvey Price, and J. Pantone. A structural characterisation of Av(1324) and new bounds on its growth rate. European Journal of Combinatorics, 88:103115, 2020. doi:10.1016/j.ejc.2020.103115.

    DOI : 10.1016/j.ejc.2020.103115
  5. M. Bouvel, V. Guerrini, A. Rechnitzer, and S. Rinaldi. Semi-Baxter and Strong-Baxter: Two Relatives of the Baxter Sequence. SIAM Journal on Discrete Mathematics, 32(4):2795-2819, 2018.

    DOI : 10.1137/17m1126734
  6. D. Callan and T. Mansour. Inversion sequences avoiding quadruple length-3 patterns. Integers, 23: Article A78, 2023. doi:10.5281/ZENODO.8399694.

    DOI : 10.5281/ZENODO.8399694
  7. D. Callan, V. Jelínek, and T. Mansour. Inversion sequences avoiding a triple of patterns of 3 letters. The Electronic Journal of Combinatorics, pages P3.19-P3.19, 2023. doi:10.37236/11603.

    DOI : 10.37236/11603
  8. W. Cao, E. Y. Jin, and Z. Lin. Enumeration of inversion sequences avoiding triples of relations. Discrete Applied Mathematics, 260:86-97, 2019. doi:10.1016/j.dam.2019.01.035.

    DOI : 10.1016/j.dam.2019.01.035
  9. J. N. Chen and Z. Lin. A bijection for length-5 patterns in permutations. Journal of Combinatorial Theory, Series A, 202:105815, 2024. doi:10.1016/j.jcta.2023.105815.

    DOI : 10.1016/j.jcta.2023.105815
  10. A. R. Conway, A. J. Guttmann, and P. Zinn-Justin. 1324-avoiding permutations revisited. Advances in Applied Mathematics, 96:312-333, 2018. doi:10.1016/j.aam.2018.01.002.

    DOI : 10.1016/j.aam.2018.01.002
  11. S. Corteel, M. A. Martinez, C. D. Savage, and M. Weselcouch. Patterns in Inversion Sequences I. Discrete Mathematics & Theoretical Computer Science, 18(2):1323, 2016. doi:10.46298/dmtcs.1323. Proceedings of Permutation Patterns 2015.

    DOI : 10.46298/dmtcs.1323
  12. P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.

    DOI : 10.1017/cbo9780511801655
  13. A. J. Guttmann. Analysis of series expansions for non-algebraic singularities. Journal of Physics A: Mathematical and Theoretical, 48(4):045209, 2015. doi:10.1088/1751-8113/48/4/045209.

    DOI : 10.1088/1751-8113/48/4/045209
  14. S. Kitaev. Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, 2011.

    DOI : 10.1007/978-3-642-17333-2
  15. D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison- Wesley, Reading, Massachusetts, 3 edition, 1997.

  16. I. Kotsireas, T. Mansour, and G. Yıldırım. An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences. Journal of Symbolic Computation, 120:102231, 2024. doi:10.1016/j.jsc.2023.102231.

    DOI : 10.1016/j.jsc.2023.102231
  17. Z. Lin. Patterns of relation triples in inversion and ascent sequences. Theoretical Computer Science, 804:115-125, 2020. doi:10.1016/j.tcs.2019.11.007.

    DOI : 10.1016/j.tcs.2019.11.007
  18. T. Mansour and M. Shattuck. Pattern avoidance in inversion sequences. Pure Mathematics and Applications, 25(2):157-176, 2015. doi:10.1515/puma-2015-0016.

    DOI : 10.1515/puma-2015-0016
  19. T. Mansour, H. Skogman, and R. Smith. Sorting inversion sequences. Discrete Mathematics & Theoretical Computer Science, 27(1), 2025. doi:10.46298/dmtcs.14010. Permutation Patterns 2024.

    DOI : 10.46298/dmtcs.14010
  20. M. A. Martinez and C. D. Savage. Patterns in inversion sequences II: Inversion sequences avoiding triples of relations. Journal of Integer Sequences, 21:Article 18.2.2, 2018.

  21. OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2025.

  22. J. Pantone. The enumeration of inversion sequences avoiding the patterns 201 and 210. Enumerative Combinatorics and Applications, 4(4):12, 2024. doi:10.54550/ECA2024V4S4R25.

    DOI : 10.54550/eca2024v4s4r25
  23. H. Prodinger. The kernel method: A collection of examples. Séminaire Lotharingien de Com- binatoire, 50:Article B50f, 19 pp., 2004.

  24. R. Simion and F. W. Schmidt. Restricted permutations. European Journal of Combinatorics, 6(4): 383-406, 1985. doi:10.1016/S0195-6698(85)80052-4.

    DOI : 10.1016/s0195-6698(85)80052-4
  25. B. Testart. Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, 2025. Preprint.

  26. B. Testart. Generating trees growing on the left for pattern-avoiding inversion sequences. Discrete Mathematics & Theoretical Computer Science, 27(1):14716, 2025. doi:10.46298/dmtcs.14716. Per- mutation Patterns 2024.

    DOI : 10.46298/dmtcs.14716
  27. C. Yan and Z. Lin. Inversion sequences avoiding pairs of patterns. Discrete Mathematics & Theo- retical Computer Science, 22(1), 2020. doi:10.23638/DMTCS-22-1-23.

    DOI : 10.23638/dmtcs-22-1-23