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


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
    $\begingroup$ Summarizing the answers below: 3124 contains a copy of 123. $\endgroup$ – Yuval Filmus Jun 25 '11 at 23:29

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.

  • $\begingroup$ @brian-m-scott thanks! $\endgroup$ – muffel Jun 26 '11 at 8:27
  • $\begingroup$ @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? $\endgroup$ – muffel Jun 26 '11 at 18:26
  • $\begingroup$ @muffel: Read more carefully. That's not what he said. $\endgroup$ – trutheality Jun 26 '11 at 19:11
  • $\begingroup$ @trutheality you are right, sorry. my fault... $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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