Index of an equivalence relation on the set of permutations

Question

Let $S_{2n}$ be the set of permutations of the following set $\left\{x_1,...,x_n,y_1,...,y_n\right\}$. I define the equivalence relation on $S_{2n}$ that identifies the substring $x_iy_i$ with the substring $y_ix_i$ for every $i$. So that for example if $n=2$ $$x_1y_1x_2y_2=y_1x_1x_2y_2=y_1x_1y_2x_2=x_1y_1y_2x_2.$$ What's the index of this relation? I tried to approach this problem recursively but it's kinda messy and I'm stuck.

Answer 1

The number of equivalence classes is $$ \sum_{k=0}^{n}(-1)^k \binom nk (2n-k)!. $$

Proof: First, I will define a particular set of representatives for each equivalence class. Given any word $w$ in the equivalence class $[w]$, the representative of $[w]$ is the result of making all possible moves of the form $y_ix_i\Rightarrow x_iy_i$ in $w$, for each $i\in \{1,\dots,n\}$. Each representative will be a permutation which contains none of the substrings of the form $y_ix_i$ for any $i\in \{1,\dots,n\}$. Therefore, to count the number of equivalence classes, you can count the number strings that avoid $y_ix_i$ for each $i\in \{1,\dots,n\}$. This is done via the principle of inclusion exclusion, and it results exactly in the above expression.

In more detail, you start with all $(2n)!$ permutations, then for each $i\in \{1,\dots,n\}$, you subtract the permutations which contain the substring $y_ix_i$. Then, for each $i,j\in \{1,\dots,n\}$ with $i<j$, you must subtract the permutations which contain both $y_ix_i$ and $y_jx_j$. This continues with the three-fold, four-fold, and so on up to $n$-fold intersections.

Answer 2

This is incorrect

Your equivalence classes are elements of a quotient group, where the group $N$ you are quotienting by is the minimal normal subgroup generated by your relation. This means the index you are after is $|G/N|=[G:N]$. $G$ has two subgroups, $S_x$ and $S_y$, isomorphic to $S_n$. It is generated by these subgroups together with any one swapping element, e.g. $(x_1y_1)$. Almost all (maybe all?) of the swapping terms get identified with $1$ in $G/N$: Your relation gives $$(x_1y_1)(x_2y_1)=(x_2y_1)(x_1y_1)$$ $$\implies(x_1x_2y_1)=(x_2x_1y_1)=\sigma$$ But clearly $(x_1x_2y_1)$ and $(x_2x_1y_1)$ are inverses, so $$\sigma=\sigma^{-1}\implies\sigma^2=1$$ But $\sigma$ is a permutation of 3 elements, so we have $\sigma^3=1$. Therefore we get $\sigma=1$ in the quotient group. The same argument applies to any 3-cycles containing at least one $x$ and $y$ element. Any even permutation in G can be generated by these together with $S_x$ and $S_y$($S_{2n}$ is generated by its 3-cycles, and every 3-cycle either gets identified with $1$ in $G/N$ or is in $S_x$ or $S_y$.). So in the quotient, any even permutation can be generated by just $S_x$ and $S_y$. Assuming I haven't made a mistake.

Edit:

But there are also elements in $S_x$ and $S_y$ which are odd, which means that more than half of the elements of $S_{2n}$ are generated by $S_x$, $S_y$, and permutations which get quotiented out. But that means the entire group must be, as the subgroup they generate has an index less than $2$. Hence every element in $G/N$ can be generated by the image of $S_x$ and $S_y$. As $S_x$ and $S_y$ commute and generate the whole group, and there are no relations between them in $G/N$ other than that they commute,$G/N \cong S_x \times S_y$. So $|G/N| = |S_x| \times |S_y| = n!^2$