Number of equivalence classes of permutations which are equivalent if neighboring even(odd) numbers can be interchanged

Question

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.

Answer 1

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.

Answer 2

Let us approach by cases (sadly).

The following seventy cases are possible: EEEEOOOO, EEEOEOOO, EEEOOEOO, EEEOOOEO, EEEOOOOE, EEOEEOOO, EEOEOEOO, EEOEOOEO, EEOEOOOE, EEOOEEOO,$\dots$

For a specific case, such as $EEEOOOEO$, pick what three even numbers appear in the first block of E's, what three odd numbers appear in the first block of O's, etc... for a total of $\binom{4}{3}\binom{4}{3}\binom{1}{1}\binom{1}{1}=16$ possibilities in this case.

Similarly, a case such as $EEOEOEOO$ would have $\binom{4}{2}\binom{4}{1}\binom{2}{1}\binom{3}{1}\binom{1}{1}\binom{2}{2} = 6\cdot 4\cdot 2\cdot 3 = 144$ possibililities, while a case such as $EEEEOOOO$ would have only one possibility.

Continuing the tedious process, one could find the overall total number of different equivalence classes in this manner.

One could also write a program to accomplish this task as well, cycling over the eighty possible cases, parsing the string of E's and O's for the lengths of the blocks, and multiplying binomial coefficients (or multinomial coefficients if you prefer).