Skip to main content
2 of 2
Formatting improvements.
Davide Giraudo
  • 4k
  • 2
  • 30
  • 42

Inverse moment of the number of inversions of a permutation

Let $\pi$ be a permutation of $\{1,2,...,n\}$. A pair of elements ($\pi_i$,$\pi_j$) is called an inversion if $i$ $>$ $j$ and $\pi_i$ $<$ $\pi_j$. The total number of inversions in $\pi$ is denoted by $\mathrm{Inv}(\pi$). My question is: How can one estimate the inverse moment of $\mathrm{Inv}(\pi$), $E\left(\frac{1}{\mathrm{Inv}(\pi)}\right)$? (I don't know if there is an issue with the fact that $Inv$($\pi$) can evaluate to 0. In case it does, assume that we want to estimate the inverse moment of $\mathrm{Inv}^{\prime}(\pi) = \mathrm{Inv}(\pi) + 1$)

All that I know is that the expected number of inversions in a random permutation $\pi$, $E(\mathrm{Inv}(\pi)$), of size $n$ is $\frac{n^2 - n}{4}$. Then, Jensen’s inequality yields $E$($\frac{1}{Inv(\pi)}$) $\geq$ $\frac{1}{E(\mathrm{Inv}(\pi))}$, but I need a better (asymptotic) approximation for $E$($\frac{1}{\mathrm{Inv}(\pi)}$).