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.


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.