Problem from an old exam:
Let $X_n$ be the number of inversions in a random permutation $\pi:\{1, \ldots, n\} \rightarrow\{1, \ldots, n\}$. (Each of the $n$! permutations is equally likely.)
Find the generating function for the probability distribution of the random variable $X_n, g_{X_n}(t)$. It is sufficient to provide the answer in the form of a product (i.e., a product of $O(n)$ expressions, each in a compact form).
How to approach this problem? I know that the number of $n$-permutations with $k$ inversions is the coefficient next to $x^k$ in the expression
$$(x^{n-1}+…+x^2+x^1+x^0)…(x^2+x^1+x^0)(x^1+x^0).$$
That's because each subsequent element chooses how many elements it wants to be in inversion with.
However, how do you obtain the generating function from this?
I've seen a similar problem before, and I think that recursion was used to solve it.
Thanks.
Best Answer
Since the probability to draw a random permutation with $k$ inversions is just the number of such permutations divided by the total number of permutations, the probability generating function is just what you wrote divided by $n!$.