---
abstract: 'Let $\mathcal{A}_k$ be the set of permutations in the symmetric group $\SS_k$ with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns $\mathcal{A}_k$. We present a bijection between symmetric Schröder paths of length $2n$ and involutions of length $n+1$ avoiding $\mathcal{A}_4$. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schröder path of a particular type. For each $k\geq 3$ we determine the generating function for the number of involutions avoiding the subsequences in $\mathcal{A}_k$, according to length, first entry and number of fixed points.'
address:
- 'Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, P.R. China.'
- 'Science Institute, University of Iceland, Reykjavík, Iceland.'
- 'Department of Mathematics, University of Haifa, Haifa 31905, Israel.'
- 'Department of Mathematics, Tianjin Normal University, Tianjin 300387, P.R. China.'
author:
- 'Eva Y. P. Deng, Mark Dukes, Toufik Mansour and Susan Y. J. Wu'
title:  Symmetric Schröder paths and restricted involutions 
---

Introduction
============

Let $\SS_n$ denote the set of permutations of $[n]=\{1,\ldots,n\}$, written in one-line notation. For two permutations $\pi\in\SS_n$ and $\tau\in\SS_k$, an [*occurrence*]{} of $\tau$ in $\pi$ is a subsequence $1\ls i_1<i_2<\dots<i_k\ls n$ such that $(\pi_{i_1},
\dots,\pi_{i_k})$ is order-isomorphic to $\tau$; in such a context $\tau$ is usually called a [*pattern*]{}. We say that $\pi$ [*avoids*]{} $\tau$, or is $\tau$-[*avoiding*]{}, if there is no occurrence of $\tau$ in $\pi$. A natural generalization of single pattern avoidance is [*subset avoidance*]{}, that is, we say that $\pi\in\SS_n$ avoids a subset $T\subseteq\SS_k$ if $\pi$ avoids all $\tau\in T$. The set of all $\tau$-avoiding (resp. $T$-avoiding) permutations of length $n$ is denoted $\SS_n(\tau)$ (resp. $\SS_n(T)$).

Several authors have considered the case of general $k$ in which $T$ enjoys various algebraic properties. Barcucci et al. [@BDPP] treat the case of permutations avoiding the collection of permutations in $\SS_k$ that have suffix $(k-1)k$. Adin and Roichman [@AR] look at the case where $T$ is a Kazhdan–Lusztig cell of $\SS_k$, or, equivalently, a Knuth equivalence class (see [@St Vol. 2, Ch. A1]). Mansour and Vainshtein [@MV] consider the situation where $T$ is a maximal parabolic subgroup of $\SS_k$.

In the current paper an analogous result is established for pattern-avoiding involutions. We say $\pi$ is an [*involution*]{} whenever $\pi_{\pi_i} = i$ for all $i\in[n]$. Let $\mathcal{I}_n$ denote the set of involutions of $[n]$. The set of all $\tau$-avoiding (resp. $T$-avoiding) involutions of length $n$ is denoted $\mathcal{I}_n(\tau)$ (resp. $\mathcal{I}_n(T)$).

Simion and Schmidt [@SS] considered the first cases of pattern-avoiding involutions, which was continued in Gouyou-Beauchamps [@G-B] and Gessel [@Ge] for increasing patterns, and subsequently in Guibert’s Ph.D. thesis [@Gu]. This paper concerns the enumeration of involutions which avoid the class of permutations in $\SS_k$ with prefix 12, that is, $$\mathcal{A}_k=\{\pi_1\pi_2\ldots\pi_k\in \SS_k\mid\pi_1=1,\pi_2=2\}.$$

We denote by $I_n$ the cardinality of the set $\mathcal{I}_n$. We say that $i$ is a fixed point of a permutation $\pi$ if $\pi_i=i$. Define $J_n(p)$ to be the polynomial $\sum_{j=0}^n I_{n;j}p^j$, where $I_{n;j}$ is the number of involutions in $\mathcal{I}_n$ with $j$ fixed points. For example $J_3(p)=3p+p^3$. It is not hard to see that the polynomials $J_n(p)$ satisfy the recurrence relation $J_n(p)=pJ_{n-1}(p)+(n-1)J_{n-2}(p)$, $n\geq2$, with the initial conditions $J_0(p)=1$ and $J_1(p)=p$. The exponential generating function for the sequence $\{J_n(p)\}_{n\geq 0}$ is given by $e^{px+x^2/2}$.

The main result of this paper can be formulated as follows.

\[thmain\] Let $k\geq2$. The generating function for the number of $\mathcal{A}_k$-avoiding involutions of length $n$ is given by\
$$\begin{aligned}
\lefteqn{\displaystyle\sum\limits_{n\geq0}\sum\limits_{\pi\in{\mathcal{I}}_n (\mathcal{A}_k)}x^np^{\#\mbox{\scriptsize{fixed points}}(\pi)} \;=\;}\\[8pt]
&&\displaystyle\sum_{j=0}^{k-3}J_j(p)x^j-\dfrac{x^{k-3}}{2}\biggl(p+(p(k-3)x^2-2x-p)u_0(x)\biggr) J_{k-2}(p)\\[8pt]
&&-\;\dfrac{x^{k-4}}{2}\biggl(x+p-(x^3(k-3)-px^2(k-1)+x+p)u_0(x)\biggr)J_{k-3}(p),\\\end{aligned}$$ where $u_0(x)=1/{\sqrt{1-2(k-1)x^2+(k-3)^2x^4}}$.

The proof is given in Section 3. Theorem \[thmain\] with $k=3$ and $p=1$ shows the generating function for the number $123$-avoiding involutions of length $n$ to be $\frac{2x}{2x-1+\sqrt{1-4x^2}}=\sum_{n\geq0}\binom{n}{\lfloor n/2\rfloor}x^n$ (see [@SS]). Also, Theorem \[thmain\] with $k=3$ and $p=0$ gives the number of $123$-avoiding involutions of length $2n$ without fixed points to be $\frac{1}{2}\binom{n}{\lfloor n/2\rfloor}$. Moreover, Theorem \[thmain\] with $k=4$ and $p=1$ gives the generating function for the number $\{1234,1243\}$-avoiding involutions of length $n$ to be $\frac{1-x}{2}+\frac{1+x}{2}\sqrt{\frac{1+2x-x^2}{1-2x-x^2}}$. In Section 2 we present a bijection between symmetric Schröder paths of length $n-1$ and $\{1234,1243\}$-avoiding involutions of length $n$, thereby providing a combinatorial proof of the above result with $k=4$.

Symmetric Schröder paths and $\{1234,1243\}$-avoiding involutions
=================================================================

A [*[Schröder path]{}*]{} of length $2n$ is a lattice path from (0,0) to $(2n,0)$ consisting of double horizontal steps ${\mathsf{h}}=(2,0)$, up steps ${\mathsf{u}}=(1,1)$ and down steps ${\mathsf{d}}=(1,-1)$ that never goes below the $x$-axis. The set of all Schröder paths of length $2n$ is enumerated by the $n$-th Schröder number. Kremer [@Kr Corollary 9] showed that $\SS_n(1243, 2143)$ is also enumerated by the $n$-th Schröder number.

A Schröder path of length $2n$ is called [*[symmetric]{}*]{} if it is symmetric about the line $x=n$. Let ${\mathsf{Sh}}_n$ be the collection of all such paths. In this section we give a bijection between [*[symmetric Schröder paths]{}*]{} of length $2n$ and the class of involutions in ${\mathfrak{S}}_{n+1}$ that avoid the patterns $\{1234,1243\}$.

We will now describe a map $\phi: {\mathsf{Sh}}_n \to {\mathcal{I}}_{n+1}(1234,1243)$. Alongside this description will be an example of the map acting on the path $p={\mathsf{u}}{\mathsf{h}}{\mathsf{u}}{\mathsf{d}}{\mathsf{u}}{\mathsf{u}}{\mathsf{d}}{\mathsf{h}}{\mathsf{u}}{\mathsf{d}}{\mathsf{d}}{\mathsf{u}}{\mathsf{d}}{\mathsf{h}}{\mathsf{d}}\in {\mathsf{Sh}}_9$. Several points may at first appear extraneous, however these will be required in the proof of the Theorem which follows.

Given $p\in{\mathsf{Sh}}_n$, let $p'$ be the word of length $n+1$ obtained from $p$ by first appending a horizontal step ${\mathsf{h}}$ to the end, then replacing all occurrences of ${\mathsf{u}}{\mathsf{d}}$ in $p$ by ${\mathsf{r}}$, and finally deleting all remaining ${\mathsf{d}}$’s. This is equivalent to projecting the steps of the path onto the diagonal, and replacing any ${\mathsf{u}}$’s that are followed by a ${\mathsf{d}}$ by ${\mathsf{r}}$.

From the diagram the example path is $p'\,=\, {\mathsf{u}}{\mathsf{h}}{\mathsf{r}}{\mathsf{u}}{\mathsf{r}}{\mathsf{h}}{\mathsf{r}}{\mathsf{r}}{\mathsf{h}}{\mathsf{h}}$. In general, $p'=p_1\ldots p_{n+1} \in \{{\mathsf{u}},{\mathsf{r}},{\mathsf{h}}\}^{n+1}$. Now form the three sets $A_{{\mathsf{h}}},A_{{\mathsf{r}}},A_{{\mathsf{u}}}$ according to the rule $i \in A_{x}$ if $p_i = x$.

In the example, $A_{{\mathsf{h}}}\,=\, \{2,6,9,10\}$, $A_{{\mathsf{r}}}\,=\, \{3,5,7,8\}$ and $A_{{\mathsf{u}}} \, = \, \{1,4\}$.

Starting with the largest entry in $A_{{\mathsf{h}}}$, replace all ${\mathsf{h}}$’s in $p'$ (from left to right) with the entries from $A_{{\mathsf{h}}}$ so that this sequence is decreasing. This is equivalent to forming a sequence of transpositions (or a fixed point), the first of which will have as first entry the index of the first ${\mathsf{h}}$ in $p'$ and whose second entry is the index of the last ${\mathsf{h}}$ in $p'$. The second transposition (or fixed point) will have as first entry the index of the second ${\mathsf{h}}$ in $p'$ and whose second entry is the index of the second last ${\mathsf{h}}$ in $p'$, and so forth.

Since $A_{{\mathsf{h}}}\,=\, \{2,6,9,10\}$ in the example, we have the transpositions $(2,10)$ and $(6,9)$.

Do likewise for the sets $A_{{\mathsf{r}}}$ and $A_{{\mathsf{u}}}$. The [*[label]{}*]{} of a particular ${\mathsf{h}}$, ${\mathsf{r}}$ or ${\mathsf{u}}$ in $p'$ is the value that replaces it. Call the resulting permutation $\pi = \phi(p)$, i.e. the labels of $p'$ read from left to right.

The label of the first ${\mathsf{h}}$ in $p'$ above is 10 and the label of the third ${\mathsf{h}}$ in $p'$ above is 6. In the example, since $A_{{\mathsf{h}}}\,=\, \{2,6,9,10\}$, $A_{{\mathsf{r}}}\,=\, \{3,5,7,8\}$ and $A_{{\mathsf{u}}} \, = \, \{1,4\}$, $\pi=\phi(p)$ is the permutation (involution) with cycles $(2,10), (6,9), (3,8), (5,7)$ and $(1,4)$. Thus we have $\phi(p) \,=\, (4,10,8,1,7,9,5,3,6,2).$

Another way to see this construction is in terms of layers of right-to-left maxima. An element $\pi_i$ of a permutation $\pi$ is called a [*right-to-left maximum*]{} if it is greater than all elements that follow it, i.e. $\pi_i>\pi_j$ for all $j>i$. We define successively the $r$-right-to-left maxima for a permutation $\pi\in\SS_n$. Let $\pi^{(1)}$ be the word consisting of all elements of $\pi$. For $r\ge 1$, the right-to-left maxima of $\pi^{(r)}$ are called [*$r$-right-to-left maxima*]{} of $\pi$. Let $\pi^{(r+1)}$ be the subword obtained from $\pi^{(r)}$ by removing all $r$-right-to-left maxima. For example, the permutation $\pi=  674583912\in \SS_{9}$ has the 1-right-to-left maxima 9 and 2; the 2-right-to-left maxima 8, 3 and 1; the 3-right-to-left maxima 7 and 5; and the 4-right-to-left maxima 6 and 4. Note that the $r$-right-to-left maxima of $\pi$ form a decreasing subsequence for each $r$.

Let $\pi$ be the unique permutation (in fact, it will be an involution) in $\SS_{n+1}$ with 1 right-to-left maxima $A_{{\mathsf{h}}}$, 2 right-to-left maxima $A_{{\mathsf{r}}}$ and 3 right-to-left maxima $A_{{\mathsf{u}}}$. If $A_{{\mathsf{h}}}=\{x_1,\ldots , x_{\alpha}\}$, $A_{{\mathsf{r}}}=\{y_1,\ldots , y_{\beta}\}$ and $A_{{\mathsf{u}}}=\{z_1,\ldots , z_{\gamma}\}$ then the cycles of $\pi$ are $$(x_1\, x_{\alpha})\, (x_2 \, x_{\alpha -1})\, \cdots\, (y_1 \, y_{\beta}) \, (y_2 \, y_{\beta -1})\, \cdots \,(z_1 \, z_{\gamma}) \, (z_2\, z_{\gamma -1}) \, \cdots.$$ We point out that if $\gamma = 2m+1$ then $(x_{m+1})$ will be a fixed point. Consequently there will be at most three fixed points in the resulting involution.

The inverse map $\phi^{-1}$ is described by means of an example. Consider $$\pi\, =\,(10,5,8,7,2,6,4,3,9,1)\in{\mathcal{I}}_{10}(1234,1243).$$ The sets of 1, 2 and 3 right-to-left maxima are $A_{{\mathsf{h}}}=\{1,9,10\}$, $A_{{\mathsf{r}}}=\{3,4,6,7,8\}$ and $A_{{\mathsf{u}}}=\{2,5\}$, respectively. This gives $p'= {\mathsf{h}}{\mathsf{u}}{\mathsf{r}}{\mathsf{r}}{\mathsf{u}}{\mathsf{r}}{\mathsf{r}}{\mathsf{r}}{\mathsf{h}}{\mathsf{h}}$. After removing the final ${\mathsf{h}}$, we have

Beginning with the last step (at position 9), we push this down so that it is symmetric with the first entry. We then move the second step of $p'$ down to meet the path. It is ${\mathsf{u}}$ so there must be a ${\mathsf{d}}$ inserted at the opposite end so the path is symmetric.

Next we move the ${\mathsf{r}}$ at position 3 down to touch the evolving path, and move the ${\mathsf{r}}$ at position 8 down to meet the path above the ${\mathsf{d}}$ step.

The ${\mathsf{u}}$ at position 4 is moved next but we must insert a ${\mathsf{d}}$ step between positions 6 and 7 to ensure the path is symmetric.

Finally, move the remaining pieces down, inserting ${\mathsf{d}}$’s where appropriate.

Thus we have $p\;=\;\phi^{-1}(\pi)\;=\;{\mathsf{h}}{\mathsf{u}}{\mathsf{u}}{\mathsf{d}}{\mathsf{u}}{\mathsf{d}}{\mathsf{u}}{\mathsf{u}}{\mathsf{d}}{\mathsf{d}}{\mathsf{u}}{\mathsf{d}}{\mathsf{u}}{\mathsf{d}}{\mathsf{d}}{\mathsf{h}}.$

The map $\phi: {\mathsf{Sh}}_n \to {\mathcal{I}}_{n+1}(1234,1243)$ is a bijection.

We first show that for any $p \in {\mathsf{Sh}}_n$, the corresponding $\pi=\phi(p) \in
{\mathcal{I}}_{n+1}(1234,1243)$.

Let $p \in {\mathsf{Sh}}_n$ and $p'=p_1\cdots p_k$ be the corresponding word on the alphabet $\{{\mathsf{u}},{\mathsf{r}},{\mathsf{h}}\}$. Suppose that $A_{{\mathsf{h}}} = \{i_1,\ldots , i_\ell\}$. Then it is clear that $\pi_{i_j} = i_{\ell+1-j}$ for all $1\leq j \leq \ell$. The same is true for the sets $A_{{\mathsf{r}}}$ and $A_{{\mathsf{u}}}$ so $\pi$ is an involution.

From the labelling scheme above, the resulting permutation $\pi$ has, at most, three levels of right-to-left maxima. It is therefore 1234 avoiding. To show that $\pi$ is 1243-avoiding, suppose $\pi$ contains a 1243 pattern $\pi_i \pi_j \pi_k \pi_{\ell}$, where $\pi_i < \pi_j < \pi_{\ell} < \pi_k$ and $i<j<k<\ell$. The 4 and 3 of the pattern ($\pi_k$ and $\pi_{\ell}$) must be in the 1 right-to-left maxima $A_{{\mathsf{h}}}$. Similarly, the 2 (resp. 1) of the pattern must be in the 2 (resp. 3) right-to-left maxima $A_{{\mathsf{r}}}$ (resp. $A_{{\mathsf{u}}})$. Then $\pi_j\pi_k\pi_{\ell}$ is a 132-pattern with $\pi_j \in A_{{\mathsf{r}}}$ and $\pi_{k},\pi_{\ell} \in A_{{\mathsf{h}}}$. This is not possible for the following reason: Given ${\mathsf{r}}$ in $p'$ with label $r_1$, let $h_1,h_2,\ldots $ be the sequence of labels of ${\mathsf{h}}$’s to the right of ${\mathsf{r}}$. Then $h_1>r_1>h_2,h_3,\ldots$. This statement is easily seen by removing all ${\mathsf{u}}$’s and the suffix ${\mathsf{h}}$ from $p'$ and relabelling. (This relabelling always gives a monotone decreasing sequence.) The fact that the label of the first ${\mathsf{h}}$ after ${\mathsf{r}}$ is greater than the label of the ${\mathsf{r}}$ is due to the appended ${\mathsf{h}}$.

We now show how to construct the unique path $p$ corresponding to $\pi \in
{\mathcal{I}}_{n+1}(1234,1243)$. For such a permutation, let $A_{{\mathsf{h}}}$, $A_{{\mathsf{r}}}$ and $A_{{\mathsf{u}}}$ be the 1, 2 and 3 right-to-left maxima of $\pi$, respectively. Insert ${\mathsf{h}}$ at position $i$ of $p'$ if $i \in A_{{\mathsf{h}}}$ and do likewise for the sets $A_{{\mathsf{r}}}$ and $A_{{\mathsf{u}}}$. Remove the suffix ${\mathsf{h}}$ from $p'$ (it is a suffix since $(n+1)$ is one of the 1 right-to-left maxima). From right to left in $p'$, insert a ${\mathsf{d}}$ where there is a corresponding ${\mathsf{u}}$ and finish by replacing all occurrences of ${\mathsf{r}}$ with ${\mathsf{u}}{\mathsf{d}}$. (As was done in the example that preceded the Theorem.) We note that for each $p'$ there will be several Schröder paths to which it may correspond, however only one of these is symmetric.

From the construction, we also have the following statistics of $\{1234, 1243\}$-avoiding involutions:

Let $p \in {\mathsf{Sh}}_n$ with $h$ steps ${\mathsf{h}}$, $r$ steps ${\mathsf{u}}{\mathsf{d}}$, and $u$ steps ${\mathsf{u}}$ that are not directly followed by a ${\mathsf{d}}$ step. Let $\pi=\phi(p) \in \mathcal{I}_n(1234, 1243)$.

1.  The number of right-to-left maxima of $\pi$ is $h+1$.

2.  The number of 2 right-to-left maxima of $\pi$ is $r$.

3.  The number of 3 right-to-left maxima of $\pi$ is $u$.

4.  The number of fixed points of $\pi$ is $((1+h) \mbox{ mod } 2) \; +\;( r\mbox{ mod }2) \; + \; (u \mbox{ mod } 2)$.

What statistic on $\pi=\phi(p)$ corresponds to the height of the path $p$?

Proof of Theorem \[thmain\]
===========================

To present the proof of Theorem \[thmain\], we must first consider the enumeration problem for the number $\mathcal{F}_k$-avoiding involutions according to length and number of fixed points, where $\mathcal{F}_k$ is the set of all permutations $\sigma\in\SS_k$ with $\sigma_1=1$.

Involutions avoiding $\mathcal{F}_k$
------------------------------------

In this subsection we present an explicit formula for the number of involutions that avoid all the patterns in $\mathcal{F}_k$. To do so we require some new notation. Define $f_k(n)$ to be the number of involutions $\pi\in\mathcal{I}_n(\mathcal{F}_k)$. Given $t\in[n]$, we also define $$f_{k;m}(n;t)=\#\{\pi\in\mathcal{I}_n(\mathcal{F}_k)\mid
 \pi_1=t\mbox{ and }\pi\mbox{ contains }m\mbox{ fixed points}\}.$$ Let $f_k(n;t)=f_k(n,p;t)$ and $f_k(n)=f_k(n,p)$ be the polynomials $\sum_{m=0}^nf_{k;m}(n;t)p^m$ and $\sum_{t=1}^nf_{k}(n;t)$, respectively. We denote by $F_k(x,p)$ the generating function for the sequence $f_k(n,p)$, that is $F_k(x,p)=\sum_{n\geq0} f_k(n,p)x^n$.

\[thmm1\] We have $$F_k(x,p)\;=\;\sum_{j=0}^{k-2}J_j(p)x^j+\frac{x^{k-1}}{1-(k-1)x^2}((k-1)J_{k-2}(p)x+J_{k-1}(p)).$$ Moreover, the number of involutions of length $k+2n$ (resp. $k+2n-1$) that avoid all the patterns in $\mathcal{F}_k$ is given by $(k-1)^{n+1}I_{k-2}$ (resp. $(k-1)^{n}I_{k-1}$), for all $n\geq0$.

Let $\pi\in\SS_n$ be a permutation that avoids all patterns in $\mathcal{F}_k$. We have $\pi_1\geq n+2-k$. Thus $\pi\in\mathcal{I}_n(\mathcal{F}_k)$ with $\pi_1=t\geq n+2-k$ if and only if $\pi_2\ldots\pi_{t-1}\pi_{t+1}\ldots\pi_n$ is an involution on the numbers $2,\ldots,t-1,t+1,\ldots,n$ that avoids all the patterns in $\mathcal{F}_k$. Hence, $f_k(n;j)=f_k(n-2)$ for all $j=n+2-k,n+3-k,\ldots,n$, and $f_k(n,j)=0$ for all $j=1,2,\ldots,n+1-k$, where $n\geq k$. Thus, for $n\geq k$, $$f_k(n)\;=\;(k-1)f_k(n-2).$$ Using the initial conditions $f_k(j)=J_{j}(p)$, $j=1,2,\ldots,k-1$, we find that $f_k(k+2j)=(k-1)^{j+1}J_{k-1}(p)$ and $f_k(k+2j-1)=(k-1)^jJ_{k-2}(p)$ for all $j\geq0$. Rewriting these formulas in terms of generating functions we obtain $$F_k(x,p)=\sum_{j=0}^{k-2}J_j(p)x^j+\frac{x^{k-1}}{1-(k-1)x^2}((k-1)J_{k-2}(p)x+J_{k-1}(p)),$$ as claimed.

Involutions avoiding $\mathcal{A}_k$
------------------------------------

In this subsection we prove Theorem \[thmain\]. In order to do this, define $g_k(n)$ to be the number of involutions $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ and given $t_1,t_2,\ldots,t_m\in\mathbb{N}$, we also define $$g_k(n;t_1,t_2,\ldots,t_m) \;=\; \#\{\pi_1\ldots\pi_n\in\mathcal{I}_n(\mathcal{A}_k)\mid \pi_1\ldots\pi_m
 =t_1\ldots t_m\}.$$

\[lem1\] Let $k\geq3$. For all $3\leq t\leq n+1-k$, $$g_k(n;t)\;=\;(k-2)g_k(n-2;t-1)+\sum_{j=1}^{t-2}g_k(n-2;j),$$ with the initial conditions $g_k(n;1)=f_{k-1}(n-1)$, $g_k(n;2)=f_{k-1}(n-2)$, and $g_k(n;t)=g_k(n-2)$ for all $t=n+2-k,n+3-k,\ldots,n$.

Let $\pi$ be any involution of length $n$ that avoids all patterns in $\mathcal{A}_k$ with $\pi_1=t$. Now let us consider all possible values of $t$. If $t=1$ then $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ if and only if $(\pi_2-1)(\pi_3-1)\ldots(\pi_n-1)\in\mathcal{I}_{n-1}(\mathcal{F}_{k-1})$. If $t=2$ then $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ if and only if $(\pi_3-2)(\pi_4-2)\ldots(\pi_n-2)\in\mathcal{I}_{n-2}(\mathcal{F}_{k-1})$. Now assume that $3\leq t\leq n+1-k$, then from the above definitions $$\begin{array}{l}
g_k(n;t) \;=\; g_k(n;t,1)+\ldots+g_k(n;t,t-1)+g_k(n;t,t+1)+\cdots+g_k(n;t,n).
\end{array}$$ But any involution $\pi$ satisfying $\pi_1<\pi_2\leq n+2-k$ contains a pattern from the set $\mathcal{A}_k$ (see the subsequence of the letters $\pi_1,\pi_2,
n+3-k,n+4-k,\ldots,n$ in $\pi$). Thus $g_k(n;t,r)=0$ for all $t<r\leq n+2-k$ and so $$\begin{array}{l}
g_k(n;t) \;=\; g_k(n;t,1)+\ldots+g_k(n;t,t-1)+g_k(n;t,n+3-k)+\cdots+g_k(n;t,n).
\end{array}$$ Also, if $\pi$ is an involution in $\mathcal{I}_n$ with $\pi_1=t$ and $\pi_2=r\geq
n+3-k$, then the entry $r$ does not appear in any occurrence of $\tau\in\mathcal{A}_k$ in $\pi$. Thus, there exists a bijection between the set of involutions $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ with $\pi_1=t$ and $\pi_2=r\geq n+3-k$ and the set of involutions $\pi'\in\mathcal{I}_{n-2}(\mathcal{A}_k)$ with $\pi'=t-1$. Therefore $g_k(n;t,r)=g_k(n-2;t-1)$ which gives $$\begin{array}{l}
g_k(n;t) \;=\; g_k(n;t,1)+\ldots+g_k(n;t,t-1)+(k-2)g_k(n-2;t-1).
\end{array}$$ Also, if $\pi$ is an involution in $\mathcal{I}_n$ with $\pi_1=t$, $\pi_2=r<t$ and if $ta_2\ldots a_k$ is an occurrence of a pattern from the set $\mathcal{A}_k$ in $\pi$, then $ra_2\ldots a_k$ is an occurrence of a pattern from the set $\mathcal{A}_k$ in $\pi$. Thus, there exists a bijection between the set of involutions $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ with $\pi_1=t$ and $\pi_2=r<t$ and the set of involutions $\pi'\in\mathcal{I}_{n-2}(\mathcal{A}_k)$ with $\pi'_1=r-1$. Therefore $g_k(n;t,r)=g_k(n-2;r-1)$ which gives $$\begin{array}{l}
g_k(n;t)\;=\;(k-2)g_k(n-2;t-1)+\displaystyle\sum_{j=1}^{t-2} g_k(n-2;j),
\end{array}$$ as required. Finally, if $\pi$ is an involution in $\mathcal{I}_n$ with $\pi_1=t\geq
n+2-k$, then the entry $t$ does not appear in any occurrence of $\tau\in\mathcal{A}_k$ in $\pi$. Thus, there exists a bijection between the set of involutions $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ with $\pi_1=t\geq n+2-k$ and the set of involutions $\pi'\in\mathcal{I}_{n-2}(\mathcal{A}_k)$. Therefore $g_k(n;t)=g_k(n-2)$, as claimed.

Let $G_k(n;v)$ be the polynomial $\sum_{t=1}^ng_k(n;t)v^{t-1}$. Rewriting the above lemma in terms of the polynomials $G_k(n;v)$ we have the following recurrence relation.

\[lem2\] Let $k\geq3$. For all $n\geq k$, $$\begin{array}{lcl}
\lefteqn{G_k(n;v)}\\
&=&f_{k-1}(n-1)+vf_{k-1}(n-2)-v(k-2)f_{k-1}(n-3)+\left(\frac{v^2}{1-v}+(k-2)v\right)G_k(n-2;v)\\
&&-\frac{v^n}{1-v}G_k(n-2;1)+\frac{v^{n-1}}{1-v}\left(k-2+\frac{v-v^{3-k}}{1-v}\right)G_k(n-4;1),
\end{array}$$ where $G_k(n;v)=I_{n-1}+\frac{v-v^n}{1-v}I_{n-2}$ for all $n=0,1,\ldots,k-1$.

Lemma \[lem1\] gives $$\begin{array}{cl}
\lefteqn{G_k(n;v)}\\
=&f_{k-1}(n-1)+vf_{k-1}(n-2)+\displaystyle\sum_{t=2}^{n-k}v^t\left((k-2)G_k(n-2;t)+\displaystyle\sum_{j=1}^{t-1}G_k(n-2;j)\right)\\
&+ G_k(n-2;1) \displaystyle\sum_{t=n+1-k}^{n-1}v^t\\
=& f_{k-1}(n-1)+vf_{k-1}(n-2)+\frac{v^2}{1-v}\left(G_k(n-2;v)-G_k(n-4;1)\displaystyle\sum_{j=n-1-k}^{n-3}v^j\right)\\
&-\frac{v^{n+1-k}}{1-v}(G_k(n-2;1)-(k-1)G_k(n-4;1))+\frac{v^{n+1-k}-v^n}{1-v}G_k(n-2;1)\\
&+(k-2)v\left(G_k(n-2;v)-f_{k-1}(n-3)-G_k(n-4;1)\displaystyle\sum_{j=n-k}^{n-3}v^j\right),
\end{array}$$ which is equivalent to $$\begin{array}{ll}
\lefteqn{G_k(n;v)}\\
=&f_{k-1}(n-1)+vf_{k-1}(n-2)-v(k-2)f_{k-1}(n-3)+\left(\frac{v^2}{1-v}+(k-2)v\right)G_k(n-2;v)\\
&-\frac{v^n}{1-v}G_k(n-2;1)+\frac{v^{n-1}}{1-v}\left(k-2+\frac{v-v^{3-k}}{1-v}\right)G_k(n-4;1).
\end{array}$$ To find the value of $G_k(n;v)$ for $n\leq k-1$, let $\pi$ be any involution with $\pi_1=t$. If $t=1$ then there are $I_{n-1}$ involutions, whereas if $t>1$ there are $I_{n-2}$ involutions, hence $G_k(n;v)=v^0I_{n-1}+\sum_{t=2}^nv^{t-1}I_{n-2}=I_{n-1}+\frac{v-v^n}{1-v}I_{n-2}$, as required.

Lemma \[lem2\] can be generalised as follows; let $g_{k;m}(n;t)$ be the number of involutions $\pi\in\mathcal{I}_n(\mathcal{A}_k)$ such that $\pi_1=t$ and $\pi$ contains exactly $m$ fixed points. Define $G_k(n;t;p)=\sum_{m=0}^ng_{k;m}(n;t)p^m$ and $G_k(n;v,p)=\sum_{t=1}^nG_k(n;t;p)v^{t-1}$. Using the same arguments as those in the proofs of Lemma \[lem1\] and Lemma \[lem2\], while carefully considering the number of fixed points, we have the following result.

\[lem3\] Let $k\geq3$. For all $n\geq k$, $$\begin{array}{ll}
\lefteqn{G_k(n;v,p)}\\
=&pf_{k-1}(n-1)+vf_{k-1}(n-2)-pv(k-2)f_{k-1}(n-3)+\left(\frac{v^2}{1-v}+(k-2)v\right)G_k(n-2;v,p)\\
&-\frac{v^n}{1-v}G_k(n-2;1,p)+\frac{v^{n-1}}{1-v}\left(k-2+\frac{v-v^{3-k}}{1-v}\right)G_k(n-4;1,p),
\end{array}$$ where $G_k(n;v,p)=pJ_{n-1}(p)+\frac{v-v^n}{1-v}J_{n-2}(p)$ for all $n=0,1,\ldots,k-1$.

Let $G_k(x,v,p)=\sum_{n\geq0}G_k(n;v,p)x^n$ be the generating function for the sequence $G_k(n;v,p)$. Define $J_i(v,p)$ to be the polynomial $\sum d_{tr}v^tp^r$ where $d_{tr}$ is the number of involutions $\pi\in\mathcal{I}_i$ such that $\pi_1=t+1$ and $\pi$ contains exactly $r$ fixed points. Rewriting the recurrence relation in the statement of Lemma \[lem3\] in terms of generating functions we obtain $$\begin{array}{l}
\lefteqn{G_k(x,v,p)\;=\;}\\
\sum\limits_{j=0}^{k-1}J_j(v,p)x^j+px\left(F_{k-1}(x,p)-\sum\limits_{j=0}^{k-2}J_j(p)x^j\right)+vx^2\left(F_{k-1}(x,p)-\sum\limits_{j=0}^{k-3}J_j(p)x^j\right)\\
-(k-2)pvx^3\left(F_{k-1}(x,p)-\sum\limits_{j=0}^{k-4}J_j(p)x^j\right)-\frac{v^2x^2}{1-v}\left(G_k(xv,1,p)-\sum\limits_{j=0}^{k-3}J_j(p)(xv)^j\right)\\
+vx^2\left(\frac{v}{1-v}+k-2\right)\left(G_k(x,v,p)-\sum\limits_{j=0}^{k-3}J_j(v,p)x^j\right)\\
+\frac{(k-2)v^3x^4}{1-v}\left(G_k(xv,1,p)-\sum\limits_{j=0}^{k-5}J_j(p)(xv)^j\right)
-\frac{x^4(1-v^{k-2})}{v^{k-6}(1-v)^2}\left(G_k(xv,1,p)-\sum\limits_{j=0}^{k-5}J_j(p)(xv)^j\right),
\end{array}$$ which is equivalent to $$\begin{array}{l}
\left(1-\frac{x^2}{1-v}-(k-2)\frac{x^2}{v}\right)G_k(x/v,v,p) \; = \; \\
-\frac{x^2}{1-v}\left(1-(k-2)\frac{x^2}{v}+\frac{x^2(1-v^{k-2})}{v^{k-2}(1-v)}\right)G_k(x,1,p)\\
+\sum\limits_{j=0}^{k-1}J_j(v,p)\frac{x^j}{v^j}+\frac{px}{v}\left(F_{k-1}(x/v,p)-\sum\limits_{j=0}^{k-2}J_j(p)\frac{x^j}{v^j}\right)+\frac{x^2}{v}\left(F_{k-1}(x/v,p)-\sum\limits_{j=0}^{k-3}J_j(p)\frac{x^j}{v^j}\right)\\
-(k-2)p\frac{x^3}{v^2}\left(F_{k-1}(x/v,p)-\sum\limits_{j=0}^{k-4}J_j(p)\frac{x^j}{v^j}\right)+\frac{x^2}{1-v}\sum\limits_{j=0}^{k-3}J_j(p)x^j\\
-\frac{x^2}{v}\left(\frac{v}{1-v}+k-2\right)\sum\limits_{j=0}^{k-3}J_j(v,p)\frac{x^j}{v^j}
-\frac{(k-2)x^4}{v(1-v)}\sum\limits_{j=0}^{k-5}J_j(p)x^j+\frac{x^4(1-v^{k-2})}{v^{k-2}(1-v)^2}\sum\limits_{j=0}^{k-5}J_j(p)x^j.
\end{array}$$ To solve this functional equation, we substitute $$v:=v_0=\frac{1}{2}\left(1+(k-3)x^2+\sqrt{1-2(k-1)x^2+(k-3)^2x^4}\right),$$ where $v_0$ is the root of the coefficient of $G_k(x/v,v,p)$ above, into the above functional equation, that is, $1-\frac{x^2}{1-v_0}-(k-2)\frac{x^2}{v_0}=0$. Since $J_j(v,p)=pJ_{j-1}(p)+\frac{v-v^j}{1-v}J_{j-2}(p)$ for all $j=1,2,\ldots,k-1$ and $J_0(v,p)=1$, it is routine to show (via some rather tedious algebraic manipulation) that we obtain Theorem \[thmain\].

[99]{} R. Adin and Yu. Roichman, Shape avoiding permutations, [*[J. Combin. Theory Ser. A]{}*]{} [**[97]{}**]{}(1) (2002), 162–176.

E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, [*Discrete Math. Theor. Comput. Sci.*]{} [**4**]{} (2000), 31–44.

Mireille Bousquet-Mélou and Einar Steingrímsson, Decreasing subsequences in permutations and Wilf equivalence for involutions, [*[J. Algeb. Comb.]{}*]{} [**[22]{}**]{} (2005), 383–409.

Eric S. Egge and Toufik Mansour, Permutations which Avoid 1243 and 2143, Continued Fractions, and Chebyshev Polynomials, [*Elec. J. Combin.*]{} [**[9]{}**]{}(2) (2003), \#R7.

D. Gouyou–Beauchamps, Standard Young tableaux of height $4$ and $5$, [*European J. Combin.*]{} [**10**]{} (1989), 69–82.

I.M. Gessel, Symmetric functions and P-recursiveness, [*J. Combin. Theory Ser. A*]{} [**53**]{} (1990), 257–285.

O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, [*PHD-thesis, University Bordeaux 1, France*]{} (1995).

D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, [*Discrete Math.*]{} [**218**]{} (2000), 121–130.

T. Mansour, Avoiding and containing certain patterns, [*Proceeding’s 12th Conference on Formal Power Series and Algebraic Combinatorics*]{}, Moscow (2000), 706–708.

T. Mansour and A. Vainshtein, Avoiding maximal parabolic subgroups of $S_k$, [*Discrete Math. Theor. Comput. Sci.*]{} [**4**]{} (2000), 67–77.

R. Simion and F.W. Schmidt, Restricted Permutations, [*European J. Combin.*]{} [**6**]{} (1985), 383–406.

R. Stanley, Enumerative Combinatorics, Volume 1-2, 1997, 1999, Cambridge University Press, Cambridge.
