Relationship between fixed points and inversions in permutations

Question

Inversions in a permutation $Y$ are defined as pairs where $Y_a < Y_b$ but $a > b$, while fixed points in $Y$ are defined as elements where $Y_a = a$ (i.e., 1-cycles). Let $S_\alpha$ be the set of all permutations of length $n$ with exactly $j$ inversions and $k$ fixed points, for some $j \leq n$ and some possible $k \leq n$ (i.e., not all $k$ are possible for all $j$). Let $S_\beta$ be the set of all permutations of length $n$ with exactly $j-1$ inversions. Let $S_\delta$ be the subset of $S_\beta$ with fewer than $k$ fixed points. I conjecture the cardinality of $S_\delta$ is no greater than half the cardinality of $S_\beta$, for all $n > 1$, all $j$, and all possible $k$.

The significance of the conjecture is that, if true, it implies the expected number of fixed points strictly increases as the expected number of inversions decreases. That, in turn, implies the expected number of fixed points in a bivariate random sample $(X, Y)$, from a population distribution with correlation parameter $\rho$, is monotone increasing in $\rho$, for any distribution where expected Kendall's $\tau$ is increasing in $\rho$ (e.g., the bivariate normal).

Edit: The "implication" stated above is false. The conjecture is strictly combinatorial--it assumes all permutations occur with equal frequency--so it can have no direct implication under nonzero tau--where permutations nearer the uniform permutation (1, 2, ... , n) occur with greater frequency as tau becomes more positive.

I'm looking for a proof if one exists (a direct proof of either implication would do as well). I've searched the mathematical statistics literature with little luck--although Mallows models with the Kendall tau distance seem promising--but I'm not a combinatorialist. Otherwise, thoughts on how to proceed are appreciated.

Answer 1

If we take $n=4,j=4$ then $k=1$ is possible (e.g. permutation $2431$). Looking at permutations with $j−1$ inversions we get $S_\beta=\{1432,2341,2413,3142,3214,4123\}$ and $S_\delta=\{2341,2413,3142,4123\}$, which is a counterexample to the conjecture in the question.

In a follow-up comment you observed

On the other hand, the inverse conjecture (ha) appears true on average (via simulations): if you increase the number of fixed points in the permutation, you will decrease the expected number of inversions.

This does appear to be true. I've tested it numerically up to $n=28$, and by examining those data I conjecture that the expected number of inversions for a permutation uniformly selected from permutations on $n$ elements with $k \in [0, n] \setminus \{n-1\}$ fixed points is $$\mathbb{E}(\textrm{inv}) = \frac{1}{12} \left( 3n^2 - 2kn - k^2 - n + k +1 + (-1)^{n-k} \frac{n-k-1}{!(n-k)} \right)$$ where $!(n-k)$ is the subfactorial / derangement number.

I would expect to find some tables for total number of inversions (i.e. the numerators of the expected values before cancelling common factors with the denominators) in OEIS if this had been studied before, and the closest I could find is A216239 for the total number of inversions in derangements on $n$ elements.

Answer 2

A counterexample for $n = 4$ was given in the comments (2431, per @PeterTaylor). Monte Carlo simulation results of my own suggest counterexamples ought to increase with increasing $n$.

Moreover, the second paragraph of my question, about implications of the conjecture, is incorrect. The expected number of inversions for fixed $n$ is a constant, so it cannot covary with anything. Also, if a conjecture is strictly combinatorial, it only has implications for when $\rho = 0$. On reflection, I believe the relevant conjecture must be probabilistic, not combinatorial.

I therefore revise my conjecture on the relationship between fixed points and inversions in permutations as follows. The expected number of fixed points, $E(k)$, increases as the expected number of inversions, $E(j)$, decreases, for $n$ fixed and $\rho$ ranging over $[-1,1]$. This is very much the sort of conjecture one might prove (or disprove) via a Mallows tau model, as described in, e.g., Mukherjee (2016) and He (2022). They model a permutation as drawn from a distribution of permutations, with location parameter the identity permutation $(1, 2, \dotsc , n)$, and spread parameter the expected Kendall tau distance. The latter is a rescaled Kendall's $\tau$ correlation coefficient.

In fact, I believe He (2022) in particular proves the revised conjecture for all $E(\tau) < 0$ (or $q < 1$, in his notation). He's Proposition 5.3 (p. 17) states that the expected number of fixed points in that case is equal to the probability that any one element in the permutation is a fixed point. Thus, expected fixed points range from $.5$ to $1$ as $\tau$ ranges from $-1$ to $0$. (The minimum expectation is $.5$ because, when the permutation is a complete inversion, it has no fixed points if $n$ is even but the middle element is always fixed for odd $n$, which averages to $.5$.)

His models for $E(\tau) > 0$ ($q > 1$) are far more complex. He does not seem to explicitly derive the expected number of fixed points in that case. This is therefore only a partial answer. Any further answers or thoughts are welcome!