Find the number of rearrangements of the string 12345 in which none of the sequences 12, 23, 34, and 45 occur. 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. 
 A: 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.$$
A: 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.
