Find the number of rearrangements of the string 123456 in which none of the sequences 123, 321, 456, and 654 occur.

Question

My attempt:

Let $A_{1}$ denotes where 123 occurs, $A_{2}$ denotes where 321 occurs, $A_{3}$ denotes where 456 occurs, and $A_{4}$ denotes where 654 occurs. Also $|U|$=6!

$$\begin{aligned}|A_{1} &\cup A_{2} \cup A_{3} \cup A_{4}|\\ &= |A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|\\ &\quad -(|A_{1}A_{2}|+|A_{1}A_{3}|+|A_{1}A_{4}|+|A_{2}A_{3}|+|A_{2}A_{4}|+|A_{3}A_{4}|)\\ &\quad +|A_{1}A_{2}A_{3}|+|A_{1}A_{2}A_{4}|+|A_{1}A_{3}A_{4}|+|A_{2}A_{3}A_{4}|\\ &\quad-|A_{1}A_{2}A_{3}A_{4}|\\ =& \ ? \end{aligned}$$

Then,

$$\begin{aligned}|A_{1}'A_{2}'A_{3}'A_{4}'|& =|U|-|A_{1} \cup A_{2} \cup A_{3} \cup A_{4}|\\ &= 6!-? \end{aligned}$$

I am pretty sure this is ALL wrong. Please help me with this problem. Thank you!

Answer 1

Your approach is quite ok.

We can enhance readability a bit by denoting the sets $A_1,A_2,A_3,A_4$ with \begin{align*} A_{123},A_{321},A_{456},A_{654} \end{align*} instead. We apply the IEP and obtain \begin{align*} |A|&=6!-\left(|A_{123}|+|A_{321}|+|A_{456}|+|A_{654}|\right)\\ &\qquad+\left(|A_{123}\cap A_{456}|+|A_{123}\cap A_{654}|+|A_{321}\cap A_{456}|+|A_{321}\cap A_{654}|\right) \end{align*}

We do not have to respect more terms, since $$A_{123}\cap A_{321}=A_{456}\cap A_{654}=\emptyset$$

Since $|A_{123}|=4!$ and $|A_{123}\cap A_{456}|=2!$ we get due to symmetry \begin{align*} \color{blue}{|A|}&=6!-4\cdot4!+4\cdot 2!\\ &=720-96+8\\ &=\color{blue}{632} \end{align*}