Refined Restricted Permutations

Abstract

Define $S_n^k(\alpha )$ to be the set of permutations of $\{1,2,...,n\}$ with exactly $k$ fixed points which avoid the pattern $\alpha \in S_m$. Let $s_n^k(\alpha )$ be the size of $S_n^k(\alpha )$. We investigate $S_n^0(\alpha )$ for all $\alpha \in S_3$ as well as show that $s_n^k(132)=s_n^k(213)=s_n^k(321)$ and $s_n^k(231)=s_n^k(312)$ for all $0\le k\le n$.

This article is dedicated to the memory of Rodica Simion