Looking at: http://dogschool.tripod.com/permutation.html

It states:

Let the following represent an ordering of the n numbers 1 to n.

a1 a2 . . . x . . . y . . . an-1 a1

Each number in the string of numbers can affect the grand total in two ways. First when it is the number we're using to count how many smaller numbers are beyond it and second when it is one of the numbers "beyond" whatever number we're using to count how many smaller numbers are beyond.

Now if we exchange elements labeled x and y how will the parity of the grand total change? Let's break up the numbers into three groups.

1. The numbers either before both x and y or after both x and y
2. The numbers between x and y.
3. x and y. 

The same numbers will be before and after the numbers in group 1 so their contribution to the grand total will not change. The numbers in group 2 will each contribute to the grand total twice once for the change in x's position (either they were less than x or x was less than them.) and again for the change in y's position. Thus their total contribution will be to change the grand total by an even number. This will not affect the parity of the permutation. Finally, x and y switching places will add or subtract 1 from the grand total depending on whether x or y is greater. Thus the parity of the grand total (odd or even) will change.

I did not undertstand this so I tried an example:

Permutations example

As described in the proof the numbers before and after the two numbers that swapped have not changed. However, the proof states that the number between the swapped numbers should change by an even number, however they do not, they changed by 1. The proof also states that the numbers swapped should increase or decrease by 1, which they have not.

To be clear I am asking about this specific proof, and trying to understand this proof. I do not want some other proof proving the same thing.


Where they talk about the contribution of a number, they don't mean the contributions as you've written them down and added them up in the bottom rows. Where it says "The numbers in group $2$ will each contribute to the grand total twice", one of these "contributions" is listed, in your sum, under that number in group $2$, and the other "contribution" is listed under the first of the swapped elements, i.e. in the third column. The only contribution that they count as a countribution of $x$ and $y$ themselves is the one that you count in the third column according to whether the number in the sixth column is lower, and that "contribution" has indeed changed by $1$.


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.