Let's say I have ABCDEF. Then, there are $6!$ permutations of reordering that string. Now, I would like to only deal with the permutations in which there are no adjacent characters. That means, I want to look at all the permutations that satisfy these constraints:
- B is not next to A or C
- C is not next to B or D
- D is not next to C or E
- E is not next to D or F
However, I am not sure where to even start with dividing out the ones I don't need.
The number of such permutations is related with the OEIS sequence A002464. By using inclusion/exclusion principle we can count the number of permutation of $\{1,2,\dots,n\}$ such that any two permuted elements are not consecutive numbers: $$n!+\sum_{i=1}^{n-1}(-1)^i\sum_{k=1}^i\binom{i-1}{i-k}\binom{n-i}{k}2^k(n-i)!$$ A proof of this formula can be found in D. P. Robbins, "The probability that neighbors remain neighbors after random rearrangements", Amer. Math. Monthly 87 (1980), 122-124.
In your case $n=6$ and the formula yields $$720-1200+768-228+32-2=90.$$