2
$\begingroup$

Let $1 \leq m \leq n, \sigma \in S_n, \pi \in S_m$. The permutation $\sigma$ avoids $\pi$ if no subset $\{j_1 < \cdots < j_m\} \subseteq \{1,\cdots,n\}$ exists, so that for all $1 \leq i < l \leq m$ applies $\sigma(j_i) < \sigma(j_l) \Leftrightarrow \pi(i) < \pi(l)$

Prove that if a permutation $\sigma \in S_n$ avoids the permutation 123 it avoids the permutation 3124 as well (one-line-notation used for permutations).

Hi!

I first reflected on what the definition of the avoiding implies for $\sigma$ (apart from $|3124| = m = 4 \Rightarrow n \geq 4$). The only fact I discovered is that according to the definition $\sigma$ contains one ascension at most and this should "cover" the last part $124$ of $3124$.

Could you please help me to go on?

Thanks in advance!

  • 1
    Summarizing the answers below: 3124 contains a copy of 123.2011-06-25

2 Answers 2

3

Note that $\sigma$ fails to avoid $123$ iff $\sigma$ contains $123$ as a pattern, i.e., iff there are $1 \le i < j < k \le n$ such that $\sigma(i) < \sigma(j) < \sigma(k)$. Similarly, $\sigma$ fails to avoid $3124$ iff there are $1 \le i_1 < i_2 < i_3 < i_4 \le n$ such that $\sigma(i_2) < \sigma(i_3) < \sigma(i_1) < \sigma(i_4)$. But in that case $\sigma(i_2)\sigma(i_3)\sigma(i_4)$ is an instance of the pattern $123$ in $\sigma$, and $\sigma$ fails to avoid $123$ as well.

  • 0
    @trutheality you are right, sorry. my fault...2011-06-26
0

Intuitively, $\sigma$ avoids $\pi$ if it is impossible to apply the $\pi$ to $m$ objects as follows:

  • Add $n-m$ objects to your ordered collection preserving the relative order of the original $m$ objects
  • Apply $\sigma$
  • Remove the objects you added.

Observation: $3124$ does not avoid $123$:

$123$ rearranges $ABC$ into $ABC$. We can add $X$ to get $XABC$, apply $3124$ to get $ABXC$, remove $X$ and get $ABC$.

I hope that intuition helps you move forward.

Also notice that $1234$ avoids $3124$ (trivial: different permutations of the same size avoid each other), but doesn't avoid $123$.