Joint distributions of statistics over permutations avoiding two patterns of
length 3

Tian Han111College of Mathematical Science, Tianjin Normal University, Tianjin
300387, P. R. China. Email:
<EMAIL_ADDRESS>and Sergey Kitaev***Department of Mathematics and
Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH,
United Kingdom. Email<EMAIL_ADDRESS>
Abstract.

Finding distributions of permutation statistics over pattern-avoiding classes
of permutations attracted much attention in the literature. In particular,
Bukata et al. [3] found distributions of ascents and descents on permutations
avoiding any two patterns of length 3. In this paper, we generalize these
results in two different ways: we find explicit formulas for the joint
distribution of six statistics ($\operatorname{asc}$, $\operatorname{des}$,
$\operatorname{lrmax}$, $\operatorname{lrmin}$, $\operatorname{rlmax}$,
$\operatorname{rlmin}$), and also explicit formulas for the joint distribution
of four statistics ($\operatorname{asc}$, $\operatorname{des}$,
$\operatorname{MNA}$, $\operatorname{MND}$) on these permutations in all
cases. The latter result also extends the recent studies by Kitaev and Zhang
[7] of the statistics $\operatorname{MNA}$ and $\operatorname{MND}$ (related
to non-overlapping occurrences of ascents and descents) on stack-sortable
permutations. All multivariate generating functions in our paper are rational,
and we provide combinatorial proofs of five equidistribution results that can
be derived from the generating functions.

Keywords: Pattern-avoiding permutation; permutation statistic; generating
function; bijection

AMS Classification 2020: 05A05, 05A15

##  1 Introduction

A permutation of length $n$ is a rearrangement of the set
$[n]:=\\{1,2,\ldots,n\\}$. Denote by $S_{n}$ the set of permutations of $[n]$.
For $\pi\in S_{n}$, let $\pi^{r}=\pi_{n}\pi_{n-1}\cdots\pi_{1}$ and
$\pi^{c}=(n+1-\pi_{1})(n+1-\pi_{2})\cdots(n+1-\pi_{n})$ denote the reverse and
complement of $\pi$, respectively. Then
$\pi^{rc}=(n+1-\pi_{n})(n+1-\pi_{n-1})\cdots(n+1-\pi_{1})$. A permutation
$\pi_{1}\pi_{2}\cdots\pi_{n}\in S_{n}$ avoids a pattern $p=p_{1}p_{2}\cdots
p_{k}\in S_{k}$ if there is no subsequence
$\pi_{i_{1}}\pi_{i_{2}}\cdots\pi_{i_{k}}$ such that $\pi_{i_{j}}<\pi_{i_{m}}$
if and only if $p_{j}<p_{m}$. For example, the permutation $32154$ avoids the
pattern $231$. Let $S_{n}(\tau,\rho)$ denote the set of permutations in
$S_{n}$ that avoid patterns $\tau$ and $\rho$. The area of permutation
patterns attracted much attention in the literature (see [5] and reference
therein).

Of interest to us are the following classical permutation statistics. For
$1\leq i\leq n-1$, $i$ is an _ascent_ (resp., _descent_) in $\pi\in S_{n}$ if
$\pi_{i}<\pi_{i+1}$ (resp., $\pi_{i}>\pi_{i+1}$) and $\operatorname{asc}(\pi)$
(resp., $\operatorname{des}(\pi)$) is the number of ascents (resp., descents)
in $\pi$. Also, $\pi_{i}$ is a _right-to-left maximum_ (resp., _right-to-left
minimum_) in $\pi$ if $\pi_{i}$ is greater (resp., smaller) than any element
to its right. Note that $\pi_{n}$ is always a right-to-left maximum and a
right-to-left minimum. Denote by $\operatorname{rlmax}(\pi)$ and
$\operatorname{rlmin}(\pi)$ the number of right-to-left maxima and right-to-
left minima in $\pi$, respectively. We define _left-to-right maximum_ , _left-
to-right minimum_ , $\operatorname{lrmax}(\pi)$ and
$\operatorname{lrmin}(\pi)$ in a similar way. For example, if $\pi=34152$ then
$\operatorname{lrmax}(\pi)=3$ and
$\operatorname{lrmin}(\pi)=\operatorname{rlmin}(\pi)=\operatorname{rlmax}(\pi)=\operatorname{asc}(\pi)=\operatorname{des}(\pi)=2$.

We are also interested in the statistics maximum number of non-overlapping
ascents (denoted $\operatorname{MNA}$) and maximum number of non-overlapping
descents (denoted $\operatorname{MND}$). For example,
$\operatorname{des}(13254)=\operatorname{MND}(13254)=2$ while
$3=\operatorname{des}(32154)\neq\operatorname{MND}(32154)=2$. These statistics
are a particular case of the study of the maximum number of non-overlapping
consecutive patterns in [6] and recently, Kitaev and Zhang [7] studied
$\operatorname{MNA}$ and $\operatorname{MND}$ on permutations avoiding a
single pattern of length 3.

Also, $k$-tuples of (permutation) statistics $(s_{1},s_{2},\ldots,s_{k})$ and
$(s_{1}^{\prime},s_{2}^{\prime},\ldots,s_{k}^{\prime})$ are equidistributed
over a set $S$ if

$\sum_{a\in S}t_{1}^{s_{1}(a)}t_{2}^{s_{2}(a)}\cdots
t_{k}^{s_{k}(a)}=\sum_{a\in
S}t_{1}^{s_{1}^{\prime}(a)}t_{2}^{s_{2}^{\prime}(a)}\cdots
t_{k}^{s_{k}^{\prime}(a)}.$

There is a line of research in the literature on finding distributions of
permutation statistics over pattern-avoiding classes of permutations (see, for
example, [1, 2, 3, 4] and references therein). In particular, Bukata et al.
[3] found distributions of ascents and descents on permutations avoiding any
two patterns of length 3. In this paper, we generalize these results in two
different ways. Namely, we find explicit formulas for the joint distribution
of six statistics ($\operatorname{asc}$, $\operatorname{des}$,
$\operatorname{lrmax}$, $\operatorname{lrmin}$, $\operatorname{rlmax}$,
$\operatorname{rlmin}$), and also explicit formulas for the joint distribution
of four statistics ($\operatorname{asc}$, $\operatorname{des}$,
$\operatorname{MNA}$, $\operatorname{MND}$) on these permutations. The latter
result also extends recent studies by Kitaev and Zhang [7] of the statistics
$\operatorname{MNA}$ and $\operatorname{MND}$ on stack-sortable permutations
(which are precisely 231-avoiding permutations). Moreover, we provide
combinatorial proofs of five equidistribution results observed from the multi-
variable generating functions derived in this paper.

In what follows, we let g.f. stand for “generating function”. We will derive
closed form expressions for the following g.f.’s

$F_{(\tau,\rho)}(x,p,q,u,v,s,t):=\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}u^{\operatorname{lrmax}(\pi)}v^{\operatorname{rlmax}(\pi)}s^{\operatorname{lrmin}(\pi)}t^{\operatorname{rlmin}(\pi)}$
$G_{(\tau,\rho)}(x,p,q,y,z):=\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}y^{\operatorname{MNA}(\pi)}z^{\operatorname{MND}(\pi)}$

for all $\tau$ and $\rho$ in $S_{3}$. All of our g.f.’s are rational
functions. Note that

$\operatorname{des}(\pi)=\operatorname{asc}(\pi^{r})=\operatorname{asc}(\pi^{c})=\operatorname{des}(\pi^{rc}),$
$\operatorname{lrmax}(\pi)=\operatorname{rlmax}(\pi^{r})=\operatorname{lrmin}(\pi^{c})=\operatorname{rlmin}(\pi^{rc}),$
$\operatorname{MND}(\pi)=\operatorname{MNA}(\pi^{r})=\operatorname{MNA}(\pi^{c})=\operatorname{MND}(\pi^{rc})$

and hence

$\displaystyle F_{(\tau^{r},\rho^{r})}(x,p,q,u,v,s,t)$
$\displaystyle=\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(\tau^{r},\rho^{r})}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}u^{\operatorname{lrmax}(\pi)}v^{\operatorname{rlmax}(\pi)}s^{\operatorname{lrmin}(\pi)}t^{\operatorname{rlmin}(\pi)}$
$\displaystyle=\sum_{n\geq 0}\ \sum_{\pi^{r}\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{des}(\pi^{r})}q^{\operatorname{asc}(\pi^{r})}u^{\operatorname{rlmax}(\pi^{r})}v^{\operatorname{lrmax}(\pi^{r})}s^{\operatorname{rlmin}(\pi^{r})}t^{\operatorname{lrmin}(\pi^{r})}$
$\displaystyle=F_{(\tau,\rho)}(x,q,p,v,u,t,s);$ $\displaystyle
F_{(\tau^{c},\rho^{c})}(x,p,q,u,v,s,t)$ $\displaystyle=\sum_{n\geq 0}\
\sum_{\pi\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{des}(\pi)}q^{\operatorname{asc}(\pi)}u^{\operatorname{lrmin}(\pi)}v^{\operatorname{rlmin}(\pi)}s^{\operatorname{lrmax}(\pi)}t^{\operatorname{rlmax}(\pi)}$
$\displaystyle=F_{(\tau,\rho)}(x,q,p,s,t,u,v);$ $\displaystyle
F_{(\tau^{rc},\rho^{rc})}(x,p,q,u,v,s,t)$ $\displaystyle=\sum_{n\geq 0}\
\sum_{\pi\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}u^{\operatorname{rlmin}(\pi)}v^{\operatorname{lrmin}(\pi)}s^{\operatorname{rlmax}(\pi)}t^{\operatorname{lrmax}(\pi)}$
$\displaystyle=F_{(\tau,\rho)}(x,p,q,t,s,v,u);$ $\displaystyle
G_{(\tau^{r},\rho^{r})}(x,p,q,y,z)$
$\displaystyle=G_{(\tau^{c},\rho^{c})}(x,p,q,y,z)=\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{des}(\pi)}q^{\operatorname{asc}(\pi)}y^{\operatorname{MND}(\pi)}z^{\operatorname{MNA}(\pi)}$
$\displaystyle=G_{(\tau,\rho)}(x,q,p,z,y);$ $\displaystyle
G_{(\tau^{rc},\rho^{rc})}(x,p,q,y,z)$ $\displaystyle=\sum_{n\geq 0}\
\sum_{\pi\in
S_{n}(\tau,\rho)}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}y^{\operatorname{MNA}(\pi)}z^{\operatorname{MND}(\pi)}=G_{(\tau,\rho)}(x,p,q,y,z).$

The following results appear in [8].

######  Theorem 1.1.

Let $A_{n}(\tau,\rho)$ be the number of elements in $S_{n}(\tau,\rho)$. Then,

  * (a)

$A_{n}(123,132)=A_{n}(123,213)=A_{n}(321,231)=A_{n}(321,312)=2^{n-1}$;

  * (b)

$A_{n}(231,312)=A_{n}(132,213)=2^{n-1}$;

  * (c)

$A_{n}(213,312)=A_{n}(132,231)=2^{n-1}$;

  * (d)

$A_{n}(213,231)=A_{n}(132,312)=2^{n-1}$;

  * (e)

$A_{n}(132,321)=A_{n}(123,231)=A_{n}(123,312)=A_{n}(213,321)=1+\binom{n}{2}$;

  * (f)

$A_{n}(123,321)=\begin{cases}0&\text{if\ $n\geq 5$}\\\ n&\text{if\ $n=1$ or\
$n=2$}\\\ 4&\text{if\ $n=3$ or\ $n=4$. }\end{cases}$

In order to determine the distribution of the statistics over
$S_{n}(\tau,\rho)$, for every $\tau,\rho\in S_{3}$, based on the properties of
the g.f.’s discussed above, out of all possible $15$ pairs it is sufficient to
examine the distributions of the statistics over the first pair in each of
(a)–(e) in Theorem 1.1 since the case of $(123,321)$-avoiding permutations is
trivial.

This paper is organized as follows. In Section 2, we derive all our
distribution results that are summarized in Tables 1 and 2, where one can find
references to the general results and to the formulas giving individual
distributions of the statistics, respectively. From our enumerative results we
note five equidistributions that are proved combinatorially in Section 3 via
introduction of two bijective maps $f$ and $g$. Finally, in Section 4 we
provide concluding remarks.

| $(\operatorname{asc},\operatorname{des},\operatorname{lrmax},\operatorname{lrmin},\operatorname{rlmax},\operatorname{rlmin})$ | $(\operatorname{asc},\operatorname{des},\operatorname{MNA},\operatorname{MND})$
---|---|---
$S_{n}(123,132)$ | Theorem 2.3 | Theorem 2.1
$S_{n}(132,321)$ | Theorem 2.7 | Theorem 2.5
$S_{n}(231,312)$ | Theorem 2.11 | Theorem 2.9
$S_{n}(213,231)$ | Theorem 2.15 | Theorem 2.13
$S_{n}(213,312)$ | Theorem 2.19 | Theorem 2.17
Table 1: G.f.’s for joint distributions of the statistics over $S_{n}(\tau,\rho)$ | $\operatorname{asc}$ | $\operatorname{des}$ | $\operatorname{lrmax}$ | $\operatorname{rlmax}$ | $\operatorname{lrmin}$ | $\operatorname{rlmin}$ | $\operatorname{MNA}$ | $\operatorname{MND}$
---|---|---|---|---|---|---|---|---
$S_{n}(123,132)$ | (4) | (5) | (11) | (12) | (13) | (14) | (6) | (7)
$S_{n}(132,321)$ | (18) | (19) | (25) | (26) | (27) | (28) | (20) | (21)
$S_{n}(231,312)$ | (32) | (33) | (39) | (40) | (41) | (42) | (34) | (35)
$S_{n}(213,231)$ | (46) | (47) | (54) | (55) | (56) | (57) | (48) | (49)
$S_{n}(213,312)$ | (59) | (60) | (64) | (65) | (66) | (67) | (61) | (62)
Table 2: G.f.’s for individual distributions of the statistics over
$S_{n}(\tau,\rho)$

##  2 Distributions over $S_{n}(\tau,\rho)$

In this section, we find joint distribution of the seven classical statistics
across the five types of arrangements in Section 1. Furthermore, we find joint
distribution of two more statistics: the maximum number of non-overlapping
descents $(\operatorname{MND})$ and the maximum number of non-overlapping
ascents $(\operatorname{MNA})$ over the same set of permutations.

Given permutations $\alpha\in S_{a}$ and $\beta\in S_{b}$, let
$\alpha\oplus\beta\in S_{a+b}$ denote the direct sum of $\alpha$ and $\beta$
and let $\alpha\ominus\beta\in S_{a+b}$ denote the skew-sum of $\alpha$ and
$\beta$, defined as follows[3]:

$\alpha\oplus\beta=\begin{cases}\alpha(i),&1\leq i\leq a;\\\
a+\beta(i-a),&a+1\leq i\leq a+b.\\\ \end{cases}$

$\alpha\ominus\beta=\begin{cases}\alpha(i)+b,&1\leq i\leq a;\\\
\beta(i-a),&a+1\leq i\leq a+b.\\\ \end{cases}$

For example, for $\alpha=123\in S_{3}$ and $\beta=4132\in S_{4}$,
$\alpha\oplus\beta=1237465$ and $\alpha\ominus\beta=5674132$.

###  2.1 Permutations in $S_{n}(123,132)$

We first describe the structure of a $(123,132)$-avoiding permutation. Let
$\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(123,132)$. If $\pi_{k}=n,1<k\leq n$, then
$\pi_{1}>\pi_{2}>\cdots>\pi_{k-1}$ in order to avoid 123. On the other hand,
in order to avoid 132, $\pi_{i}>n-k$ if $i<k$. Hence, $\pi_{i}=n-i$ for $1\leq
i\leq k-1$, while $\pi_{k+1}\pi_{k+2}\cdots\pi_{n}$ must be a (123,
132)-avoiding permutation in $S_{n-k}$. So $\pi=(\alpha\oplus
S_{1})\ominus\beta$, where $\alpha\in S_{k-1}$ is a decreasing permutation and
$\beta\in S_{n-k}$ is a (123,132)-avoiding permutation, and we use the
structure of $\pi$ to prove the following theorems.

######  Theorem 2.1.

For $S_{n}(123,132)$, we have

$G_{(123,132)}(x,p,q,y,z)=\frac{A}{1-2q^{2}x^{2}z-pqx^{2}yz-2pq^{2}x^{3}yz+q^{4}x^{4}z^{2}-pq^{3}x^{4}yz^{2}},$
(1)

where

$\displaystyle
A=1+x+px^{2}y+qx^{2}z-2q^{2}x^{2}z-q^{2}x^{3}z-pqx^{2}yz+2pqx^{3}yz-2pq^{2}x^{3}yz-$
$\displaystyle
q^{3}x^{4}z^{2}+q^{4}x^{4}z^{2}+pq^{2}x^{4}yz^{2}-pq^{3}x^{4}yz^{2}.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(123,132)$. If $n=0$, it will give 1 to
$G_{(123,132)}(x,p,q,y,z)$. For $n\geq 1$, we consider three cases based on
where the element $n$ appears in $\pi$.

  * (a)

If $\pi_{1}=n$, we let the g.f. for these permutations be

$g_{(123,132)}(x,p,q,y,z):=\sum_{n\geq 1}\ \sum_{\begin{subarray}{c}\pi\in
S_{n}(123,132)\\\
\pi_{1}=n\end{subarray}}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}y^{\operatorname{MNA}(\pi)}z^{\operatorname{MND}(\pi)}.$

  * (b)

Suppose $\pi_{k}=n$, where $k=2i,i\geq 1$. In this case, $\pi=(\alpha\oplus
S_{1})\ominus\beta$, where $\alpha\in S_{2i-1}$ is a decreasing permutation
with $i-1$ non-overlapping descents and $2i-2$ descents, the corresponding
g.f. is

$\sum_{i\geq 1}x^{2i-1}q^{2i-2}z^{i-1}=\frac{x}{1-x^{2}zq^{2}},$

and $S_{1}\ominus\beta$ is a (123,132)-avoiding permutation in $S_{n-2i+1}$.
Because the first element of the permutation $S_{1}\ominus\beta$ is the
maximum, the corresponding g.f. is $g_{(123,132)}(x,p,q,y,z)$. Additionally,
$\pi_{k-1}<\pi_{k}=n$, and $\pi_{k-1}\pi_{k}$ contributes to
$\operatorname{MNA}$ giving an extra factor of $yp$. In conclusion, the g.f.
for permutations in case (b) is

$g_{(123,132)}(x,p,q,y,z)\frac{xyp}{1-x^{2}zq^{2}}.$

  * (c)

Suppose $\pi_{k}=n$, where $k=2i+1,i\geq 1$. In this case, $\pi=(\alpha\oplus
S_{1})\ominus\beta$, where $\alpha\in S_{2i}$ is a decreasing permutation with
$i$ non-overlapping descents and $2i-1$ descents, the corresponding g.f. is

$\sum_{i\geq 1}x^{2i}z^{i}q^{2i-1}=\frac{x^{2}zq}{1-x^{2}zq^{2}},$

and $S_{1}\ominus\beta$ is a (123,132)-avoiding permutation in $S_{n-2i}$.
Using similar considerations as those in case (b), the g.f. for permutations
in case (c) is

$g_{(123,132)}(x,p,q,y,z)\frac{x^{2}zypq}{1-x^{2}zq^{2}}.$

Combining cases (a)–(c), we have

$\displaystyle
G_{(123,132)}(x,p,q,y,z)=1+g_{(123,132)}(x,p,q,y,z)+g_{(123,132)}(x,p,q,y,z)\frac{xyp}{1-x^{2}zq^{2}}+$
$\displaystyle g_{(123,132)}(x,p,q,y,z)\frac{x^{2}zypq}{1-x^{2}zq^{2}}.$ (2)

Next, we compute $g_{(123,132)}(x,p,q,y,z)$ similarly to the derivation of
$G_{(123,132)}(x,p,q,y,z)$. If $1\leq n\leq 2$, the corresponding g.f. is
$x+x^{2}zq$. Next, we distinguish three cases($n\geq 3$):

  * (d)

If $\pi_{2}=n-1$ then $\pi_{1}\pi_{2}=n(n-1)$ contributes to
$\operatorname{MND}$ that is independent from the count of MND in
$\pi_{3}\cdots\pi_{n}$, which can be any non-empty permutation in
$S_{n-2}(123,132)$. Note that $\pi_{2}>\pi_{3}$ contributes to a descent, so
the corresponding g.f. in this case is
$x^{2}zq^{2}(G_{(123,132)}(x,p,q,y,z)-1)$.

  * (e)

Suppose $\pi_{m}=n-1$, where $m=2i,i\geq 2$. In this case,
$\alpha=\emptyset,\beta=\gamma\ominus S_{1}\ominus\zeta$, so
$\pi=S_{1}\ominus\gamma\ominus S_{1}\ominus\zeta$, where
$S_{1}\ominus\gamma\in S_{2i-1}$ is a decreasing permutation with $i-1$ non-
overlapping descents and $2i-2$ descents, and the corresponding g.f. is

$\sum_{i\geq 2}x^{2i-1}z^{i-1}q^{2i-2}=\frac{x^{3}zq^{2}}{1-x^{2}zq^{2}}.$

Also, the permutation $S_{1}\ominus\zeta$ is in $S_{n-2i+1}(123,132)$ where
$\zeta\in S_{n-2i}$. Because the first element of $S_{1}\ominus\zeta$ is the
maximum, the corresponding g.f. is $g_{(123,132)}(x,p,q,y,z)$. Moreover,
$\pi_{m-1}<\pi_{m}=n-1$, so $\pi_{m-1}\pi_{m}$ forms an extra non-overlapping
ascent and ascent. To summarize, the corresponding g.f. for permutations in
case (e) is

$g_{(123,132)}(x,p,q,y,z)\frac{x^{3}yzpq^{2}}{1-x^{2}zq^{2}}.$

  * (f)

Suppose $\pi_{m}=n-1$, where $m=2i+1,i\geq 1$. In this situation,
$\pi=S_{1}\ominus\gamma\ominus S_{1}\ominus\zeta$, where
$S_{1}\ominus\gamma\in S_{2i}$ is a decreasing permutation contributing $i$
non-overlapping descents and $2i-1$ descents. The g.f. for
$S_{1}\ominus\gamma\in S_{2i}$ is

$\sum_{i\geq 1}x^{2i}z^{i}q^{2i-1}=\frac{x^{2}zq}{1-x^{2}zq^{2}}.$

In conclusion, the g.f. for the permutations in case (f) is

$g_{(123,132)}(x,p,q,y,z)\frac{x^{2}zqyp}{1-x^{2}zq^{2}}.$

Summarizing (d)–(f) we obtain

$\displaystyle
g_{(123,132)}(x,p,q,y,z)=x+x^{2}zq+x^{2}zq^{2}(G_{(123,132)}(x,p,q,y,z)-1)+$
$\displaystyle
g_{(123,132)}(x,p,q,y,z)\frac{x^{3}yzpq^{2}}{1-x^{2}zq^{2}}+g_{(123,132)}(x,p,q,y,z)\frac{x^{2}zqyp}{1-x^{2}zq^{2}}.$
(3)

By simultaneously solving (2.1) and (2.1), we obtain (1). ∎

######  Corollary 2.2.

Setting three out of the four variables $y$, $z$, $p$ and $q$ equal to one
individually in (1), we obtain single distributions of $\operatorname{asc}$,
$\operatorname{des}$, $\operatorname{MNA}$ and $\operatorname{MND}$ over
$S_{n}(123,132)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(123,132)}x^{n}p^{\operatorname{asc}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-2x+x^{2}-px^{2}};$ (4) $\displaystyle\sum_{n\geq
0}\ \sum_{\pi\in S_{n}(123,132)}x^{n}q^{\operatorname{des}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1+x-2qx+x^{2}-2qx^{2}+q^{2}x^{2}}{1-2qx-
qx^{2}+q^{2}x^{2}};$ (5) $\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(123,132)}x^{n}y^{\operatorname{MNA}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-2x+x^{2}-x^{2}y};$ (6) $\displaystyle\sum_{n\geq
0}\ \sum_{\pi\in S_{n}(123,132)}x^{n}z^{\operatorname{MND}(\pi)}$
$\displaystyle=$
$\displaystyle\frac{1+x+x^{2}-2x^{2}z-x^{3}z}{1-3x^{2}z-2x^{3}z}.$ (7)

######  Theorem 2.3.

For $S_{n}(123,132)$, we have

$\displaystyle F_{(123,132)}(x,p,q,u,v,s,t)=$ (8)
$\displaystyle\frac{1+q^{2}s^{2}vx^{2}+stuvx(1+ptux)-qsx(1+puv^{2}x^{2}st(-1+t)(-1+u)+v(1+px+stux))}{1+q^{2}s^{2}vx^{2}-qsx(1+v+pvx)}.$

###### Proof.

For $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(123,132)$, if $n=0$, it will give 1 to
$F_{(123,132)}(x,p,q,u,v,s,t)$. Let $n\geq 1$, we consider the following
cases.

  * •

If $\pi_{1}=n$, the element $n$ is the only left-to-right maximum, a left-to-
right minimum and a right-to-left maximum, and $\pi_{1}\pi_{2}$ is a descent.
So $\operatorname{lrmax}(\pi)=1$ and the g.f. of permutations with $\pi_{1}=n$
is given by $xquvs(F_{(123,132)}(x,p,q,1,v,s,t)-1)+xuvst$, where the element
$n$ gives a factor of $xquvs$ (multiplied by the g.f. of all non-empty
permutations with the value of $\operatorname{lrmax}$ not taken into account)
and the term $xuvst$ corresponds to the permutation of length 1.

  * •

If $\pi_{n}=n$, then $\pi=(n-1)(n-2)\cdots 1n=(\alpha\oplus
S_{1})\ominus\beta$, where $\beta$ is the empty permutation. The g.f. for the
decreasing permutation $\alpha$ is

$\sum_{i\geq 1}x^{i}q^{i-1}us^{i}t=\frac{usxt}{1-xsq}.$

So, the g.f. for permutations in this case is

$xpuvt\sum_{i\geq 1}x^{i}q^{i-1}us^{i}t=\frac{u^{2}sx^{2}pvt^{2}}{1-xsq},$

where the element $n$ gives a factor of $xpuvt$.

  * •

If $\pi_{k}=n,1<k\leq n$, we have $\pi_{1}>\pi_{2}>\cdots>\pi_{k-1}$ and
$\operatorname{lrmax}(\pi)=2$. Then $\pi=(\alpha\oplus S_{1})\ominus\beta$,
where any non-empty permutation in $S_{n-k}(123,132)$ is possible for $\beta$.
The g.f. for $\alpha\oplus S_{1}$ is

$xpquv\sum_{i\geq 1}x^{i}q^{i-1}us^{i}=\frac{u^{2}sx^{2}pqv}{1-xsq},$

where the maximum element $n$ gives a factor of $xpquv$. So the g.f. in this
case is

$(F_{(123,132)}(x,p,q,1,v,s,t)-1)\frac{u^{2}sx^{2}pqv}{1-xsq}.$

Synthesizing the above three conditions yields

$\displaystyle F_{(123,132)}(x,p,q,u,v,s,t)=$ (9) $\displaystyle
1+xquvs(F_{(123,132)}(x,p,q,1,v,s,t)-1)+xtuvs+\frac{u^{2}sx^{2}pvt^{2}}{1-xsq}+$
$\displaystyle(F_{(123,132)}(x,p,q,1,v,s,t)-1)\frac{u^{2}sx^{2}pqv}{1-xsq}.$

Let $u=1$ in (9), we obtain

$\displaystyle F_{(123,132)}(x,p,q,1,v,s,t)=$ (10) $\displaystyle
1+xtvs+xqvs(F_{(123,132)}(x,p,q,1,v,s,t)-1)+\frac{sx^{2}pvt^{2}}{1-xsq}+$
$\displaystyle(F_{(123,132)}(x,p,q,1,v,s,t)-1)\frac{x^{2}pqvs}{1-xsq}.$

By simultaneously solving (9) and (10), we obtain the desired result. ∎

######  Corollary 2.4.

Let $p=q=1$, then setting three out of the four variables $u$, $v$, $s$ and
$t$ equal to one individually in (8), we obtain single distributions of
$\operatorname{lrmax}$, $\operatorname{rlmax}$, $\operatorname{lrmin}$ and
$\operatorname{rlmin}$ over $S_{n}(123,132)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(123,132)}x^{n}u^{\operatorname{lrmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+ux-ux^{2}+u^{2}x^{2}}{1-2x};$ (11)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(123,132)}x^{n}v^{\operatorname{rlmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-x-vx};$ (12) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(123,132)}x^{n}s^{\operatorname{lrmin}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1-sx}{1-2sx-sx^{2}+s^{2}x^{2}};$ (13)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(123,132)}x^{n}t^{\operatorname{rlmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+tx-tx^{2}+t^{2}x^{2}}{1-2x}.$ (14)

###  2.2 Permutations in $S_{n}(132,321)$

We first describe the structure of a $(132,321)$-avoiding permutation. Let
$\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(132,321)$. If $\pi_{1}=n$, then
$\pi=n12\cdots(n-1)$. If $\pi_{k}=n,1<k<n$, then
$\pi_{k+1}<\pi_{k+2}<\cdots<\pi_{n}$ in order to avoid 321; on the other hand,
in order to avoid 132, $\pi_{i}=n-k+i$ if $1\leq i\leq k-1$. If $\pi_{n}=n$
then $\pi_{1}\pi_{2}\cdots\pi_{n-1}\in S_{n-1}(132,321)$. So
$\pi=(\alpha\oplus S_{1})\ominus\beta$, where $\alpha\oplus S_{1}\in S_{k}$
and $\beta\in S_{n-k}$ are two increasing (132, 321)-avoiding permutations. We
use the structure of $\pi$ to prove the following theorems.

######  Theorem 2.5.

For $S_{n}(132,321)$, we have

$G_{(132,321)}(x,p,q,y,z)=\frac{A}{(1-p^{2}x^{2}y)^{3}},$ (15)

where

$\displaystyle
A=1+x+px^{2}y-3p^{2}x^{2}y-2p^{2}x^{3}y-2p^{3}x^{4}y^{2}+3p^{4}x^{4}y^{2}+p^{4}x^{5}y^{2}+$
$\displaystyle
p^{5}x^{6}y^{3}-p^{6}x^{6}y^{3}+qx^{2}z+3pqx^{3}yz+p^{2}qx^{4}yz+2p^{2}qx^{4}y^{2}z+p^{3}qx^{5}y^{2}z.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(132,321)$. The empty permutation,
corresponding to the case of $n=0$ gives the term of 1 in
$G_{(132,321)}(x,p,q,y,z)$. If $\pi\in S_{1}$, the corresponding g.f. is $x$.
For $n\geq 2$, the permutations are divided into three classes depending on
the position of $n$.

  * (a)

If $\pi_{1}=n$ then $\pi=n12\cdots(n-1)$. When $n$ is even, the number of non-
overlapping ascents is $(n-2)/2$, and the corresponding g.f. is

$\sum_{\begin{subarray}{c}i\geq
1\end{subarray}}x^{2i}y^{\frac{2i-2}{2}}zqp^{2i-2}=\frac{x^{2}qz}{1-x^{2}yp^{2}}.$

When $n$ is odd, the number of non-overlapping ascents is $(n-1)/2$, and the
corresponding g.f. is

$\sum_{\begin{subarray}{c}i\geq
1\end{subarray}}x^{2i+1}y^{i}zp^{2i-1}q=\frac{x^{3}ypqz}{1-x^{2}yp^{2}}.$

  * (b)

Let $\pi_{k}=n$, where $1<k<n$. In this case, $\pi=(\alpha\oplus
S_{1})\ominus\beta$, where $\alpha\oplus S_{1}\in S_{k}$ and $\beta\in
S_{n-k}$ are two increasing (132, 321)-avoiding permutations. Aditionately,
$\pi_{k}=n>\pi_{k+1}$, and $\pi_{k}\pi_{k+1}$ contributes to
$\operatorname{MND}$ giving an extra factor of $z$. Using similar
considerations as those in case (a), the g.f. for permutations in case (b) is

$\frac{z(x^{2}ypq+x^{3}yp^{2}q)(x+x^{2}yp)}{(1-x^{2}yp^{2})^{2}}.$

  * (c)

If $\pi_{n}=n$, we let the g.f. for these permutations be

$g_{(132,321)}(x,p,q,y,z):=\sum_{n\geq 2}\ \sum_{\begin{subarray}{c}\pi\in
S_{n}(132,321)\\\
\pi_{n}=n\end{subarray}}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}y^{\operatorname{MNA}(\pi)}z^{\operatorname{MND}(\pi)}.$

Combining cases (a)–(c), we have

$\displaystyle
G_{(132,321)}(x,p,q,y,z)=1+x+\frac{x^{2}zq+x^{3}yzpq}{1-x^{2}yp^{2}}+$ (16)
$\displaystyle\frac{z(x^{2}ypq+x^{3}yp^{2}q)(x+x^{2}yp)}{(1-x^{2}yp^{2})^{2}}+g_{(132,321)}(x,p,q,y,z).$

Next, we evaluate $g_{(132,321)}(x,p,q,y,z)$:

  * (d)

If $\pi\in S_{2}$, then $\pi_{1}\pi_{2}=12$ and the corresponding g.f. is
$x^{2}yp$.

  * (e)

If $\pi_{1}=n-1$ then $\pi=(n-1)12\cdots n$. Using similar considerations as
those in case (a), the g.f. for permutations in case (e) is

$\frac{x^{3}yzpq+x^{4}yzp^{2}q}{1-x^{2}yp^{2}}.$

  * (f)

If $\pi_{m}=n-1$, where $1<m<n-1$, then $\pi=((\gamma\oplus
S_{1})\ominus\zeta)\oplus S_{1}$, where $\alpha=(\gamma\oplus
S_{1})\ominus\zeta\in S_{n-1}$ and $\beta$ is the empty permutation.
$\gamma\oplus S_{1}\in S_{m}$ and $\zeta\oplus S_{1}\in S_{n-m}$ are two
increasing (132, 321)-avoiding permutations. Using similar considerations as
those in case (a), the g.f. for permutations in case (f) is

$\frac{(x^{2}ypq+x^{3}yp^{q})^{2}zq}{(1-x^{2}yp^{2})^{2}}.$

  * (g)

If $\pi_{n-1}=n-1$ then $\pi_{n-1}\pi_{n}=(n-1)n$ contributes to
$\operatorname{MNA}$ giving an extra factor of $x^{2}yp$. Note that
$\pi_{n-2}<\pi_{n-1}=(n-1)$ and any non-empty permutation in
$S_{n-2}(132,321)$ is possible for $\pi_{1}\cdots\pi_{n-2}$. The g.f. in case
(g) is $x^{2}yp^{2}(G_{(132,321)}(x,p,q,y,z)-1)$.

Taking into account cases (d)–(g), we have

$\displaystyle
g_{(132,321)}(x,p,q,y,z)=x^{2}yp+\frac{x^{3}yzpq+x^{4}yzp^{2}q}{1-x^{2}yp^{2}}+$
(17)
$\displaystyle\frac{(x^{2}ypq+x^{3}yp^{q})^{2}zq}{(1-x^{2}yp^{2})^{2}}+x^{2}yp^{2}(G_{(132,321)}(x,p,q,y,z)-1).$

Solving equations (16) and (17) simultaneously, we obtain the desired result
(15). ∎

######  Corollary 2.6.

Setting three out of the four variables $y$, $z$, $p$ and $q$ equal to one
respectively in (15), we obtain single distributions of $\operatorname{asc}$,
$\operatorname{des}$, $\operatorname{MNA}$ and $\operatorname{MND}$ over
$S_{n}(132,321)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}p^{\operatorname{asc}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1+x-3px+x^{2}-2px^{2}+3p^{2}x^{2}+p^{2}x^{3}-p^{3}x^{3}}{(1-px)^{3}};$
(18) $\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}q^{\operatorname{des}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+x^{2}+qx^{2}}{(1-x)^{3}};$ (19)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}y^{\operatorname{MNA}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1+x+x^{2}-2x^{2}y+x^{3}y+x^{4}y+3x^{4}y^{2}+2x^{5}y^{2}}{(1-x^{2}y)^{3}};$
(20) $\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}z^{\operatorname{MND}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+x^{2}+x^{2}z}{(1-x)^{3}}.$ (21)

######  Theorem 2.7.

For $S_{n}(132,321)$, we have

$F_{(132,321)}(x,p,q,u,v,s,t)=\frac{A}{(1-ptx)(1-pux)(1-ptux)}$ (22)

where

$\displaystyle
A=1+stuvx+qs^{2}tuv^{2}x^{2}-p^{3}t^{2}u^{2}x^{3}+p^{2}tux^{2}(1+t+u+stuvx)-$
$\displaystyle px(u+st^{2}uvx(1+qsu(-1+v)x)+t(1+u+su^{2}vx).$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(132,321)$. If $n=0$, we get the term of
1 in $A_{(132,321)}(x,y,z)$. If $\pi\in S_{1}$, the corresponding g.f. is
$xuvst$. For $n\geq 2$, we consider the following cases.

  * •

If $\pi_{1}=n$ then $\pi=n12\cdots(n-1)$. The element $n$ is the only left-to-
right maximum, a left-to-right minimum and a right-to-left maximum, and
$\pi_{1}\pi_{2}$ is a descent. So $\operatorname{lrmax}(\pi)=1$ and the g.f.
of permutations with $\pi_{1}=n$ is given by

$xquvs\sum_{i\geq 2}x^{i-1}p^{i-2}vst^{i-1}=\frac{x^{2}quv^{2}s^{2}t}{1-xpt},$

where the element $n$ gives a factor of $xquvs$.

  * •

If $\pi_{n}=n$ then $\operatorname{rlmax}(\pi)=1$. Any non-empty permutation
in $S_{n-1}(132,321)$ is possible for $\pi_{1}\pi_{2}\cdots\pi_{n-1}$ and we
do not need to consider right-to-left maxima. So the g.f. in this case is

$xpuvt(F_{(132,321)}(x,p,q,u,1,s,t)-1).$

  * •

If $\pi_{k}=n$, $1<k<n$, then $\pi=(\alpha\oplus S_{1})\ominus\beta$, where
$\alpha\in S_{k-1}$ and $\beta\in S_{n-k}$ are two increasing (132,
321)-avoiding permutations. The g.f. for the permutation $\alpha\in S_{k-1}$
is

$\sum_{i\geq 1}x^{i}p^{i}u^{i}s=\frac{xpus}{1-xpu}$

(note that $\pi_{k-1}\pi_{k}$ is an ascent). The g.f. for
$S_{1}\ominus\beta\in S_{n-k+1}$ is

$xquv\sum_{i\geq 2}x^{i-1}p^{i-2}vst^{i-1}=\frac{x^{2}quv^{2}st}{1-xpt},$

where the element $n$ gives the factor of $xquv$. So the g.f. in this case is

$\frac{x^{3}pqu^{2}v^{2}s^{2}t}{(1-xpt)(1-xpu)}.$

Taking into account all the cases, we conclude that

$\displaystyle
F_{(132,321)}(x,p,q,u,v,s,t)=1+xtuvs+\frac{x^{2}quv^{2}s^{2}t}{1-xpt}+$ (23)
$\displaystyle\frac{x^{3}pqu^{2}v^{2}s^{2}t}{(1-xpt)(1-xpu)}+xpuvt(F_{(132,321)}(x,p,q,u,1,s,t)-1).$

Let $v=1$ in (23), we get

$\displaystyle
F_{(132,321)}(x,p,q,u,1,s,t)=1+xtus+\frac{x^{2}qus^{2}t}{1-xpt}+$ (24)
$\displaystyle\frac{xpusx^{2}qust}{(1-xpt)(1-xpu)}+xput(F_{(132,321)}(x,p,q,u,1,s,t)-1).$

By simultaneously solving (23) and (24), we obtain the desired result. ∎

######  Corollary 2.8.

Let $p=q=1$, then setting three out of the four variables $u$, $v$, $s$ and
$t$ equal to one individually in (22), we obtain single distributions of
$\operatorname{lrmax}$, $\operatorname{rlmax}$, $\operatorname{lrmin}$ and
$\operatorname{rlmin}$ over $S_{n}(132,321)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}u^{\operatorname{lrmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x-ux+2ux^{2}}{(1-x)(1-ux)^{2}};$ (25)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}v^{\operatorname{rlmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-3x+vx+3x^{2}-2vx^{2}+v^{2}x^{2}-x^{3}+2vx^{3}-v^{2}x^{3}}{(1-x)^{3}};$
(26) $\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}s^{\operatorname{lrmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-3x+sx+3x^{2}-2sx^{2}+s^{2}x^{2}-x^{3}+sx^{3}}{(1-x)^{3}};$
(27) $\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(132,321)}x^{n}t^{\operatorname{rlmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x-tx+2tx^{2}}{(1-x)(1-tx)^{2}}.$ (28)

###  2.3 Permutations in $S_{n}(231,312)$

We first describe the structure of a $(231,312)$-avoiding permutation. Let
$\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(231,312)$. If $\pi_{1}=n$ then
$\pi=n(n-1)\cdots 21$. If $\pi_{k}=n,1<k<n$, then
$\pi_{k+1}>\pi_{k+2}>\cdots>\pi_{n}$ in order to avoid 312. On the other hand,
in order to avoid 231, $\pi_{i}=n+k-i$ if $k+1\leq i\leq n$,
$\pi_{1}\pi_{2}\cdots\pi_{k-1}$ must be a permutation in $S_{k-1}(231,312)$.
If $\pi_{n}=n$, $\pi_{1}\pi_{2}\cdots\pi_{n-1}$ must be a permutation in
$S_{n-1}(231,312)$. Namely, for $\pi\in S_{n}(231,312)$, its structure is
$\pi=\alpha\oplus(S_{1}\ominus\beta)$, where $\alpha\in S_{k-1}(231,312)$ and
$S_{1}\ominus\beta\in S_{n-k+1}$ is a decreasing (231, 312)-avoiding
permutation. We use the structure of $\pi$ to prove the following theorems.

######  Theorem 2.9.

For $S_{n}(231,312)$, we have

$\displaystyle G_{(231,312)}(x,p,q,y,z)=$ (29)
$\displaystyle\frac{1+x+px^{2}y-p^{2}x^{2}y+qx^{2}z-q^{2}x^{2}z-pqx^{2}yz+pqx^{3}yz-p^{2}qx^{3}yz-
pq^{2}x^{3}yz}{1-p^{2}x^{2}y-q^{2}x^{2}z-pqx^{2}yz-p^{2}qx^{3}yz-
pq^{2}x^{3}yz}.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(231,312)$. If $n\leq 1$, we have the
term of $1+x$ in $G_{(231,312)}(x,p,q,y,z)$. For $n\geq 2$, the permutations
are divided into three classes depending on the position of $n$.

  * (a)

If $\pi_{1}=n$ then $\pi=n(n-1)\cdots 21$. When $n$ is even, $\pi$ has $n/2$
non-overlapping descents and $n-1$ descents. The corresponding g.f. is

$\sum_{i\geq 1}x^{2i}z^{i}q^{2i-1}=\frac{x^{2}zq}{1-x^{2}q^{2}z}.$

When $n$ is odd, $\pi$ has $(n-1)/2$ non-overlapping descents and $n-1$
descents. The corresponding g.f. is

$\sum_{i\geq 1}x^{2i+1}z^{i}q^{2i}=\frac{x^{3}zq^{2}}{1-x^{2}zq^{2}}.$

  * (b)

If $\pi_{n}=n$, we let the g.f. for these permutations be

$g_{(231,312)}(x,p,q,y,z):=\sum_{n\geq 2}\ \sum_{\begin{subarray}{c}\pi\in
S_{n}(132,321)\\\
\pi_{n}=n\end{subarray}}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}y^{\operatorname{MNA}(\pi)}z^{\operatorname{MND}(\pi)}.$

  * (c)

If $\pi_{k}=n$, $1<k<n$, then $\pi=\alpha\oplus(S_{1}\ominus\beta)$, where
$\alpha\in S_{k-1}(231,312)$ and $S_{1}\ominus\beta\in S_{n-k+1}$ is a
decreasing (231, 312)-avoiding permutation. For $\alpha\oplus S_{1}$, the g.f.
is $g_{(231,312)}(x,p,q,y,z)$. For $\beta\in S_{n-k+1}$, similarly to case
(a), we see that the corresponding g.f. is $(xzq+x^{2}zq^{2})/(1-x^{2}zq^{2})$
(note that $\pi_{k}\pi_{k+1}$ contributes to $\operatorname{MND}$).

Combining cases (a)–(c), we have

$\displaystyle
G_{(231,312)}(x,p,q,y,z)=1+x+\frac{x^{2}zq+x^{3}zq^{2}}{1-x^{2}zq^{2}}+$ (30)
$\displaystyle
g_{(231,312)}(x,p,q,y,z)\frac{xzq+x^{2}zq^{2}}{1-x^{2}zq^{2}}+g_{(231,312)}(x,p,q,y,z).$

Next we evaluate $g_{(231,312)}(x,p,q,y,z)$:

  * (d)

If $n=2$, the g.f. is $x^{2}yp$.

  * (e)

If $\pi_{1}=n-1$ then $\pi=(n-1)(n-2)\cdots 1n$, and the corresponding g.f. is

$xyp\frac{x^{2}zq+x^{3}zq^{2}}{1-x^{2}zq^{2}},$

where the element $n$ gives a factor of $xyp$.

  * (f)

If $\pi_{m}=n-1$, $1<m<n$, then $\pi=\gamma\oplus(S_{1}\ominus\zeta)\oplus
S_{1}$, where $\gamma\in S_{m-1}(231,312)$ and $\zeta\in S_{n-m-1}(231,312)$.
For $\gamma\oplus S_{1}$, the g.f. is $g_{(231,312)}(x,p,q,y,z)$. For
$\zeta\oplus S_{1}\in S_{n-m+1}$, because the structure is the same as in case
(b), we obtain the g.f. is $(xzq+x^{2}zq^{2})/(1-x^{2}zq^{2})$ (recall that if
$\zeta$ is of odd length, $\pi_{m}\pi_{m+1}$ will contribute to
$\operatorname{MND}$). To summarize, the g.f. in case (f) is

$xypg_{(231,312)}(x,p,q,y,z)\frac{xzq+x^{2}zq^{2}}{1-x^{2}zq^{2}},$

where the element $n$ gives the factor of $xyp$.

  * (g)

If $\pi_{n-1}=n-1$ then $\pi_{n-1}\pi_{n}=(n-1)n$ contributes to
$\operatorname{MNA}$, and it is independent from the count of MNA in
$\pi_{1}\cdots\pi_{n-2}$, which can be any permutation in $S_{n-2}(231,312)$.
So the corresponding g.f. in this case is
$x^{2}yp^{2}(G_{(231,312)}(x,p,q,y,z)-1)$.

Combining cases (d)–(g), we have

$\displaystyle
g_{(231,312)}(x,p,q,y,z)=x^{2}yp+xyp\frac{x^{2}zq+x^{3}zq^{2}}{1-x^{2}zq^{2}}+$
(31) $\displaystyle
xypg_{(231,312)}(x,p,q,y,z)\frac{xzq+x^{2}zq^{2}}{1-x^{2}zq^{2}}+x^{2}yp^{2}(G_{(231,312)}(x,p,q,y,z)-1).$

Solving the equations (30) and (31) simultaneously, we obtain (29). ∎

######  Corollary 2.10.

Setting three out of the four variables $y$, $z$, $p$ and $q$ equal to one
respectively in (29), we obtain single distributions of $\operatorname{asc}$,
$\operatorname{des}$, $\operatorname{MNA}$ and $\operatorname{MND}$ over
$S_{n}(231,312)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(231,312)}x^{n}p^{\operatorname{asc}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-px}{1-x-px};$ (32) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(231,312)}x^{n}q^{\operatorname{des}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-qx}{1-x-qx};$ (33) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(231,312)}x^{n}y^{\operatorname{MNA}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x^{2}y}{1-x-2x^{2}y};$ (34) $\displaystyle\sum_{n\geq
0}\ \sum_{\pi\in S_{n}(231,312)}x^{n}z^{\operatorname{MND}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1-x^{2}z}{1-x-2x^{2}z}.$ (35)

######  Theorem 2.11.

For $S_{n}(231,312)$, we have

$F_{(231,312)}(x,p,q,u,v,s,t)=\frac{A}{(1-qsx)(1-qx-ptux)(1-qvx)(1-qsvx)}$
(36)

where

$\displaystyle
A=1-ptux+stuvx+q^{4}s^{2}v^{2}x^{4}+q^{3}svx^{3}(-1-v+s(-1+v(-1+(-1+p)tux)))-$
$\displaystyle qx(1+v-ptuvx+s^{2}tuvx(1+ptu(-1+v)x)+s(1+v-ptux-(-1+p)tuvx+$
$\displaystyle
pt^{2}u^{2}vx^{2}+tuv^{2}x(1-ptux)))+q^{2}x^{2}(v+s^{2}v(1+tu(1-p+v)x)+$
$\displaystyle s(1+v^{2}(1-(-1+p)tux)+v(2-ptux))).$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(231,312)$. The case of $n=0$
contributes the term 1 to $A_{(231,312)}(x,y,z)$. If $\pi\in S_{1}$, the g.f.
is $xuvst$. For $n\geq 2$, we consider the following cases.

  * •

If $\pi_{1}=n$ then $\pi=n(n-1)\cdots 1$. The element $n$ is the only left-to-
right maximum, a left-to-right minimum and a right-to-left maximum, and
$\pi_{1}\pi_{2}$ is a descent. So $\operatorname{lrmax}(\pi)=1$ and the g.f.
of permutations with $\pi_{1}=n$ is given by

$xquvs\sum_{i\geq
2}x^{i-1}q^{i-2}v^{i-1}s^{i-1}t=\frac{x^{2}quv^{2}s^{2}t}{1-xqvs},$

where the element $n$ gives the factor of $xquvs$.

  * •

If $\pi_{n}=n$, then $\operatorname{rlmax}(\pi)=1$. Any non-empty permutation
in $S_{n-1}(231,312)$ is possible for $\pi_{1}\pi_{2}\cdots\pi_{n-1}$ and we
do not need to consider right-to-left maxima. So the g.f. is
$xpuvt(F_{(231,312)}(x,p,q,u,1,s,t)-1)$, where the element $n$ gives the
factor of $xpuvt$.

  * •

If $\pi_{k}=n$, $1<k<n$, then $\pi=\alpha\oplus(S_{1}\ominus\beta)$, where
$\alpha\in S_{k-1}(231,312)$ and $S_{1}\ominus\beta\in S_{n-k+1}$ is a
decreasing (231, 312)-avoiding permutation. For $\alpha\oplus S_{1}\in
S_{k-1}$, because we do not need to consider right-to-left maxima, the g.f. is
$xpquv(F_{(231,312)}(x,p,q,u,1,s,t)-1)$, where the element $n$ gives the
factor of $xpquv$. For $\beta$, we have

$\sum_{i\geq 1}x^{i}q^{i-1}v^{i}t=\frac{xvt}{1-xqv}.$

So the g.f. in this case is
$(F_{(231,312)}(x,p,q,u,1,s,t)-1)\frac{x^{2}pquv^{2}t}{1-xqv}$.

Taking into account all cases, we obtain

$\displaystyle
F_{(231,312)}(x,p,q,u,v,s,t)=1+xtuvs+\frac{x^{2}quv^{2}s^{2}t}{1-xqvs}+$ (37)
$\displaystyle(F_{(231,312)}(x,p,q,u,1,s,t)-1)\frac{x^{2}pquv^{2}t}{1-xqv}+xpuvt(F_{(231,312)}(x,p,q,u,1,s,t)-1).$

Let $v=1$ in (37), we obtain

$\displaystyle
F_{(231,312)}(x,p,q,u,1,s,t)=1+xtus+\frac{x^{2}qus^{2}t}{1-xqs}+$ (38)
$\displaystyle(F_{(231,312)}(x,p,q,u,1,s,t)-1)\frac{x^{2}pqut}{1-xq}+xput(F_{(231,312)}(x,p,q,u,1,s,t)-1).$

By simultaneously solving (37) and (38), we obtain the desired result. ∎

######  Corollary 2.12.

Let $p=q=1$, then setting three out of the four variables $u$, $v$, $s$ and
$t$ equal to one individually in (36), we obtain single distributions of
$\operatorname{lrmax}$, $\operatorname{rlmax}$, $\operatorname{lrmin}$ and
$\operatorname{rlmin}$ over $S_{n}(231,312)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(231,312)}x^{n}u^{\operatorname{lrmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-x-ux};$ (39) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(231,312)}x^{n}v^{\operatorname{rlmax}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1-2x+vx^{2}}{(1-2x)(1-vx)};$ (40)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(231,312)}x^{n}s^{\operatorname{lrmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+sx^{2}}{(1-2x)(1-sx)};$ (41)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(231,312)}x^{n}t^{\operatorname{rlmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-x-tx}.$ (42)

###  2.4 Permutations in $S_{n}(213,231)$

We first describe the structure of a $(213,231)$-avoiding permutation. Let
$\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(213,231)$. If $\pi_{1}=n$ then
$\pi=n(n-1)\cdots 21$. If $\pi_{k}=n,1<k<n$, then
$\pi_{1}<\pi_{2}<\cdots<\pi_{k-1}$ in order to avoid 213. On the other hand,
in order to avoid 231, $\pi_{i}>\pi_{k-1}$ if $k+1\leq i\leq n$. If
$\pi_{n}=n$ then $\pi=12\cdots n$. So, for $\pi\in S_{n}(213,231)$, its
structure is $\pi=\alpha\oplus(S_{1}\ominus\beta)$, where $\alpha\in S_{k-1}$
is an increasing (213, 231)-avoiding permutation and $S_{1}\ominus\beta\in
S_{n-k+1}(213,231)$, and we use the structure of $\pi$ to prove the following
theorems.

######  Theorem 2.13.

For $S_{n}(213,231)$, we have

$\displaystyle G_{(213,231)}(x,p,q,y,z)=$ (43)
$\displaystyle\frac{1+x+px^{2}y-p^{2}x^{2}y+qx^{2}z-q^{2}x^{2}z-pqx^{2}yz+pqx^{3}yz-p^{2}qx^{3}yz-
pq^{2}x^{3}yz}{1-p^{2}x^{2}y-q^{2}x^{2}z-pqx^{2}yz-p^{2}qx^{3}yz-
pq^{2}x^{3}yz}.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(213,231)$ . If $n\leq 1$ then
$G_{(213,231)}(x,p,q,y,z)=1+x$. For $n\geq 2$, the permutations are divided
into three classes depending on the position of $n$.

  * (a)

If $\pi_{1}=n$, we let the g.f. for these permutations be

$g_{(213,231)}(x,p,q,y,z):=\sum_{n\geq 2}\ \sum_{\begin{subarray}{c}\pi\in
S_{n}(213,231)\\\
\pi_{1}=n\end{subarray}}x^{n}p^{\operatorname{asc}(\pi)}q^{\operatorname{des}(\pi)}y^{\operatorname{MNA}(\pi)}z^{\operatorname{MND}(\pi)}.$

  * (b)

If $\pi_{n}=n$ then $\pi=12\cdots n$. When $n$ is even, $\pi$ has $n/2$ non-
overlapping ascents and $n-1$ ascents, and the corresponding g.f. is

$\sum_{i\geq 1}x^{2i}y^{i}p^{2i-1}=\frac{x^{2}yp}{1-x^{2}yp^{2}}.$

When $n$ is odd, $\pi$ has $(n-1)/2$ non-overlapping ascents and $n-1$
ascents, and the corresponding g.f. is

$\sum_{i\geq 1}x^{2i+1}y^{i}p^{2i}=\frac{x^{3}yp^{2}}{1-x^{2}yp^{2}}.$

  * (c)

If $\pi_{k}=n$, $1<k<n$, then $\pi=\alpha\oplus(S_{1}\ominus\beta)$, where
$\alpha\in S_{k-1}$ is an increasing (213, 231)-avoiding permutation and
$S_{1}\ominus\beta\in S_{n-k+1}(213,231)$, whose corresponding g.f. is
$g_{(213,231)}(x,p,q,y,z)$. For $\alpha\in S_{k-1}$, take into account that if
the increasing sequence is of odd length, $\pi_{k-1}\pi_{k}$ contributes to
$\operatorname{MNA}$ giving an extra factor of $y$. To summarize, in this case
the g.f. is

$g_{(213,231)}(x,p,q,y,z)\frac{xpy+x^{2}yp^{2}}{1-x^{2}p^{2}y}.$

Combining cases (a)–(c), we obtain

$\displaystyle G_{(213,231)}(x,p,q,y,z)=1+x+g_{(213,231)}(x,p,q,y,z)+$
$\displaystyle
g_{(213,231)}(x,p,q,y,z)\frac{xpy+x^{2}yp^{2}}{1-x^{2}p^{2}y}+\frac{x^{2}yp+x^{3}yp^{2}}{1-x^{2}p^{2}y}.$
(44)

Next, we evaluate $g_{(213,231)}(x,p,q,y,z)$:

  * (d)

If $n=2$, the g.f. is $x^{2}zq$.

  * (e)

If $\pi_{2}=n-1$ then any non-empty permutation in $S_{n}(213,231)$ is
possible for $\pi_{3}\cdots\pi_{n}$. The corresponding g.f. is
$x^{2}zq^{2}(G_{(213,231)}(x,p,q,y,z)-1)$, where $\pi_{1}\pi_{2}$ contributes
to $\operatorname{MND}$ giving an extra factor of
$x^{2}zq^{2}$($\pi_{2}>\pi_{3}$).

  * (f)

If $\pi_{n}=n-1$ then $\pi=S_{1}\ominus(\gamma\oplus S_{1})$, where
$\gamma\oplus S_{1}\in S_{n-1}$ is an increasing (213, 231)-avoiding
permutation. In this case, the corresponding g.f. is

$\frac{x^{3}yzpq+x^{4}yzp^{2}q}{1-x^{2}p^{2}y}.$

  * (g)

If $\pi_{m}=n-1$, $2<m<n$, then
$\pi=S_{1}\ominus(\gamma\oplus(S_{1}\ominus\zeta))$, where $\gamma\in S_{m-2}$
is an increasing (213, 231)-avoiding permutation and $S_{1}\ominus\zeta\in
S_{n-m+1}(213,231)$, whose corresponding g.f. is $g_{(213,231)}(x,p,q,y,z)$.
For $S_{1}\ominus\gamma\in S_{m-1}$, note that if $\gamma$ contains an odd
number of elements, $\pi_{m-1}\pi_{m}$ contributes to $\operatorname{MNA}$. To
summarize, in this case the g.f. is

$g_{(213,231)}(x,p,q,y,z)\frac{x^{2}yzpq+x^{3}yzp^{2}q}{1-x^{2}p^{2}y},$

where the element $n$ gives a factor of $xzq$.

Combining cases (d)–(g), we obtain

$\displaystyle
g_{(213,231)}(x,p,q,y,z)=x^{2}zq+x^{2}zq^{2}(G_{(213,231)}(x,p,q,y,z)-1)+$
$\displaystyle\frac{x^{3}yzpq+x^{4}yzp^{2}q}{1-x^{2}p^{2}y}+g_{(213,231)}(x,p,q,y,z)\frac{x^{2}yzpq+x^{3}yzp^{2}q}{1-x^{2}p^{2}y}.$
(45)

Solving equations (2.4) and (2.4) simultaneously, we obtain (43). ∎

From Theorem 2.13 we have the following results.

######  Corollary 2.14.

Setting three out of the four variables $y$, $z$, $p$ and $q$ equal to one
respectively in (43), we obtain single distributions of $\operatorname{asc}$,
$\operatorname{des}$, $\operatorname{MNA}$ and $\operatorname{MND}$ over
$S_{n}(213,231)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,231)}x^{n}p^{\operatorname{asc}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-px}{1-x-px};$ (46) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(213,231)}x^{n}q^{\operatorname{des}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-qx}{1-x-qx};$ (47) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(213,231)}x^{n}y^{\operatorname{MNA}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x^{2}y}{1-x-2x^{2}y};$ (48) $\displaystyle\sum_{n\geq
0}\ \sum_{\pi\in S_{n}(213,231)}x^{n}z^{\operatorname{MND}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1-x^{2}z}{1-x-2x^{2}z}.$ (49)

######  Theorem 2.15.

For $S_{n}(213,231)$, we have

$F_{(213,231)}(x,p,q,u,v,s,t)=\frac{A}{(1-ptux)(1-ptx-qvx)(1-qsvx)}$ (50)

where $A$ is given by

$\displaystyle 1-ptx-ptux-qvx-
qsvx+stuvx+p^{2}t^{2}ux^{2}+pqstvx^{2}+pqtuvx^{2}+pqstuvx^{2}-pst^{2}uvx^{2}+$
$\displaystyle
q^{2}sv^{2}x^{2}-qstuv^{2}x^{2}-p^{2}qst^{2}uvx^{3}-pq^{2}stuv^{2}x^{3}+pqs^{2}t^{2}uv^{2}x^{3}+pqst^{2}u^{2}v^{2}x^{3}-pqs^{2}t^{2}u^{2}v^{2}x^{3}.$

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(213,231)$. If $n=0$, $\pi$ contributes
the term of 1 to $A_{(213,231)}(x,y,z)$. If $\pi\in S_{1}$, the g.f. is
$xuvst$. For $n\geq 2$, we consider the following cases.

  * •

If $\pi_{1}=n$ then the element $n$ is the only left-to-right maximum, a left-
to-right minimum and a right-to-left maximum, and $\pi_{1}\pi_{2}$ is a
descent. So $\operatorname{lrmax}(\pi)=1$ and the g.f. of permutations with
$\pi_{1}=n$ is given by $xquvs(F_{(213,231)}(x,p,q,1,v,s,t)-1)$, where we used
the g.f. of all non-empty permutations with the value of
$\operatorname{lrmax}$ not taken into account and the element $n$ gives the
factor of $xquvs$.

  * •

If $\pi_{n}=n$ then $\pi=12\cdots n$. So we have

$xpuvt\sum_{i\geq
1}x^{i}p^{i-1}u^{i}st^{i}=\frac{x^{2}pu^{2}vst^{2}}{1-xput},$

where the element $n$ gives the factor of $xpuvt$.

  * •

If $\pi_{k}=n,1<k<n$, then $\pi=\alpha\oplus(S_{1}\ominus\beta)$, where
$\alpha$ is an increasing permutation in $S_{k-1}(213,231)$ and
$S_{1}\ominus\beta\in S_{n-k+1}(213,231)$. The g.f. for $\alpha\in S_{k-1}$ is
$\frac{xust}{1-xput}$ and the element $n$ gives a factor of $xpquv$. For the
permutation $\beta\in S_{n-k}$, we do not need to consider left-to-right
maxima and left-to-right minima, so the g.f. is
$(F_{(213,231)}(x,p,q,1,v,1,t)-1)$. The g.f. of permutations with
$\pi_{k}=n,1<k<n$, is

$(F_{(213,231)}(x,p,q,1,v,1,t)-1)\frac{x^{2}pqu^{2}vst}{1-xput}.$

Taking into account all cases, we obtain

$\displaystyle
F_{(213,231)}(x,p,q,u,v,s,t)=1+xtuvs+xquvs(F_{(213,231)}(x,p,q,1,v,s,t)-1)+$
$\displaystyle(F_{(213,231)}(x,p,q,1,v,1,t)-1)\frac{x^{2}pqu^{2}vst}{1-xput}+\frac{x^{2}pu^{2}vst^{2}}{1-xput};$
(51)

If $u=1$ in (2.4), we have

$\displaystyle
F_{(213,231)}(x,p,q,1,v,s,t)=1+xtvs+xqvs(F_{(213,231)}(x,p,q,1,v,s,t)-1)+$
$\displaystyle(F_{(213,231)}(x,p,q,1,v,1,t)-1)\frac{x^{2}pqvst}{1-xpt}+\frac{x^{2}pvst^{2}}{1-xpt};$
(52)

If $s=1$ in (2.4), we have

$\displaystyle
F_{(213,231)}(x,p,q,1,v,1,t)=1+xtv+xqv(F_{(213,231)}(x,p,q,1,v,1,t)-1)+$
$\displaystyle(F_{(213,231)}(x,p,q,1,v,1,t)-1)\frac{x^{2}pqvt}{1-xpt}+\frac{x^{2}pvt^{2}}{1-xpt}.$
(53)

By simultaneously solving (2.4),(2.4) and (2.4), we obtain the desired result.
∎

######  Corollary 2.16.

Let $p=q=1$, then setting three out of the four variables $u$, $v$, $s$ and
$t$ equal to one individually in (50), we obtain single distributions of
$\operatorname{lrmax}$, $\operatorname{rlmax}$, $\operatorname{lrmin}$ and
$\operatorname{rlmin}$ over $S_{n}(213,231)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,231)}x^{n}u^{\operatorname{lrmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+ux^{2}}{(1-2x)(1-ux)};$ (54)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,231)}x^{n}v^{\operatorname{rlmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-x-vx};$ (55) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(213,231)}x^{n}s^{\operatorname{lrmin}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1-2x+sx^{2}}{(1-2x)(1-sx)};$ (56)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,231)}x^{n}t^{\operatorname{rlmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-x-tx}.$ (57)

###  2.5 Permutations in $S_{n}(213,312)$

We first describe the structure of a $(213,312)$-avoiding permutation. Let
$\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(213,312)$. If $\pi_{i}=n$ then
$\pi_{1}<\pi_{2}<\cdots<\pi_{i-1}$ in order to avoid 213. On the other hand,
in order to avoid 312, $\pi_{i+1}>\pi_{i+2}>\cdots>\pi_{n}$. We use the
structure of $\pi$ to prove the following theorems.

######  Theorem 2.17.

For $S_{n}(213,312)$, we have

$G_{(213,312)}(x,p,q,y,z)=\frac{A}{p^{4}x^{4}y^{2}+(-1+q^{2}x^{2}z)^{2}-2p^{2}x^{2}y(1+q^{2}x^{2}z)},$
(58)

where
$A=(1-p^{3}x^{3}y^{2}+qxz-q^{2}x^{2}z-q^{3}x^{3}z^{2}+p^{2}x^{2}y(-1+qxz)+pxy(1+2qxz+q^{2}x^{2}z))$.

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(213,312)$. If $\pi_{i}=n$ then
$\pi_{1}<\pi_{2}<\cdots<\pi_{i-1}$ in order to avoid 213. On the other hand,
in order to avoid 312, $\pi_{i+1}>\pi_{i+2}>\cdots>\pi_{n}$.

Next, we consider the following cases based on the parity of $i$. If $i=2k$,
$k\geq 1$, we obtain $\binom{n-1}{2k-1}$ permutations with $k$ non-overlapping
ascents and $\lfloor\frac{n-2k+1}{2}\rfloor$ non-overlapping descents. If
$i=2k+1,k\geq 0$, we obtain $\binom{n-1}{2k}$ permutations with $k$ non-
overlapping ascents and $\lfloor\frac{n-2k}{2}\rfloor$ non-overlapping
descents. So we have

$\displaystyle
G_{(213,312)}(x,p,q,y,z)=1+\sum_{n=1}^{\infty}{\sum_{k=1}^{\lfloor
n/2\rfloor}\binom{n-1}{2k-1}x^{n}y^{k}z^{\lfloor\frac{n-2k+1}{2}\rfloor}p^{2k-1}q^{n-2k}}+$
$\displaystyle\sum_{n=1}^{\infty}{\sum_{k=0}^{\lfloor(n+1)/2\rfloor}\binom{n-1}{2k}x^{n}y^{k}z^{\lfloor\frac{n-2k}{2}\rfloor}p^{2k}q^{n-2k-1}}.$

By using MATHEMATICA, we simplify $G_{(213,312)}(x,p,q,y,z)$ and obtain (58).
∎

######  Corollary 2.18.

Setting three out of the four variables $y$, $z$, $p$ and $q$ equal to one
respectively in (58), we obtain single distributions of $\operatorname{asc}$,
$\operatorname{des}$, $\operatorname{MNA}$ and $\operatorname{MND}$ over
$S_{n}(213,312)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,312)}x^{n}p^{\operatorname{asc}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-px}{1-x-px};$ (59) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(213,312)}x^{n}q^{\operatorname{des}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-qx}{1-x-qx};$ (60) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(213,312)}x^{n}y^{\operatorname{MNA}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{x-x^{2}+x^{2}y}{1-2x+x^{2}-x^{2}y};$ (61)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,312)}x^{n}z^{\operatorname{MND}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{x-x^{2}+x^{2}z}{1-2x+x^{2}-x^{2}z}.$ (62)

######  Theorem 2.19.

For $S_{n}(213,312)$, we have

$\displaystyle
F_{(213,312)}(x,p,q,u,v,s,t)=1+xuvst+\frac{pqst^{2}u^{2}v^{2}x^{3}}{(-1+ptux)(-1+pux+qvx)}+$
$\displaystyle\frac{qs^{2}tuv^{2}x^{2}}{1-qsvx}+\frac{pst^{2}u^{2}vx^{2}}{1-ptux}+\frac{pqs^{2}tu^{2}v^{2}x^{3}}{(-1+pux+qvx)(-1+qsvx)}.$
(63)

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}(213,312)$. If $n=0$, we have the term
of 1 in $F_{(213,312)}(x,p,q,u,v,s,t)$. If $\pi\in S_{1}$, the g.f. is
$xuvst$. For $n\geq 2$, suppose that $\pi_{1}=i$, $\pi_{k}=n$ and $\pi_{n}=j$.
We consider the following cases.

If $i=n$, namely $k=1$, then we have

$F_{(213,312)}(x,p,q,u,v,s,t)=\sum_{n=2}^{\infty}x^{n}q^{n-1}uv^{n}s^{n}t.$

If $j=n$, namely $k=n$, then we have

$F_{(213,312)}(x,p,q,u,v,s,t)=\sum_{n=2}^{\infty}x^{n}p^{n-1}u^{n}vst^{n}.$

Next, let $2\leq i,j,k\leq n-1$. If $\pi_{1}=1$, in order to avoid 312, there
are $\binom{n-j-1}{n-k-1}$ permutations whose g.f. is
$x^{n}p^{k-1}q^{n-k}u^{k}v^{n-k+1}st^{j}$, so the g.f. in this case is

$\sum_{n=2}^{\infty}{\sum_{j=2}^{n-1}{\sum_{k=j}^{n-1}\binom{n-j-1}{n-k-1}x^{n}p^{k-1}q^{n-k}u^{k}v^{n-k+1}st^{j}}}.$

If $\pi_{1}\neq 1$, in order to avoid 213, there are $\binom{n-i-1}{k-2}$
permutations whose g.f. is $x^{n}p^{k-1}q^{n-k}u^{k}v^{n-k+1}s^{i}t$, so the
g.f. in this case is

$\sum_{n=2}^{\infty}{\sum_{i=2}^{n-1}{\sum_{k=2}^{n+1-i}\binom{n-i-1}{k-2}x^{n}p^{k-1}q^{n-k}u^{k}v^{n-k+1}s^{i}t}}.$

In conclusion,

$\displaystyle
F_{(213,312)}(x,p,q,u,v,s,t)=1+xtuvs+\sum_{n=2}^{\infty}x^{n}q^{n-1}uv^{n}s^{n}t+\sum_{n=2}^{\infty}x^{n}p^{n-1}u^{n}vst^{n}+$
$\displaystyle\sum_{n=2}^{\infty}{\sum_{j=2}^{n-1}{\sum_{k=j}^{n-1}\binom{n-j-1}{n-k-1}x^{n}p^{k-1}q^{n-k}u^{k}v^{n-k+1}st^{j}}}+$
$\displaystyle\sum_{n=2}^{\infty}{\sum_{i=2}^{n-1}{\sum_{k=2}^{n+1-i}\binom{n-i-1}{k-2}x^{n}p^{k-1}q^{n-k}u^{k}v^{n-k+1}s^{i}t}}$

By using MATHEMATICA, we simplify $F_{(213,312)}(x,p,q,u,v,s,t)$ and obtain
(2.19). ∎

######  Corollary 2.20.

Let $p=q=1$, then setting three out of the four variables $u$, $v$, $s$ and
$t$ equal to one individually in (2.19), we obtain single distributions of
$\operatorname{lrmax}$, $\operatorname{rlmax}$, $\operatorname{lrmin}$ and
$\operatorname{rlmin}$ over $S_{n}(213,312)$:

$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,312)}x^{n}u^{\operatorname{lrmax}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-x}{1-x-ux};$ (64) $\displaystyle\sum_{n\geq 0}\
\sum_{\pi\in S_{n}(213,312)}x^{n}v^{\operatorname{rlmax}(\pi)}$
$\displaystyle=$ $\displaystyle\frac{1-x}{1-x-vx};$ (65)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,312)}x^{n}s^{\operatorname{lrmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+sx^{2}}{(1-2x)(1-sx)};$ (66)
$\displaystyle\sum_{n\geq 0}\ \sum_{\pi\in
S_{n}(213,312)}x^{n}t^{\operatorname{rlmin}(\pi)}$ $\displaystyle=$
$\displaystyle\frac{1-2x+tx^{2}}{(1-2x)(1-tx)}.$ (67)

##  3 Equidistribution results

From Theorems 2.9, 2.13 and 2.17, swapping the variables $p$ and $q$, and $y$
and $z$ in the respective formulas, we obtain algebraic proofs of the
following equidistribution results.

######  Theorem 3.1.

The quadratuples of statistics
$(\operatorname{asc},\operatorname{des},\operatorname{MNA},\operatorname{MND})$
and
$(\operatorname{des},\operatorname{asc},\operatorname{MND},\operatorname{MNA})$
are equidistributed on $S_{n}(231,312)$ for all $n\geq 0$.

######  Theorem 3.2.

The quadratuples of statistics
$(\operatorname{asc},\operatorname{des},\operatorname{MNA},\operatorname{MND})$
and
$(\operatorname{des},\operatorname{asc},\operatorname{MND},\operatorname{MNA})$
are equidistributed on $S_{n}(213,231)$ for all $n\geq 0$.

######  Theorem 3.3.

The quadratuples of statistics
$(\operatorname{asc},\operatorname{des},\operatorname{MNA},\operatorname{MND})$
and
$(\operatorname{des},\operatorname{asc},\operatorname{MND},\operatorname{MNA})$
are equidistributed on $S_{n}(213,312)$ for all $n\geq 0$.

######  Theorem 3.4.

The quadratuple of statistics
$(\operatorname{asc},\operatorname{des},\operatorname{MNA},\operatorname{MND})$
on $S_{n}(231,312)$ has the same distribution as
$(\operatorname{des},\operatorname{asc},\operatorname{MND},\operatorname{MNA})$
on $S_{n}(213,231)$.

######  Theorem 3.5.

The quadratuple of statistics
$(\operatorname{asc},\operatorname{des},\operatorname{MNA},\operatorname{MND})$
is equidistributed on $S_{n}(231,312)$ and $S_{n}(213,231)$.

In this section we provide combinatorial proofs of the five theorems. The
combinatorial proofs of Theorems 3.2 and 3.3 are trivial: in Theorem 3.2 we
can apply the complement operation to permutations in $S_{n}(213,231)$, and in
Theorem 3.3 we can apply the reverse operation to permutations in
$S_{n}(213,312)$.

Combinatorial proofs of Theorems 3.1, 3.4 and 3.5 are much more involved and
they require introduction of two bijective maps $f$ and $g$ in Sections 3.1
and 3.2, respectively. The map $f$, to be introduced next, is shown by us in
Lemma 3.6 to be an involution.

###  3.1 Map $f$ and its applications

One can see that the structure of a permutation $\pi\in S_{n}(231,312)$,
$n\geq 1$, is $\pi=\pi^{\prime}\oplus\pi^{\prime\prime}$ where $\pi^{\prime}$
and $\pi^{\prime\prime}$ are $(231,312)$-avoiding permutations and
$\pi^{\prime\prime}$ is non-empty and decreasing. The map
$f:S_{n}(231,312)\rightarrow S_{n}(231,312)$ is defined recursively as
follows. As the base case, for all $n\geq 1$, $f(n(n-1)\cdots 1)=12\cdots n$.
Now, if $\pi=\pi^{\prime}\oplus\pi^{\prime\prime}$ as above and
$f(\pi^{\prime})=A_{1}aA_{2}$, with $a$ being the maximum element and
$A_{1}A_{2}\in S_{a-1}(231,312)$ then

$f(\pi)=A_{1}(a+1)aA_{2}(a+2)(a+3)\cdots n.$ (68)

Note that, to avoid the patterns 231 and 312, $aA_{2}=a(a-1)\cdots(a-k)$ for
$k\geq 0$. For example,

$f(124358769(14)(13)(12)(11)(10))=3216547(10)98(11)(12)(13)(14).$ (69)

######  Lemma 3.6.

The map $f$ is an involution, i.e. $f^{2}(\pi)=\pi$ for any $\pi\in
S_{n}(231,312)$ and $n\geq 1$.

###### Proof.

We prove the lemma by establishing an alternative description of $f$. For
$\pi\in S_{n}(231,312)$ line the elements in $\\{1,2,\ldots n\\}$ in a row and
insert a vertical line between element $a$ and $a+1$ if $\pi$ can be written
as $\pi=\pi^{\prime}\oplus\pi^{\prime\prime}$ so that $x\in\pi^{\prime}$ and
$x+1$ corresponds to 1 in $\pi^{\prime\prime}$. For example, for $\pi$ in
(69), we have

$1|2|34|5|678|9|(10)(11)(12)(13)(14).$

Clearly, this way to represent permutations in $S_{n}(231,312)$ by the
increasing permutation $12\cdots n$ with vertical lines inserted between some
of the elements is a bijection. Using the definition of $f$, it is not
difficult to see that $f$ can be described on the representations of
permutations by replacing $x(x+1)$ with $x|(x+1)$ and $x|(x+1)$ by $x(x+1)$
for all $x\in\\{1,2,\ldots,n-1\\}$, that is, by removing the existent vertical
lines and inserting new vertical lines in all other places. For the
permutation $\pi$ above we have

$123|456|7|89(10)|(11)|(12)|(13)|(14).$

which is consistent with (69). ∎

######  Remark 3.7.

Using the alternative description of $f$ introduced in Lemma 3.6 we see that
$f$ has no fixed points (the vertical lines cannot be on the same place after
application of $f$).

######  Lemma 3.8.

The map $f:S_{n}(231,312)\rightarrow S_{n}(231,312)$ is an automorphism.

###### Proof.

We only need to show that $f$ is injective. Suppose that $f(\pi)=f(\sigma)$
for $\pi\neq\sigma$. Using Lemma 3.6,

$\pi=f^{2}(\pi)=f(f(\pi))=f(f(\sigma))=f^{2}(\sigma)=\sigma$

which is a contradiction. So, $f$ is injective. ∎

######  Lemma 3.9.

Suppose $\pi=A\oplus B\in S_{n}(231,312)$ where $A$ is any
$(231,312)$-avoiding permutation, and $B$ is a decreasing permutation of
length at least $2$. Then, $f(\pi)=D\oplus 1$ for $D\in S_{n-1}(231,312)$,
that is, $f(\pi)$ ends with $n$.

###### Proof.

The claim follows immediately from the definition of $f$ in (68). ∎

######  Lemma 3.10.

Suppose $\pi=A\oplus B\oplus C\in S_{n}(231,312)$ where $A$ is any
$(231,312)$-avoiding permutation, $B$ is a decreasing permutation of length at
least $2$, and $C$ is a non-empty increasing permutation. Then,
$f(\pi)=D\oplus F$ where $F$ is an decreasing permutation of length one more
than the length of $C$.

###### Proof.

We prove the statement by induction on the length of $C$. For $A\oplus B\oplus
1$ the statement is true, because by definition of $f$ we first need to
compute $f(A\oplus B)$ which, by Lemma 3.9, ends with $n-1$, and hence
$f(A\oplus B\oplus 1)=D\oplus 21$. Suppose the statement is true for length
$k\geq 1$ of $C$ and $C$ is now of length $k+1$. Then, computing $f(A\oplus
B\oplus C)$ is done by first computing $E=f(A\oplus B\oplus C^{\prime})$ where
$C^{\prime}$ is an increasing permutation of length $k$. By the induction
hypothesis, $E$ ends with $(n-1)(n-2)\cdots(n-k-1)$ and using the definition
of $f$, $f(A\oplus B\oplus C)$ ends with $n(n-1)\cdots(n-k-1)$, a decreasing
permutation of length $k+2$. ∎

For our example (69), $\operatorname{asc}(\pi)=\operatorname{des}(f(\pi))=6$,
$\operatorname{des}(\pi)=\operatorname{asc}(f(\pi))=7$,
$\operatorname{MNA}(\pi)=\operatorname{MND}(f(\pi))=3$, and
$\operatorname{MND}(\pi)=\operatorname{MNA}(f(\pi))=4$. The notable reltions
between $\operatorname{asc}$, $\operatorname{des}$, $\operatorname{MNA}$ and
$\operatorname{MND}$ in $\pi$ and $f(\pi)$ are not a coincidence as is shown
in the following theorem. Note that the set of statistics in Theorem 3.1
cannot be extended by adding more statistics considered in this paper because
in (69), $\operatorname{lrmax}(\pi)=7$, $\operatorname{lrmax}(f(\pi))=8$,
$\operatorname{lrmin}(\pi)=1$, $\operatorname{lrmin}(f(\pi))=3$,
$\operatorname{rlmax}(\pi)=5$, $\operatorname{rlmax}(f(\pi))=1$,
$\operatorname{rlmin}(\pi)=7$ and $\operatorname{rlmin}(f(\pi))=8$.

Next, we prove Theorem 3.1.

###### Proof.

The equidistribution of the quadratuples can be established by induction using
the automorphism $f$ as follows. For the base case in the definitioin of $f$,
we have

$\displaystyle\operatorname{asc}(n(n-1)\cdots 1)=\operatorname{des}(12\cdots
n),\ \operatorname{des}(n(n-1)\cdots 1)=\operatorname{asc}(12\cdots n),$
$\displaystyle\operatorname{MNA}(n(n-1)\cdots 1)=\operatorname{MND}(12\cdots
n)\mbox{ and }\operatorname{MND}(n(n-1)\cdots 1)=\operatorname{MNA}(12\cdots
n).$

Now, suppose that $\pi\in S_{n}(231,312)$ and
$\pi=\pi^{\prime}\oplus\pi^{\prime\prime}$ where $\pi^{\prime}\in
S_{a}(231,312)$ and $\pi^{\prime\prime}$ is a decreasing permutation. Then,
referring to the definition of $f$, where $a,A_{1},A_{2}$ are introduced, we
have the following derivations.

$\displaystyle\operatorname{asc}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{asc}(\pi^{\prime})+\operatorname{asc}(\pi^{\prime\prime})+1\mbox{
\ \ \ \ (``+1'' is given by the ascent between $\pi^{\prime}$ and
$\pi^{\prime\prime}$)}$ $\displaystyle=$
$\displaystyle\operatorname{des}(f(\pi^{\prime}))+\operatorname{des}(f(\pi^{\prime\prime}))+1\mbox{\
\ \ \ (by the induction hypothesis)}$ $\displaystyle=$
$\displaystyle\operatorname{des}(A_{1})+\operatorname{des}(aA_{2})+1\mbox{\ \
\ \ (``+1'' is given by $(a+1)a$ in (\ref{def-f-pi}))}$ $\displaystyle=$
$\displaystyle\operatorname{des}(f(\pi)).$
$\displaystyle\operatorname{des}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{des}(\pi^{\prime})+\operatorname{des}(\pi^{\prime\prime})$
$\displaystyle=$
$\displaystyle\operatorname{asc}(f(\pi^{\prime}))+\operatorname{asc}(f(\pi^{\prime\prime}))\mbox{\
\ \ \ (by the induction hypothesis)}$ $\displaystyle=$
$\displaystyle\operatorname{asc}(A_{1}a)+\operatorname{asc}(A_{2})+\operatorname{asc}(12\cdots(n-a))\mbox{\
\ \ \ (here $\operatorname{asc}(A_{2})=0$)}$ $\displaystyle=$
$\displaystyle\operatorname{asc}(A_{1}(a+1))+\operatorname{asc}(12\cdots(n-a))\mbox{\
\ \ ($f(\pi)$ ends with the pattern $12\cdots(n-a)$)}$ $\displaystyle=$
$\displaystyle\operatorname{asc}(f(\pi)).$

Replacing $\operatorname{des}$ and $\operatorname{asc}$ by
$\operatorname{MND}$ and $\operatorname{MNA}$, respectively, in the
derivations for $\operatorname{des}(\pi)$, we see that
$\operatorname{MND}(\pi)=\operatorname{MNA}(f(\pi))$. Finally, for
$\operatorname{MNA}$ we distinguish two cases for $\pi^{\prime}$:

  * •

$\pi^{\prime}=12\cdots a$ so that $\pi=12\cdots an(n-1)\cdots(a+1)$,
$f(\pi^{\prime})=a(a-1)\cdots 1$ and $f(\pi)=(a+1)a\cdots 1(a+2)(a+3)\cdots
n$. It is straightforward to verify that
$\operatorname{MNA}(\pi)=\operatorname{MND}(f(\pi))$ and
$\operatorname{MND}(\pi)=\operatorname{MNA}(f(\pi))$.

  * •

$\pi^{\prime}=A\oplus B\oplus C\in S_{a}(231,312)$ where $A$, $B$ and $C$ are
defined as in Lemma 3.10 and the length of $C$ is $i$. So, $\pi=A\oplus
B\oplus 12\cdots i\oplus(n-a)(n-a-1)\cdots 1$ and, by Lemma 3.10 where $D$
(and $E=(i+1)i\cdots 1$) is introduced,
$f(\pi)=D(a+1)a\cdots(a-i)(a+2)(a+3)\cdots n$.

    * –

If $i$ is odd.

$\displaystyle\operatorname{MNA}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{MNA}(\pi^{\prime})\mbox{ \ \ \ \ (the ascent $an$
in $\pi$ does not contribute to $\operatorname{MNA}$)}$ $\displaystyle=$
$\displaystyle\operatorname{MND}(f(\pi^{\prime}))\mbox{\ \ \ \ (by the
induction hypothesis)}$ $\displaystyle=$
$\displaystyle\operatorname{MND}(f(\pi))\mbox{\ \ \ \ ($a+1$ does not
contribute to $\operatorname{MND}$ since $i+1$ is even).}$

    * –

If $i$ is even.

$\displaystyle\operatorname{MNA}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{MNA}(\pi^{\prime})+1\mbox{ \ \ (considering min
element in $B$, ``+1'' is given by $an$)}$ $\displaystyle=$
$\displaystyle\operatorname{MND}(f(\pi^{\prime}))+1\mbox{\ \ \ \ (by the
induction hypothesis)}$ $\displaystyle=$
$\displaystyle\operatorname{MND}(f(\pi))\mbox{\ \ ($a+1$ contributes to
$\operatorname{MND}$ since $i+1$ is odd).}$

The theorem is proved. ∎

###  3.2 Map $g$ and its applications

Recall that the structure of a permutation $\sigma\in S_{n}(213,231)$ is
$\sigma=\sigma^{\prime}\oplus(1\ominus\sigma^{\prime\prime})$ where
$\sigma^{\prime}$ and $\sigma^{\prime\prime}$ are $(213,231)$-avoiding
permutations and $\sigma^{\prime}$ is increasing. Also, the structure of a
permutation $\pi\in S_{n}(231,312)$ is
$\pi=\pi^{\prime}\oplus(1\ominus\pi^{\prime\prime})$ where $\pi^{\prime}$ and
$\pi^{\prime\prime}$ are (possibly empty) $(231,312)$-avoiding permutations
and $\pi^{\prime\prime}$ is decreasing. The map $g:S_{n}(231,312)\rightarrow
S_{n}(213,231)$ is defined recursively as follows. As the base case,
$f(\varepsilon)=\varepsilon$. Now, if
$\pi=\pi^{\prime}\oplus(1\ominus\pi^{\prime\prime})$ as above then

$g(\pi)=\sigma^{\prime}\oplus(1\ominus g(\pi^{\prime}))$

where $\sigma^{\prime}$ is the increasing permutation of the same length as
$\pi^{\prime\prime}$. For example, for the same permutation as in (69), we
have

$g(124358769(14)(13)(12)(11)(10))=1234(14)(13)56(12)(11)7(10)98.$ (70)

######  Lemma 3.11.

The map $g$ is a bijection.

###### Proof.

Since the sets $S_{n}(231,312)$ and $S_{n}(213,231)$ have each $2^{n-1}$
elements [5], it is sufficient to prove that $g$ is injective. We proceed by
induction on the length of permutations with the trivial base case $n=1$.

Suppose $\pi,\delta\in S_{n}(231,312)$ and $\pi\neq\delta$. Moreover, let

$\displaystyle\pi=\pi^{\prime}\oplus(1\ominus\pi^{\prime\prime})$
$\displaystyle g(\pi)=\sigma^{\prime}\oplus(1\ominus g(\pi^{\prime}))$
$\displaystyle\delta=\delta^{\prime}\oplus(1\ominus\delta^{\prime\prime})$
$\displaystyle g(\delta)=\sigma^{\prime\prime}\oplus(1\ominus
g(\delta^{\prime}))$

where $\pi^{\prime\prime}$ and $\delta^{\prime\prime}$ are decreasing of the
same length, and $\sigma^{\prime}$ and $\sigma^{\prime\prime}$ are increasing
of the same length. Clearly, either $\pi^{\prime}\neq\delta^{\prime}$ or
$\pi^{\prime\prime}\neq\delta^{\prime\prime}$.

If $\pi^{\prime\prime}\neq\delta^{\prime\prime}$ then
$\sigma^{\prime}\neq\sigma^{\prime\prime}$ and $g(\pi)\neq g(\delta)$. On the
other hand, if $\pi^{\prime}\neq\delta^{\prime}$ then, by the induction
hypothesis, $g(\pi^{\prime})\neq g(\delta^{\prime})$ and so $g(\pi)\neq
g(\delta)$. We are done. ∎

######  Remark 3.12.

We note that $g$ has a single fixed point for each odd $n$ and no fixed points
for any even $n$. Indeed, a fixed point must avoid the patterns $213$, $231$
and $312$, and hence $\pi=12\cdots in(n-1)\cdots(i+1)$ for $i\geq 0$ and
$g(\pi)=12\cdots(n-i-1)n(n-1)\cdots(n-i)$. Since $\pi=g(\pi)$ we have that
$i=\frac{n-1}{2}$ and the observation follows.

For our example (70), $\operatorname{asc}(\pi)=\operatorname{des}(g(\pi))=6$,
$\operatorname{des}(\pi)=\operatorname{asc}(g(\pi))=7$,
$\operatorname{MNA}(\pi)=\operatorname{MND}(g(\pi))=3$, and
$\operatorname{MND}(\pi)=\operatorname{MNA}(g(\pi))=4$. The notable reltions
between $\operatorname{asc}$, $\operatorname{des}$, $\operatorname{MNA}$ and
$\operatorname{MND}$ in $\pi$ and $g(\pi)$ are not a coincidence as is shown
in the following theorem. Note that the set of statistics in Theorem 3.4
cannot be extended by adding more statistics considered in this paper because
in (70), $\operatorname{lrmax}(\pi)=\operatorname{lrmax}(f(\pi))=7$,
$\operatorname{lrmin}(\pi)=\operatorname{lrmin}(f(\pi))=1$,
$\operatorname{rlmax}(\pi)=\operatorname{rlmax}(f(\pi))=5$ and
$\operatorname{rlmin}(\pi)=7\neq\operatorname{rlmin}(f(\pi))=8$, and the fact
that $g(12)=21$ shows that none of the statistics in
$\\{\operatorname{lrmax},\operatorname{lrmin},\operatorname{rlmax},\operatorname{rlmin}\\}$
can be preserved.

Next, we prove Theorem 3.4.

###### Proof.

Suppose that $\pi\in S_{n}(231,312)$ so that
$\pi=\pi^{\prime}\oplus(1\ominus\pi^{\prime\prime})$ where $\pi^{\prime}$ and
$\pi^{\prime\prime}$ are (possibly empty) $(231,312)$-avoiding permutations
and $\pi^{\prime\prime}$ is decreasing. Referring to the definitioin of $g$
(involving $\sigma^{\prime}$), we have

$\displaystyle\operatorname{asc}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{asc}(\pi^{\prime})+1\mbox{ \ \ \ \ ($n$
contributes an extra ascent)}$ $\displaystyle=$
$\displaystyle\operatorname{des}(g(\pi^{\prime}))+1\mbox{\ \ \ \ (by the
induction hypothesis)}$ $\displaystyle=$
$\displaystyle\operatorname{des}(g(\pi))\mbox{ \ \ \ \ ($n$ contributes an
extra descent).}$ $\displaystyle\operatorname{des}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{des}(\pi^{\prime})+\operatorname{des}(1\ominus\pi^{\prime\prime})$
$\displaystyle=$
$\displaystyle\operatorname{asc}(g(\pi^{\prime}))+\operatorname{asc}(\sigma^{\prime}\oplus
1)\mbox{\ \ \ \ (by the induction hypothesis)}$ $\displaystyle=$
$\displaystyle\operatorname{asc}(g(\pi)).$

Replacing $\operatorname{des}$ and $\operatorname{asc}$ by
$\operatorname{MND}$ and $\operatorname{MNA}$, respectively, in the
derivations for $\operatorname{des}(\pi)$, we see that
$\operatorname{MND}(\pi)=\operatorname{MNA}(g(\pi))$. Finally, for
$\operatorname{MNA}$ we distinguish two cases for $\pi^{\prime}$:

  * •

$\pi^{\prime}=12\cdots a$ so that $\pi=12\cdots an(n-1)\cdots(a+1)$ and
$g(\pi)=12\cdots(n-a-1)n(n-1)\cdots(n-a)$. It is straightforward to verify
that $\operatorname{MNA}(\pi)=\operatorname{MND}(g(\pi))$ and
$\operatorname{MND}(\pi)=\operatorname{MNA}(g(\pi))$.

  * •

$\pi^{\prime}=A\oplus B\oplus C\in S_{a}(231,312)$ where $A$, $B$ and $C$ are
defined as in Lemma 3.10 and the length of $C$ (resp., $B$) is $i\geq 1$
(resp., $j\geq 2$). So,

$\pi=A\oplus j(j-1)\cdots 1\oplus 12\cdots i\oplus(n-a)(n-a-1)\cdots 1$

and from definition of $g$, it is easy to see that

$g(\pi)=12\cdots(n-a-1)\oplus(1\ominus(i\cdots
1\ominus(12\cdots(j-1)\oplus(1\ominus g(A))))).$

$\displaystyle\operatorname{MNA}(\pi)$ $\displaystyle=$
$\displaystyle\operatorname{MNA}(A\oplus
B)+\operatorname{MNA}(12\cdots(i+2))\mbox{ \ \ (2nd term is given by $1\oplus
12\cdots i\oplus 1$)}$ $\displaystyle=$
$\displaystyle\operatorname{MND}(12\cdots(j-1)\oplus(1\ominus
g(A)))+\operatorname{MND}((i+2)(i+1)\cdots 1)$ (by the induction hypothesis)
$\displaystyle=$ $\displaystyle\operatorname{MND}(g(\pi))$ (the term
$\operatorname{MND}((i+2)\cdots 1)$ is given by $n(n-1)\cdots(n-i+1)(n-a)$ in
$g(\pi)$).

The theorem is proved. ∎

Finally, we prove Theorem 3.5.

###### Proof.

The map $g(f(\pi))$ proves the statement by Theorems 3.1 and 3.4. ∎

##  4 Concluding remarks

In this paper, we found the joint distributions of ($\operatorname{asc}$,
$\operatorname{des}$, $\operatorname{lrmax}$, $\operatorname{lrmin}$,
$\operatorname{rlmax}$, $\operatorname{rlmin}$) and the joint distributions of
($\operatorname{asc}$, $\operatorname{des}$, $\operatorname{MNA}$,
$\operatorname{MND}$) on permutations avoiding any two patterns of length 3.
All g.f.’s derived in our paper are rational and we provided combinatorial
proofs for five equidistribution results observed from the formulas. It is
remarkable that we were able to control so many statistics at the same time
while deriving explicit distribution results.

Studying (joint) distributions of statistics in other permutation classes, for
example, those studied in the literature [5] is an interesting direction of
further research.

Acknowledgments. The second author is grateful to Tianjin Normal University
for its hospitality.

## References

  * [1] M. Barnabei, F. Bonetti, M. Silimbani. The descent statistic on 123-avoiding permutations. Sém. Loth. de Comb. 63 (2010), Article B63a.
  * [2] M. Barnabei, F. Bonetti, and M. Silimbani. The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2. European J. Combin. 31 (2010), 1360–1371.
  * [3] M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, T. Wheeland. Distributions of statistics over pattern-avoiding permutations. J. Integer Sequences 22 (2019) Article 19.2.6.
  * [4] S. Elizalde, Statistics on pattern-avoiding permutations, Ph.D. thesis, MIT, 2004.
  * [5] S. Kitaev. Patterns in permutations and words, Monographs in Theoretical Computer Science, An EATCS Series, Springer, 2011.
  * [6] S. Kitaev. Partially ordered generalized patterns, Discr. Math. 298 (2005), 212–229.
  * [7] S. Kitaev and P.B. Zhang. Non-overlapping descents and ascents in stack-sortable permutations, Discr. Appl. Math., to appear.
  * [8] R. Simion and F. W. Schmidt. Restricted Permutations, European J. of Combin. 6 (1985) 383–406.