# Finding The Number Of Inversions In A Permutation

Let the be the following permutation: $(1 5 4)(3 6)\in S_6$

How do I count the number of inversions to calculate the sign of the permutation?

$(1 5 4)(3 6)=(1 5)(1 4),(3 6)=3$ so it has an odd sign
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 2 & 6 & 1 & 4 & 3 \end{pmatrix}

before $5$ there are $0$ elements.
before $2$ there are $1$ elements (5).
before $6$ there are $0$ elements.
before $1$ there are $3$ elements (5,2,6).
before $4$ there are $2$ elements (5,6).
before $3$ there are $3$ elements (5,6,4).
Therefore there are $9$ inversions so it is $(-1)^9=-1$

Are both of the ways are ok?

• The sign is not even, it is odd. I'm not sure what you mean to show in that link, the permutation above is not there. – Matt Samuel May 4 '15 at 16:58
• @MattSamuel a link to WolframAlpha, it do not work, edited – gbox May 4 '15 at 16:59

If the goal is to calculate the sign of a permutation in $S_n$, then there is an easier method than calculating the number of inversions. The number of inversions in a permutation is the smallest length of an expression for the permutation in terms of transpositions of the form $(i,i+1)$. The permutation is odd if and only if this length is odd. However, it is easier to determine the smallest length of an expression for the permutation in terms of arbitrary transpositions. The permutation is odd if and only if this length is odd. A permutation can be expressed as a product of transpositions in many different ways, but the lengths of all of these products will have the same parity - always even or always odd, and this determines the sign of the permutation.
A $k$-cycle $(1,2,\ldots,k)$ can be expressed as a product of exactly $k-1$ transpositions. Thus, if the permutation consists of $r$ cycles, of lengths $k_1,\ldots,k_r$, respectively, then the permutation is odd iff $(k_1-1)+\cdots+(k_r-1)$ is odd. In the above example where the permutation was $(154)(36)$, the permutation can be expressed as a product of $(3-1)+(2-1)=2+1=3$ transpositions, hence is odd.
• "the smallest length" is the number of permutations written as $(i,i+1)$? – gbox May 6 '15 at 13:26
• Imagine placing the numbers $5,2,6,1,4,3$ in order on a line. You want to sort the array by interchanging pairs of elements at a time, but suppose that you are allowed to only swap adjacent elements each time. What is the minimum number of swaps needed? This is the number of inversions of a permutation. If $k$ such adjacent swaps are used to sort the elements in increasing order, then the given permutation can be expressed as a product of $k$ transpositions, where each transposition is of the form $(i,i+1)$ for some i. – Ashwin Ganesan May 7 '15 at 3:09