Shuzhen Lv and Philip B. Zhang
1 · 2025
Read Shuzhen Lv and Philip B. Zhang by 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00357.txt.
Introduction
Lv and Zhang wrote a combinatorics paper, published in twenty twenty-four, on mesh patterns in permutations. A permutation is an ordering of numbers, and a mesh pattern adds shading rules to a pattern within it. They study how often the patterns one-two-three and three-two-one appear together.
The authors prove twenty of twenty-two possible joint equidistributions for symmetric shadings. An equidistribution means two different patterns occur the same number of times. They prove all thirty-six such results for a second shading type. Their results connect these counts to known number sequences. Those include Stirling numbers and harmonic numbers, plus counts of special sequences studied by Lin and Yan.
Catalog record
| CREATOR | 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 470 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00357
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shuzhen Lv and Philip B. Zhang 1 Abstract Joint Equidistributions of Mesh Patterns 123 and 321 with Symmetric and Minus-Antipodal Shadings Abstract. In this paper, we extend recent results by Lv and Kitaev by proving 20 (out of 22 possible) joint equidistributions of mesh patterns 123 and 321 with symmetric shadings, as well as all 36 joint equidistributions of these patterns with minus-antipodal shadings. Our results link several joint equidistributions of mesh patterns to various integer sequences, including unsigned Stirling numbers of the first kind, harmonic numbers, and the numbers of inversion sequences avoiding a certain vincular pattern studied by Lin and Yan. Keywords: Pattern avoidance, Mesh pattern, Joint equidistribution, Symmetric shading, Minus-antipodal shading, Stirling number of the first kind AMS Subject Classifications: 05A05, 05A15. 1 Introduction The concept of a mesh pattern was introduced by Brändén and Claesson [ 4 ] . The study of mesh patterns has become a prominent area of research within the theory of patterns in permutations, which has attracted significant attention (see [ 9 ] ). For enumerative results related to mesh patterns, see, for example, [ 2 , 7 , 10 , 12 , 13 , 15 , 18 ] . An n -permutation is an arrangement of \{1,2,\ldots,n\} , and the set of all n -permutations is denoted by S_{n} . A mesh pattern of length k is a pair (\tau,R) , where \tau\in S_{k} and R is a subset of {\llbracket 0,k\rrbracket}\times{\llbracket 0,k\rrbracket} , where {\llbracket 0,k\rrbracket} denotes the interval of integers from 0 to k . Let ({i,j}) be the box whose corners have coordinates (i,j),(i,j+1),(i+1,j+1) , and (i+1,j) , and let the horizontal lines (resp., vertical lines) represent the values (resp., positions) in the pattern. Mesh patterns can be drawn by shading the boxes in R . A mesh pattern with \tau=123 and R=\{({0,0}),({1,2}),({2,1}),({3,1})\} is drawn as follows \raisebox{2.58334pt}{ \hbox to32.11pt{\vbox to32.11pt{\pgfpicture\makeatletter\hbox{\hskip 0.12038pt\lower-0.12038pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}}{{\lx@inpgf@ignorespaces}} {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin=1} \color[rgb]{0.75,0.75,0.75}\lxSVG@fill\lxSVG@drawpath@unclipped{M 0 0 M 0 0 L 0 11.02 L 11.02 11.02 L 11.02 0 Z M 11.02 11.02}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin=1} \color[rgb]{0.75,0.75,0.75}\lxSVG@fill\lxSVG@drawpath@unclipped{M 11.02 22.05 M 11.02 22.05 L 11.02 33.07 L 22.05 33.07 L 22.05 22.05 Z M 22.05 33.07}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin=1} \color[rgb]{0.75,0.75,0.75}\lxSVG@fill\lxSVG@drawpath@unclipped{M 22.05 11.02 M 22.05 11.02 L 22.05 22.05 L 33.07 22.05 L 33.07 11.02 Z M 33.07 22.05}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{} {{}{}}{{}}{}{}{}{}{{}}{}\lxSVG@begingroup@{_scopebegin=1} \color[rgb]{0.75,0.75,0.75}\lxSVG@fill\lxSVG@drawpath@unclipped{M 33.07 11.02 M 33.07 11.02 L 33.07 22.05 L 44.09 22.05 L 44.09 11.02 Z M 44.09 22.05}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {}{{}}{}{}{ {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{ }{ }{ }{ }{ }{ }{}}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0.11 0.11 M 0.11 11.02 L 43.98 11.02 M 0.11 22.05 L 43.98 22.05 M 0.11 33.07 L 43.98 33.07 M 11.02 0.11 L 11.02 43.98 M 22.05 0.11 L 22.05 43.98 M 33.07 0.11 L 33.07 43.98 M 43.98 43.98}{fill:none} \lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 11.02 11.02 M 13.35 11.02 C 13.35 12.31 12.31 13.35 11.02 13.35 C 9.74 13.35 8.7 12.31 8.7 11.02 C 8.7 9.74 9.74 8.7 11.02 8.7 C 12.31 8.7 13.35 9.74 13.35 11.02 Z M 11.02 11.02}{} \lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 22.05 22.05 M 24.37 22.05 C 24.37 23.33 23.33 24.37 22.05 24.37 C 20.76 24.37 19.72 23.33 19.72 22.05 C 19.72 20.76 20.76 19.72 22.05 19.72 C 23.33 19.72 24.37 20.76 24.37 22.05 Z M 22.05 22.05}{} \lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 33.07 33.07 M 35.4 33.07 C 35.4 34.35 34.35 35.4 33.07 35.4 C 31.79 35.4 30.75 34.35 30.75 33.07 C 30.75 31.79 31.79 30.75 33.07 30.75 C 34.35 30.75 35.4 31.79 35.4 33.07 Z M 33.07 33.07}{} \lx@inpgf@ignorespaces \lxSVG@closescope {{ {}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}. A mesh pattern has a symmetric shading if the shading of the box (i,j) implies the shading of the box (j,i) , and minus-antipodal shading if, for any i\neq j , precisely one of the boxes (i,j) and (j,i) is shaded. See Table 1 (resp., Table 2 ) for examples of symmetric (resp., minus-antipodal) shadings of mesh patterns. Given a permutation \pi=\pi_{1}\pi_{2}\cdots\pi_{n}\in S_{n} , a subsequence \pi^{\prime}=\pi_{i_{1}}\pi_{i_{2}}\cdots\pi_{i_{k}} is an occurrence of a mesh pattern p=(\tau,R) in \pi if (i) \pi^{\prime} is order-isomorphic to \tau , and (ii) the shaded regions defined by R contain no elements of \pi that are not in \pi^{\prime} . Otherwise, \pi is said to avoid p , denoted by \pi\in S_{n}(p) . For example, consider the mesh pattern p=\bigl(123,\{(0,0),(1,2),(2,1),(3,1)\}\bigr) . The permutation 23154 contains two occurrences of p , namely 235 and 234 . However, the permutation 14325 contains three occurrences of the pattern 123 , namely 145 , 135 and 125 , but it avoids p because some entries lie inside the shaded regions, as shown in Fig 1 . Figure 1: An example of the permutation 14325 avoiding p , where the circled dots in the diagrams represent the respective occurrences of the pattern 123 . Two patterns q_{1} and q_{2} are Wilf-equivalent , denoted q_{1}\sim q_{2} , if |S_{n}(q_{1})|=|S_{n}(q_{2})| . Moreover, q_{1} and q_{2} are called equidistributed , denoted q_{1}\sim_{d}q_{2} , if the number of permutations of length n with k occurrences of q_{1} is equal to that with k occurrences of q_{2} for any nonnegative integers n and k . The stronger notion of joint equidistribution of two patterns, denoted q_{1}\sim_{jd}q_{2} , means that the number of n -permutations with k occurrences of q_{1} and \ell occurrences of q_{2} is equal to that with \ell occurrences of q_{1} and k occurrences of q_{2} . Hilmarsson et al. [ 7 ] initiated the systematic study of the avoidance of mesh patterns. This research was later extended by Kitaev and Zhang in [ 12 ] , focusing on the distribution of mesh patterns. Subsequently, Han and Zeng [ 6 ] resolved several distribution conjectures posed by Kitaev and Zhang. More recently, Lv and Kitaev [ 15 ] established 75 joint equidistribution results for the mesh patterns 123 and 132 with identical symmetric shadings, primarily using bijections. Note that the permutations 123 and 321 remain invariant under the group-theoretic inverse, which corresponds to the reflection of the elements across the diagonal in the respective permutation matrices. This observation motivates our study of the joint equidistributions of mesh patterns 123 and 321 with certain shadings, extending the results of Lv and Kitaev. In this paper, as suggested by computer experiments, we derive 56 of the 58 possible joint equidistributions of the mesh patterns 123 and 321 as presented in Tables 1 and 2 , which arise from 20 identical symmetric shadings and 36 minus-antipodal shadings considered in Sects. 2 and 3 , respectively. We also propose the remaining two pairs as conjectures. Our main results are obtained through recurrence relations for the joint distribution generating functions, which lead to expressions that connect to several integer sequences. The most interesting pairs, Nr. A17–A24 discussed in Theorem 4 , have joint distributions involving both the unsigned Stirling numbers of the first kind and the harmonic numbers . It is also worth pointing out that one of the patterns in any pair among Nr. A25–A36 is equidistributed, as deduced in Corollary 8 , and is linked to the inversion sequences avoiding a certain vincular pattern . This paper is organized as follows. In Sect. 2 , we consider 20 joint equidistributions with symmetric shadings, summarizing our results in Table 1 . The joint equidistribution