How many inversions in a permutation contain a fixed point?

43 Views Asked by At

An inversion occurs in permutation $X$ when $i < j$ and $X_i > X_j$, or when $i > j$ and $X_i < X_j$. A fixed point occurs when $X_i = i$, i.e., it is a cycle of length 1. If the pair $(X_i, X_j)$ is an inversion, obviously at most one of the two can be a fixed point.

I have found that, for $n = 4$, if a permutation of length $n$ contains any inversions, then the majority of inverted pairs contains no fixed points. In other words, for any of the $n!$ permutations of length $n = 4$, the probability of picking an inversion at random in that permutation, and finding that either $X_i$ or $X_j$ is a fixed point, is $P < .5$.

I would like to show whether this holds for larger $n$. Does a proof (or disproof) exist with respect to the proportion of inversions that contain fixed points? Or can someone guide me to how one would prove (disprove) it? Thanks!

Edit: I found a counterexample at $n = 5$: $(1,5,3,4,2)$. The fixed points are {$1,3,4$}, and the inversions are {$(5,3),(5,4),(5,2),(3,2),(4,2)$}. So $4/5$ of inversions contain a fixed point. I'm still interested in any theorems that exist related to this question.