Proof. For \(1\le i\le n-1\), by the definition of \(\sigma^{rc}\), we have \[\begin{align} i\in\mathrm{Des}(\sigma^{rc}) &\Longleftrightarrow \sigma^{rc}(i)>\sigma^{rc}(i+1) \\ &\Longleftrightarrow n+1-\sigma(n+1-i)> n+1-\sigma(n-i) \\ &\Longleftrightarrow \sigma(n+1-i)<\sigma(n-i) \\ &\Longleftrightarrow n-i\in\mathrm{Des}(\sigma), \end{align}\] and for \(1\le i\le n\), \[\begin{align} \sigma^{rc}(i)=i &\Longleftrightarrow n+1-\sigma(n+1-i)=i \\ &\Longleftrightarrow \sigma(n+1-i)=n+1-i. \end{align}\] It follows that \(\sigma\mapsto\sigma^{rc}\) preserves both \(\mathrm{des}\) and \(\mathrm{fix}\). ◻

Proof. We first compute \(\operatorname{des}(\sigma)\). Since every index \(i\in\{2,\dots,n\}\) is either an ascent top position or a descent bottom position of \(\sigma\), we see that indices in \(\{2,\dots,n\}\setminus \mathrm{Asct}(\sigma)\) are exactly the descent bottoms of \(\sigma\). Then, by ?? , \(\mathrm{des}(\sigma)=|B|-1\).

It remains to compute \(\operatorname{ides}(\sigma)\). Set \(m=|\mathrm{Asct}(\sigma)|\). If \(m=0\), then \(\sigma=n(n-1)\cdots1\), and hence \(\mathrm{ides}(\sigma)=n-1=|B|-1\). Thus, assume \(m\ge 1\). By 6 , the permutation \(\sigma\) is constructed by placing the \(m\) largest values \(\{n-m+1, \dots, n\}\) in strictly increasing order at positions in \(\mathrm{Asct}(\sigma)\), and the remaining \(n-m\) values \(\{1, \dots, n-m\}\) in strictly decreasing order at positions in \(B\). An inverse descent occurs for a value \(v\) if and only if \(v+1\) appears to the left of \(v\) in \(\sigma\). One can check that

• For \(v \in \{n-m+1, \dots, n-1\}\): These values are placed in increasing order, so \(v+1\) is always to the right of \(v\). Hence, there are no inverse descents.

• For \(v \in \{1, \dots, n-m-1\}\): These values are placed in strictly decreasing order from left to right. Thus, the larger value \(v+1\) is always placed before (to the left of) \(v\). Hence, there are exactly \(n - m - 1\) inverse descents.

• For \(v = n-m\): Since \(1 \notin \mathrm{Asct}(\sigma)\), position \(1\) belongs to \(B\), giving \(\sigma(1) = n-m\). The value \(v+1 = n-m+1\) is placed at the first ascent position \(a_1 \ge 2\). Thus, \(v\) is to the left of \(v+1\), which means that \(v\) is not an inverse descent.

It follows from the above argument that \(\mathrm{ides}(\sigma)=|B|-1\). ◻

Proof. Suppose that \(B=\{b_1<b_2<\cdots<b_N\}\). Under the reverse construction of the Simion–Schmidt bijection \(\xi\) defined by 6 , we have \(\sigma(b_j)=N+1-j \text{ for } 1\leq j\leq N\), i.e., the entries in the positions belonging to \(B\) are filled, from left to right, by \(N,N-1,\ldots,1.\) It follows that \(b_j\) is a fixed point if and only if \[b_j=N+1-j,\] or equivalently, \[b_j+j=N+1.\] Since the sequence \(b_j+j\) is strictly increasing, this can happen for at most one index \(j\). Define \[\label{equ:epsilon-B} \epsilon(B)= \begin{cases} 1,&\text{if there exists }j\text{ such that }b_j+j=N+1;\\[4pt] 0,&\text{otherwise.} \end{cases}\tag{7}\]

Since \(b_N\) is the maximum element of the set \(B\), it follows that all positions \(b_N + 1, b_N + 2, \ldots, n\) are contained in \(\mathrm{Asct}(\sigma)\). It is easy to see that by the reverse construction of \(\xi\), these positions are forced to be fixed points. It follows that \[\label{equ:fix-point} \mathrm{fix}(\sigma)=n-b_N+\epsilon(B).\tag{8}\]

By combining the bijection \(\xi\) with Lemma 2 and 8 , the polynomials \(F_{\Pi}(t;x,y)\) (for \(\Pi=T_1=\{132,312\}\)) defined in 2 can be reformulated in the following manner, \[F_{T_1}(t;x,y)=1+\sum_{n\ge 1}\sum_{\substack{B\subseteq[n]\\1\in B}}x^{|B|-1}y^{n-\max B+\epsilon(B)}t^n,\] where \(\max B\) denotes the maximum element of set \(B\). By first fixing \(B\) and summing over all \(n\ge \max B\), we obtain \[\begin{align} \label{F-set-version} F_{T_1}(t;x,y) &= 1+ \sum_{\substack{B\subseteq \mathbb{P}\\1\in B}} x^{|B|-1}y^{\epsilon(B)} \sum_{n\geq \max B}y^{n-\max B}t^n\nonumber \\ &= 1+ \frac{1}{1-yt} \sum_{\substack{B\subseteq \mathbb{P}\\1\in B}} x^{|B|-1}y^{\epsilon(B)}t^{\max B}. \end{align}\tag{9}\] Define the enumerative polynomials \[\label{H-set} H(t;x,y):= \sum_{\substack{B\subseteq \mathbb{P}\\1\in B}} x^{|B|-1}y^{\epsilon(B)}t^{\max B}.\tag{10}\] We now compute \(H(t;x,y)\). First ignore the statistic \(\epsilon(B)\), and set \[\label{equ:H950} H_0(t;x):=\sum_{\substack{B\subseteq \mathbb{P}\\1\in B}} x^{|B|-1}t^{\max B}.\tag{11}\] If \(B=\{1\}\), the contribution is \(t\). If \(\max B=L\geq 2\), then \(1\) and \(L\) are forced to be in \(B\), while the elements of \(\{2,3,\ldots,L-1\}\) may be chosen freely. Hence, \[\label{gen-fun-H950} H_0(t;x)= t+\sum_{L\geq 2}x(1+x)^{L-2}t^L.\tag{12}\] Next, we compute the contribution of those sets \(B\) satisfying \(\epsilon(B)=1\). Let \[\label{def:H951} H_1(t;x):=\sum_{\substack{B\subseteq \mathbb{P}\\1\in B,\,\epsilon(B)=1}}x^{|B|-1}t^{\max B}.\tag{13}\] The set \(B=\{1\}\) satisfies \(\epsilon(B)=1\) and contributes \(t\). Now suppose that \(B=\{b_1<b_2<\cdots<b_N\}\) has \(N\geq 2\) elements and satisfies \(\epsilon(B)=1\). Then there exist a unique index \(j\) such that \[\label{relation:b95j-N} b_j+j=N+1.\tag{14}\] Set \(p=b_j\). Then \(N=p+j-1\). Since \(1=b_1\) and \(b_j=p\), the elements of \(B\) before \(p\) consist of \(1\), together with \(j-2\) elements chosen from \(\{2,3,\ldots,p-1\}\). Thus there are \[\binom{p-2}{j-2}\] choices for the part of \(B\) before \(p\).

On the other hand, the number of elements of \(B\) after \(p\) is \(N - j = b_j - 1\). If \(L=\max B\), then one of these elements is \(L\), and the remaining \(p-2\) elements are chosen from \(\{p+1,p+2,\ldots,L-1\}.\) Thus, for fixed \(p\) and \(L\), the number of choices after \(p\) is \[\binom{L-p-1}{p-2}.\] Summing over all possible \(L\), we obtain \[\sum_{L\ge 2p-1}\binom{L-p-1}{p-2}t^L = \frac{t^{2p-1}}{(1-t)^{p-1}}.\] Moreover, since \(N=p+j-1\), the exponent of \(x\) is \(|B|-1=N-1=p+j-2.\) Therefore \[H_1(t;x) = t+ \sum_{p\ge 2}\sum_{j=2}^{p} \binom{p-2}{j-2} x^{p+j-2} \frac{t^{2p-1}}{(1-t)^{p-1}}.\] Setting \(k=p-2\) and \(i=j-2\), we get

\[H_1(t;x)-t= \sum_{k\ge 0} \frac{x^{k+2}t^{2k+3}}{(1-t)^{k+1}} \sum_{i=0}^{k}\binom{k}{i}x^i\] Combining the binomial theorem and the geometric series identity, we derive \[\label{gen-fun-H951} H_1(t;x)= t+\frac{x^2t^3}{1-t-x(1+x)t^2}.\tag{15}\] Since \(y\) only records whether the possible extra fixed point inside \(B\) exists, we have \[\label{relation-H-H950-H951} H(t;x,y)=H_0(t;x)+(y-1)H_1(t;x).\tag{16}\] Substituting 12 and 15 into 16 , and using \[1-t-x(1+x)t^2=(1+xt)(1-(1+x)t),\] we obtain \[H(t;x,y) = yt+ \frac{xt^2(1+xyt)(1-xt)}{(1-x^2t^2)(1-(1+x)t)}.\] Combining this with 9 and 10 , we obtain ?? . ◻

Proof. We first consider the case \(\mathrm{Asct}(\sigma)=\{2,3,\ldots,n\}\). Then \(\sigma=12\cdots n\) and \(B=[n]\setminus \mathrm{Asct}(\sigma)=\{1\}\). Hence, by the pixed factorization, we have \(\mathrm{pix}(\sigma)=n\), and by Lemma 2, we have \(\mathrm{ides}(\sigma)=0\). Therefore, this case and the empty permutation contribute \[\label{gen-trival} 1+\sum_{n\geq 1} y^n t^n =1+ \frac{yt}{1-yt}.\tag{17}\] For the remaining part, assume that \(|B|\geq 2\) and \(B=\{b_1<b_2<\cdots<b_N\}\) with \(b_1=1\). Since \(B=[n]\setminus \mathrm{Asct}(\sigma)\), the positions \(2,3,\ldots,b_2-1\) belong to \(\mathrm{Asct}(\sigma)\). Hence the maximal increasing prefix of \(\sigma\) has length \(b_2-1\). Now let \(r\geq 1\) be the length of the maximal consecutive segment of elements of \(B\) beginning at \(b_2\), i.e., \[b_2,b_2+1,\ldots,b_2+r-1\in B,\] and either \(b_2+r\notin B\) or \(b_2+r>n\). Define \[\label{eta-B} \eta(B)= \begin{cases} 0,&\text{if r is even;}\\[4pt] 1,&\text{if r is odd.} \end{cases}\tag{18}\] One can check that the number of pixed points of \(\sigma\) is decided by the parity of \(r\), \[\label{equ:pix-B} \mathrm{pix}(\sigma)=b_2-1-\eta(B),\tag{19}\] or equivalently, \[\mathrm{pix}(\sigma)= \begin{cases} b_2-1, & \text{if } r \text{ is even};\\[4pt] b_2-2, & \text{if } r \text{ is odd}. \end{cases}\] By combining the bijection \(\xi\) with Lemma 2, 19 and 17 , the polynomials \(P_{\Pi}(t;x,y)\) (for \(\Pi=T_1=\{132,312\}\)), defined in 3 , can be reformulated as follows: \[P_{T_1}(t;x,y)=1+\frac{yt}{1-yt}+\sum_{n\ge 2}\sum_{\substack{B\subseteq[n]\\1\in B,\, |B|\ge 2}}x^{|B|-1}y^{b_2-1-\eta(B)}t^n.\] By first fixing \(B\) and summing over all \(n\ge \max B\), we obtain \[\begin{align} \label{rewrite-P} P_{T_1}(t;x,y)&=1+\frac{yt}{1-yt}+\sum_{\substack{B\subseteq[n]\\1\in B,\, |B|\ge 2}}x^{|B|-1}y^{b_2-1-\eta(B)}\sum_{n\ge \max B}t^n\notag\\ &=1+\frac{yt}{1-yt}+\frac{1}{1-t}\sum_{\substack{B\subseteq\mathbb{P}\\1\in B,\, |B|\ge 2}}x^{|B|-1}y^{b_2-1-\eta(B)}t^{\max B}. \end{align}\tag{20}\] Define the following enumerative polynomials \[\label{def-K} K(t;x,y)=\sum_{n\ge 2}\sum_{\substack{B\subseteq \mathbb{P}\\1\in B,\,|B|\ge 2}}x^{|B|-1}y^{b_2-1-\eta(B)}t^{\max B}.\tag{21}\] Combining this with 20 , we have \[\label{gen-P-K} P_{\Pi}(t;x,y)=1+\frac{yt}{1-yt}+\frac{K(t;x,y)}{1-t}.\tag{22}\] We now enumerate finite subsets \(B\) of positive integers containing 1 and satisfying \(|B|\ge 2\). Fix \(\ell:=b_2-1\geq 1\) and \(r\geq 1\). Then \(B\) begins as \[B=\{1\}\cup\{\ell+1,\ell+2,\ldots,\ell+r\}\cup\{\text{later elements}\}.\] We now count the possible later elements.

• If there are no later elements, then \(\max B=\ell+r,\) and the contribution is \(t^{\ell+r}\).

• If there are later elements, then \(\ell+r+1\notin B\), by maximality of the segment of consecutive elements, and the next possible elements lie in \[\{\ell+r+2,\ell+r+3,\ldots \}.\] If the maximum is \(L:=\max B\geq \ell+r+2\), then \(L\) is forced to belong to \(B\), and the elements of \[\{\ell+r+2,\ell+r+3,\ldots,L-1\}\] may be chosen freely. Thus the contribution of the later part is \[\sum_{L\geq \ell+r+2} x(1+x)^{L-(\ell+r+2)}t^L = \frac{x t^{\ell+r+2}}{1-(1+x)t}.\]

Therefore, for fixed \(\ell\) and \(r\), the contribution of the final part is \[\label{gen-fix-l-r} t^{\ell+r} + \frac{x t^{\ell+r+2}}{1-(1+x)t} = t^{\ell+r} \frac{(1-t)(1-xt)}{1-(1+x)t}.\tag{23}\] Since \(x\) records \(|B|-1\), the segment \(\ell+1,\ell+2,\ldots,\ell+r\) contributes \(x^r\). Combining this with 23 , we derive that \(K(t;x,y)\) defined in 21 is equal to \[\label{equ:K} K(t;x,y)= \frac{(1-t)(1-xt)}{1-(1+x)t} \sum_{\ell\geq 1}\sum_{r\geq 1} x^r t^{\ell+r} y^{\ell-\chi(2\,\nmid \,r)},\tag{24}\] where \(\chi(P)\) is equal to \(1\) if the proposition \(P\) is true, and \(0\) otherwise. Separating \(r\) according to its parity, we get \[\begin{align} K(t;x,y) &= \frac{(1-t)(1-xt)}{1-(1+x)t} \sum_{\ell\geq 1} t^\ell \left( y^\ell \sum_{\substack{r\geq 1\\ r\text{ even}}}(xt)^r + y^{\ell-1} \sum_{\substack{r\geq 1\\ r\text{ odd}}}(xt)^r \right) \notag \\ &= \frac{(1-t)(1-xt)}{1-(1+x)t} \sum_{\ell\geq 1} t^\ell \left( y^\ell\frac{x^2t^2}{1-x^2t^2} + y^{\ell-1}\frac{xt}{1-x^2t^2} \right) \notag\\ &= \frac{x t^2(1+xyt)(1-t)(1-xt)}{(1-yt)(1-x^2t^2)(1-(1+x)t)}.\label{gen-K} \end{align}\tag{25}\] Substituting \(K(t;x,y)\) by 25 in 22 , we obtain ?? . ◻

Proof. By Lemma 1, the reversal-complement map \(\sigma\mapsto\sigma^{rc}\) restricts a bijection between \(\mathfrak{S}_n(132,312)\) and \(\mathfrak{S}_n(213,231)\), thus we have \(F_{T_2}(t;x,y)=F_{T_1}(t;x,y), \text{ where } T_1=\{132,312\}.\) By the formula for \(F_{T_1}(t;x,y)\) given in ?? , we obtain ?? . ◻

Proof. From the decomposition 26 , if \(a=n-1\), then \(\sigma=12\cdots n\). Hence, \(\mathrm{ides}(\sigma)=0\) and \(\mathrm{pix}(\sigma)=n\). Together with the empty permutation, these identity permutations contribute \[\label{equ:identity} 1+\sum_{n\geq 1}y^n t^n=1+\frac{yt}{1-yt}.\tag{27}\] Now suppose \(a\le n-2\), and put \(m=n-a-1\ge 1\). Then \[\label{dec:sigma-tau} \sigma=12\cdots a\,n\,\tau^{^{+}a}, \text{ with }\tau\in\mathfrak{S}_{m}(213,231).\tag{28}\] Since \(n\) occurs before all letters of \(\tau^{^{+}a}\), the pair \((n-1,n)\) always creates one new inverse descent. The remaining inverse descents are exactly those coming from \(\tau\). Hence, \[\label{ides-P-T952} \mathrm{ides}(\sigma)=\mathrm{ides}(\tau)+1.\tag{29}\] For the pixed statistic, we distinguish whether \(\tau\) is a desarrangement. If \(\tau\) is a desarrangement, then the suffix \(\tau^{^{+}a}\) is itself a desarrangement. By the pixed factorization of \(\sigma\), we have \(\mathrm{pix}(\sigma)=a+1\). If \(\tau\) is not a desarrangement, then the prefix cannot include the letter \(n\). In this case the suffix \(n\,\tau^{^{+}a}\) is a desarrangement. Then we have \(\mathrm{pix}(\sigma)=a\). Therefore, Therefore \[\label{pix-T952} \mathrm{pix}(\sigma)= \begin{cases} a+1, & \text{if } \tau \text{ is a desarrangement};\\[5pt] a, & \text{otherwise}. \end{cases}\tag{30}\] Define the following two enumerative polynomials \[A(t;x)=\sum_{n\ge 0}\Bigg(\sum_{\sigma\in\mathfrak{S}_{n}(213,231)}x^{\mathrm{ides}(\sigma)}\Bigg)t^n,\] and \[B(t;x)=\sum_{n\ge 1}\left(\sum_{\substack{\sigma\in\mathfrak{S}_{n}(213,231)\\\sigma\text{ is a desarrangement}}}x^{\mathrm{ides}(\sigma)}\right)t^n.\]

We first compute \(A(t;x)\). Together with the empty permutation, identity permutations contribute \[1+\sum_{n\ge1}t^n=\frac{1}{1-t}.\] For the non-identity part, using the decomposition 28 , the initial segment \(12\cdots a\) contributes \(t^a\), the letter \(n\) contributes \(t\), and by 29 it also contributes a factor \(x\). The remaining nonempty permutation \(\tau\) contributes \(A(t;x)-1\). Thus \[A(t;x) = \frac{1}{1-t} + \frac{xt}{1-t}\bigl(A(t;x)-1\bigr).\] Solving this equation gives \[\label{gen-A} A(t;x)=\frac{1-xt}{1-(1+x)t}.\tag{31}\]

Next we compute \(B(t;x)\). A desarrangement in \(\mathfrak S_n(213,231)\) cannot begin with a nonempty increasing segment \(12\cdots a\) with \(a\ge1\), since then the first ascent occurs at position \(1\). Hence, in the decomposition 26 , we must have \(a=0\). Thus every nonempty desarrangement in this class is of the form \[\sigma=n\,\tau,\,\text{ with } \tau\in\mathfrak S_{n-1}(213,231).\] Moreover, \(\tau\) is nonempty, since the singleton permutation is not a desarrangement.

The first ascent of \(n\,\tau\) occurs one position later than the first ascent of \(\tau\). Thus the parity of the position of the first ascent is reversed. Consequently, \(n\,\tau\) is a desarrangement if and only if \(\tau\) is not a desarrangement. Since the initial letter \(n\) creates one new inverse descent, we obtain \[B(t;x) = xt\bigl(A(t;x)-1-B(t;x)\bigr).\] Therefore \[\label{gen-B} B(t;x) = \frac{xt(A(t;x)-1)}{1+xt}.\tag{32}\] Substituting \(A(t;x)\) by 31 , we obtain \[B(t;x)= \frac{xt^2}{(1+xt)(1-(1+x)t)}.\]

We now return to \(P_{T_2}(t;x,y)\). The contribution of empty permutation and identity permutations is already given by 27 . For the non-identity part, from the decomposition \(\sigma=12\cdots a\,n\,\tau^{^{+}a}, \text{ with }\tau\in\mathfrak{S}_{m}(213,231)\), we see that the initial segment \(12\cdots a\) contributes \((yt)^a\), and summing over all \(a\ge0\) gives \[\sum_{a\ge0}(yt)^a=\frac{1}{1-yt}.\] The letter \(n\) contributes \(t\) and creates one new inverse descent, hence gives a factor \(xt\). Thus the common contribution is \[\frac{xt}{1-yt}.\]

It remains to account for the contribution of \(\tau\). All nonempty \(\tau\)’s contribute \(A(t;x)-1\). However, by 30 , when \(\tau\) is a desarrangement, the value of \(\operatorname{pix}(\sigma)\) is \(a+1\) rather than \(a\), so these terms acquire one additional factor \(y\). Therefore the contribution of the \(\tau\)-part is \[A(t;x)-1+(y-1)B(t;x).\] From the above argument, we see that the contribution of non-identity permutations is \[\frac{xt}{1-yt} \left( A(t;x)-1+(y-1)B(t;x) \right).\] It follows that \[P_{T_2}(t;x,y)= 1+\frac{yt}{1-yt} + \frac{xt}{1-yt} \left( A(t;x)-1+(y-1)B(t;x) \right).\] Substituting \(A(t;x)\) and \(B(t;x)\) by 31 and 32 , respectively, we obtain ?? . ◻

Proof. The identity permutation \(\sigma_{n,n}\) contributes \(y^n\) to the coefficient of \(t^n\) in \(F_{T_3}(t;x,y)\). For a non-identity element \(\sigma_{k,m}\), by 33 , we see that the three displayed segments are increasing, i.e., \((m-k+1,\ldots,m)\), \((1,\ldots,m-k)\) and \((m+1,\ldots,n)\), and the only descent occurs between the first and second segments. Thus, we have \[\mathrm{des}(\sigma_{k,m})=1.\] The fixed points are precisely those in the final segment \(m+1,m+2,\ldots,n\), and hence \[\mathrm{fix}(\sigma_{k,m})=n-m.\] For a fixed \(m\), there are exactly \(m-1\) non-identity permutations, and each permutation contributes \(xy^{n-m}\). Thus, \[\label{rec-des-fix-F} \sum_{\sigma\in\mathfrak{S}_n(132,321)}x^{\mathrm{des}(\sigma)}y^{\mathrm{fix}(\sigma)} =y^n+x\sum_{m=2}^n(m-1)y^{n-m}.\tag{34}\] Together with the contribution \(1\) of the empty permutation, multiplying 34 by \(t^n\) and summing over \(n\geq 1\) yields ?? . ◻

Proof. For the identity permutation \(\sigma_{n,n}\), we have \(\mathrm{ides}(\sigma_{n,n})=0\). By 33 , it is easy to see that, for \(1\le k< m\le n\) \[\label{form-inverse} \sigma_{k,m}^{-1} = (k+1)(k+2)\cdots m\,12\cdots k\,(m+1)\cdots n = \sigma_{m-k,m}.\tag{35}\] It follows that \(\mathrm{ides}(\sigma_{k,m})=1\). The length of the maximal consecutive increasing prefix of \(\sigma_{k,m}\) is equal to \(k\). In order to make the suffix of \(\sigma_{k,m}\) a desarrangement, we need to have the following form \[m,1,2,\dots,m-k,m+1,\dots,n.\] Hence, we have \(\mathrm{pix}(\sigma_{k,m})=k-1\). It follows that \[\label{rec-des-fix-P} \sum_{\sigma\in\mathfrak{S}_n(132,321)}x^{\mathrm{ides}(\sigma)}y^{\mathrm{pix}(\sigma)} =y^n+\sum_{m=2}^n\sum_{k=1}^{m-1}xy^{k-1} =y^n+\sum_{j=0}^{n-2}(n-1-j)y^{j}.\tag{36}\] Together with the contribution \(1\) of the empty permutation, multiplying 36 by \(t^n\) and summing over \(n\geq 1\) yields ?? . ◻

Proof. By 37 , we see that \[\sum_{\sigma\in\mathfrak{S}_n(T_4)} x^{\mathrm{des}(\sigma)} y^{\mathrm{fix}(\sigma)} = \sum_{k=1}^{n} x^{\mathrm{des}(\hat{\sigma}_{n,k})} y^{\mathrm{fix}(\hat{\sigma}_{n,k})}.\]

Let us first determine the number of descents of \(\hat{\sigma}_{n,k}\). If \(k<n\), then the only ascent occurs at position \(n-k\), while all other positions \(i\in[n-1]\setminus\{n-k\}\) are descents. If \(k=n\), then \(\hat{\sigma}_{n,n}=n(n-1)\cdots1\), so every position \(i\in[n-1]\) is a descent. Therefore, \[\label{case-des} \mathrm{des}(\hat{\sigma}_{n,k})= \begin{cases} n-2, & \text{if } 1\le k<n;\\[4pt] n-1, & \text{if } k=n. \end{cases}\tag{38}\] We next compute the number of fixed points of \(\hat{\sigma}_{n,k}\). From 37 , the letter \(n\) occurs in position \(n-k+1\). Hence, it is easy to see that the letter \(n\) is a fixed point if and only if \(k=1\). For \(k\le a\le n-1\), the letter \(a\) occurs in position \(n-a\), and it is a fixed point if and only if \(n\) is even and \(a=n/2\). For \(1\le a\le k-1\), the letter \(a\) occurs in position \(n-a+1\), and it is a fixed point if and only if \(n\) is odd and \(a=(n+1)/2\). It follows that \[\label{fix-chi} \mathrm{fix}(\hat{\sigma}_{n,k})=\chi(k=1)+\chi(n \text{ is even and } k\le n/2)+\chi(n \text{ is odd and } k> (n+1)/2).\tag{39}\] Equivalently, if \(n=2m+1\), then \[\label{case-fix-2m431} \mathrm{fix}(\hat{\sigma}_{2m+1,k})= \begin{cases} 1, & k=1 \text{ or } m+2\le k\le 2m+1;\\[4pt] 0, & 2\le k\le m+1, \end{cases}\tag{40}\] while if \(n=2m\), then \[\label{case-fix-2m} \mathrm{fix}(\hat{\sigma}_{2m,k})= \begin{cases} 2, & k=1;\\[3pt] 1, & 2\le k\le m;\\[3pt] 0, & m+1\le k\le 2m. \end{cases}\tag{41}\] Hence, for \(n=2m+1\), by 40 , we have \[\label{odd-F-rec} \sum_{\sigma\in\mathfrak{S}_{2m+1}(T_4)} x^{\mathrm{des}(\sigma)}y^{\mathrm{fix}(\sigma)} = x^{2m}y+x^{2m-1}m(1+y).\tag{42}\] For \(n=2m\), by 41 , we have \[\label{even-F-rec} \sum_{\sigma\in\mathfrak{S}_{2m}(T_4)} x^{\mathrm{des}(\sigma)}y^{\mathrm{fix}(\sigma)} = x^{2m-1}+x^{2m-2}\bigl((m-1)(1+y)+y^2\bigr).\tag{43}\] Together with the initial contributions \(1\) and \(yt\) corresponding to \(n=0\) and \(n=1\), respectively, the stated generating function ?? follows by multiplying 42 and 43 by \(t^{2m+1}\) and \(t^{2m}\), respectively, then summing over \(m\ge 1\). ◻

Proof. First, let us determine \(\mathrm{ides}\). From 37 , a direct check gives \[\label{ides-hat} \mathrm{ides}(\hat{\sigma}_{n,k})= \begin{cases} n-2, & \text{if } 1\le k<n;\\[4pt] n-1, & \text{if } k=n. \end{cases}\tag{44}\] Now we compute \(\mathrm{pix}\). Recall that \(\mathrm{pix}(\sigma)\) is the length of the initial increasing word in the pixed factorization of \(\sigma\). If \(k<n\), then the unique ascent of \(\hat{\sigma}_{n,k}\) occurs at position \(n-k\). Therefore \(\hat{\sigma}_{n,k}\) itself is a desarrangement precisely when \(n-k\) is even.

Suppose first that \(n=2m+1\). Then \(n-k\) is even exactly when \(k\) is odd. Thus, for odd \(k<2m+1\), we have \(\mathrm{pix}(\hat{\sigma}_{2m+1,k})=0\). For even \(k\), deleting the first letter shifts the unique ascent to an even position, so the remaining word is a desarrangement and \(\mathrm{pix}(\hat{\sigma}_{2m+1,k})=1\). Finally, when \(k=2m+1\), deleting the first letter leaves a decreasing word of even length, which is a desarrangement. Hence \[\label{odd-P-case} \mathrm{pix}(\hat{\sigma}_{2m+1,k})= \begin{cases} 0, & k \text{ is odd and } k<2m+1;\\[3pt] 1, & k \text{ is even};\\[3pt] 1,& k=2m+1. \end{cases}\tag{45}\]

Now suppose that \(n=2m\). Then \(n-k\) is even exactly when \(k\) is even, so \(\mathrm{pix}(\hat{\sigma}_{2m,k})=0\) for even \(k\). If \(k\) is odd and \(k<2m-1\), deleting the first letter shifts the unique ascent to an even position, and hence \(\mathrm{pix}(\hat{\sigma}_{2m,k})=1\). In the remaining case \(k=2m-1\), the first two letters form the increasing word \((2m-1,2m)\), and deleting them leaves a decreasing word of even length, which is a desarrangement. If \(n=2m\), then \[\label{even-P-case} \mathrm{pix}(\hat{\sigma}_{2m,k})= \begin{cases} 0, & k \text{ is even;}\\[3pt] 1, & k \text{ is odd and } k<2m-1;\\[3pt] 2, & k=2m-1. \end{cases}\tag{46}\] Therefore, using 44 and 45 , for \(n=2m+1\), \[\label{odd-P-rec} \sum_{\sigma\in\mathfrak{S}_{2m+1}(T_4)} x^{\mathrm{ides}(\sigma)}y^{\mathrm{pix}(\sigma)} = x^{2m}y+x^{2m-1}m(1+y),\tag{47}\] and using 44 and 46 , for \(n=2m\), \[\label{even-P-rec} \sum_{\sigma\in\mathfrak{S}_{2m}(T_4)} x^{\mathrm{ides}(\sigma)}y^{\mathrm{pix}(\sigma)} = x^{2m-1}+x^{2m-2}\bigl((m-1)(1+y)+y^2\bigr).\tag{48}\] Together with the initial contributions \(1\) and \(yt\) corresponding to \(n=0\) and \(n=1\), respectively, the stated generating function ?? follows by multiplying 47 and 48 by \(t^{2m+1}\) and \(t^{2m}\), respectively, then summing over \(m\ge 1\). ◻

Proof. By Lemma 1, the reversal-complement map \(\sigma\mapsto\sigma^{rc}\) restricts a bijection between \(\mathfrak{S}_n(123,213,231)\) and \(\mathfrak{S}_n(123,132,312)\), thus we have \(F_{T_5}(t;x,y)=F_{T_4}(t;x,y)\), where \(T_4=\{123,132,312\}\). Then the stated formula follows immediately from Theorem 9. ◻

Proof. It is straightforward to see that \[\label{case-ides-P} \mathrm{ides}(\tilde{\sigma}_{n,k})= \begin{cases} n-2, & 1\le k<n;\\[4pt] n-1, & k=n. \end{cases}\tag{50}\]

Next we compute \(\mathrm{pix}(\tilde{\sigma}_{n,k})\). From the explicit form of \(\tilde{\sigma}_{n,k}\), if \(k<n\), the unique ascent occurs at position \(k\), namely the adjacent pair \(1<n-k+1\). Thus \(\tilde{\sigma}_{n,k}\) is itself a desarrangement exactly when \(k\) is even. If \(k\) is odd and \(k<n\), deleting the first letter shifts this unique ascent to position \(k-1\), which is even.

Now suppose \(n=2m+1\). If \(k\) is even, then \(\tilde{\sigma}_{2m+1,k}\) is already a desarrangement, so its pix is \(0\). If \(k\) is odd and \(k<2m+1\), deleting the first letter gives a desarrangement, so the pix is \(1\). Finally, when \(k=2m+1\), the word \(\tilde{\sigma}_{2m+1,2m+1}=(2m+1)(2m)\cdots1\) is decreasing of odd length; deleting the first letter leaves a decreasing word of even length, which is a desarrangement. Hence \[\label{case-pix-odd} \mathrm{pix}(\tilde{\sigma}_{2m+1,k})= \begin{cases} 0, & k \text{ is even};\\[4pt] 1, & k \text{ is odd}. \end{cases}\tag{51}\]

Next suppose \(n=2m\). If \(k\) is even, then \(\tilde{\sigma}_{2m,k}\) is already a desarrangement, so its pix is \(0\). If \(k\) is odd and \(3\le k\le 2m-1\), deleting the first letter shifts the unique ascent to the even position \(k-1\), so the pix is \(1\). The remaining case is \(k=1\). In this case \(\tilde{\sigma}_{2m,1}=1~ 2m~ 2m-1 ~\ldots~2\) and the initial increasing word has length \(2\), since deleting the first two letters leaves the decreasing word \((2m-1)\cdots2\) of even length, which is a desarrangement. Therefore \[\label{case-pix-even} \mathrm{pix}(\tilde{\sigma}_{2m,k})= \begin{cases} 0, & k \text{ is even};\\[3pt] 1, & k \text{ is odd and } 3\le k\le 2m-1;\\[3pt] 2, & k=1. \end{cases}\tag{52}\]

Combining 50 and 51 , for \(n=2m+1\), we get \[\label{odd-t955} \sum_{\sigma\in\mathfrak S_{2m+1}(T_5)} x^{\mathrm{ides}(\sigma)}y^{\mathrm{pix}(\sigma)} = x^{2m}y+mx^{2m-1}(1+y).\tag{53}\] Similarly, combining 50 and 52 , for \(n=2m\), we get \[\label{even-t955} \sum_{\sigma\in\mathfrak S_{2m}(T_5)} x^{\mathrm{ides}(\sigma)}y^{\mathrm{pix}(\sigma)} = x^{2m-1} +x^{2m-2}\bigl((m-1)(1+y)+y^2\bigr).\tag{54}\]

Together with the initial contributions \(1\) and \(yt\) corresponding to \(n=0\) and \(n=1\), respectively, the stated generating function follows by multiplying 53 and 54 by \(t^{2m+1}\) and \(t^{2m}\), respectively, and summing over \(m\ge1\). ◻

Proof. From the characterization 55 , for \(k=1\), we have \(\bar{\sigma}_{n,1}=12\cdots n\). Hence \[\label{des-fix-d} \mathrm{des}(\bar{\sigma}_{n,1})=0 \text{ and } \mathrm{fix}(\bar{\sigma}_{n,1})=n.\tag{56}\] For \(2\leq k\leq n\), it is straightforward to see that the permutation \(\bar{\sigma}_{n,k}\) has exactly one descent, and its fixed points are exactly \(k+1,k+2,\ldots,n\), i.e., \[\label{des-fix-d-gen} \mathrm{des}(\bar{\sigma}_{n,k})=1\text{ and }\mathrm{fix}(\bar{\sigma}_{n,k})=n-k.\tag{57}\] Therefore, combining 56 and 57 , we obtain \[\sum_{\sigma\in\mathfrak{S}_n(T_6)} x^{\mathrm{des}(\sigma)}y^{\mathrm{fix}(\sigma)} = y^n+\sum_{k=2}^n x y^{n-k}.\] Consequently, after multiplying by \(t^n\) and summing over \(n\geq 1\), and after adding the initial contribution \(1\) of the empty permutation corresponding to \(n=0\), we obtain ?? . ◻

Proof. From the characterization 55 , for \(k=1\), we have \(\bar{\sigma}_{n,1}=12\cdots n\). Hence \[\label{des-fix-T956} \mathrm{ides}(\bar{\sigma}_{n,1})=0 \text{ and } \mathrm{pix}(\bar{\sigma}_{n,1})=n.\tag{58}\] It remains to determine \(\mathrm{pix}(\bar{\sigma}_{n,r})\). Recall that \(\mathrm{pix}(\bar{\sigma})\) is the length of the increasing prefix in the pixed factorization of \(\bar{\sigma}\). For \(2\leq k\leq n\), the maximal increasing prefix of \(\bar{\sigma}_{n,k}\) which occurs before the desarrangement is \(23\cdots (k-1)\), that is, \[\bar{\sigma}_{n,k} = \underbrace{2\cdots(k-1)}_{\iota}\, \underbrace{k1(k+1)\cdots(n-1)}_{\delta}.\] Thus, we have \[\label{pix-T956} \mathrm{pix}(\bar{\sigma}_{n,k})=k-2.\tag{59}\] Therefore, combining 58 and 59 , we have \[\sum_{\sigma\in\mathfrak{S}_n(T_6)} x^{\mathrm{ides}(\sigma)}y^{\mathrm{pix}(\sigma)} = y^n+\sum_{k=2}^n x y^{n-k}.\] Consequently, after multiplying by \(t^n\) and summing over \(n\geq 1\), and after adding the initial contribution \(1\) of the empty permutation corresponding to \(n=0\), we obtain ?? . ◻

Proof. By Lemma 1, the reversal-complement map \(\sigma\mapsto\sigma^{rc}\) restricts a bijection between \(\mathfrak{S}_n(213,231,321)\) and \(\mathfrak{S}_n(132,312,321)\), thus we have \(F_{T_7}(t;x,y)=F_{T_6}(t;x,y)\), where \(T_6=\{132,312,321\}\). By the formula for \(F_{T_6}(t;x,y)\) given in ?? , we obtain ?? . ◻

Proof. From the characterization 60 , for \(k=n\), we have \(^\star{\sigma}_{n,n}=12\cdots n\). Hence, \[\label{T957-special-case} \mathrm{ides}(^\star{\sigma}_{n,n})=0 \text{ and } \mathrm{pix}(^\star{\sigma}_{n,n})=n.\tag{61}\] For \(1\leq k\leq n-1\), one has \[\label{ides-T957} \mathrm{ides}(^\star{\sigma}_{n,k})=1\tag{62}\]

Recall that \(\mathrm{pix}(\pi)\) is the length of the initial increasing factor in the pixed factorization of \(\pi\). For \(1\le k\le n-1\), we may write \[{}^\star\sigma_{n,k} = \underbrace{12\cdots(k-1)}_{\iota}\, \underbrace{nk(k+1)\cdots(n-1)}_{\delta}.\] The word \(\iota=12\cdots(k-1)\) is increasing. Moreover, the suffix \(\delta=nk(k+1)\cdots(n-1)\) is a desarrangement: if \(k\le n-2\), then its first ascent occurs at the second position, while if \(k=n-1\), then \(\delta=n(n-1)\) has no ascent and is a desarrangement by convention. Thus the above decomposition is precisely the pixed factorization of \({}^\star\sigma_{n,k}\). Consequently, \[\label{pix-T957} \operatorname{pix}({}^\star\sigma_{n,k})=k-1.\tag{63}\]

Combining 61 , 62 and 63 , we obtain, for \(n\ge1\), \[\sum_{\sigma\in\mathfrak{S}_n(T_7)} x^{\operatorname{ides}(\sigma)} y^{\operatorname{pix}(\sigma)} = y^n+\sum_{k=1}^{n-1}xy^{k-1}.\] Consequently, after multiplying by \(t^n\) and summing over \(n\geq 1\), and after adding the initial contribution \(1\) of the empty permutation corresponding to \(n=0\), we obtain ?? . ◻

Proof. From 64 , the initial segment \(12\cdots k\) is increasing, whereas the final segment \(n(n-1)\cdots(k+1)\) is decreasing and has length \(n-k\). Hence the descents occur precisely inside this final decreasing segment. Therefore \[\label{des-T958} \mathrm{des}(\mathring{\sigma}_{n,k})=n-k-1.\tag{65}\] It remains to determine the number of fixed points. The letters \(1,2,\ldots,k\) are fixed points, and hence contribute \(k\) fixed points. Now consider the final decreasing segment. Its positions are \(k+1,k+2,\ldots,n,\) and its corresponding values are \(n,n-1,\ldots,k+1.\) The \(j\)-th entry of this segment, where \(1\le j\le n-k\), lies in position \(k+j\) and has value \(n-j+1\). It is fixed if and only if \(k+j=n-j+1,\) or equivalently, \(2j=n-k+1.\) Thus the final decreasing segment contributes exactly one additional fixed point when \(n-k\) is odd. Consequently, \[\label{fix-T958} \operatorname{fix}(\mathring{\sigma}_{n,k}) = k+\chi(n-k\;\text{is odd}).\tag{66}\]

Combining 65 and 66 , we obtain, for \(n\ge1\), \[\label{rec-T958} \sum_{\sigma\in\mathfrak{S}_n(T_8)} x^{\operatorname{des}(\sigma)} y^{\operatorname{fix}(\sigma)} = \sum_{k=0}^{n-1} x^{n-k-1} y^{k+\chi(n-k\;\text{is odd})}.\tag{67}\] Taking also into account the empty permutation for \(n=0\), which contributes \(1\), and multiplying both side of 67 by \(t^n\) and summing over \(n\ge 1\), we get \[\begin{align} F_{T_8}(t;x,y) &= 1+\sum_{n\ge1}t^n \sum_{\sigma\in\mathfrak{S}_n(T_8)} x^{\operatorname{des}(\sigma)} y^{\operatorname{fix}(\sigma)} \\ &= 1+\sum_{n\ge1}\sum_{k=0}^{n-1} t^n x^{n-k-1} y^{k+\chi(n-k\;\text{is odd})}. \end{align}\] Setting \(\ell=n-k\), the length of the final decreasing segment in the above identity. Then for \(\ell\ge1\), \(k\ge0\) and \(n=k+\ell\), we have \[\begin{align} \label{F-T958} F_{T_8}(t;x,y) &= 1+\sum_{k\ge0}\sum_{\ell\ge1} t^{k+\ell}x^{\ell-1} y^{k+\chi(\ell\;\text{is odd})} \notag \\ &= 1+\left(\sum_{k\ge0}(yt)^k\right) \left(\sum_{\ell\ge1}t^\ell x^{\ell-1} y^{\chi(\ell\;\text{is odd})}\right) \notag \\ &= 1+\frac{1}{1-yt} \sum_{\ell\ge1}t^\ell x^{\ell-1} y^{\chi(\ell\;\text{is odd})}. \end{align}\tag{68}\] Splitting according to the parity of \(\ell\), the last sum of 68 is equal to \[\begin{align} \sum_{\ell\ge1}t^\ell x^{\ell-1} y^{\chi(\ell\;\text{is odd})} &= \sum_{m\ge0}t^{2m+1}x^{2m}y + \sum_{m\ge1}t^{2m}x^{2m-1} =\frac{yt+xt^2}{1-x^2t^2}. \end{align}\] Combining this and 68 yields ?? . ◻

Proof. Recall that \(\operatorname{ides}(\sigma)\) counts the values \(v\in[n-1]\) such that \(v+1\) appears before \(v\) in \(\sigma\). By 64 , we see that each \(v\) is an inverse descent of \(\mathring{\sigma}_{n,k}\) for \(k+1\le v\le n-1\). Since the final segment is decreasing, while the initial segment \(12\cdots k\) is increasing and \(k\) appears before \(k+1\). Hence, \(k\) is also an inverse descent of \(\mathring{\sigma}_{n,k}\). \[\label{ides-T958} \mathrm{ides}(\mathring{\sigma}_{n,k})=n-k-1.\tag{69}\]

It remains to determine the number of pixed points. For \(\mathring{\sigma}_{n,k}\), the initial increasing part is \(12\cdots k,\) and the remaining suffix is the decreasing word \(n(n-1)\cdots(k+1),\) of length \(n-k\). We distinguish two cases according to the parity of \(n-k\). If \(n-k\) is even, then the decreasing suffix \(n(n-1)\cdots(k+1)\) is a desarrangement. Thus the pixed factorization is \[\mathring{\sigma}_{n,k} = \underbrace{12\cdots k}_{\iota} \, \underbrace{n(n-1)\cdots(k+1)}_{\delta},\] and consequently \(\mathrm{pix}(\mathring{\sigma}_{n,k})=k.\)

If \(n-k\) is odd, then the decreasing suffix \(n(n-1)\cdots(k+1)\) is not a desarrangement. In this case, the first letter \(n\) of the final segment must be included in the increasing prefix. The remaining suffix \((n-1)(n-2)\cdots(k+1)\) has even length and is therefore a desarrangement. Hence the pixed factorization is \[\mathring{\sigma}_{n,k} = \underbrace{12\cdots k\,n}_{\iota} \, \underbrace{(n-1)(n-2)\cdots(k+1)}_{\delta},\] and so \(\mathrm{pix}(\mathring{\sigma}_{n,k})=k+1\). Thus, in all cases, we have \[\label{pix-T958} \mathrm{pix}(\mathring{\sigma}_{n,k}) = k+\chi(n-k\;\text{is odd}).\tag{70}\] Combining 69 and 70 , we obtain, for fixed \(n\ge1\), \[\label{rec-P-T958} \sum_{\sigma\in\mathfrak{S}_n(T_8)} x^{\operatorname{ides}(\sigma)} y^{\operatorname{pix}(\sigma)} = \sum_{k=0}^{n-1} x^{n-k-1} y^{k+\chi(n-k\;\text{is odd})}.\tag{71}\] Since the right-hand side of 71 is identical to that of 67 , the same summation argument as above gives \(F_{T_8}(t;x,y)=P_{T_8}(t;x,y)\). Hence, by ?? , we obtain the desired formula. ◻