Asymptotic normality for the count of distinct entries in uniformly random inversion sequences avoiding 010 and 0211

Year 2025, Volume: 3 Issue: 2, 61 - 65, 16.12.2025

Gökhan Yıldırım

https://doi.org/10.26650/ijmath.2025.00028

https://izlik.org/JA38TG69YC

Abstract

We study the class of inversion sequences of length 𝑛 that avoid the patterns 010 and 0211, denoted 𝐼𝑛 (010, 0211). We construct an explicit bijection between this class and the set of partitions of [𝑛] := {1, 2, 3, · · · , 𝑛}. This correspondence allows us to interpret natural statistics on 𝐼𝑛 (010, 0211) in terms of classical statistics on set partitions. In particular, we show that the number of distinct entries in an inversion sequence from 𝐼𝑛 (010, 0211) corresponds to the number of blocks in the associated partition of [𝑛]. As a consequence, the distribution of this statistic is governed by Stirling numbers of the second kind, which in turn leads to a central limit theorem for the number of distinct entries in a random element of 𝐼𝑛 (010, 0211).

Keywords

Inversion sequences , pattern-avoidance , set partitions , central limit theorem

References

• Arratia, R., Barbour, A.D., Tavare, S., 2018, Logarithmic combinatorial structures: a probabilistic approach. European Mathematical Society, 10, 142-149. google scholar
• Bona, M., 2004, Combinatorics of Permutations, 2nd ed.; Chapman & Hall/CRC: Boca Raton, FL, USA. https://doi.org/10.1201/b12210 google scholar
• Corteel, S., Martinez, M.A., Savage, C.D., Weselcouch, M., 2015, Patterns in inversion sequences I. Discrete Mathematics and Theoretical Computer Science, 18 (2). https://doi.org/10.46298/dmtcs.1323 google scholar
• de Bruijn, N. G. Asymptotic Methods in Analysis. Dover Publications. google scholar
• Harper, L.H., 1967, Stirling behavior is asymptotically normal. Annals of Mathematical Statistics, 38, 410-414. google scholar
• Hong, L., Li, R., 2022, Length-four pattern avoidance in inversion sequences. Electronic Journal of Combinatorics, 29 (4). https://doi.org/10.37236/10948 google scholar
• Kitaev, S., 2011, Patterns in Permutations and Words. Monographs in Theoretical Computer Science; Springer: Berlin, Germany. https://doi.org/10.1007/978-3-642-17333-2 google scholar
• Kotsireas, I., Mansour, T., Yıldırım, G., 2024, An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences. Journal of Symbolic Computation, 120. https://doi.org/10.1016/j.jsc.2023.09.005 google scholar
• Mansour, T., 2012, Combinatorics of Set Partitions. Chapman & Hall/CRC: Boca Raton, FL, USA. https://doi.org/10.1201/b13038 google scholar
• Mansour, T., Shattuck, M., 2016, Pattern avoidance in inversion sequences. Pure Mathematics and Applications, 25 (2), 157-176. https://doi.org/10.1515/puma-2015-0016 google scholar
• Mansour, T., Yıldırım, G., 2023, Inversion sequences avoiding 021 and another pattern of length four. Discrete Mathematics and Theoretical Computer Science, 25 (2). https://doi.org/10.46298/DMTCS.10444 google scholar
• Martinez, M.A., Savage, C.D., 2018, Patterns in inversion sequences II: inversion sequences avoiding triples of relations. Journal of Integer Sequences, 21, Article 18.2.2. google scholar
• Pitman, J., 1997, Some probabilistic aspects of set partitions. American Mathematical Monthly, 104, 201-209. google scholar
• Pudwell, L., 2020, From permutation patterns to the periodic table. Notices of the American Mathematical Society, 67 (7), 994-1001. google scholar
• Testart, B., 2022, Inversion sequences avoiding the pattern 010. Preprint. arXiv:2212.07222. https://doi.org/10.48550/arXiv.2212.07222 google scholar
• Yan, C., Lin, Z., 2020, Inversion sequences avoiding pairs of patterns. Discrete Mathematics and Theoretical Computer Science, 22 (1). https://doi.org/10.23638/DMTCS-22-1-23 google scholar
• Yıldırım, G., 2025, Enumeration of inversion sequences avoiding 010 and some patterns of length-four. submitted. google scholar