Question

Show that there are \(n(n-1) / 2\) inversions in a permutation of \(n\) distinct ordered elements with respect to its transpose.

Short answer

Yes, there are \(n(n-1) / 2\) inversions in a permutation of \(n\) distinct ordered elements with respect to its transpose because each of the \(nC2=n(n-1)/2\) pairs formed by the \(n\) elements will be an inversion when arranged in transposed sequence.

Step-by-step solution

Understanding Permutations

Start off with the definition of a permutation. A permutation of \(n\) ordered elements is an arrangement of those elements into a particular sequence. For example, if we have \(n=3\) distinct elements {1,2,3}, the permutation of these elements could be {1,3,2}, {2,1,3}, {3,1,2}, etc. Each arrangement is termed as a permutation.

Transposing the Permutations

Now, understanding that a transpose of a permutation is simply the reverse order of the permutation. As an example, the transpose of the permutation {1,3,2} would be {2,3,1}.

Inversion in Permutations

An inversion in a permutation is an arrangement where some larger element precedes a smaller one. For example, in the permutation {3,1,2}, (3,1) and (3,2) are inversions as 3 is larger and comes before 1 and 2 respectively.

Counting the Inversions

A pair of elements forms an inversion if and only if the larger number is to the right of the smaller number in the initial arrangement. So, in ordered permutation with \(n\) distinct elements, the number of pairs can be calculated by choosing 2 out of \(n\) elements which implies using the combination formula, \(nC2\). The combination formula, \(nC2=n(n-1)/2\), results from the basic principle of counting combinations in statistics and is defined mathematically by \(nC2=n!/((n-2)!2!)\). This formula gives the number of ways, disregarding order, that \(k\) items can be chosen from among \(n\) items. Therefore, there are \(n(n-1) / 2\) possible inversions in a permutation of \(n\) ordered elements with respect to its transpose because each possible pair counts as an inversion when arranged in the transposed sequence since each of them will be in reverse order in transposition.