Número de clases de equivalencia de permutaciones que son equivalentes si los números pares(Impares) vecinos pueden intercambiarse

Question

Dejemos que $S_8$ sea el conjunto de todas las permutaciones de $1,2,\dots, 8$ . Por ejemplo $\sigma=(8,5,4,3,1,2,6,7)$ es una permutación . Definimos la relación de equivalencia $\sim$ en $S_8$ tal que si dos números vecinos Impares (o pares) en una permutación $\sigma$ se intercambian, la permutación derivada $\tau$ equivale a $\sigma$ Es decir, $\sigma \sim \tau$ . Por ejemplo:

$$(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)$$

He escrito un programa que dice que hay 6902 clases de equivalencia (si es un programa correcto). ¿Hay algún método matemático más sencillo para contar el número de clases de equivalencia?

Nota: $(8,5,4,3,1,2,6,7)$ es un arreglo de números y no tiene nada que ver con las permutaciones cíclicas.

Answer 1

Acerquémonos por casos ( tristemente ).

Los siguientes setenta casos son posibles: EEEEOOOO, EEEOEOOO, EEEOOEO, EEEOOOEO, EEEOOOOE, EEOEOEOOO, EEOEOEOO, EEOEOOEO, EEOEOOEO, $\dots$

Para un caso concreto, como $EEEOOOEO$ Elige qué tres números pares aparecen en el primer bloque de E's, qué tres números Impares aparecen en el primer bloque de O's, etc... para un total de $\binom{4}{3}\binom{4}{3}\binom{1}{1}\binom{1}{1}=16$ posibilidades en este caso.

Del mismo modo, un caso como $EEOEOEOO$ habría $\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$ posibilidades, mientras que un caso como $EEEEOOOO$ sólo tendría una posibilidad.

Continuando con el tedioso proceso, se podría encontrar el número total de clases de equivalencia diferentes de esta manera.

También se podría escribir un programa para realizar esta tarea, recorriendo los ochenta casos posibles, analizando la cadena de E's y O's para las longitudes de los bloques, y multiplicando los coeficientes binomiales (o multinomiales, si se prefiere).

Answer 2

Podemos dividirlo en casos, según el número de bloques de enteros Impares y enteros pares que aparezcan en la permutación, utilizando el hecho de que 2 bloques son de la forma 2/2 o 3/1:

$\textbf{a)}$ 1 impar, 1 incluso: $\;\;$$ \posibilidades

$\textbf{b)}$ 1 impar, 2 par o 2 impar, 1 par: $\;\;2\cdot\left(2\binom{4}{1}+\binom{4}{2}\right)=\color{red}{28}$ posibilidades

$\textbf{c)}$ 2 Impares, 2 pares: $\;\;\left[\binom{4}{2}+2\binom{4}{1}\right]\left[2\binom{4}{2}+2\cdot2\binom{4}{1}\right]=\color{red}{392}$ posibilidades

$\textbf{d)}$ 2 Impares, 3 pares o 3 Impares, 2 pares: $\;\;2\cdot\left[\binom{4}{2}+2\binom{4}{1}\right]\left[3\cdot2\binom{4}{2}\right]=\color{red}{1008}$ posibilidades

$\textbf{e)}$ 3 impar, 3 incluso: $\;\;2\left[3\binom{4}{2}\cdot2\right]^2=\color{red}{2592}$ posibilidades

$\textbf{f)}$ 3 Impares, 4 pares o 4 Impares, 3 pares: $\;\;2\cdot4!\cdot3\binom{4}{2}\cdot2=\color{red}{1728}$ posibilidades

$\textbf{g)}$ 4 impar, 4 incluso: $\;\;2\cdot4!\cdot4!=\color{red}{1152}$ posibilidades

Esto da un total de $\color{blue}{6902}$ clases de equivalencia.