Bubble sort: average number of total key comparisons
I'm assuming that all elements in the array you're sorting are distinct.
The average number of comparisons over all permutations of the array is equal to the expected value of the number of comparisons, so let's calculate that instead.
The total number of comparisons done to sort some array $A$ (length $N$) is equal to $N - 1 + (\text{Number of inversions in } A)$, where an inversion is a pair of indices $i &lt; j$ where $A_i &gt; A_j$. By linearity of expectation, the expected number of comparisons is thus
$$
N - 1 + \sum_{i &lt; j}P(A_i &gt; A_j) = N - 1 + \frac{N(N - 1)}{4}
$$