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

Improve this question
$\endgroup$
2
  • $\begingroup$ Is $X$ the same thing as $N$? $\endgroup$
    – Gerry Myerson
    Commented Nov 6, 2021 at 12:10
  • 1
    $\begingroup$ @GerryMyerson Yes, sorry for my typo. I correct it. Thanks for your comment. $\endgroup$
    – Rowan Ruiyuan Huang
    Commented Nov 6, 2021 at 13:55

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .