There is an array $a\_1,\dotsc,a\_n$ whose elements are pairwise distinct. We define a reverse order pair to be an ordered pair $(a\_i,a\_j)$ such that $i < j$ and $a\_i > a\_j$. Consider the total number of reverse order pairs $N$.


Assume the array is permuted uniformly and randomly, it is well known that $E[N] = \frac{n(n+1)}{4}$. What is the probability distribution of $N$?



The distribution of number of reverse order pairs in a randomly permuted array
First, a quick note on terminology: the standard term for a "reverse order pair" is an *inversion*. Knowing this makes it easier to search for the answer:


The generating function for the number of permutations with $k$ inversions is the $q$-factorial $[n]\_q!$ as shown e.g. [here](https://www.tvhoang.com/articles/2021/03/inversion-stat-distribution-proof).


