<s>[INST] Number of equivalence classes of permutations which are equivalent if neighboring even(odd) numbers can be interchanged Let $S_8$ be the set of all permutations of $1,2,\dots, 8$. For example $\sigma=(8,5,4,3,1,2,6,7)$ is a permutation . We define the equivalence relation $\sim$ on $S_8$ such that if two odd (or even) neighboring numbers in a permutation $\sigma$ are interchanged, the derived permutation $\tau$, is equivalent to $\sigma$, that is, $\sigma \sim \tau$. For example:
$$(8,5,4,3,1,2,6,7)\sim (8,5,4,3,1,6,2,7) \sim (8,5,4,1,3,6,2,7)$$
I wrote a program which says there are 6902 equivalence classes (if it is a correct program). Is there a simpler mathematical method to count the number of equivalence classes?
Note: $(8,5,4,3,1,2,6,7)$ is an arrangement of numbers and has nothing to do with cyclic permutations.
 [/INST] We can break this up into cases, according to how many blocks of odd integers and even integers appear in the permutation, using the fact that 2 blocks are either of the form 2/2 or 3/1:
$\textbf{a)}$ 1 odd, 1 even: $\;\;$$\color{red}{2}$ possibilities
$\textbf{b)}$ 1 odd, 2 even or 2 odd, 1 even: $\;\;2\cdot\left(2\binom{4}{1}+\binom{4}{2}\right)=\color{red}{28}$ possibilities
$\textbf{c)}$ 2 odd, 2 even: $\;\;\left[\binom{4}{2}+2\binom{4}{1}\right]\left[2\binom{4}{2}+2\cdot2\binom{4}{1}\right]=\color{red}{392}$ possibilities
$\textbf{d)}$ 2 odd, 3 even or 3 odd, 2 even: $\;\;2\cdot\left[\binom{4}{2}+2\binom{4}{1}\right]\left[3\cdot2\binom{4}{2}\right]=\color{red}{1008}$ possibilities
$\textbf{e)}$ 3 odd, 3 even: $\;\;2\left[3\binom{4}{2}\cdot2\right]^2=\color{red}{2592}$ possibilities
$\textbf{f)}$ 3 odd, 4 even or 4 odd, 3 even: $\;\;2\cdot4!\cdot3\binom{4}{2}\cdot2=\color{red}{1728}$ possibilities
$\textbf{g)}$ 4 odd, 4 even: $\;\;2\cdot4!\cdot4!=\color{red}{1152}$ possibilities
This gives a total of $\color{blue}{6902}$ equivalence classes.
</s>