Number of Inversions: Image vs. Text

This post is quick. I’m going to draw your attention to a neat technique used to calculate a number of inversions of a given permutation. It’s a really pity I wasn’t told it when they first tried to teach me determinants. My only hope is that if you are ever to explain the concept of a parity of a permutation you will provide your listener with this trick. There are people (like me) for whom it will make a huge difference.

So consider a permutation

\displaystyle{\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 3 & 5 & 1 & 6 & 2\end{pmatrix}}

You could find it’s number of inversions to be 8. Arguably the common method for such a calculation is more suitable for a computer, rather than a human. It is so unnatural to me that I won’t even formulate one. However the following picture should be self-explanatory:

The number of inversions is just the number of intersections of the curves. However, there are some rules to be followed while drawing such diagrams. But again, I won’t bother myself formulating them. I simply state that the following picture is wrong:

No doubt you got the idea in less than a second. Obviously, a common algorithm is well suited for computers and calculation of inversions is really a job for a computer. But for teaching humans it not so good.

Advertisements
This entry was posted in Math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s