0
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ Is $X$ the same thing as $N$? $\endgroup$ Nov 6, 2021 at 12:10
  • 1
    $\begingroup$ @GerryMyerson Yes, sorry for my typo. I correct it. Thanks for your comment. $\endgroup$ Nov 6, 2021 at 13:55

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.