Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Summarizing the answers below: 3124 contains a copy of 123. –  Yuval Filmus Jun 25 '11 at 23:29

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
@brian-m-scott thanks! –  muffel Jun 26 '11 at 8:27
    
@brian-m-scott I just thought about it again. You said that if $\sigma$ fails to avoid 123 it fails to avoid 3124 as well. But does this imply that if $\sigma$ avoids 123 it avoids 3124 as well? –  muffel Jun 26 '11 at 18:26
    
@muffel: Read more carefully. That's not what he said. –  trutheality Jun 26 '11 at 19:11
    
@trutheality you are right, sorry. my fault... –  muffel Jun 26 '11 at 21:25

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.