2
$\begingroup$

Show that the largest number of inversions of a permutation of $\{1,2,3,4,5,6,7,8\}$ equals $n(n-1)/2$. Determine the unique permutation with $n(n-1)/2$ inversions. Also determine all those permutations with one fewer inversion.

$\endgroup$
  • $\begingroup$ Your use of the imperative, and lack of any context or any displayed effort to solve it yourself, are considered impolite here. I'm surprised your question was upvoted, and not put on hold. There is a FAQ list you should read before you ask any more questions. You are lucky that a few people were generous enough to answer. $\endgroup$ – Stefan Smith Oct 2 '13 at 19:32
3
$\begingroup$

For the first part, observe that the number of inversions cannot exceed the number of ways to choose two numbers (since each pair accounts for at most one inversion). Hence, the number of inversions cannot exceed $\binom{n}{2} = \frac{n(n-1)}{2}$.

As for the second part, how else would you make a permutation with a lot of inversions? Put everything in reverse order. You can see that in $\{8,7,6,5,4,3,2,1\}$ that every pair is inverted, and thus we have the full $\binom{n}{2} = \frac{n(n-1)}{2}$ inversions.

Lastly, suppose you started with an arbitrary permutation with one less inversion. I claim that the only inversion must be between two adjacent elements.

  • To see this, suppose we had $a < b$ and the permutation was something like $\{..., b, ..., a, ...\}$. If any element between $b$ and $a$ is less than $b$, then it creates another inversion with $b$. However, if it is greater than $b$, it must create an inversion with $a$. Any element in between can't be equal to $b$ either. Hence, we can't have an element in between if there's only one inversion.

The permutations with one less inversion are then the 7 permutations that are just like $\{8,7,6,5,4,3,2,1\}$, but with two adjacent elements swapped.

$\endgroup$
0
$\begingroup$

$\{8,7,6,5,4,3,2,1\}$ has $8(8-1)/2$ inversions.

The number of inversions is one less in the following permutations: $\{7,8,6,5,4,3,2,1\}$,$\{8,6,7,5,4,3,2,1\}$,$\{8,7,5,6,4,3,2,1\}$,$\{8,7,6,4,5,3,2,1\}$,$\{8,7,6,5,3,4,2,1\}$,$\{8,7,6,5,4,2,3,1\}$,$\{8,7,6,5,4,3,1,2\}$. There are no others because we need only one pair of numbers to be in correct order. If $i$ and $j$ are in correct order, any number located between the two has to be less than $i$ and more than $j$, which is not possible so $i$ and $j$ have to be adjacent. Moreover, they should be consecutive numbers because any number more than $i$ and less than $j$ cannot be located to right of $i$ or left of $j$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.