Permutations containing and avoiding certain patterns

T. Mansour

Let T_k^m={σ\in S_k | σ_1=m}. We prove that the number of permutations which avoid all patterns in T_k^m equals (k-2)!(k-1)^{n+1-k} for k <= n. We then prove that for any τin T_k^1…