Find the number of rearrangements of the string 12345 in which none of the sequences 12, 23, 34, and 45 occur.

Question

My attempt: Let $A_{1}$ denote where 12 occurs, $A_{2}$ denote where 23 occurs, $A_{3}$ denote where 34 occurs, $A_{4}$ denote where 45 occurs.

|$A_{1} \cup A_{2} \cup A_{3} \cup A_{4}$|= |$A_{1}$|+|$A_{2}$|+|$A_{3}$|+|$A_{4}$|-(|$A_{1}A_{2}$|+|$A_{1}A_{3}$|+|$A_{1}A_{4}$|+|$A_{2}A_{3}$|+|$A_{2}A_{4}$|+|$A_{3}A_{4}$|)+|$A_{1}A_{2}A_{3}$|+|$A_{1}A_{2}A_{4}$|+|$A_{1}A_{3}A_{4}$|+|$A_{2}A_{3}A_{4}$|-|$A_{1}A_{2}A_{3}A_{4}$|

I don't know if I'm doing this write or not. I tried to glue the 12, 23, 34, and 45 together but I don't think this is correct. The total ways this can be done with no restrictions is |U|=5!

The actual answer is: 5!-[96-3+8-1]=53.

If someone can tell me how to get this answer that would be excellent.

Answer 1

Yes, your approach is correct. Note that $|A_i|=4\cdot 3!=24$, $|A_iA_j|=6$, $|A_iA_j A_k|=2$ and $|A_1A_2A_3A_4|=1$. Hence $|A_{1} \cup A_{2} \cup A_{3} \cup A_{4}|$ is equal to $$\binom{4}{1}\cdot |A_i|-\binom{4}{2}\cdot |A_iA_j|+\binom{4}{3}\cdot |A_iA_j A_k|-\binom{4}{4}\cdot |A_1A_2A_3A_4|.$$ which implies that the number of those permutations is $|U|-|A_{1} \cup A_{2} \cup A_{3} \cup A_{4}|$: $$5!-(4\cdot 24-6\cdot 6+4\cdot 2-1)=120-(96-36+8-1)=53.$$

Alternative approach. Let $p(n)$ be the number of permutations of $[1,\dots,n]$ having no substring $[k,k+1]$ with $1\leq k\leq n-1$. Then $p(1) = 1$, $p(2) =1$ and, for $n\geq 2$ it satisfies the recurrence $$p(n+1) = n p(n) + (n-1)p(n-1).$$ Hence $p(3)=2p(2)+p(1)=3$, $p(4)=3p(3)+2p(2)=11$ and $$p(5)=4p(4)+3p(3)=44+9=53.$$

Answer 2

This is basically the right approach. You just have to work out the sizes of the various intersections. A couple of examples. Consider $A_2\cap A_3$. This consists of permutations where $2$ is followed by $3$ and $3$ by $4$. So these are arrangements of "blocks", $1$, $234$ and $5$, so $|A_2\cap A_3|=3!$ of these. On the other hand $A_2\cap A_4$ counts arrangements of blocks $1$, $23$ and $45$ so again $|A_2\cap A_4|=3!$, etc.