Deriving the average number of inversions across all permutations In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation:

$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A) \tag{1},$$

where $A$ is an array, $\mathbb{E}[C_{\text{swaps}}]$ is the expected number of swaps it takes to sort a random permutation with Bubblesort, $n$ is the length of $A$, and $\operatorname{inv}(A)$ is the number of inversions of $A$. 

Then (1) is equal to the following equation:

$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}. \tag{2}$$

But I don't understand how to prove (2) based on (1). Could anyone please give me a proof?
You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown".

A boring proof using induction is here.

For a constructive proof, you can follow the idea from here:


Show that the maximum number of inversions is $\binom{n}{2}$.
Observe that every permutation and its reverse pair up: their respective
sets of inversions are complement to each other, so both together add $\binom{n}{2}$ inversions to the sum.
Since this pairing neatly and uniquely covers all permutations, we get that the total number of inversions across all permutations is $\frac{n!}{2} \cdot \binom{n}{2}$.


The claim follows immediately.