1

Sorry for this basic question. In here, we have $2$ inversions of $1$ element (from the set $\lbrace 1,2,3\rbrace$):

$$ 132, \\ 213, $$

and that $321$ is a $3$-element inversion permutation. Why $321$ is not a 1-element inversion (just switch $1 \rightarrow3$?

user2820579
  • 2,389
  • 1
    We refer to inversions as the operation of swapping adjacent elements in the permutation. Since $1$ and $3$ are not adjacent in the beginning, it is not accomplishable via a single inversion. – JMoravitz May 19 '16 at 17:24
  • I think I get it more or less. Certainly the adjacent word helps a lot! Just a comment, by some strange reason, all the definitions that I have seen never say it. – user2820579 May 19 '16 at 17:28

1 Answers1

1

First of all the number of inversions isn't defined as the minimum number of switches we can do to arrange a permutation. As explicitly stated in the give link: "Given a permutation $a_1, a_2, a_3,...$, an of the $n$ integers $1, 2, 3, ..., n$, an inversion is a pair $(a_i, a_j)$ where $i < j$ and $a_i > a_j$".

Another way to look on inversions is as swapping two adjacent elements, s.t $(a_i, a_{i+1})$ where $a_i > a_{i+1}$. So the number of inversions in a sequence is given by the number of such defined swaps you need to perform in order to sort the sequence. Additionally this type of swapping is called Bubble Sort

Stefan4024
  • 35,843