An explicit bijection between the inversion sequences avoiding 0312 and 0321

Abstract

We present an explicit bijection between the set of inversion sequences avoiding the patterns 0312 and 0321, preserving five statistics: the counts of zeros, distinct elements, repeating elements, left-to-right maxima, and the maximum entry. We also provide some sampling algorithms for these pattern-avoiding inversion sequences

Keywords

• inversion sequences
• pattern avoidance
• random sampling

Supporting Institution

Tübitak

Project Number

Tübitak-Ardeb grant no: 120F352

References

1. [1] J. S. Auli and S. Elizalde, Consecutive patterns in inversion sequences, Discrete Math. Theor. Comput. Sci. 21 (2), Paper No. 6, 22 pp, 2019.
2. [2] M. Bona, Combinatorics of Permutations. Chapman Hall/CRC, Boca Raton, FL, 2. edition edition, 2004.
3. [3] S. Chern, On 0012-avoiding inversion sequences and a conjecture of Lin and Ma., Quaest. Math. 46 (4), 681–694, 2023.
4. [4] S. Corteel, M. A. Martinez, C. D. Savage, and M. Weselcouch, Patterns in inversion sequences I, Discrete Math. Theor. Comput. Sci. 18 (2), 2015.
5. [5] L. Hong and R. Li, Length-four pattern avoidance in inversion sequences, Electron. J. Combinatorics, 29 (4), 2022.
6. [6] S. Kitaev, Patterns in Permutations and Words, Monographs in Theoretical Computer Science. Springer, 2011.
7. [7] 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, 2024.
8. [8] S. Liu, Statistics on trapezoidal words and k-inversion sequences, Discrete Appl. Math. 325, 1–8, 2023.

9. [9] S. Liu, r-Euler-Mahonian statistics on permutations, J. Combin. Theory Ser. A, 208, Paper No. 105940, 30, 2024.
10. [10] N. Madras and H. Liu, Random pattern-avoiding permutations, Algorithmic Probability and Combinatorics, volume 520 of Contemporary Mathematics, pages 173–194. American Mathematical Society, Providence, RI, 2010.
11. [11] T. Mansour, Five classes of pattern avoiding inversion sequences under one roof: generating trees, J. Difference Equ. Appl. 29 (7), 748–762, 2023.
12. [12] T. Mansour, Generating trees for 0021-avoiding inversion sequences and a conjecture of Hong and Li, Discrete Math. Lett. 12, 11–14, 2023.
13. [13] T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, Pure Math. Appl. 25 (2),157–176, 2016.
14. [14] 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.
15. [15] J. Pantone, The enumeration of inversion sequences avoiding the patterns 201 and 210, Enumer. Comb. Appl. 4 (4), Paper No. S2R25, 12, 2024.
16. [16] L. Pudwell, From permutation patterns to the periodic table, Notices Amer. Math. Soc. 67 (7), 994–1001, 2020.
17. [17] B. Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv preprint arXiv:2407.07701, 2024.
18. [18] C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, Discrete Math. Theor. Comput. Sci, 22 (1), 2020.