Skip to main content
MathOverflow

Return to Answer

Simplify the conjectured form to a closed form
Source Link
Peter Taylor
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

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{k(n-k)}3 + \frac{\sum_{j=0}^{n-k-2} (-1)^j \frac{(3n-3k+j)(n-k-j-1)}{j!}}{ 12 \sum_{j=0}^{n-k} (-1)^j \frac{1}{j!}}$$$$\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.

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{k(n-k)}3 + \frac{\sum_{j=0}^{n-k-2} (-1)^j \frac{(3n-3k+j)(n-k-j-1)}{j!}}{ 12 \sum_{j=0}^{n-k} (-1)^j \frac{1}{j!}}$$

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.

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.

Source Link
Peter Taylor
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

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{k(n-k)}3 + \frac{\sum_{j=0}^{n-k-2} (-1)^j \frac{(3n-3k+j)(n-k-j-1)}{j!}}{ 12 \sum_{j=0}^{n-k} (-1)^j \frac{1}{j!}}$$

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.