\documentclass[12pt]{article}
 \textwidth= 6.5in
 \textheight= 9.0in
 \topmargin = -20pt
 \evensidemargin=10pt
 \oddsidemargin=0pt
 \headsep=25pt
 \parskip=10pt
 \font\smallit=cmti10
 \font\smalltt=cmtt10
 \font\smallrm=cmr9

\usepackage{latexsym}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{eg}[theorem]{Example}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{note}[theorem]{Note}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{openproblem}[theorem]{Open Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{project}[theorem]{Project}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{conjecture}[theorem]{Conjecture}

\newenvironment{proof}{\noindent{\it Proof.\
}}{\hfill\mbox{$\Box$}}

\begin{document}

\def\eqnsep{50pt}

\def\sof{\hfill\rule{2mm}{2mm}}
\def\ls{\leq}
\def\gs{\geq}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\qq{{\bold q}}
\def\txx{{\frac1{2\sqrt{x}}}}

\vspace*{-60pt} 
\centerline{\smalltt INTEGERS: 
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 
(2005), \#A01} 
\vskip 50pt 




\begin{center}
 \uppercase{\bf Restricted Permutations, Fibonacci Numbers, and $k$-generalized Fibonacci Numbers}
 \vskip 20pt
 {\bf Eric S. Egge}\\
 {\smallit Department of Mathematics, Gettysburg College,
Gettysburg, PA  17325  USA}\\
 {\tt eggee@member.ams.org}\\ 
 \vskip 10pt
 {\bf Toufik Mansour\footnote{Research financed by EC's
IHRP Programme, within the Research Training Network ``Algebraic
Combinatorics in Europe'', grant HPRN-CT-2001-00272}}\\
 {\smallit Department of Mathematics, Haifa University
31905 Haifa, Israel }\\
 {\tt toufik@math.haifa.ac.il}\\
 \end{center}
 \vskip 30pt
 \centerline{\smallit Received: 5/2/04, Accepted: 1/3/05, Published: 2/1/05}
 \vskip 30pt

%\title{Restricted Permutations, Fibonacci Numbers, and $k$-generalized Fibonacci Numbers\footnote{2000
%Mathematics Subject Classification:  Primary 05A15}}
   


\centerline{\bf Abstract}
\noindent
In 1985 Simion and Schmidt showed that the number of permutations in $S_n$ which avoid 132, 213, and 123 is equal to the Fibonacci number $F_{n+1}$.
We use generating function and bijective techniques to give other sets of pattern-avoiding permutations which can be enumerated in terms of Fibonacci or $k$-generalized Fibonacci numbers.

\noindent \footnotesize
{\it Keywords:}
Restricted permutation;  pattern-avoiding permutation;  forbidden subsequence;  Fibonacci number
\normalsize

\pagestyle{myheadings}
 \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005),
\#A01\hfill}

 \thispagestyle{empty} 
 \baselineskip=15pt 
 \vskip 30pt

\section*{\normalsize 1. Introduction and Notation}
\addtocounter{section}{+1}
Let $S_n$ denote the set of permutations of $\{1, \ldots, n\}$, written in one-line notation, and suppose $\pi \in S_n$ and $\sigma \in S_k$.
We say $\pi$ {\it avoids} $\sigma$ whenever $\pi$ contains no subsequence with all of the same pairwise comparisons as $\sigma$.
For example, the permutation 214538769 avoids 312 and 2413, but it has 2586 as a subsequence so it does not avoid 1243.
In this context $\sigma$ is called a {\it pattern} or a {\it forbidden subsequence} and $\pi$ is called a {\it restricted permutation} or a {\it pattern-avoiding permutation}. 
For any permutations $\sigma_1,\ldots,\sigma_k$ we write $S_n(\sigma_1,\ldots,\sigma_k)$ to denote the set of permutations in $S_n$ which avoid $\sigma_1,\ldots,\sigma_k$ and we write $S(\sigma_1,\ldots,\sigma_k)$ to denote the set of permutations of any length which avoid $\sigma_1,\ldots,\sigma_k$.
Pattern avoidance has proved to be a useful language in a variety of seemingly unrelated problems, from stack sorting \cite[Ch. 2.2.1]{KnuthVol1}, to singularities of Schubert varieties \cite{LakSong}, to Chebyshev polynomials of the second kind \cite{CW,Krattenthaler,MansourVainshtein2}, to rook polynomials for a rectangular board \cite{MansourVainshtein3}. 

In this paper we investigate connections pattern-avoiding permutations have with Fibonacci numbers and $k$-generalized Fibonacci numbers.
To define the $k$-generalized Fibonacci numbers, first fix $k \ge 1$.
The sequence of $k$-generalized Fibonacci numbers is given by $F_{k,n} = 0$ for $n \le 0$, $F_{k,1} = 1$, and $F_{k,n} = \sum_{i=1}^k F_{k,n-i}$ for $n \ge 2$.
We observe that $F_{2,n}$ is the ordinary Fibonacci number $F_n$ for all $n \ge 0$.
Moreover, the ordinary generating function for the $k$-generalized Fibonacci numbers is given by
\begin{equation}
\label{eqn:Fkngf}
\sum_{n=0}^\infty F_{k,n} x^n = \frac{x}{1 - x - x^2 - \ldots - x^k} \hspace{30pt} (k \ge 1).
\end{equation}
We will also make use of the fact, which can be verified by induction on $n$, that the number of tilings of a $1 \times n$ rectangle with tiles of size $1 \times 1$, $1 \times 2, \ldots, 1 \times k$ is given by $F_{k,n+1}$ for all $k \ge 1$ and all $n \ge 0$.

In this paper we give families of pattern-avoiding permutations which can be enumerated in terms of Fibonacci numbers or $k$-generalized Fibonacci numbers.
The earliest example of such a result is Simion and Schmidt's proof \cite[Prop. 15]{SimionSchmidt} that 
\begin{equation}
\label{eqn:SimionSchmidtintro}
|S_n(132, 213, 123)| = F_{n+1} \hspace{\eqnsep} (n \ge 0).
\end{equation}
Somewhat later West used generating trees to show \cite{WestGenTrees} that for many sets $R$ consisting of one pattern of length three and one of length four, $|S_n(R)| = F_{2n-1}$.
More recently Mansour expressed \cite[Thm. 8]{Mansour33k} the ordinary generating function for $|S_n(132, 213, \tau)|$ as a determinant for every $\tau \in S_k(132, 213)$.
Using this result, Mansour showed that
\begin{equation}
\label{eqn:2341}
|S_n(132, 213, 2341)| = F_{n+2} - 1 \hspace{30pt} (n \ge 1).
\end{equation}
One can also use \cite[Thm. 8]{Mansour33k} to show that
$$|S_n(132, 213, 12\ldots k)| = F_{k-1,n+1} \hspace{\eqnsep} (k \ge 2),$$
and that if $a$, $b$, and $c$ are nonnegative integers with $b \ge 1$ and $a+c \ge 1$ then
$$\sum_{n=0}^\infty |S_n(132, 213, \beta_{a,b,c})| x^n = \frac{(1-x)^{a+c} +x^b \left( \sum\limits_{i=0}^{a+c-1} (1-x)^i x^{a+c-i+1} \right)}{(1-x)^{a+c} (1 - x - \ldots - x^{b-1})},$$
where $\beta_{a,b,c}$ is the permutation in $S_{a+b+c}$ given by
$$\beta_{a,b,c} = c+b+a, c+b+(a-1), \ldots, c+b+1, c+1, c+2, \ldots, b+c, c, c-1, \ldots, 2,1.$$
Moreover, it is apparent from Mansour's description of the elements of $S_n(132, 213)$ in \cite[Thm. 8]{Mansour33k} that there is a constructive bijection between $S_n(132, 213)$ and the set of tilings of a $1 \times n$ rectangle with tiles of size $1 \times i$, where $i \ge 1$.
One can show that the restriction of this map to $S_n(132, 213, 12\ldots k)$ is a bijection between $S_n(132, 213, 12\ldots k)$ and the set of tilings of a $1 \times n$ rectangle with tiles of size $1 \times 1, 1 \times 2, \ldots, 1 \times (k-1)$.
One can also show that the restriction of this map to $S_n(132, 213, \beta_{a,b,c})$ is a bijection between $S_n(132, 213, \beta_{a,b,c})$ and the set of tilings of a $1 \times n$ rectangle in which all but the leftmost $a$ tiles and the rightmost $c$ tiles have length at most $b - 1$.
It follows that for $n \ge 1$,
$$|S_n(132, 213, \beta_{a,b,c})| = \sum_{k=1}^{a+c-1} {{n-1} \choose {k-1}} + \sum_{k=a+c}^n {{k-1} \choose {a+c-1}} F_{b-1,n-k+1}.$$
Mansour has also expressed \cite[Thm. 3]{Mansour33k} the ordinary generating function for $|S_n(123, 132, \tau)|$ as a determinant for certain $\tau \in S_k(123, 132)$.
Using this result, Mansour showed that
\begin{equation}
\label{eqn:3241}
|S_n(123, 132, 3241)| = F_{n+2} - 1 \hspace{30pt} (n \ge 1).
\end{equation}
One can also use Mansour's description of the elements of $S_n(123, 132)$ in \cite[Thm. 3]{Mansour33k} to give a bijective proof that
$$|S_n(123, 132, (k-1)(k-2)\ldots 2 1 k)| = F_{k-1,n+1} \hspace{\eqnsep} (k \ge 2).$$

We begin our results with an extension of \cite[Thm. 3]{Mansour33k} in which we give recurrence relations for the generating function for $|S_n(123, 132, \tau)|$ which apply for all $\tau \in S(123, 132)$.
Using these recurrence relations, we give an explicit enumeration of $S_n(123, 132, \tau)$ in terms of $k$-generalized Fibonacci numbers for all $\tau$ of the form
$$\tau = k + (l-1),k+(l-2),\ldots,k+1,k+l,k,k-1,\ldots,2,1.$$
We also give a bijective proof of this enumeration.
We then turn our attention to generalizations of (\ref{eqn:2341}) and (\ref{eqn:3241}).
To generalize (\ref{eqn:2341}) we give a recurrence relation for the generating function for $|S_n(132, 2341, \omega_k)|$, where $\omega_k$ is the permutation in $S_k$ given by $\omega_k = k, k-1, \ldots, 4, 2, 1, 3$.
Using this relation we give explicit enumerations of $S_n(132, 2341, \omega_k)$ in terms of Fibonacci numbers and binomial coefficients for several small values of $k$.
To generalize (\ref{eqn:3241}) we give recurrence relations for the generating function for $|S_n(132, 3241, \mu_{a,b})|$, where $\mu_{a,b}$ is the permutation in $S_{a+b}$ given by $\mu_{a,b} = b+a, b+a-1, \ldots, b+1, 1, 2, \ldots, b$.
Using these relations we give explicit enumerations of $S_n(132, 3241, \mu_{a,b})$ in terms of $k$-generalized Fibonacci numbers for several small values of $a$ and $b$.

\section*{\normalsize 2. Avoiding 123, 132, and Another Pattern}
\addtocounter{section}{+1}
\label{sec:MoreSS}


For any permutation $\pi$, let $\cF_\pi(x)$ denote the generating function given by
$$\cF_\pi(x) = \sum_{n=0}^\infty |S_n(123, 132, \pi)| x^n.$$
In this section we give recurrence relations for $\cF_\pi(x)$ for all $\pi \in S_n(123,132)$.
We begin by setting some notation.

\begin{definition}
For all $k \ge 1$, we write $[k]$ to denote the permutation in $S_k$ given by
$$[k] = k (k-1) \ldots 21.$$
For notational convenience we let $[0]$ denote the empty permutation.
For all $k \ge 2$, we write $\langle k \rangle$ to denote the permutation in $S_k$ given by
$$\langle k \rangle = (k-1) (k-2) \ldots 2 1 k.$$
For notational convenience we set $\langle 1 \rangle = 1$ and we let $\langle 0 \rangle$ denote the empty permutation.
\end{definition}

\begin{definition}
For all $\pi_1 \in S_m$ and all $\pi_2 \in S_n$, we write $\pi_1 \ominus \pi_2$ to denote the permutation in $S_{m+n}$ which is given by
$$(\pi_1 \ominus \pi_2)(i) = \cases{n + \pi_1(i) & $1 \le i \le m$ \cr
\pi_2(i-m) & $m+1 \le i \le m+n$ \cr}.$$
We refer to $\pi_1 \ominus \pi_2$ as the {\em skew sum} of $\pi_1$ and $\pi_2$.
\end{definition}

Mansour has shown \cite[Thm. 3]{Mansour33k} that $\pi \in S_n(123, 132)$ if and only if $\pi$ is a skew sum of permutations of the forms $[k]$, $k \ge 1$, and $\langle l \rangle$, $l \ge 2$.
In the same theorem Mansour expresses $\cF_\pi(x)$ as a determinant when $\pi$ is a skew sum of permutations of the form $\langle l \rangle$, $l \ge 2$.
It is clear from the form of this determinant that for these $\pi$, the set $S_n(123, 132, \pi)$ can always be enumerated in terms of $k$-generalized Fibonacci numbers.
Here we give recurrence relations which enable one to compute $\cF_\pi(x)$ for any permutation $\pi$.
We then find simple formulas for $|S_n(123, 132, \pi)|$ in terms of $k$-generalized Fibonacci numbers for a variety of $\pi$ which are not handled by \cite[Thm. 3]{Mansour33k}.
We begin by examining $\cF_{[k]}(x)$.

\begin{theorem}
For all $k \ge 1$ we have
\begin{equation}
\label{eqn:[k]}
\cF_{[k]}(x) = 1 + x \cF_{[k-1]}(x) + \sum_{i=2}^{k+1} x^i \cF_{[k-i+1]}(x).
\end{equation}
\end{theorem}
\begin{proof}
First observe that $S(123, 132, [k])$ may be partitioned into the sets $A_0, A_1,\ldots,A_k$, where $A_0$ is the set containing only the empty permutation, and for $1 \le i \le k$ the set $A_i$ consists of those permutations $\pi \in S(123, 132, [k])$ such that $\pi(i)$ is $\pi$'s largest entry.
Now observe that the set $A_1$ consists of those permutations of the form $1 \ominus \tau$, where $\tau \in S(123, 132, [k-1])$.
Similarly, for $2 \le i \le k$ the set $A_i$ consists of those permutations of the form $\langle i \rangle \ominus \tau$, where $\tau \in S(123, 132, [k-i+1])$.
The generating function for $A_0$ is 1, the generating function for $A_1$ is $x \cF_{[k-1]}(x)$, and the generating function for $A_i$, $2 \le i \le k$, is $x^i \cF_{[k-i+1]}(x)$.
Add these generating functions to obtain (\ref{eqn:[k]}).
\end{proof}

Next we consider the case in which $\pi$ has the form $[k] \ominus \pi_1$, where $\pi_1$ is not the empty permutation.
Observe that in this case we may assume $\pi_1 = \langle l \rangle \ominus \pi_2$ for $l \ge 2$, since $[r] \ominus [s] = [r+s]$ and $\langle 1 \rangle = [1]$.

\begin{theorem}
\label{thm:[k]minus}
For any permutation $\pi$, any $k \ge 1$, and any $l \ge 2$ we have
\begin{equation}
\label{eqn:[k]<l>}
\cF_{[k] \ominus \langle l \rangle \ominus \pi}(x) = 1 + x \cF_{[k-1]\ominus \langle l \rangle \ominus \pi}(x) + \sum_{i=2}^k x^i \cF_{[k-i+1]\ominus \langle l \rangle \ominus \pi}(x) + \frac{x^{k+1}}{1-x} \cF_{\langle l \rangle \ominus \pi}(x).
\end{equation}
\end{theorem}
\begin{proof}
This is similar to the proof of (\ref{eqn:[k]}).
\end{proof}

Next we consider the case in which $\pi$ has the form $\langle k \rangle \ominus \pi_1$.

\begin{theorem}
For any permutation $\pi$ and any $k \ge 2$ we have
\begin{equation}
\label{eqn:<k>}
\cF_{\langle k \rangle \ominus \pi}(x) = \frac{1-x+x^k \cF_\pi(x)}{1-2x+x^k}.
\end{equation}
\end{theorem}
\begin{proof}
This is similar to the proof of (\ref{eqn:[k]}).
\end{proof}

To illustrate our recurrence relations for $\cF_\pi(x)$, we now use them to find $|S_n(123, 132, \pi)|$ for various $\pi$.
In each case, $|S_n(123, 132, \pi)|$ is given by a simple formula involving Fibonacci numbers or $k$-generalized Fibonacci numbers.
We begin with $\pi = \langle 3 \rangle \ominus [2] = 43521$.

\begin{proposition}
For all $n \ge 3$,
\begin{equation}
\label{eqn:022}
|S_n(123, 132, \langle 3 \rangle \ominus [2])| = F_{n+2} + F_n - 3.
\end{equation}
Moreover,
\begin{equation}
\label{eqn:022gf}
\cF_{\langle 3 \rangle \ominus [2]}(x) = 3 + x + x^2 + \frac{x^2+4x-2}{1-2x+x^3}.
\end{equation}
\end{proposition}
\begin{proof}
To obtain (\ref{eqn:022gf}), set $k =3$ and $\pi = [2]$ in (\ref{eqn:<k>}) and use the fact that $\cF_{[2]}(x) = 1 + x + x^2$ to simplify the result.
To obtain (\ref{eqn:022}), observe that
$$\frac{x^2 + 4x - 2}{1-2x+x^3} = \frac{-3}{1-x} + \frac{2x + 1}{1-x-x^2}.$$
Now (\ref{eqn:022}) is immediate in view of (\ref{eqn:Fkngf}).
\end{proof}

We now use (\ref{eqn:[k]}), (\ref{eqn:[k]<l>}), and (\ref{eqn:<k>}) to obtain explicit enumerations of $S_n(123, 132, \langle l \rangle \ominus [2])$ for $l \ge 4$.

\begin{proposition}
\label{prop:0b2}
Fix $l \ge 4$.
Then for all $n \ge 3$,
\begin{equation}
\label{eqn:0b2}
|S_n(123, 132, \langle l \rangle \ominus [2])| \!=\! \left( \frac{1}{l-2} \right) \!\!\left( \!3 F_{l-1,n+1}\!+\!
(l\!-\!5) F_{l-1,n-1} \!+\! 3 \sum_{i=3}^{l-2} (l\!-\!i\!-\!1) F_{l-1,n-i+1} \!-\! 3 \!\right).
\end{equation}
Alternatively, for all $n \ge 3$,
\begin{equation}
\label{eqn:0b2alt}
|S_n(123, 132, \langle l \rangle \ominus [2])| = \sum_{k=1}^{n-1} F_{l-1,k} + 2 \sum_{k=1}^{n-2} F_{l-1,k}.
\end{equation}
Moreover, 
\begin{equation}
\label{eqn:0b2gf}
\sum_{n=0}^\infty |S_n(123, 132, \langle l \rangle \ominus [2])| x^n = 1 + x + x^2 + \frac{x^2 + 2x^3}{1-2x+x^l}.
\end{equation}
\end{proposition}
\begin{proof}
To obtain (\ref{eqn:0b2gf}), set $k = l$ and $\pi = [2]$ in (\ref{eqn:<k>}) and use the fact that $\cF_{[2]}(x) = 1 + x + x^2$.
To obtain (\ref{eqn:0b2}), observe that if $l \ge 4$ then
$$\frac{x^2 + 2x^3}{1-2x+x^l} = \left( \frac{1}{l-2} \right) \left( \frac{-3}{1-x} + \frac{3 + (l-5) x^2 + 3 \sum\limits_{i=3}^{l-2} (l-i-1) x^i}{1-x-\ldots -x^{l-1}} \right).$$
Now (\ref{eqn:0b2}) is immediate in view of (\ref{eqn:Fkngf}).
To obtain (\ref{eqn:0b2alt}), observe that
\begin{eqnarray*}
\frac{x^2 + 2 x^3}{(1-x)(1-x-\ldots-x^{l-1})} &=& \left( \sum_{n=0}^\infty x^n \right) \left( \sum_{n=0}^\infty \left( F_{l-1,n-1} + 2 F_{l-1,n-2} \right) x^n \right) \\
&=& \sum_{n=0}^\infty \left( \sum_{k=0}^{n-1} F_{l-1,k} + 2 \sum_{k=0}^{n-2} F_{l-1,k} \right) x^n. \\
\end{eqnarray*}
Now (\ref{eqn:0b2alt}) is immediate in view of (\ref{eqn:Fkngf}).
\end{proof}

We also give a bijective proof of (\ref{eqn:022}) and (\ref{eqn:0b2alt}).

\begin{theorem}
\label{thm:0220b2bijection}
Let $l \ge 3$.
For all $n \ge 1$, let $B_n$ denote the set of tilings of a $1 \times n$ rectangle in which there is at most one tile with length greater than $l-1$, and this tile has at most one tile, of length 1 or 2, to its right.
Then there exists a constructive bijection between $B_n$ and $S_n(123, 132, \langle l \rangle \ominus [2])$.
\end{theorem}
\begin{proof}
Suppose we are given such a tiling.
We construct its corresponding permutation as follows.
Let $m$ denote the length of the rightmost tile.
Fill this tile with the numbers $1,2, \ldots, m$ from left to right in the order $m-1, m-2, \ldots, 1, m$.
Fill the tile immediately to the left of the rightmost tile in the same way, using the smallest available numbers.
Repeat this process until every tile is filled.
It is routine to verify that this map is invertible, and that the permutation constructed avoids 123, 132, and $\langle l \rangle \ominus [2]$.
\end{proof}

Lines (\ref{eqn:[k]}), (\ref{eqn:[k]<l>}) and (\ref{eqn:<k>}) yield many additional enumerations involving $k$-generalized Fibonacci numbers.
We summarize some of these in the following table.



\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$k$ & $l$ & $m$ & $|S_n(123, 132, [k] \ominus \langle l \rangle \ominus [m])|$ & valid for \\
\hline
\hline
1 & 2 & 2 & $F_{n+3}+ F_{n+1} - 3n +2$ & $n \ge 3$\\
\hline
2 & 2 & 2 & $5 F_{n+1} - 9n + 21$ & $n \ge 5$ \\
\hline
3 & 2 & 2 & $3 F_{n+2} + 3 F_n - 24n +91$ & $n \ge 7$ \\
\hline
1 & 3 & 2 & $\frac{1}{2} \left( F_{3,n+2} + 2 F_{3,n} + F_{3,n-1} - 3n + 5 \right)$ & $n \ge 3$\\
\hline
2 & 3 & 2 & $\frac{1}{2} \left( 4 F_{3,n+1} + F_{3,n} - 3 F_{3,n-1} - 9n + 30 \right)$ & $n \ge 5$ \\
\hline
3 & 3 & 2 & $\frac{1}{2}\left( 3 F_{3,n} + 10 F_{3,n-1} - 3 F_{3,n-2} - 24n + 115 \right)$ & $n \ge 7$ \\
\hline
\end{tabular}



Table 1
\end{center}

\section*{\normalsize 3. Avoiding 132 and Two Longer Permutations}
\addtocounter{section}{+1}
In this section we generalize Mansour's results (\ref{eqn:2341}) and (\ref{eqn:3241}) by lengthening some of the forbidden subsequences.
We begin with (\ref{eqn:2341}).

\begin{definition}
\label{defn:gk}
For all $k \ge 3$ we write $\omega_k$ to denote the permutation in $S_k$ given by $\omega_k = [k-3] \ominus 213$.
We write $\cG_k(x)$ to denote the generating function
\begin{displaymath}
\cG_k(x) = \sum_{n=0}^\infty |S_n(132, 2341, \omega_k)| x^n.
\end{displaymath}
\end{definition}

In \cite[Thm. 8]{Mansour33k} Mansour uses generating function techniques to find $\cG_3(x)$, from which he proves (\ref{eqn:2341}).
We give a bijective proof of (\ref{eqn:2341}).

\begin{proposition}
For all $n \ge 1$, there exists a constructive bijection between the set $S_n(132, 213, 2341)$ and the set of
tilings of a $1 \times (n+1)$ rectangle with tiles of size $1 \times 1$ and $1 \times 2$ using at least one $1
\times 2$ tile.
\end{proposition}
\begin{proof}
Suppose we are given such a tiling.
We construct its corresponding permutation as follows.
Replace the rightmost $1 \times 2$ tile with a 1 and fill the (necessarily $1 \times 1$) tiles to the right of
the 1 with $2, 3, \ldots$ from left to right. Now fill the rightmost empty tile with the smallest numbers
available, placing them in the tile from left to right in increasing order. Repeat this process until every tile
is filled. It is routine to verify that this map is invertible and that the permutation constructed avoids 132,
213, and 2341, as desired.
\end{proof}

We now give a recurrence relation for $\cG_k(x)$.

\begin{proposition}
We have 
\begin{equation}
\label{eqn:g3}
\cG_3(x) = \frac{x^3-x+1}{(1-x)(1-x-x^2)}.
\end{equation}
Moreover, for all $k > 3$,
\begin{equation}
\label{eqn:gk}
\cG_k(x) = \left( \frac{1}{1-x} \right) \left( 1 + x ( \cG_{k-1}(x) - 1 ) + \sum_{r=2}^{k-2} x^r ( \cG_{k-r+1}(x) - 1 ) + \frac{x^{k-1}}{1-x} ( \cG_3(x) - 1) \right).
\end{equation}
\end{proposition}
\begin{proof}
Line (\ref{eqn:g3}) is immediate from (\ref{eqn:2341}), since $\omega_3 = 213$.
The proof of (\ref{eqn:gk}) is similar to the proof of (\ref{eqn:[k]}).
\end{proof}

The table below gives $|S_n(132, 2341, \omega_k)|$ for several small values of $k$.
Observe that in each case $|S_n(132, 2341, \omega_k)|$ is given by a simple formula involving Fibonacci numbers and binomial coefficients.



\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$k$ & $|S_n(132, 2341, \omega_k)|$ & valid for \\
\hline
\hline
4 & ${\displaystyle F_{n+5} - {{n+1} \choose {2}} - 2 {{n+1} \choose {1}} - 2}$ & $n \ge 1$ \\
\hline
5 & ${\displaystyle 3 F_{n+5} - 2 {{n+1} \choose {3}} - 4 {{n+1} \choose {2}} - 3 {{n+1} \choose {1}} - 14}$ & $n \ge 2$ \\
\hline
6 & ${\displaystyle 5 F_{n+6} + F_{n+4} - 4 {{n+1} \choose {4}} - 7 {{n+1} \choose {3}} - 5 {{n+1} \choose {2}} - 27 {{n+1} \choose {1}} - 8}$ & $n \ge 2$ \\
\hline
\end{tabular}



Table 2
\end{center}



We now turn our attention to a generalization of (\ref{eqn:3241}).

\begin{definition}
For all $k \ge 1$, let $[k]^r$ denote the permutation $12\ldots k$.
For notational convenience, let $[0]^r$ denote the empty permutation.
For all $k \ge 0$ and all $l \ge 0$ we write $\cH_{k,l}(x)$ to denote the generating function
$$\cH_{k,l}(x) = \sum_{n=0}^\infty |S_n(132, 3241, [k] \ominus [l]^r)| x^n.$$
\end{definition}

In \cite[Thm. 3]{Mansour33k} Mansour uses generating function techniques to find $\cH_{0,3}(x)$, from which he proves (\ref{eqn:3241}).
We give a bijective proof of (\ref{eqn:3241}).

\begin{proposition}
\label{prop:h03bijection}
For all $n \ge 1$ there exists a constructive bijection between $S_n(132, 3241, [3]^r)$ and the set of tilings of a $1 \times (n+1)$ rectangle with tiles of size $1 \times 1$ and $1 \times 2$ using at least one $1 \times 2$ tile.
\end{proposition}
\begin{proof}
Suppose we are given such a tiling.
To construct the corresponding permutation, we consider two cases:  the rightmost tile is $1 \times 2$ or the rightmost tile is $1 \times 1$.

If the rightmost tile is $1 \times 2$, then first place a 1 in the rightmost tile.
Now fill the rightmost empty tile with the smallest available numbers, placing them in the tile from left to right in increasing order.
Repeat this process until every tile is filled.

If the rightmost tile is $1 \times 1$, then let $m$ denote the number of $1 \times 1$ tiles to the right of the rightmost $1 \times 2$ tile.
Place an $m$ in the rightmost $1 \times 2$ tile.
Fill the (necessarily $1 \times 1$) tiles to the right of the rightmost $1 \times 2$ with the numbers $m-1, m-2, \ldots, 1, m+1$, in this order.
Now fill the rightmost empty tile with the smallest available numbers, placing them in the tile from left to right in increasing order.
Repeat this process until every tile is filled.

It is routine to verify that this map is invertible, and that the permutation constructed avoids 132, 3241, and $\mu_{0,3}$.
\end{proof}

We now give recurrence relations for $\cH_{0,l}(x)$ and $\cH_{k,l}(x)$.

\begin{proposition}
Let $k$ and $l$ denote positive integers.
Then $\cH_{0,1}(x) = 1$,
\begin{equation}
\label{eqn:h0b}
\cH_{0,l}(x) = 1 + \frac{x \cH_{0,l-1}(x)}{1 - x -\ldots - x^{l-1}} \hspace{\eqnsep} (l \ge 2),
\end{equation}
and
\begin{equation}
\label{eqn:hab}
\cH_{k,l}(x) = \frac{1-2x+ x \cH_{k-1,l}(x)}{(1-x)^2} \hspace{\eqnsep} (k \ge 1).
\end{equation}
\end{proposition}
\begin{proof}
This is similar to the proof of (\ref{eqn:[k]}).
\end{proof}

Specializing $k$ and $l$ in (\ref{eqn:hab}) yields many explicit enumerations.
We summarize some of these in the table below.
The enumerations in this table are valid for $n \ge 1$.



\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$k$ & $l$ & $|S_n(132, 3241, [k] \ominus [l]^r)|$ \\
\hline
\hline
0 & 4 & ${\displaystyle \frac{1}{2} \left( 2 F_{3,n+3} + F_{3,n+2} + F_{3,n} - 2 F_{n+4} + 1\right)}$ \\
\hline
0 & 5 & ${\displaystyle \frac{1}{6}\left( 14 F_{4,n+4} + 8 F_{4,n+3} + 4 F_{4,n+2} + 2 F_{4,n} - 6 F_{3,n+6} - 3 F_{3,n+5} - 3 F_{3,n+3} + 6 F_{n+5} - 1 \right)}$ \\
\hline
1 & 3 & ${\displaystyle F_{n+5} - {{n+1} \choose {2}} - 2 {{n+1} \choose {1}} - 2}$ \\
\hline
2 & 3 & ${\displaystyle F_{n+8} - {{n+1}\choose{4}} - 3 {{n+1} \choose {3}} - 4 {{n+1} \choose {2}} - 9 {{n+1} \choose {1}} - 11}$ \\
\hline
1 & 4 & ${\displaystyle \frac{1}{2}\left( F_{3,n+5} + 2 F_{3,n+4} \right) - F_{n+7} + \frac{1}{2} {{n+1}\choose{2}} + \frac{3}{2} {{n+1} \choose {1}} + 5}$ \\
\hline
\end{tabular}



Table 3
\end{center}



Observe that for $n \ge 1$ we have $|S_n(132, 3241, [1] \ominus [3]^r)| = |S_n(132, 2341, \omega_4)|.$
This is no surprise, however, since $S_n(132, 2341, \omega_4)$ is precisely the set of group-theoretic inverses of the elements of $S_n(132, 3241, [1] \ominus [3]^r)$.

\section*{\normalsize 4. Extended Restrictions}
\addtocounter{section}{+1}
Let $R$ denote a set of permutations.
In this section we describe a method of building sets of forbidden subsequences from $R$ for which the associated sets of restricted permutations can be easily enumerated in terms of $|S_n(R)|$.
We then use this method to produce some specific enumerations, several of which involve Fibonacci numbers or $k$-generalized Fibonacci numbers.
We begin by describing our technique for building on $R$.

\begin{definition}
Suppose $\alpha \in S_{n-1}$ and $\beta \in S_n$.
We say $\beta$ is an {\upshape extension} of $\alpha$ whenever $\alpha$ is the permutation obtained by removing $n$ from $\beta$.
We observe that every permutation in $S_n$ has exactly $n+1$ extensions.
\end{definition}

\begin{definition}
Let $R$ denote a set of permutations.
We write $E(R)$ to denote the set of permutations $\pi$ such that $\pi$ is an extension of an element of $R$, and we refer to $E(R)$ as the {\upshape extension of $R$}.
More generally, we write $E^0(R) = R$ and for any $k \ge 2$ we define $E^k(R)$ inductively, so that $E^k(R) = E(E^{k-1}(R))$.
\end{definition}

Our results in this section are based on the following observation.

\begin{theorem}
Let $R$ denote a set of permutations.
Then for all $n \ge 1$,
\begin{equation}
\label{eqn:SEES}
S_n(E(R)) = E(S_{n-1}(R)).
\end{equation}
Moreover, for all $k \ge 0$,
\begin{equation}
\label{eqn:nkSn}
|S_n(E^k(R))| = \frac{n!}{(n-k)!} |S_{n-k}(R)| \hspace{30pt} (n \ge k)
\end{equation}
and
\begin{equation}
\label{eqn:n!}
|S_n(E^k(R))| = n! \hspace{30pt} (0 \le n < k).
\end{equation}
\end{theorem}
\begin{proof}
To obtain (\ref{eqn:SEES}), suppose $\pi' \in S_{n-1}$, $\pi$ is an extension of $\pi'$, and $\sigma'$ is a permutation.
Observe that $\pi'$ contains a subsequence of type $\sigma'$ if and only if there exists an extension $\sigma$ of $\sigma'$ such that $\pi$ contains a subsequence of type $\sigma$.
Now (\ref{eqn:SEES}) is immediate.

To obtain (\ref{eqn:nkSn}), we argue by induction on $k$.
Since $E^0(R) = R$, the result is immediate for $k = 0$.
Now observe that every permutation in $S_n$ has exactly $n+1$ extensions, and every permutation in $S_{n+1}$ is the extension of exactly one permutation in $S_n$.
Therefore, using (\ref{eqn:SEES}) and induction we find
\begin{eqnarray*}
|S_n(E^k(R))| &=& |E(S_{n-1}(E^{k-1}(R)))| \\
&=& n |S_{n-1}(E^{k-1}(R))| \\
&=& \frac{n!}{(n-k)!} |S_{n-k}(R)|,
\end{eqnarray*}
as desired.

To obtain (\ref{eqn:n!}), observe that every permutation in $E^k(R)$ has length at least $k$, so $S_n(E^k(R)) = S_n$ when $n < k$.
\end{proof}

We now give several applications of this theorem.

\begin{proposition} 
For all $k \ge 0$ and all $n \ge k$,
$$|S_n(E^k(123,132,213))| = \frac{n!}{(n-k)!} F_{n+1-k}.$$
In particular, for all $n \ge 1$,
$$|S_n(1234,1243,1423,4123,1324,1342,1432,4132,2134,2143,2413,4213)| = n F_n.$$	
\end{proposition}
\begin{proof}
Set $R = \{123, 132, 213\}$ in (\ref{eqn:nkSn}) and use (\ref{eqn:SimionSchmidtintro}) to simplify the result.
\end{proof}

\begin{proposition}
Let $R$ denote one of the following sets of permutations.
$$\begin{array}{c}
\{123,1432\};\ \{123,2143\};\ \{123,2413\};\ \{132,1234\};\ \{132,2134\};\\
\{132,2314\};\ \{132,2341\};\ \{132,3241\};\ \{132,3412\}
\end{array}$$
For all $k \ge 0$ and all $n \ge k$,
\begin{equation}
\label{eqn:nWest}
|S_n(E^k(R))| = \frac{n!}{(n-k)!} F_{2(n-k)-1}.
\end{equation} 
\end{proposition}
\begin{proof}
In \cite{WestGenTrees} West shows that for each of the sets listed, $S_n(R) = F_{2n-1}$.
Combine this with (\ref{eqn:nkSn}) to obtain (\ref{eqn:nWest}).
\end{proof}

\begin{proposition} 
(see also \cite{G})
Fix $\tau \in S_3$.
For all $k \ge 0$ and all $n \ge k$,
\begin{equation}
\label{eqn:nCn}
|S_n(E^k(\tau))| = \frac{n!}{(n-k+1)!}{{2n-2k}\choose{n-k}}.
\end{equation} 
\end{proposition}
\begin{proof}
It is well known that for all $\tau \in S_3$ we have $S_n(\tau) = C_n$, where ${\displaystyle C_n = \frac{1}{n+1} {{2n} \choose {n}}}$ is the $n$th Catalan number.
Combine this with (\ref{eqn:nkSn}) to obtain (\ref{eqn:nCn}).
\end{proof}

\footnotesize
\begin{thebibliography}{10}
\bibitem{CW}
T.~Chow and J.~West.
\newblock Forbidden subsequences and {C}hebyshev polynomials.
\newblock {\em Discrete Math.}, 204(1--3):119--128, 1999.

\bibitem{G}
O.~Guibert.
\newblock {\em Permutations sans sous-s\'equence interdite}.
\newblock PhD thesis, Universit\'e Bordeaux I, 1992.

\bibitem{KnuthVol1}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume~1.
\newblock Addison-Wesley, 3rd edition, 1997.

\bibitem{Krattenthaler}
C.~Krattenthaler.
\newblock Permutations with restricted patterns and {D}yck paths.
\newblock {\em Adv. in Appl. Math.}, 27(2/3):510--530, 2001.

\bibitem{LakSong}
V.~Lakshmibai and M.~Song.
\newblock A criterion for smoothness of {S}chubert varieties in
  ${S}p_{2n}/{B}$.
\newblock {\em J. Algebra}, 189(2):332--352, 1997.

\bibitem{Mansour33k}
T.~Mansour.
\newblock Permutations avoiding a pattern from ${S}_k$ and at least two
  patterns from ${S}_3$.
\newblock {\em Ars Combin.}, 62, 2002.

\bibitem{MansourVainshtein3}
T.~Mansour and A.~Vainshtein.
\newblock Avoiding maximal parabolic subgroups of ${S}_k$.
\newblock {\em Discrete Math. Theor. Comput. Sci.}, 4(1):67--75, 2000.

\bibitem{MansourVainshtein2}
T.~Mansour and A.~Vainshtein.
\newblock Restricted 132-avoiding permutations.
\newblock {\em Adv. in Appl. Math.}, 26(3):258--269, 2001.

\bibitem{SimionSchmidt}
R.~Simion and F.~Schmidt.
\newblock Restricted permutations.
\newblock {\em Europ. J. Combin.}, 6:383--406, 1985.

\bibitem{WestGenTrees}
J.~West.
\newblock Generating trees and forbidden subsequences.
\newblock {\em Discrete Math.}, 157:363--374, 1996.

\end{thebibliography}

\end{document}