1

I came across inverse number defined as - the number of transpositions of pairs of elements that must be composed to place the elements in canonical order $012\ldots(n-1)$.

Please clarify it with an example. In general is there any way to calculate it?

Michael Hardy
  • 1
Adam Levine
  • 73
  • If you have the permutation $(0,1,2)$ the inversion number is $0$. For the permutation $(0,2,1)$ the inversion number is $1$ since it is enough to switch $1$ and $2$ to get it in order. For the permutation $(2,0,1)$ we switch first $2$ and $0$ to get $(0,2,1)$ and then we switch $2$ and $1$ to get $(0,1,2)$. So, inversion number is $2$. – conditionalMethod Dec 01 '19 at 13:53
  • @conditionalMethod do we have a generalized method to find the number given any random permutation of length n? – Adam Levine Dec 01 '19 at 14:07
  • Whenever, you see a pair of entries that are not in order swap them and add $1$ to the count. Do that until the permutation is in order. In other words, you run Bubble sort counting how many steps it took to get the permutation sorted. – conditionalMethod Dec 01 '19 at 14:11

0 Answers0