Skip to main content
1 of 2

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 $Inv$($\pi$). My question is: How can one estimate the inverse moment of $Inv$($\pi$), $E$($\frac{1}{Inv(\pi)}$)? (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 $Inv^{\prime}$($\pi$) $=$ $Inv$($\pi$) $+$ $1$)

All that I know is that the expected number of inversions in a random permutation $\pi$, $E$($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(Inv(\pi))}$, but I need a better (asymptotic) approximation for $E$($\frac{1}{Inv(\pi)}$).