Restricted single or double signed patterns

Abstract

Let $E_n^r=\{[\tau {]}_a=({\tau }_1^{(a_1)},...,{\tau }_n^{(a_n)})|\tau \in S_n,1\le a_i\le r\}$ be the set of all signed permutations on the symbols 1,2,...,n with signs 1,2,...,r. We prove, for every 2-letter signed pattern $[\tau {]}_a$, that the number of $[\tau {]}_a$-avoiding signed permutations in $E_n^r$ is given by the formula $\sum _{j=0}^{n}j!(r-1{)}^j{\left(\genfrac{}{}{0ex}{}{n}{j}\right)}^2$. Also we prove that there are only one Wilf class for r=1, four Wilf classes for r=2, and six Wilf classes for $r\ge 3$.

13 pages, 1 table, 1 figure