Let A be an Array of the length n. A is filled randomly with distinct numbers ($\forall (i,j) < n: i \neq j \implies A[i] \neq A[j] $).
What is the total expected value (amount) of pairs (indexed i,j) with $i < j \land A[i] > A[j]$ in an array of the length n?
I started to look at a certain index $i$ but couldn't figure out the expectancy value of the count of numbers with an index smaller than $i$ and bigger than the number at index $i$.
Implementing that code I figured out, that the higher n is the nearer the expectancy value is to the count of pairs, when the array is sorted descending.
I would appreciate any hint to help me wrapping my mind around it.
You are counting what are called "inversions of permutations".
For each $i$ and $j$ with $i < j$, the probability that $A[i] > A[j]$ is $1/2$ (since it's equally likely for $A[i]$ or $A[j]$ to be the larger of the two).
There are $n(n-1)/2$ pairs of indices $i$ and $j$, and so the expectation you want is $n(n-1)/4$.
It can also be shown that the standard deviation of the number of inversions of a permutation of $n$ elements is on the order of $n^{3/2}$, so as $n$ gets larger these distributions get more concentrated relative to their mean.