We study how the inversion statistic is influenced by fixed points in a permutation. %The expected number of inversions in a uniformly random permutation in $S_n$ is $\frac{ n(n-1)}4$. For each $n\in\mathbb{ N}$, and each $k\in\{ 0,1,\cdots, n\}$, let $P_n^{ (k)}$ denote the uniform probability measure on the set of permutations in $S_n$ with exactly $k$ fixed points. We obtain an exact formula for the expected number of inversions under the measure $P_n^{ (k)}$ as well as for $P_n^{ (k)}(\sigma^{ -1}_i<\sigma^{ -1}_j)$, for $1\le i<j\le n$, the $P_n^{ (k)}$-probability that the number $i$ precedes the number $j$. In particular, up to a super-exponentially small correction as $n\to\infty$, the expected number of inversions in a random derangement $(k=0)$ is $\frac16n+\frac1{ 12}$ more than the value $\frac{ n(n-1)}4$ that one obtains for a uniformly random general permutation in $S_n$. On the other hand, up to a super-exponentially small correction, for $k\ge2$, the expected number of inversions in a random permutation with $k$ fixed points is $\frac{ k-1}6n+\frac{ k^2-k-1}{ 12}$ less than $\frac{ n(n-1)}4$. In the borderline case, $k=1$, up to a super-exponentially small correction, the expected number of inversions in a random permutation with one fixed point is $\frac1{ 12}$ more than $\frac{ n(n-1)}4$. The proofs make strategic and perhaps novel use of the Chinese restaurant construction for a uniformly random permutation.
Categories: math.PR math.CO