Show that the permutation [n, n-1,..., 2,1] has n(n-1) inversions

Question

Show that the permutation $[n, n-1,..., 2,1]$ has $n(n-1)$ inversions

How do I show that this is true? Why isn't $(n(n-1))/2$

Answer 1

Call your permutation $\pi$, and it's elements $\pi_i$, indexed left to right. So in this case $\pi_1=n,\pi_2=n-1,\cdots \pi_n=1$. For any pair of indices $(i,j)$, with $i<j$, you have $\pi_i>\pi_j$, the definition of an inversion. Thus the number of inversions is precisely the number of pairs of indices $(i,j)$ with $i<j$ picked from numbers $1,2,\cdots,n$. The answer is $\binom{n}{2}=\frac{n(n-1)}{2}$, which is the number of ways to pick two unordered elements from a list of $n$ numbers.