1
$\begingroup$

Suppose I have two $n$-cycles $\rho_1$ and $\rho_2$ from the same group $S_n$. I want to know how to calculate the number of adjacent transpositions I need to apply to $\rho_1$ to get $\rho_2$. It might be unclear what I mean, so here's an example:

Let $n=4$, $\rho_1 = (1423)$ and $\rho_2 = (1243)$. The answer I am looking for is that 1 adjacent transposition is needed, since you can swap the 4 and the 2. If $\rho_1 = (1234)$ and $\rho_2 = (1423)$, the answer is also 1, since I can swap the 4 and the 1.

Here are some things I have thought about to simplify the problem:

I can rename elements so $\rho_1$ is $(1 \ldots n)$, then the question is how many adjacent (where I consider the first and last elements to be adjacent) transpositions of the list $\rho_2$ (if I have a cycle $(abc)$, the list is just $[a,b,c]$) do I need to perform to sort it (where I consider it sorted if it gives the cycle $\rho_1$, i.e. there is only 1 inversion in the list).

There are some related properties of a permutation, like inversion number, that I think are closely related to this problem, but I'm not sure how to apply them to this problem, since usually what is talked about is lists that aren't cyclic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.