Inclusion Exclusion Problem Regarding Reordering Strings My question is: How many ways are there to reorder $ABCDEFGHI$ such that no letter is preceded by the letter it was originally preceded by? 
I am pretty sure the answer is:
$N($sets of sequential numbers$) =$ number of places to put the set $\times$ ways to reorder other letters
$9! - N(AB) - N(BC) - N(CD) - N(DE) -...- N(HI) + N(ABC) + N(BCD)+...+N(GHI)-N(ABCD)-N(BCDE)-...-N(FGHI)+....+N(ABCDEFGHI)$
(Inclusion Exclusion Theorem)
Am I correct in this reasoning?
 A: Your formula, by the looks of it, does not consider all of the combinations. If you try it for $ABCD$, you will get $9$ instead of the correct answer of $11$.
The original eight subsets are "permutations containing AB", "permutations containing BC", "permutations containing CD", etc.
Therefore, you must then flip all $\tbinom82=28$ intersections of two subsets ("permutations containing both AB and BC", "permutations containing both AB and CD", etc), then flip back all $\tbinom83=56$ intersections of three subsets, etc.
This is not the quickest way to solve the problem.
Instead, we'll find a recurrence. Let $f(n)$ be the answer for $n$ letters.
Now, to create a valid permutation on $n+1$ letters, we can do either of two things:


*

*Take a valid permutation on $n$ letters, and insert the new letter anywhere except after the $n$th letter. There are $n\cdot f(n)$ ways to do this.

*Take a permutation on $n$ letters which is almost valid except for one pair, and break up the pair with our new letter.


How many almost-valid-but-for-one-pair permutations are there? Well, any such permutation on $n$ letters can be created from a valid permutation on $n-1$ letters by choosing one of the $n-1$ letters and "expanding" it into a pair, incrementing all the letters above. So, for instance, choosing $B$ in $BADC$, we turn it into $(BC)$ and make the old $C$ into $D$ and the old $D$ into $E$: $(BC)AED$. This process is one-to-one, so there are $(n-1)\cdot f(n-1)$ almost-valid permutations.
Therefore $f(n+1)=n\cdot f(n)+(n-1)\cdot f(n-1)$. Starting with $f(1)=1, f(2)=1, f(3)=3$ you will find that $f(9)=148329$.
