Enumeration of inversion sequences avoiding 010 and some patterns of length four

Abstract

We study classes of pattern-avoiding inversion sequences defined by simultaneously avoiding the classical pattern $010$ and one additional pattern $\tau$ of length four. We construct explicit generating trees that capture the structural evolution of these classes. For each of the studied classes, we derive functional equations for the corresponding generating functions, solve them explicitly in several cases, and compute closed-form or recursive formulas for the enumeration sequences. Using this framework, we obtain exact enumeration results for $I_n(010,\tau)$ when $\tau$ belongs to $\{0011, 0012, 0021, 0132, 0211, 0212, 0321, 0312\}$.

Keywords

• inversion sequences
• generating tree method
• generating functions

References

1. [1] M. Bóna, Combinatorics of Permutations, 2nd ed., Chapman & Hall/CRC, Boca Raton, FL, 2004.
2. [2] S. Chern, On 0012-avoiding inversion sequences and a conjecture of Lin and Ma, Quaest. Math. 46 (4), 681–694, 2023.
3. [3] S. Corteel, M. A. Martinez, C. D. Savage and M. Weselcouch, Patterns in Inversion Sequences I, Discrete Math. Theor. Comput. Sci. 18 (2), 2016.
4. [4] L. Hong and R. Li, Length-Four Pattern Avoidance in Inversion Sequences, Electron. J. Combin. 29 (4), 2022.
5. [5] S. Kitaev, Patterns in Permutations and Words, Monogr. Theor. Comput. Sci., Springer, 2011.
6. [6] I. Kotsireas, T. Mansour and G. Yıldırım, An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences, J. Symbolic Comput. 120, Paper No. 102231, 18 pp, 2024.
7. [7] T. Mansour, Five classes of pattern avoiding inversion sequences under one roof: generating trees, J. Difference Equ. Appl. 29 (7), 748–762, 2023.
8. [8] T. Mansour, Generating trees for 0021-avoiding inversion sequences and a conjecture of Hong and Li, Discrete Math. Lett. 12, 11–14, 2023.

9. [9] T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, Pure Math. Appl. 25 (2), 157–176, 2016.
10. [10] T. Mansour and G. Yıldırım, Inversion sequences avoiding 021 and another pattern of length four, Discrete Math. Theor. Comput. Sci. 25 (2), 2023.
11. [11] M. A. Martinez and C. D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, J. Integer Seq. 21, Article 18.2.2, 2018.
12. [12] L. Pudwell, From permutation patterns to the periodic table, Notices Amer. Math. Soc. 67 (7), 994–1001, 2020.
13. [13] B. Testart, Inversion sequences avoiding the pattern 010, arXiv:2212.07222, 2022.
14. [14] B. Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, Electron. J. Combin. 32 (4), 70pp, 2025.
15. [15] B. Testart, Generating trees growing on the left for pattern-avoiding inversion sequences, Discrete Math. Theor. Comput. Sci. 27 (1), 1–23, 2025.
16. [16] J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146, 247–262, 1995.
17. [17] J. West, Generating trees and forbidden subsequences, Discrete Math. 157, 363–374, 1996.
18. [18] C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, Discrete Math. Theor. Comput. Sci. 22 (1), 2020.