Enumeration of inversion sequences according to the outer and inner perimeter

Mansour, Toufik; Shattuck, Mark

doi:10.2478/puma-2023-0004

Abstract

The integer sequence π = π₁ ‧‧‧ π_n is said to be an inversion sequence if 0 ≤ π_i ≤ i – 1 for all i. Let ℐ_n denote the set of inversion sequences of length n, represented using positive instead of non-negative integers. We consider here two new statistics defined on the bargraph representation b(π) of an inversion sequence π which record the number of unit squares touching the boundary of b(π) and that are either exterior or interior to b(π). We denote these statistics on ℐ_n recording the number of outer and inner perimeter squares respectively by oper and iper. In this paper, we study the distribution of oper and iper on ℐ_n and also on members of ℐ_n that end in a particular letter. We find explicit formulas for the maximum and minimum values of oper and iper achieved by a member of ℐ_n as well as for the average value of these parameters. We make use of both algebraic and combinatorial arguments in establishing our results.

References

M. Archibald, A. Blecher and A. Knopfmacher, Parameters in inversion sequences, Math. Slovaca 73(3) (2023), 551–564.
Search in Google Scholar Back to article
A. Blecher, C. Brennan and A. Knopfmacher, The inner site-perimeter of compositions, Quaest. Math. 43(1) (2020), 55–66.
Search in Google Scholar Back to article
A. Blecher, C. Brennan, A. Knopfmacher and T. Mansour, The site-perimeter of words, Trans. Combin. 6(2) (2017), 37–48.
Search in Google Scholar Back to article
A. Blecher, A. Knopfmacher and T. Mansour, Alphabetic points and records in inversion sequences, Discrete Math. Lett. 10 (2022), 85–90.
Search in Google Scholar Back to article
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86–112.
Search in Google Scholar Back to article
W. Cao, E. Y. Jin and Z. Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Appl. Math. 260 (2019), 86–97.
Search in Google Scholar Back to article
S. Corteel, M. A. Martinez, C. D. Savage and M. Weselcouch, Patterns in inversion sequences I, Discrete Math. Theor. Comput. Sci. 18(2) (2016), Art. #2.
Search in Google Scholar Back to article
D. Kim and Z. Lin, Refined restricted inversion sequences, Sém. Lothar. Combin. 78B (2017), Art. #52.
Search in Google Scholar Back to article
Z. Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, European J. Combin. 70 (2018), 202–211.
Search in Google Scholar Back to article
Z. Lin and and S. H. F. Yan, Vincular patterns in inversion sequences, Appl. Math. Comput. 364 (2020), Art. 124672.
Search in Google Scholar Back to article
T. Mansour, Border and tangent cells in bargraphs, Discrete Math. Lett. 1 (2019), 26–29.
Search in Google Scholar Back to article
T. Mansour, The perimeter and the site-perimeter of set partitions, Electron. J. Combin. 26 (2019), Art. P2.30.
Search in Google Scholar Back to article
T. Mansour and A. Sh. Shabani, Enumerations on bargraphs, Discrete Math. Lett. 2 (2019), 65–94.
Search in Google Scholar Back to article
T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, Pure Math. Appl. 25 (2015), 157–176.
Search in Google Scholar Back to article
T. Mansour and M. Shattuck, Statistics on bargraphs of inversion sequences of permutations, Discrete Math. Lett. 4 (2020), 37–44.
Search in Google Scholar Back to article
T. Mansour and M. Shattuck, Counting inversion sequences by parity successions and runs, Discrete Appl. Math. 330 (2023), 24–39.
Search in Google Scholar Back to article
T. Mansour and M. Shattuck, Enumeration of smooth inversion sequences and proof of a recent related conjecture, J. Difference Equ. Appl. 29(3) (2023), 270–296.
Search in Google Scholar Back to article
M. Martinez and C. Savage, Patterns in inversion sequences II: inversion sequences avoiding triples of relations, J. Integer Seq. 21 (2018), Art. 18.2.2.
Search in Google Scholar Back to article
N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available at https://oeis.org.
Search in Google Scholar Back to article
R. P. Stanley, Enumerative Combinatorics, Volume I, Cambridge University Press, Cambridge, UK (1997).
Search in Google Scholar Back to article
C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, Discrete Math. Theor. Comput. Sci. 22(1) (2020), Art. 6539.
Search in Google Scholar Back to article
S. H. F. Yan, Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions, Appl. Math. Comput. 325 (2018), 24–30.
Search in Google Scholar Back to article

Enumeration of inversion sequences according to the outer and inner perimeter

Abstract

Paradigm

My account