Tags: #definition

pattern avoidance

Let $w=w_1,w_2,\dots ,w_n\in S_n$ (the symmetric group, but for now think of it as a permutation on $n$ letters) and $\sigma ={\sigma }_1,\dots ,{\sigma }_k\in S_k$. We say $w$ contains a pattern $\sigma$ if

• there exists $i_1<i_2<\cdots <i_k\in \{1,\dots ,n\}$
• such that $w_{i_1},w_{i_2},\dots ,w_{i_k}$ are in the same relative order as ${\sigma }_1,\dots ,{\sigma }_k$
  Otherwise, we say that $w$ avoids the pattern $\sigma$ or it is $\sigma$-avoiding.

Examples

• $w=4,6,5,1,3,2$
  • $w$ contains the pattern $\sigma =2,3,1$
  • $w$ does not contain the pattern $\rho =1,2,3$

Properties