I was watching this Algorithms Course and section where he mentions n choose 2. I wrote out the maximum number of inversions by hand for a 6-array element like this answer.
However, I am curious how he got n choose 2. I don't see how combinations come from there. My best idea to get the formula would have been start with 1 and do an arithmetic series up to n-1 as the general formula but I don't see how he got n choose 2.
I get that for the maximum number of inversions the array has to be ordered in reverse.
$\endgroup$1 Answer
$\begingroup$Well, the array has to be ordered in reverse, no? So the first element is the biggest one, that gives you $n-1$ elements in inversion with it. Then the second one has $n-2$ elements in inversion with it. In general then the inversions are$$\sum _{i=1}^n n-i=\sum _{i=0}^{n-1}i=\frac{(n-1)\cdot n}{2}=\binom{n}{2}.$$Another way to think about this is that any pair of different elements in the array are in inversion! And so there are $\binom{n}{2}$ ways to choose two elements in the array.
Edit: In general $\binom{n}{k}$ is the number of ways to pick $k$ objects without order out of $n$ objects. In your particular problem say you pick one number first, you have $n$ ways to do this. Then you want to pick a different number so now you have $n-1$ options, then you have $n\cdot (n-1)$ ways to do this by the multiplication principle. The problem is that you are giving them an order (for example, you could have chosen $3,2$ or $2,3$) so every pair of numbers you are picking twice so divide by $2$ to get $\frac{n(n-1)}{2}=\binom{n}{2}.$ The same principle can be extended to $\binom{n}{k}.$
