\documentclass[12pt]{article} \textwidth=6.5in \textheight=8.75in \topmargin=-.5in \oddsidemargin=0in \evensidemargin=0in \usepackage{theorem} \usepackage{latexsym} \usepackage{amssymb} \parskip=7pt \parindent=0pt \def\Bx{\hfill{$\Box$}} \font\rms=cmr10 \font\its=cmti8 \font\bfs=cmbx8 \newtheorem{thm}{Theorem}[section] \newtheorem{lemma}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{defn}[thm]{Definition} \begin{document} \begin{center} {\bf RESTRICTED PERMUTATIONS FROM CATALAN TO FINE AND BACK} \vskip 15pt {\sc Aaron Robertson\footnote{ Homepage: {\tt http://math.colgate.edu/$\sim$aaron/}\vskip 0pt \hskip 9pt 2000 Mathematics Subject Classification: 05A15, 68R15} }\\ {\rms Department of Mathematics,} {\rms Colgate University, Hamilton, NY 13346, U.S.A.}\\ {\tt aaron@math.colgate.edu} \end{center} % \begin{abstract} \noindent \footnotesize We give some history and recent results in the area of pattern restricted permutations. We also present a new bijection between certain pattern restricted permutations. \end{abstract} %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 50 \rms (2004), Article~B50g\hfill} \def\thepage{} % % \section*{\normalsize Introduction} It was a great pleasure to have been given the opportunity to speak at the landmark $50^{\mathrm{th}}$ meeting of the S\'eminaire Lotharingien de Combinatoire, held in March 2003, at Domaine Saint Jacques, near Ottrott, France. The meeting was a wonderful celebration, replete with wonderful company, wonderful food, and, of course, wonderful mathematics. This article is an expanded version of the talk that I presented at the meeting. We give some history and recent results in the area of pattern restricted permutations, as well as present a pertinent new bijection. \section*{\normalsize 1. Preliminaries} We first get the definitions and notation out of the way. Let $\pi \in S_n$ be a permutation of $\{1,2,\dots,n\}$ written in one-line notation. Let $\alpha \in S_m$. We say that $\pi$ {\it contains the pattern $\alpha$} if there exist indices $i_1\tau_k$ and thus $i,k \not \in \{y,z\}$. Hence, we must have $j \in \{y,z\}$. From the minimality of $\tau_i \tau_j \tau_k$, clearly $j \neq z$. Thus, $\tau_x \tau_j \tau_z$ with $i\tau_x > \tau_k$ implies that $\tau_i \tau_z \tau_k$ is a smaller $132$ occurrence in $\tau$ than $\tau_i \tau_j \tau_k$, a contradiction. Next, assume, for a contradiction, that $\tau_j \tau_x \tau_y$ in $\mathcal{M}\tau$ is a smaller $132$ occurrence (with respect to the indices) than $\tau_i \tau_j \tau_k$ is in $\tau$. This implies that $\tau_i \tau_x \tau_k$ is a smaller $132$ occurrence in $\tau$ than $\tau_i \tau_j \tau_k$, contradicting the minimality of $\tau_i \tau_j \tau_k$. We now show that $\gamma$ is a bijection; it is enough to give $\gamma^{-1}$. To do so, we make the following definition. {\bf Definition.} Let $k \geq 2$. Let $\alpha=\alpha_1\dots \alpha_k$ and $\beta=\beta_1\dots \beta_k$ be two distinct occurrences of $k (k-1) \dots 1$ in $\pi$. We say $\alpha$ is larger that $\beta$ if there exists $i$, $1 \leq i \leq k$, such that $\pi^{-1}(\alpha_j) = \pi^{-1}(\beta_j)$ for all $j>i$ and $\pi^{-1}(\alpha_i) > \pi^{-1}(\beta_i)$. We can now describe $\gamma^{-1}: S_n(132) \rightarrow S_n(321)$. Let $\pi_1 \pi_2 \dots \pi_n=\pi \in S_n(132)$ and let $zyx=\pi_{p_1}\pi_{p_2}\pi_{p_3}$ be the largest $321$ occurrence in $\pi$. If no such occurrence exists, $\gamma^{-1}(\pi)=\pi$. Otherwise, let $\mathcal{N}$ be the operation that creates the permutation $\mathcal{N}\pi$ where $\mathcal{N}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,p_3\}$ and $\mathcal{N}\pi_{p_1}=x$, $\mathcal{N}\pi_{p_2}=z$, and $\mathcal{N}\pi_{p_3}=y$. Now let $zyx$ be the largest $321$ occurrence in $\mathcal{N}\pi$ and apply $\mathcal{N}$ again. Repeat until the resulting permutation is $321$-avoiding. It is easy to check that $\gamma^{-1} \gamma(\pi) = \pi$ for any $\pi \in S_n(321)$. We can extend $\gamma$ to a bijection ${\Gamma_k} : S_n(k (k-1) \dots 1) \rightarrow S_n(1k(k-1)\cdots 2)$ for any $k \geq 2$. Let $\pi_1 \pi_2 \dots \pi_n=\pi \in S_n(k(k-1)\dots 1)$ and let $\alpha=\pi_{p_1}\pi_{p_2}\dots \pi_{p_k}$ be the smallest $1k (k-1) \dots 2$ occurrence in $\pi$. If no such occurrence exists, ${\Gamma_k}(\pi)=\pi$. Otherwise, let $\mathcal{P}$ be the operation that creates the permutation $\mathcal{P}\pi$ where $\mathcal{P}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,\dots,p_k\}$ and $\mathcal{P}\pi_{p_i}=\pi_{p_{i+1 \, (\mathrm{mod} \, k)}}$ for $i=1,2,\dots,k$. Now let $\alpha$ be the smallest $1k (k-1) \dots 2$ occurrence in $\mathcal{P}\pi$ and apply $\mathcal{P}$ again. Repeat until the resulting permutation avoids the pattern $1k (k-1) \dots 2$. To prove that ${\Gamma_k}$ is well-defined we show that, with respect to the indices of elements, the smallest $1 k \dots 2$ occurrence in $\mathcal{P}\pi$ is larger than the smallest $1 k \dots 2$ occurrence in $\pi$. Hence, $\mathcal{P}^j \tau$ has no $1 k \dots 2$ occurrence for some finite $j$. Let $\tau$ be our permutation and let $\gamma_1 \dots \gamma_k$ be the smallest $1 k \dots 2$ occurrence in $\tau$. Assume, for a contradiction, that $\mathcal{P}\tau$ has a $1 k \dots 2$ occurrence $\sigma=\sigma_1 \dots \sigma_k$ with $\sigma_1^{-1} <\gamma_1^{-1}$. Since $\tau$ has no such occurrence, we must have $$\{\sigma_1,\dots,\sigma_k \} \cap \{\gamma_1,\dots,\gamma_k\} \neq \emptyset.$$ Let $\gamma_j$ be the minimal element in the above intersection such that there exists $\ell \geq 1$, $\ell$ maximal, where we have (in $\mathcal{P} \tau$) \begin{equation} \sigma = \sigma_1 \dots \sigma_{i-1} \gamma_j \sigma_{i+1} \dots \sigma_{i+\ell} \sigma_{i+\ell+1} \dots \sigma_k \end{equation} with \begin{equation} \{\sigma_{i+1},\dots,\sigma_{i+\ell}\} \cap \{ \gamma_1,\dots,\gamma_k\} = \emptyset \end{equation} (so that $ \{\sigma_{i+\ell+1},\dots,\sigma_k\} \subseteq \{\gamma_1,\dots,\gamma_k\} $ where $\{\sigma_{i+\ell+1},\dots,\sigma_k\}$ is possibly empty). We may further require that there do not exist $\gamma_{m+1},\dots,\gamma_{m+\ell}$ such that \begin{equation} \sigma_1 \dots \sigma_{i-1} \gamma_j \gamma_{m+1} \dots \gamma_{m+\ell} \sigma_{i+\ell+1} \dots \sigma_k \end{equation} is also a $1 k \dots 2$ occurrence. Since this is quite a bit to require of $\gamma_j$, we must prove its existence. Assume, for a contradiction, that no such $\gamma_j$ exists. Then, for all $\gamma_i$, $1 \leq i \leq k$, we have no such $\ell$ satisfying (1) and (2), or there exist $\gamma_{m+1},\dots,\gamma_{m+\ell}$ such that (3) is also a $1 k \dots 2$ occurrence. In either case, there exists a $1 k \dots 2$ occurrence of the form $\sigma_1 \dots \sigma_x \gamma_y \dots \gamma_z$ in $\mathcal{P} \tau$ with $\{\sigma_1,\dots,\sigma_x\} \cap \{\gamma_1,\dots,\gamma_k\} = \emptyset$ and hence, $\sigma_1 \dots \sigma_x \gamma_y \dots \gamma_z$ is also in $\tau$, a contradiction since such an occurrence is smaller than $\gamma_1 \dots \gamma_k$. We rewrite (1) as \begin{equation} \sigma_1 \dots \sigma_{i-1} \gamma_j \sigma_{i+1} \dots \sigma_{i+\ell} \gamma_{j+m+1} \dots \sigma_k. \end{equation} From (4) we must have, by assumption (3), $ |\{\gamma_{j+1},\dots,\gamma_{j+m}\}| < |\{\sigma_{i+1},\dots,\sigma_{i+ \ell} \}|. $ But then $$ \gamma_1 \dots \gamma_{j-1} \sigma_{i+1} \dots \sigma_{i+\ell} \gamma_{j+m+1} \dots \gamma_k $$ contains a smaller $1k \dots 2$ occurrence in $\tau$ than $\gamma_1 \dots \gamma_k$, a contradiction. Thus, $\mathcal{P}\tau$ contains no $1 k \dots 2$ occurrence $\sigma_1 \dots \sigma_k$ with $\sigma_1^{-1} < \gamma_2^{-1}$ (order in $\mathcal{P}\tau$). To finish proving that $\Gamma_k$ is well-defined, assume, for a contradiction, that $\gamma_2 \beta_1 \dots \beta_{k-1}$ in $\mathcal{P}\tau$ is a smaller $1k \dots 2$ occurrence (with respect to the indices) than $\gamma_1 \dots \gamma_k$ is in $\tau$. Then we must have $\beta_1^{-1}<\gamma_3^{-1}$ (order in $\mathcal{P}\tau$). However, this implies that $\gamma_1 \beta_1 \gamma_3 \dots \gamma_k$ is a smaller $1k \dots 2$ occurrence in $\tau$ than $\gamma_1 \dots \gamma_k$, a contradiction. This concludes the proof that $\Gamma_k$ is well-defined. To show that $\Gamma_k$ is a bijection, note that ${\Gamma_k}^{-1}$ is found by using the operation $\mathcal{Q}$ where $\mathcal{Q}\pi_i=\pi_i$ if $i \not \in \{p_1,p_2,\dots,p_k\}$ and $\mathcal{Q}\pi_{p_i}=\pi_{p_{i-1 \, (\mathrm{mod} \, k)}}$ for $i=1,2,\dots,k$. Using ${\Gamma_k}$, along with the standard bijections, we immediately have the following theorem. {\bf Theorem.} Let $k \geq 2$. The following patterns are Wilf equivalent. $$ \begin{array}{ll} A. \,\,\,\, k (k-1) \cdots 1& B. \,\,\,\, 1k(k-1) \cdots 2\\ C. \,\,\,\, 12 \cdots k & D.\,\,\,\, 2 3 \cdots k 1 \\ E. \,\,\,\, k 1 2 \cdots (k-1)& F.\,\,\,\, (k-1) (k-2) \cdots 1 k \\ \end{array} $$ {\it Remark.} ${\Gamma_4}$ proves the Wilf equivalence of $1234$ and $4123$, a result of Stankova [28]. \section*{\normalsize 4. Enumeration Results} In this section we give some enumeration results along with their relevant references. The first table gives the number of permutations that avoid a single pattern. \begin{center} \centerline{{\bf Avoid 1}} \renewcommand{\arraystretch}{.5} \begin{tabular}{|l|l|l|} \hline \multicolumn{1}{|c|}{$\!\!$Class $\cal{W} \!\!$}& \multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}& \multicolumn{1}{|c|}{References}\\ \hline &&\\ $\overline{(123)}$&$C_n=\frac{1}{n+1} {2n \choose n}$ &[14], [12]\\ &&\\ $\overline{(1234)}$&$2\sum_{k=0}^n {2k \choose k} {n \choose k}^2 \frac{3k^2-(2k+1)(n-1)}{(k+1)^2(k+2)(n-k+1)}$ &[10]\\ &&\\ $\overline{(1342)}$&$ \frac{(-1)^{n-1}(7n^2-3n-2)}{2} +3 \sum_{k=2}^n (-1)^{n-k}2^{k}{2k-4 \choose k-2} \frac{(n-k+2)(n-k+1)} {k(k+1)}$ &[1]\\ &&\\ $\overline{(1324)}$&$?$ &open\\ &&\\ \hline \end{tabular} \end{center} \footnotesize \baselineskip=10pt $\overline{(123)} = S_3$; $\overline{(1234)} = \{1234,1243,2134,2143,3412,3421,4312,4321\}$; $\overline{(1342)} =\{1342,1423,2341,2413,$ \\ $2431,3124,3142,3241,4132,4213\} $; $\overline{(1324)} = \{1324, 4231\}$. \normalsize We continue with a table giving the number of permutations that contain a given pattern exactly once. \begin{center} \centerline{{\bf Contain 1}} \begin{tabular}{|l|l|l|} \hline \multicolumn{1}{|c|}{Class $\cal{W}$} & \multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}& \multicolumn{1}{|c|}{Reference}\\ \hline &&\\ $\overline{(\emptyset;123)}$&$\frac{3}{n} {2n \choose n-3}$ for $n \geq 3$&[20]\\ &&\\ $\overline{(\emptyset;132)}$&${2n-3 \choose n-3}$ for $n \geq 3$&[2]\\ &&\\ \hline \end{tabular} \end{center} \footnotesize $\overline{(\emptyset;123)} =\{(\emptyset;123),(\emptyset;321)\}$; $\overline{(\emptyset;132)} = \{(\emptyset;132),(\emptyset;213),(\emptyset;231),(\emptyset;312)\}$. \normalsize \vskip 10pt The penultimate table gives the number of permutations that avoid a given pattern and contain a different given pattern exactly once. The last table gives the number of permutations that contain each of two given (not necessarily distinct) patterns exactly once. \begin{center} \centerline{{\bf Avoid 1, Contain 1}} \begin{tabular}{|l|l|l|} \hline \multicolumn{1}{|c|}{Class $\cal{W}$} & \multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}& \multicolumn{1}{|c|}{Reference}\\ \hline &&\\ $\overline{(123;321)}$&0 for $ n \geq 6$&-----\\ &&\\ $\overline{(123;132)}$&$(n-2)2^{n-3}$ for $n \geq 3$&[20]\\ &&\\ $\overline{(123;231)}$&$2n-5$ for $n \geq 3$&[17]\\ &&\\ $\overline{(132;213)}$&$n2^{n-5}$ for $n \geq 4$&[16]\\ &&\\ $\overline{(132;231)}$&$2^{n-3}$ for $n \geq 3$&[16]\\ &&\\ \hline \end{tabular} \end{center} \footnotesize \baselineskip=10pt $\overline{(123;321)}= \{(123;321), (321;123) \}$; $\overline{(123;132)}=\{(123;132), (123;213), (132;123), (213;123), (231;321),$ \\$ (312;321), (321;231),(321;312)\}$; $\overline{(123;231)}=\{(123;231),(123;312),(132;321),(213;321),(231;123),$ \\ $(312;123),(321;132),(321;213)\}$; $\overline{(132;213)}=\{(132;213), (213;132), (231;312), (312;231) \}$; \\ $\overline{(132;231)}=\{(132;231),(132;312), (213;231),(213;312), (231;132), (231;213), (312;132),(312;213)\}$. \normalsize \baselineskip=15pt \begin{center} \centerline{{\bf Contain 2}} \begin{tabular}{|l|l|l|} \hline \multicolumn{1}{|c|}{Class $\cal{W}$} & \multicolumn{1}{c|}{$s_n(T), T \in \cal{W}$}& \multicolumn{1}{|c|}{Reference}\\ \hline &&\\ $\overline{(\emptyset;\{123,321\})}$&$0$ for $n \geq 6$&----- \\ &&\\ $\overline{(\emptyset;\{123,231\})}$&$2n-5$ for $n \geq 5$&[23]\\ &&\\ $\overline{(\emptyset;\{123,132\})}$&${{n-3} \choose 2}2^{n-4}$ for $n \geq 5$&[22] \\ &&\\ $\overline{(\emptyset;\{132,213\})}$&$(n^2+21n-28)2^{n-9}$ for $n \geq 7$&[23]\\ &&\\ $\overline{(\emptyset;\{132,231\})}$&$2^{n-3}$ for $n \geq 4$ &[23]\\ &&\\ $\overline{(\emptyset;\{123,123\})}$&$\frac{59n^2+117n+100} {2n(2n-1)(n+5)} {2n \choose n-4}$ for $n \geq 4$&[9]\\ &&\\ $\overline{(\emptyset;\{132,132\})}$&$\frac{(n-2)^2(n+21)-4}{2n(n-1)} {{2n-6} \choose {n-4}}$ for $n \geq 4$ &[15]\\ &&\\ \hline \end{tabular} \end{center} \footnotesize \baselineskip=10pt $\overline{(\emptyset;\{123,\!321\})}=\{(\emptyset;\{123,321\}), (\emptyset;\{321,123\}) \}$; $\overline{(\emptyset;\{123,231\})}=\{(\emptyset;\{123,231\}), (\emptyset;\{123,312\}),$ \\ $(\emptyset;\{132,321\}),(\emptyset;\{213,321\})\}$; $\overline{(\emptyset;\{123,132\})}=\{(\emptyset;\{123,132\}), (\emptyset;\{123,213\}), (\emptyset;\{231,321\}),$ \\ $(\emptyset;\{312,321\})\}$; $\overline{(\emptyset;\{132,213\})}=\{(\emptyset;\{132,213\}), (\emptyset;\{231,312\})\}$; $\overline{(\emptyset;\{132,231\})}=\{(\emptyset;\{132,231\}),$ \\ $(\emptyset;\{132,312\}), (\emptyset;\{213,231\}),(\emptyset;\{213,312\})\}$; $\overline{(\emptyset;\{123,123\})} = \{(\emptyset;\{123,123\}), (\emptyset;\{321,321\})\}$;\\ $\overline{(\emptyset;\{132,132\})} = \{ {(\emptyset;\{132,132\})},{(\emptyset;\{213,213\})}, {(\emptyset;\{231,231\})},{(\emptyset;\{312,312\})} \}.$ \normalsize \baselineskip=15pt \section*{\normalsize 5. An Interesting Generating Function} An interesting generating function can be obtained when we consider $\{s_n(132;\{(123)^r\})\}_n$. To this end, let $$f(x,y;k) = \sum_{n,r} s_n(132,\{(123\dots k)^r\})x^ny^r.$$ In [25], the authors show that $$ f(x,y;3) ={1\over\displaystyle 1-{\strut x\over\displaystyle 1-{\strut x\over\displaystyle 1-{\strut xy\over\displaystyle 1-{\strut xy^3\over\displaystyle 1-{\strut xy^6\over\displaystyle \hskip 15pt\ddots}}}}}} $$ in which the $n^{\mathrm{th}}$ numerator is $xy^{{n-1\choose 2}}$. This result was the apparent impetus for several papers, of which we note a few. Let $F_r(x;k) = [y^r]f(x,y;k),$ i.e., the coefficient of $y^r$ in $f(x,y;k)$. Let $U_n(x)$ denote the Chebyshev polynomials of the second kind, defined by $$U_n(\cos(x)) = \frac{\sin((n+1)x)}{\sin(x)}.$$ {Mansour and Vainshtein [18]} show that for any $k\ge 1$ and $1\le r\le k(k+3)/2$, $$ F_r(x;k)=\frac{x^{\frac {r-1}2}U_{k-1}^{r-1}\left(\frac1{2\sqrt{x}}\right)} {U_{k}^{r+1}\left(\frac1{2\sqrt{x}}\right)}\sum_{j=0}^{\lfloor(r-1)/k\rfloor} {r-kj+j-1\choose j}\left(\frac{U_k\left(\frac1{2\sqrt{x}}\right)} {x^{\frac{k-2}{2k}}U_{k-1}\left(\frac1{2\sqrt{x}}\right)}\right)^{kj}. $$ (The case $F_0(x;k)$ had already been determined in terms of Chebyshev polynomials by Chow and West [4].) This result was followed closely by a result of {Jani and Rieper [11]}, who give a bijection between ordered trees and $S_n(132;\{(123\dots k)^r\})$. We then come to a quote found in [13]: \begin{quote}{\it Whenever you encounter generating functions which can be expressed in terms of continued fractions or Chebyshev polynomials, then expect that Dyck or Motzkin paths are at the heart of your problem, and will help to solve it.}\vskip 2pt \hfill - Krattenthaler \end{quote} In this paper, Krattenthaler reproves and extends all the above results as well as proves new ones with continued fractions, Chebyshev polynomials of the second kind, and Dyck and Motzkin paths. \section*{\normalsize 6. Refined Restricted Permutations} \begin{quote}{\it Combinatorics without algebra ... is like sex without love.\vskip 0pt} \hfill - Anthony Joseph \end{quote} We now move on to some very recent results on restricted permutations. In [24], the study of restricted permutations refined by the number of fixed points was initiated (to the best of my knowledge) in an attempt to combine the ``purely combinatorial" with the algebraic properties of permutations. We first look at restricted permutations classified by cycle structure. \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|} {Cycle structure}&$S_6(123)$&$S_6(132)$&$S_6(213)$ &$S_6(321)$ &$S_6(231)$&$S_6(312)$\\ \hline $1^6$&0& 1 &1&1&1&1\\ $1^42^1$&0& 5 &5&5&9&9\\ $1^33^1$&0& 8 &8&8&12&12\\ $1^22^2$&10& 9&9&9&18&18\\ $1^24^1$& 8& 12&12&12&17&17\\ $1^12^13^1$&24& 20 &20&20&24&24\\ $1^15^1$&24& 20&20&20&20&20\\ $2^3$& 10& 5 &5&5&4&4\\ $2^14^1$&26& 20 &20&18&12&12\\ $3^2$&6& 8 &8&10&3&3\\ $6^1$& 24& 24 &24&24&12&12\\ \hline {Sum}&132&132&132&132 &132&132\\ \end{tabular} \vskip -218pt \hskip -20pt \setlength{\unitlength}{1.5mm} \begin{picture}(0,45.7)(44,0) \linethickness{.5mm} \put(33,10){{\line(1,0){35}}} \put(33,4){{\line(1,0){35}}} \put(33,4){{\line(0,1){6}}} \put(68,4){{\line(0,1){6}}} \end{picture} \end{center} \vskip 20pt In this table, we see that $S_6(132) $ and $ S_6(213)$ have the same cycle structure breakdown, and that the same holds true for $S_6(231) $ and $ S_6(312)$. This is fairly easy to explain. {\bf Theorem} (Robertson, Saracino, Zeilberger [24]) Let $\gamma \in S_n$ be given by $\gamma_i =n+1-i$ for $1 \leq i \leq n$. For $\pi \in S_n$, let $\pi^\star = \gamma \pi \gamma^{-1}$. The number of occurrences of the pattern $213$ (resp. $312$) in $\pi$ equals the number of occurrences of the pattern $132$ (resp. $231$) in $\pi^\star$. This is just the reversal bijection followed by the complement bijection. However, written in the above form as a conjugation, we see that the cycle structure is preserved. Digging a little deeper into the cycle structure breakdown, we notice that $S_6(321)$ has a breakdown very close to that of $S_6(132)$. In fact, the only place where a difference occurs in the table is boxed in. And, if we look at the number of fixed points, we have the same breakdown according to the number of fixed points. Let $S_n^k(S;T)$ be the elements of $S_n(S;T)$ with exactly $k$ fixed points and let $s_n^k(T)=|S_n^k(T)|$. Robertson, Saracino, and Zeilberger [24] prove that for all $n$ and all $k$, $0 \leq k \leq n$, \begin{itemize} \item $s_n^k(132)=s_n^k(231)=s_n^k(321)$ \item $s_n^k(231) = s_n^k(312)$ \item $s_n^k(123)$ \end{itemize} are the three classes, where we have \footnotesize \setlength{\arraycolsep}{1.5pt} \renewcommand{\arraystretch}{.85} $$ \begin{array}{ccccc} \begin{array}{lcccccccccccc} {}_n \diagdown^k \!\! &\vline&^0&^1&^2&^3&^4&^5&^6&^7&^8 \\ \hline _0&\vline&1\\ _1&\vline&0&1\\ _2&\vline&1&0&1\\ _3&\vline&2&2&0&1\\ _4&\vline&6&4&3&0&1\\ _5&\vline&18&13&6&4&0&1\\ _6&\vline&57&40&21&8&5&0&1\\ _7&\vline&186&130&66&30&10&6&0&1\\ _8&\vline&622&432&220&96&40&12&7&0&1\\ \end{array} & \hskip 10pt & \begin{array}{lcccccccccccc} {}_n \diagdown^k \!\! &\vline&^0&^1&^2&^3&^4&^5&^6&^7&^8 \\ \hline _0&\vline&1\\ _1&\vline&0&1\\ _2&\vline&1&0&1\\ _3&\vline&1&3&0&1\\ _4&\vline&4&4&5&0&1\\ _5&\vline&10&16&8&7&0&1\\ _6&\vline&31&44&35&12&9&0&1\\ _7&\vline&94&146&102&59&16&11&0&1\\ _8&\vline&303&464&362&180&87&20&13&0&1\\ \end{array} & \hskip 10pt & \begin{array}{lcccccccccccc} {}_n \diagdown^k \!\! &\vline&^0&^1&^2&^3&^4&^5&^6&^7&^8 \\ \hline _0&\vline&1\\ _1&\vline&0&1\\ _2&\vline&1&0&1\\ _3&\vline&2&3&0&0\\ _4&\vline&7&4&3&0&0\\ _5&\vline&20&20&2&0&0&0\\ _6&\vline&66&48&18&0&0&0&0\\ _7&\vline&218&183&28&0&0&0&0&0\\ _8&\vline&725&552&153&0&0&0&0&0&0\\ \end{array}\\ \\ \mathbf{s_n^k(132)=s_n^k(213)=s_n^k(321)} & & \mathbf{s_n^k(231)=s_n^k(312)} & & \mathbf{s_n^k(123)} \end{array} $$ \normalsize It is quite amazing that $s_n^k(132) = s_n^k(321)$. Robertson, Saracino, and Zeilberger [24] give a fairly technical proof. This was followed by a proof due to Elizalde [7], a student of Stanley, who refines this result further by showing that we have ``number of excedances" in addition to the number of fixed points. Pak and Elizalde [21] follow this up by giving a nice bijective proof. An interesting sequence appears when we consider $132$-avoiding derangements. We see that $$\{s_n^0(132)\}_{n \geq 0}=1,0,1,2,6,18,57,186,622,\dots.$$ This is Fine's sequence, initially given in [8], which stems from similarity relations. (For a good survey of Fine's sequence, see [6].) Fine's sequence $\{F_n\}_{n \geq 0}$ is characterized by \begin{equation} 2F_n+F_{n-1}=C_n, \end{equation} which may be thought of as the defining equation for the sequence. We now take a very brief sidestep to look at similarity relations. {\bf Definition.} A similarity relation, $R$, is a binary relation on an ordered set which is reflexive, symmetric, but not necessarily transitive, with the condition that if $iRk$ and $i