Equidistributions of mesh patterns of length two

Bin Han*¹ and Jiang Zeng†²

¹Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel.

²Univ Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 blvd. du 11 novembre 1918, F-69622 Villeurbanne cedex, France

**Abstract.** A systematic study of *avoidance* of mesh patterns of length 2 was conducted by Hilmarsson *et al*. in 2015. In a recent paper Kitaev and Zhang examined the distribution of the aforementioned patterns. The aim of this paper is to prove more equidistributions of mesh pattern and confirm Kitaev and Zhang's four conjectures by constructing two involutions on permutations.

**Keywords:** permutation, mesh pattern, distribution, involution, continued fraction, antirecord

# 1 Introduction

Patterns in permutations and words have implicitly appeared in the mathematics literature for over a century, but interest in them has blown up in the past four decades (see [4, 6, 7, 10, 11, 14, 17] and references therein), and the research of this area continues to increase gradually.

A permutation $\sigma = \sigma(1) \cdots \sigma(n)$ of length $n$ is an arrangement of $1 \cdots n$. If $\pi$ and $\sigma$ are two permutations represented in this way, then $\pi$ is said to contain $\sigma$ as a pattern if some subsequence of the digits of $\pi$ has the same relative order as all of the digits of $\sigma$. For example, the permutation 31542 contains two occurrences of the pattern 231 as the two subwords 352 and 342 all have the same ordering as 231. Let $S_n$ be the set of all permutations of length $n$. We call $\sigma(i)$ the value of $\sigma$ at position $i$ ($1 \le i \le n$) and draw a graphical presentation of $\sigma$ by putting a dot at $(i, \sigma(i))$ for $i = 1, \dots, n$ in the plan. For example, the permutation $231 \in S_3$ is presented as follows,

<figure><img src="image_1.png" /></figure>

where the horizontal lines represent the values and the vertical lines denote the positions in the permutation. In [4] Brändén and Claesson introduced and studied *mesh patterns* as a common extension of several types of generalized permutation patterns.

<footnote>*han@math.biu.ac.il, han.combin@hotmail.com. Supported by the Israel Science Foundation, grant no. 1970/18.</footnote>

<footnote>†zeng@math.univ-lyon1.fr.</footnote>
A mesh pattern of length $k$ is a pair $(\tau, R)$, where $\tau$ is a permutation of length $k$ and $R$ is a subset of $\llbracket 0, k \rrbracket \times \llbracket 0, k \rrbracket$ with $\llbracket 0, k \rrbracket = \{0, 1, \dots, k\}$. Let $(i, j)$ denote the box whose corners have coordinates $(i, j)$, $(i, j+1)$, $(i+1, j+1)$, and $(i+1, j)$. Mesh patterns can be depicted by shading the boxes in $R$. A mesh pattern with $\tau = 231$ and $R = \{(1,2), (2,1)\}$ is drawn as follows.

<figure><img src="image_2.png" /></figure>

For example, the permutation 346512 depicted in the following picture contains the mesh pattern $(231, \{(1,2), (2,1)\})$ since the subsequence 462 forms the classical pattern 231 and there are no points in the shaded areas.

<figure><img src="image_3.png" /></figure>

Mesh patterns and their generalizations were studied in many papers; e.g. see [1, 2, 3, 8, 9, 10, 12, 13, 14, 18]. In the first systematic study of the mesh patterns avoidance, Hilmarsson et al. [10] solved 25 out of 65 non-equivalent avoidance cases of patterns of length 2. In a recent paper [14], Kitaev and Zhang further studied the distributions of mesh patterns considered in [10] by giving 27 distribution results, see [14, Table 1]. Moreover, for the unsolved case, they gave an equidistribution result and conjectured 6 more equidistributions (see Table 1). We prove 3 conjectured equidistributions and 2 more equidistributions (see Table 2) by constructing two involutions. This extended abstract is a summary of the recent paper [9].

For a pattern $p$ and a permutation $\pi$, we let $p(\pi)$ denote the number of occurrences of $p$ in $\pi$. Kitaev and Zhang [14, Conjecture 6.1] conjectured a Stieltjes continued fraction formula for the distribution of pattern Nr. 3 = $\frac{1}{1-\frac{\alpha_1 t}{1-\frac{\alpha_2 t}{1-\dots}}}$ (see [15, A200545]), which is equivalent to the following identity.

**Conjecture 1.1** ([14, Conjecture 6.1]). We have

$$ \sum_{n \ge 0} t^n \sum_{\pi \in S_n} y^{\mathbb{N}^+(\pi)} = \frac{1}{1 - \frac{\alpha_1 t}{1 - \frac{\alpha_2 t}{1 - \dots}}} \quad (1.1a) $$
<table><caption>**Table 1:** Equidistributions for which enumeration is unknown. Pattern's numbers are adopted from [10, 14]</caption><thead><tr><th></th><th>Nr.</th><th>Repr. p</th><th>Ref.</th><th>Nr.</th><th>Repr. p</th><th>Ref.</th></tr></thead><tbody><tr><td rowspan="2">proved<br>equidistributions</td><td>48</td><td>□</td><td rowspan="2">[14, Theorem 5.1]</td><td></td><td></td><td></td></tr><tr><td>49</td><td>□</td><td></td><td></td><td></td></tr><tr><td rowspan="2">conjectured<br>equidistributions<br>in [14]</td><td>23</td><td>□</td><td rowspan="2">Theorem 1.6</td><td>53</td><td>□</td><td rowspan="2">Corollary 1.1</td></tr><tr><td>24</td><td>□</td><td>54</td><td>□</td></tr><tr><td rowspan="3"></td><td>48</td><td>□</td><td rowspan="3">Corollary 1.1 and<br>[14, Theorem 5.1]</td><td>57</td><td>□</td><td rowspan="2">N/A</td></tr><tr><td>49</td><td>□</td><td>58</td><td>□</td></tr><tr><td>50</td><td>□</td><td>61</td><td>□</td><td>N/A</td></tr></tbody></table>

with coefficients

$$ \alpha_{2k-1} = k, \quad \alpha_{2k} = y + k - 1. \qquad (1.1b) $$

Presenting their conjecture in this way, we notice that the S-continued fraction (1.1a) appears in a recent paper of Sokal and Zeng [16]. Let us reformulate the relevant permutation statistics in [16] in terms of mesh patterns. Given a permutation $\pi \in S_n$, an index $i \in [n]$ (or a value $\pi(i) \in [n]$) is called

* an *excedance* if $\pi(i) > i$;

* a *record* (rec) (or *left-to-right maximum*) if $\pi(j) < \pi(i)$ for all $j < i$ [note in particular that the index 1 is always a record and that the value $n$ is always a record]; in other words, a record of $\pi$ is one occurrence of pattern $\text{---}$ of $\pi$;

* an *antirecord* (arec) (or *right-to-left minimum*) if $\pi(j) > \pi(i)$ for all $j > i$ [note in particular that the index $n$ is always an antirecord and that the value 1 is always an antirecord]; in other words, an antirecord of $\pi$ is one occurrence of pattern $\text{---}$ of $\pi$;

* an *exclusive record* (erec) if it is a record and not also an antirecord; in other words, an exclusive record of $\pi$ is one occurrence of pattern $\text{---}$ of $\pi$, see (1.9);
with coefficients

$$ \alpha_{2k-1} = q^{k-1}(x + q + q^2 + \cdots + q^{k-1}) \qquad (1.3c) $$

$$ \alpha_{2k} = q^k v(y + q + q^2 + \cdots + q^{k-1}). \qquad (1.3d) $$

**Remark 1.3.**

* We can also prove (1.3a) by following the same steps in the special case as in [14] and then derive (1.3b) directly from [16, Theorem 2.8].

* The case $x = y = v = q = 1$ of Theorem 1.2 is Theorem 1.1 in [14].

* Since $(arec, inv)\pi = (rec, inv)\pi^{-1}$ we derive from [19] that

$$ F(x, 1, 1, 1, q; t) = \sum_{n=0}^{\infty} x(x+q) \cdots (x+q + \cdots + q^{n-1}) t^n. \qquad (1.4) $$

For $\pi = \pi(1) \cdots \pi(n) \in S_n$ we define the following three associated permutations:

$$ \pi^{-1} := \pi^{-1}(1)\pi^{-1}(2) \cdots \pi^{-1}(n) \qquad (1.5) $$

$$ \pi^r := \pi(n) \cdots \pi(2)\pi(1) \qquad (1.6) $$

$$ \pi^c := (n + 1 - \pi(1))(n + 1 - \pi(2)) \cdots (n + 1 - \pi(n)) \qquad (1.7) $$

Obviously we have

$$ \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}^c}(\pi^c) = \mathbb{1}_{\mathbb{Z}^{\text{roc}}}(\pi^{\text{roc}}) = \mathbb{1}_{\mathbb{Z}^r}(\pi^r) $$

and

$$ \begin{aligned} \mathbb{1}_{\mathbb{Z}}(\pi) &= \mathbb{1}_{\mathbb{Z}}(\pi^c) = \mathbb{1}_{\mathbb{Z}^{\text{roc}}}(\pi^{\text{roc}}) = \mathbb{1}_{\mathbb{Z}}(\pi^r) \\ &= \mathbb{1}_{\mathbb{Z}}(\pi^{-1}) = \mathbb{1}_{\mathbb{Z}}(\tau^r) = \mathbb{1}_{\mathbb{Z}^{\text{roc}}}(\tau^{\text{roc}}) = \mathbb{1}_{\mathbb{Z}}(\tau^c) \end{aligned} $$

with $\tau = \pi^{-1}$.

**Lemma 1.1.** For $\pi \in S_n$, we have

$$ \text{arec}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi), \qquad (1.8) $$

$$ \text{erec}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi) = \mathbb{1}_{\mathbb{Z}}(\pi). \qquad (1.9) $$

*Proof.* We just prove (1.8) as the proof of (1.9) is similar. In the entries placement representation of a permutation $\pi \in S_n$ the entry $y = (i, \pi(i))$ is an exclusive antirecord iff there is another entry $x = (j, \pi(j))$ at left of $y$, i.e., $j < i$ and higher than $x$, i.e., $\pi(j) > \pi(i)$. Hence there are four unique choices for such a entry $x$: the highest, lowest, farthest and nearest. This corresponds to the four mesh patterns in (1.8), respectively. $\square$
**Remark 1.4.** As earec($\pi$) = erec($\pi^{\text{roc}}$) for $\pi \in S_n$, we can also derive (1.9) from (1.8).

**Theorem 1.5.** There exists an involution $\Phi$ on $S_n$ such that for $\pi \in S_n$,

$$ (\begin{smallmatrix} \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \end{smallmatrix})\pi = (\begin{smallmatrix} \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \end{smallmatrix})\Phi(\pi). $$

**Corollary 1.1.** The triple pattern (Nr.3, Nr.48, Nr.53) is equidistributed with the triple pattern (erec, Nr.50, Nr.54) on $S_n$.

*Proof.* For any $\pi \in S_n$ we have

$$ \begin{bmatrix} \text{Nr.3} \\ \text{Nr.48} \\ \text{Nr.53} \end{bmatrix} \pi = \begin{bmatrix} \ddots \\ \ddots \\ \ddots \end{bmatrix} \pi = \begin{bmatrix} \ddots \\ \ddots \\ \ddots \end{bmatrix} \pi^{-1} = \begin{bmatrix} \ddots \\ \ddots \\ \ddots \end{bmatrix} (\pi^{-1})^r \quad (1.10) $$

and

$$ (\text{Nr.50, Nr.54})\pi = (\begin{smallmatrix} \ddots & \ddots \\ \ddots & \ddots \end{smallmatrix})\pi = (\begin{smallmatrix} \ddots & \ddots \\ \ddots & \ddots \end{smallmatrix})\pi^{-1} = (\begin{smallmatrix} \ddots & \ddots \\ \ddots & \ddots \end{smallmatrix})(\pi^{-1})^r. \quad (1.11) $$

By Theorem 1.5 the result follows from (1.9), (1.10) and (1.11). $\square$

**Corollary 1.2.** Conjecture 1.1 holds true.

*Proof.* By Corollary 1.1 this follows from (1.3b) with $x = v = q = 1$. $\square$

As the equidistribution of Nr.48 and Nr.49 is known [14, Theorem 5.1], Corollary 1.1 confirms two conjectured equidistributions in Table 1.

**Theorem 1.6.** There exist an involution $\Psi$ on $S_n$ such that for $\pi \in S_n$,

$$ (\begin{smallmatrix} \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \end{smallmatrix})\pi = (\begin{smallmatrix} \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \\ \ddots & \ddots & \ddots \end{smallmatrix})\Psi(\pi). $$

For the patterns Nr.23 and Nr.24, we have

$$ (\text{Nr.23, Nr.24})\pi = (\begin{smallmatrix} \ddots & \ddots \\ \ddots & \ddots \end{smallmatrix})\pi = (\begin{smallmatrix} \ddots & \ddots \\ \ddots & \ddots \end{smallmatrix})\pi^r. $$

By Theorem 1.6, we confirm another conjecture in Table 1, i.e., the patterns Nr.23 and Nr.24 are equidistributed.

We shall prove Theorem 1.5 and Theorem 1.6 in Section 2 and Section 3, respectively.
## 2 Proof outlines of Theorem 1.5

For $\pi \in S_n$ let $AREC(\pi) = (i_1, i_2, \dots, i_l)$ be the sequence of antirecord positions of $\pi$ from left to right. So $\pi(i_1) = 1$, $i_1 < \dots < i_l$ and $i_l = n$. For each antirecord position $i_k$ define two mappings

$$ \varphi_1^{(i_k)} : \pi \mapsto \pi' \qquad (2.1a) $$

$$ \varphi_2^{(i_k)} : \pi \mapsto \pi'' \qquad (2.1b) $$

as follows:

* let $w = w_1 \dots w_r$ be the subword of $\pi$ consisting of letters greater than $\pi(i_k)$ on the left of $\pi(i_k)$ (resp. $\pi(i_{k-1})$);

* let $w' = w'_1 \dots w'_r$ be the word obtained by substituting the $j$th largest letter with the $j$th smallest letter in $w$ for $j = 1, \dots, r$;

* let $\pi'$ (resp. $\pi''$) be the word obtained by replacing $w_j$ with $w'_j$ for $j = 1, \dots, r$ in $\pi$.

**Remark 2.1.** By convention, we define $\varphi_2^{(i_1)}$ to be the identity mapping. Clearly the two operations keep the sequence of antirecords for both values and positions, that is,

$$ \mathrm{AREC}(\pi) = \mathrm{AREC}(\pi') = \mathrm{AREC}(\pi'') \qquad (2.2a) $$

$$ \pi'(i_k) = \pi''(i_k) = \pi(i_k) \quad \text{for } k = 1, \dots, l. \qquad (2.2b) $$

Let $P = \{p_1 < \dots < p_r\}$ and $Q = \{q_1 < \dots < q_r\}$ be two ordered sets and $\pi = p_1 \dots p_r$ and $\tau = q_1 \dots q_r$ are permutations of $P$ and $Q$, respectively. We say that $\pi$ and $\tau$ are order isomorphic and write $\pi \sim \tau$ if for any two indices $r$ and $s$ we have the equivalence $p_r < p_s$ if and only if $q_r < q_s$. In other words, $\tau$ is the permutation obtained from $\pi$ by substituting $p_i$ by $q_i$ for $i = 1, \dots, r$.

Let $w = w_1 \dots w_n$ be a permutation of $a_1 < a_2 < \dots < a_n$. We define the complement of $w$ by $w^c$, which is the word obtained by substituting $a_i$ by $a_{n+1-i}$ in $w$ for $i = 1, \dots, n$. If $x$ is a subset of the letters in $w$, we write $[w]_x$ as the subword of $w$ consisting of the letters $a \in x$.

**Lemma 2.1.** 1. If $w = w_1w_2$ and $w^c = w'_1w'_2$, then $(w'_1)^c \sim w_1^c$.

2. Let $w = w_1w_2w_3$ and $v = v_1v_2v_3$ with $|w_1| = |v_1|$. If $w_1w_2 \sim v_1v_2$ with $(w_1w_2)^c = w'_1w'_2$ and $(v_1v_2)^c = v'_1v'_2$, then $w_1 \sim v_1$, $w_2 \sim v_2$, $w'_1 \sim v'_1$ and $w'_2 \sim v'_2$. Moreover, we have $(w'_1)^c \sim (v'_1)^c$ and $(w'_2)^c \sim (v'_2)^c$.

<footnote n="1">¹When $a_i = i$, $w^c$ reduces to $\pi^c$, see (1.7).</footnote>

<footnote n="2">²The word $w'_1$ is the complement of $w_1$ in the alphabet of $w$, while $(w'_1)^c$ is the complement of $w'_1$ in the alphabet of $w'_1$.</footnote>
3. If $w \sim v$ and $[w]_x = [v]_x$ for some set $x$ of some common letters in $w$ and $v$, then

* $w^c \sim v^c$ and $[w^c]_x = [v^c]_x$.

* $[w]_y \sim [v]_z$, where $y$ (resp. $z$) is the complementary of $x$ in the alphabet of $w$ (resp. $v$).

For example, if $w = 359147286$, then $w^c = 751963824$. Let $w = w_1w_2$ with $w_1 = 359147$ and $w_2 = 286$, then $w'_1 = 751963$ and $(w'_1)^c = 369157$. Clearly $(w'_1)^c \sim w_1$ and $[(w'_1)^c]_x = [w_1]_x$ with $x = \{1, 3, 9\}$. We see that $w_1^c = 741953$ and $[w'_1]_x = [w_1^c]_x = 193$.

**Lemma 2.2.** For any antirecord position $i$ of $\pi \in S_n$ the mappings $\varphi_1^{(i)}$ and $\varphi_2^{(i)}$ are involutions and commute, namely,

$$ \varphi_1^{(i)} \circ \varphi_1^{(i)}(\pi) = \varphi_2^{(i)} \circ \varphi_2^{(i)}(\pi) = \pi \qquad (2.3) $$

and

$$ \varphi_2^{(i)} \circ \varphi_1^{(i)}(\pi) = \varphi_1^{(i)} \circ \varphi_2^{(i)}(\pi). \qquad (2.4) $$

*Proof.* From the definitions of $\varphi_1^{(i)}$ and $\varphi_2^{(i)}$ in Eq. (2.1), it is easy to check Eq. (2.3) holds and

$$ \varphi_2^{(i)} \circ \varphi_1^{(i)}(\pi) \sim \varphi_1^{(i)} \circ \varphi_2^{(i)}(\pi). $$

Since the set of letters greater than $\pi(i)$ on the left of $\pi(i)$ are invariant under the operation $\varphi_1^{(i)}$ and $\varphi_2^{(i)}$ on $\pi$, we obtain Eq.(2.4) immediately. $\square$

Let $\pi \in S_n$ with sequence of antirecord positions AREC($\pi$) = $(i_1, i_2, \dots, i_l)$. We define the operation $\Phi$ on $\pi$ by

$$ \Phi(\pi) = \varphi^{(i_1)} \circ \varphi^{(i_2)} \circ \dots \circ \varphi^{(i_l)}(\pi) \qquad (2.5) $$

with $\varphi^{(i_k)} = \varphi_2^{(i_k)} \circ \varphi_1^{(i_k)}$ for $k = 1, \dots, l$.

**Lemma 2.3.** For $\pi \in S_n$ with AREC($\pi$) = $\{i_1, \dots, i_l\}$. The mappings $g := \varphi^{(i_{k-1})}$ and $f := \varphi^{(i_k)}$ commute, i.e.,

$$ g \circ f(\pi) = f \circ g(\pi). $$

**Lemma 2.4.** The mapping $\varphi^{(i_k)}$ is an involution such that for $\pi \in S_n$ and $r \neq k$,

$$ (\begin{tikzpicture}[baseline=(current bounding box.center)]
    \node at (0,0) {$\pi$};
    \node at (0,1) {$k$};
    \node at (1,0) {$r$};
    \node at (1,1) {$i_k$};
    \draw[->] (0,0) -- (1,0);
    \draw[->] (0,1) -- (1,1);
\end{tikzpicture})_k = (\begin{tikzpicture}[baseline=(current bounding box.center)]
    \node at (0,0) {$\pi$};
    \node at (0,1) {$r$};
    \node at (1,0) {$k$};
    \node at (1,1) {$i_k$};
    \draw[->] (0,0) -- (1,0);
    \draw[->] (0,1) -- (1,1);
\end{tikzpicture})_k \varphi^{(i_k)}(\pi), \qquad (2.6a) $$

$$ (\begin{tikzpicture}[baseline=(current bounding box.center)]
    \node at (0,0) {$\pi$};
    \node at (0,1) {$r$};
    \node at (1,0) {$k$};
    \node at (1,1) {$i_k$};
    \draw[->] (0,0) -- (1,0);
    \draw[->] (0,1) -- (1,1);
\end{tikzpicture})_r = (\begin{tikzpicture}[baseline=(current bounding box.center)]
    \node at (0,0) {$\pi$};
    \node at (0,1) {$r$};
    \node at (1,0) {$k$};
    \node at (1,1) {$i_k$};
    \draw[->] (0,0) -- (1,0);
    \draw[->] (0,1) -- (1,1);
\end{tikzpicture})_r \varphi^{(i_k)}(\pi), \qquad (2.6b) $$

$$ (\begin{tikzpicture}[baseline=(current bounding box.center)]
    \node at (0,0) {$\pi$};
    \node at (0,1) {$r$};
    \node at (1,0) {$k$};
    \node at (1,1) {$i_k$};
    \draw[->] (0,0) -- (1,0);
    \draw[->] (0,1) -- (1,1);
\end{tikzpicture})_r = (\begin{tikzpicture}[baseline=(current bounding box.center)]
    \node at (0,0) {$\pi$};
    \node at (0,1) {$r$};
    \node at (1,0) {$k$};
    \node at (1,1) {$i_k$};
    \draw[->] (0,0) -- (1,0);
    \draw[->] (0,1) -- (1,1);
\end{tikzpicture})_r \varphi^{(i_k)}(\pi), \qquad (2.6c) $$

where $(\text{pattern})_k$ means the number of the patterns between $\pi(i_{k-1})$ and $\pi(i_k)$.
*Proof of Theorem 1.5.* By (2.5) the reverse of the mapping $\Phi$ is given by

$$ \Phi^{-1}(\pi) = \varphi^{(i_1)} \circ \dots \circ \varphi^{(i_2)} \circ \varphi^{(i_1)}(\pi). \qquad (2.7) $$

Theorem 1.5 follows from Lemma 2.2, Lemma 2.3 and Lemma 2.4. $\square$

<figure><img src="image_4.png" /><figcaption>**Figure 1:** The involution $\Phi$ on the permutation 257189463</figcaption></figure>

**Example 2.2.** We show the process of the involution $\Phi$ in Figure 1, For $\pi = 257189463$, we have $AREC(\pi) = (4,9)$. We proceed from right to left.

1. For position 9 with value 3, we have $w = 578946$ and $w' = 865497$. Thus $\varphi_1^{(9)} : \pi \mapsto \pi' = 286154973$. Next, we have $w = 86$ and $w' = 68$. Thus $\varphi_2^{(9)} : \pi' \mapsto \pi'' = 268154973$.

2. For position 4 with value 1 we have $w = 268$ and $w' = 862$. Finally we obtain $\Phi(\pi) = 862154973$.

Now, we check the mesh patterns.
* First, $\varphi_1^{(9)}: \pi = 257189463 \mapsto \pi' = 286154973$, the pair (8,3) of $\pi$ contributes the pattern $\ddots\ddots$ without the patterns $\ddots\ddots, \ddots\ddots$, the pair (5,3) of $\pi'$ contributes the pattern $\ddots\ddots$ without the patterns $\ddots\ddots, \ddots\ddots$, the operations $\varphi_2^{(9)}, \varphi_1^{(1)}$ do not change the corresponding mesh patterns at position 9 of $\pi'$.

* Second, $\varphi_2^{(9)} \circ \varphi_1^{(9)}: \pi = 257189463 \mapsto \pi'' = 268154973$ it is easy to see that $257 \sim 268$. The pair (5,1) of $\pi$ contributes the patterns $\ddots\ddots$ without the pattern $\ddots\ddots$, the pair (6,1) of $\pi''$ also contributes the pattern $\ddots\ddots$ without the pattern $\ddots\ddots$, $\varphi_1^{(1)}: \pi'' = 268154973 \mapsto \pi''' = 862154973$, the pair (6,1) of $\pi'''$ contributes the pattern $\ddots\ddots$ without the pattern $\ddots\ddots$.

### 3 Proof outlines of Theorem 1.6

First we introduce two mappings different from Section 2. For $\pi \in S_n$, recall that $\text{AREC}(\pi) = (i_1, i_2, \dots, i_l)$ be the sequence of antirecord positions of $\pi$ from left to right. For any antirecord position $i_k$ we define two mappings

$$ \psi_1^{(i_k)}: \pi \mapsto \pi' \qquad (3.1a) $$

$$ \psi_2^{(i_k)}: \pi \mapsto \pi'' \qquad (3.1b) $$

as follows:

* let $w = w_1 \dots w_r$ is the subword of $\pi$ consisting of letters greater than $\pi(i_k)$ on the right side of $\pi(i_{k-1})$ (resp. $\pi(i_k)$) with $\pi(i_0) = 0$;

* let $w' = w'_1 \dots w'_r$ be the word obtained by substituting the $j$th largest letter with the $j$th smallest letter in $w$ for $j = 1, \dots, r$;

* let $\pi'$ (resp. $\pi''$) is defined to be the word obtained by replacing $w_j$ with $w'_j$ in $\pi$.

Note that $\pi'(i_k) = \pi(i_k)$.

**Lemma 3.1.** For any antirecord positions $i_{k-1}$ and $i_k$ of $\pi \in S_n$ the mappings $\psi_1^{(i_k)}$ and $\psi_2^{(i_k)}$ are involutions and commutate, namely,

$$ \psi_1^{(i_k)} \circ \psi_1^{(i_k)}(\pi) = \psi_2^{(i_k)} \circ \psi_2^{(i_k)}(\pi) = \pi \qquad (3.2) $$

and

$$ \psi_2^{(i_k)} \circ \psi_1^{(i_k)}(\pi) = \psi_1^{(i_k)} \circ \psi_2^{(i_k)}(\pi). \qquad (3.3) $$

Let $\psi^{(i_k)} = \psi_2^{(i_k)} \circ \psi_1^{(i_k)}$. Then $\psi^{(i_k)}(\pi)$ and $\pi$ have the same sequence of antirecord positions.
**Lemma 3.2.** For $\pi \in S_n$ with $AREC(\pi) = \{i_1, \dots, i_l\}$. For $k = 2, \dots, l$ the mappings $\psi^{(i_{k-1})}$ and $\psi^{(i_k)}$ commute, i.e.,

$$ \psi^{(i_k)} \circ \psi^{(i_{k-1})}(\pi) = \psi^{(i_{k-1})} \circ \psi^{(i_k)}(\pi). $$

**Lemma 3.3.** The mapping $\psi^{(i)}$ is an involution such that for $\pi \in S_n$ and $r \neq k$

$$ (\begin{tikzpicture}[baseline=(current bounding box.center)] \node at (0,0) {$\pi$}; \node at (0,1) {$\pi^{-1}$}; \draw[->] (0,0) -- (0,1); \draw[->] (0,1) -- (1,1); \draw[->] (1,1) -- (1,0); \draw[->] (1,0) -- (0,0); \end{tikzpicture})_k = (\begin{tikzpicture}[baseline=(current bounding box.center)] \node at (0,0) {$\pi$}; \node at (0,1) {$\pi^{-1}$}; \draw[->] (0,0) -- (0,1); \draw[->] (0,1) -- (1,1); \draw[->] (1,1) -- (1,0); \draw[->] (1,0) -- (0,0); \end{tikzpicture})_k \psi^{(i_k)}(\pi), \quad (3.4a) $$

$$ (\begin{tikzpicture}[baseline=(current bounding box.center)] \node at (0,0) {$\pi$}; \node at (0,1) {$\pi^{-1}$}; \draw[->] (0,0) -- (0,1); \draw[->] (0,1) -- (1,1); \draw[->] (1,1) -- (1,0); \draw[->] (1,0) -- (0,0); \end{tikzpicture})_r = (\begin{tikzpicture}[baseline=(current bounding box.center)] \node at (0,0) {$\pi$}; \node at (0,1) {$\pi^{-1}$}; \draw[->] (0,0) -- (0,1); \draw[->] (0,1) -- (1,1); \draw[->] (1,1) -- (1,0); \draw[->] (1,0) -- (0,0); \end{tikzpicture})_r \psi^{(i_k)}(\pi), \quad (3.4b) $$

$$ (\begin{tikzpicture}[baseline=(current bounding box.center)] \node at (0,0) {$\pi$}; \node at (0,1) {$\pi^{-1}$}; \draw[->] (0,0) -- (0,1); \draw[->] (0,1) -- (1,1); \draw[->] (1,1) -- (1,0); \draw[->] (1,0) -- (0,0); \end{tikzpicture})_r = (\begin{tikzpicture}[baseline=(current bounding box.center)] \node at (0,0) {$\pi$}; \node at (0,1) {$\pi^{-1}$}; \draw[->] (0,0) -- (0,1); \draw[->] (0,1) -- (1,1); \draw[->] (1,1) -- (1,0); \draw[->] (1,0) -- (0,0); \end{tikzpicture})_r \psi^{(i_k)}(\pi). \quad (3.4c) $$

where $(\text{pattern})_k$ means the number of the patterns between $\pi(i_{k-1})$ and $\pi(i_k)$.

*Proof of Theorem 1.6.* For $\pi \in S_n$ and $AREC(\pi) = (i_1, i_2, \dots, i_l)$, we define the operation $\Psi$ on $\pi$ by

$$ \Psi(\pi) = \psi^{(i_1)} \circ \dots \circ \psi^{(i_2)} \circ \dots \circ \psi^{(i_l)}(\pi). \quad (3.5) $$

By (3.5) the mapping $\Psi$ is reversible with reverse

$$ \Psi^{-1}(\pi) = \psi^{(i_1)} \circ \psi^{(i_2)} \circ \dots \circ \psi^{(i_l)}(\pi). $$

Theorem 1.6 follows from Lemma 3.1, Lemma 3.2 and Lemma 3.3. $\square$

An example of the involution $\Psi$ could be found in [9, Example 3.4].

## References

[1] S. Avgustinovich, S. Kitaev, and A. Valyuzhenich. "Avoidance of boxed mesh patterns on permutations". Discrete Appl. Math. 161.1-2 (2013), pp. 43–51. DOI.

[2] J.-L. Baril and S. Kirgizov. "Transformation à la Foata for Special Kinds of Descents and Excedances". ECA 1.3 (2021), Article S2R19.

[3] N. Borie. "On the combinatorics of quadrant marked mesh patterns in 132-avoiding permutations". Australas. J. Combin. 64 (2016), pp. 140–153.

[4] P. Brändén and A. Claesson. "Mesh patterns and the expansion of permutation statistics as sums of permutation patterns". Electron. J. Combin. 18.2 (2011), Paper 5, 14.

[5] D. Dumont and G. Kreweras. "Sur le développement d'une fraction continue liée à la série hypergéométrique et son interprétation en termes de records et anti-records dans les permutations". European J. Combin. 9.1 (1988), pp. 27–32. DOI.

[6] B. Han, J. Mao, and J. Zeng. "Eulerian polynomials and excedance statistics". Adv. in Appl. Math. 121 (2020), pp. 102092, 45. DOI.
[7] B. Han, J. Mao, and J. Zeng. "Eulerian polynomials and excedance statistics via continued fractions". Sém. Lothar. Combin. **84B** (2020), Art. 40, 12.

[8] B. Han, J. Mao, and J. Zeng. "Equidistributions around special kinds of descents and excedances". 2021. arXiv:2103.13092v2.

[9] B. Han and J. Zeng. "Equidistributions of mesh patterns of length two and Kitaev and Zhang's conjectures". Adv. in Appl. Math. **127** (2021), pp. 102149, 17. DOI.

[10] I. Hilmarsson, I. Jónsdóttir, S. Sigurdardóttir, L. Vidarsdóttir, and H. Ulfarsson. "Wilf-classification of mesh patterns of short length". Electron. J. Combin. **22.4** (2015), Paper 4.13, 27. DOI.

[11] S. Kitaev. *Patterns in permutations and words*. Monographs in Theoretical Computer Science. An EATCS Series. With a foreword by Jeffrey B. Remmel. Springer, Heidelberg, 2011, pp. xxii+494. DOI.

[12] S. Kitaev and J. Liese. "Harmonic numbers, Catalan's triangle and mesh patterns". Discrete Math. **313.14** (2013), pp. 1515–1531. DOI.

[13] S. Kitaev, J. Remmel, and M. Tiefenbruck. "Quadrant marked mesh patterns in 132-avoiding permutations". Pure Math. Appl. (PU.M.A.) **23.3** (2012), pp. 219–256.

[14] S. Kitaev and P. B. Zhang. "Distributions of mesh patterns of short lengths". Adv. in Appl. Math. **110** (2019), pp. 1–32. DOI.

[15] N. J. A. Sloane. "The On-Line Encyclopedia of Integer Sequences". Link.

[16] A. D. Sokal and J. Zeng. "Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions". 2020. arXiv:2003.08192v1.

[17] E. Steingrímsson. "Generalized permutation patterns—a short survey". Permutation patterns. Vol. 376. London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2010, pp. 137–152. DOI.

[18] B. E. Tenner. "Mesh patterns with superfluous mesh". Adv. in Appl. Math. **51.5** (2013), pp. 606–618. DOI.

[19] J. Zeng. "Records, antirecords et permutations discordantes". European J. Combin. **10.1** (1989), pp. 103–109. DOI.