Expected value of inversions of pairs in a list of numbers Question:
For $1 < i,j <n$, the ordered pair $(i, j)$ is called an inversion in a permutation
of $1,2,...,n$ if $i < j$ and $j$ precede $i$ in the permutation. For instance,
in the permutation $3,5, 1,4,2$ there are six inversions: $(1,3), (1,5), (2,3), (2,4), (2,5)$, and $(4,5)$. Suppose we choose a permutation $\rho$
from among the $n!$ permutations.

*

*Let $X_{i,j}$, be a random variable such that $X_{i,j} = 1$ if
$(i,j)$ is an inversion in $\rho$, and $X_{i,j} = 0$ otherwise. What
is $E(X_{i,j})$, the expectation of $X_{i,j}$?


*What is the expected number function of inversions in $\rho$?
Express it as a function of $n$.

Solution attempt:
I have been thinking and noticed that if we have a sorted list of numbers like this: $1,2,3,4,5$ then there is no inversion pair.
Similarly, if we have a reverse sorted list like this: $5,4,3,2,1$ then we have a maximum number of inversions.
Now the question is asking for $E(X_{i,j}) = 1 \times \text{Prob}(X_{i,j} \in \rho) + 0 \times \text{Prob}(X_{i,j} \not \in \rho) = \text{Prob}(X_{i,j} \in \rho)$
I have also been thinking about the number of possibilities of inversion pairs if we have a list of $n$ numbers. There is a constraint about the position of $i$ and $j$ in the list and there is a constraint about the value of the list at $i$ and $j$. If we just look at the position then in the best-case scenario we have $(n-1) + (n-2) + \dots + 1 = \frac{n \times (n-1)}{2}$ possibilities.
I think I am lost.
 A: For every permutation where $i$ precedes $j$ there is one where $j$ precedes $i$ (just swap $i, j$ in the permutation). If all permutations are equally likely then the probability that $X_{i,j} = 1$ is $1/2$. So $\mathbb{E}(X_{i,j}) = 1/2$.
The number of inversions is given by
$$I = \sum_{i=1}^n \sum_{j=i+1}^n X_{i,j},$$
and since for any RVs $X,Y$, $\mathbb{E}(X + Y) = \mathbb{E}(X) + \mathbb{E}(Y)$, we have
$$\mathbb{E}(I) = \sum_{i=1}^n \sum_{j = i + 1}^n \mathbb{E}(X_{i,j}).$$
We know that $\mathbb{E}(X_{i,j}) = 1/2$ for any $i,j$ so
$$\mathbb{E}(I) = \sum_{i=1}^n \sum_{j= i+1}^n 1/2 = \frac{n(n-1)}{4}$$
gives the expected number of inversions.
A: I just want to outline a different method to solve the same problem.
Let $\mathfrak{S}_n$ be the set of permutations of $[n]$. Then, we can define the polynomial $$I_n(q)=\sum_{w\in \mathfrak{S}_n}
q^{\mathrm{inv}{(w)}},$$ where $\mathrm{inv}(w)$ is the number of inversions in a particular permutation $w\in \mathfrak{S}_n$.
If $I_{n,k}$ denotes the number of permutations with $k$ inversions, then we can say that $$\tag1 I_n(q)=\sum\limits_{k\ge 0}I_{n,k}q^k .$$
From $(1)$, the expected value of inversions is then, $$\mathbb{E}(I)=\frac{\sum\limits_{k\ge 0}kI_{n,k}}{n!}=\frac{I'_n(1)}{n!}.$$
It is known that $I_n(q)=(1+q)(1+q+q^2)\dots(1+q+\cdots+q^{n-1})$.
$$\frac{I'_n(q)}{I_n(q)}=\sum_{i=1}^{n-1} \frac{(1+2q+3q^2+\cdots+iq^{i-1})}{1+q+\cdots+q^i}\ \ \ \ \text{(Product rule for differentiation)}$$
$$\implies \frac{I'_n(1)}{n!}=\sum_{i=1}^{n-1} \frac{i(i+1)}{2(i+1)}=\sum_{i=1}^{n-1} \frac{i}{2}=\frac{n(n-1)}{4}$$
We have used the fact that $I_n(1)=\sum_{w\in \mathfrak{S}_n} 1^{\mathrm{inv}(w)}=n!.$
A: You can use q-analog to solve the question.
$$
\sum_{\pi \in \mathrm{S}_n} q^{\mathrm{maj}(\pi)}=\sum_{\pi \in \mathrm{S}_n} q^{\operatorname{inv}(\pi)}=[n]_{q} ! .
$$
we can say $[n]_q!$ describes how 【inversion numbers of permutaions from $S_n$】 distribute.
e.g.
QFactorial[4, q] // FunctionExpand // Expand    (*Mathematica*)

$$
1 + 3 q + 5 q^2 + 6 q^3 + 5 q^4 + 3 q^5 + q^6
$$
which means in $S_4$, there are $1$ permutation whose inversion number is $0$, $3$ permutation whose inversion number is $1$, $5$ permutation whose inversion number is $2$,...
also,
it  means in $S_4$, there are $1$ permutation whose major index is $0$, $3$ permutation whose major index is $1$, $5$ permutation whose inversion number is $2$,...
note that $1+3+5+6+5+3+1=24=4!$
we use $[n]_q!/n!$ as normalized version(i.e. PGF,ProbabilityGeneratingFunction of the distributioon of inversion number of a permutaion from $S_n$)

We have calculated the PGF here is $[n]_q!/n!$ , it's easy to calculate numerical characters like: （if PGF $G(q)=\sum \operatorname{Pr}(X=q) q^k$）
Expectation,
$$
\begin{gathered}
\operatorname{Mean}(X)=G^{\prime}(1) 
\end{gathered}
$$
Variance,
$$
\operatorname{Var}(X)=G^{\prime \prime}(1)+G^{\prime}(1)-G^{\prime}(1)^2
$$
etc.

see first $10$ values of $G'(1)$       for n in (1..=10)
gPrimeAt1 = 
 Table[QFactorial[n, q]/n! // FunctionExpand // Expand, {n, 1, 10}] //
   Map[D[#, {q, 1}] /. {q -> 1} &, #] &

$$
\left\{0,\frac{1}{2},\frac{3}{2},3,5,\frac{15}{2},\frac{21}{2},14,18,\frac{45}{2}\right\}
$$
see first $10$ values of $G''(1)$     for n in (1..=10)
gPrime2At1 = 
 Table[QFactorial[n, q]/n! // FunctionExpand // Expand, {n, 1, 10}] //
   Map[D[#, {q, 2}] /. {q -> 1} &, #] &

$$
\left\{0,0,\frac{5}{3},\frac{49}{6},\frac{145}{6},\frac{335}{6},\frac{665}{6},\frac{595}{3},329,515\right\}
$$
