Timeline for Relationship between fixed points and inversions in permutations
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14 at 11:26 | comment | added | Peter Taylor | @virtuolie, yes. Multiply by $\binom{n}{k} \cdot !(n-k)$ to get the total number of inversions in all permutations with $k$ fixed points. | |
| Feb 13 at 19:01 | comment | added | virtuolie | Useful indeed. Just to be clear, your formula assumes permutations are random uniform, right? Meaning, it answers the combinatorial conjecture in the posted question, which is the special case of the probabilistic conjecture in my own "answer" where all n! permutations of length n occur with equal frequency? | |
| Feb 13 at 12:56 | comment | added | Peter Taylor | @virtuolie, part (b) done: I think the simplified form should be sufficiently useful for you subject to part (a). | |
| Feb 13 at 12:55 | history | edited | Peter Taylor | CC BY-SA 4.0 |
Simplify the conjectured form to a closed form
|
| Feb 13 at 10:59 | comment | added | Peter Taylor | @virtuolie, the full list of values for n=30 is (to 3dp) [222.583, 217.583, 212.417, 207.083, 201.583, 195.917, 190.083, 184.083, 177.917, 171.583, 165.083, 158.417, 151.583, 144.583, 137.417, 130.083, 122.583, 114.917, 107.083, 99.083, 90.917, 82.583, 74.083, 65.416, 56.585, 47.576, 38.444, 29.000, 19.667, NaN, 0.000]. Empirically it seems that there's more to be said about the trend: if you fit a quadratic to E(inv) as a function of k for fixed n, it seems to be an extremely good fit, so it may be worth trying to (a) prove the conjectured formula; (b) prove a quadratic asymptotic form. | |
| Feb 12 at 23:20 | comment | added | virtuolie | Interesting. In my simulation, I'm generating 100,000 random permutations of length n and outputting the number of fixed points and the number of inversions in each. I'm then computing the mean number of inversions among all permutations with 0 fixed points, then the mean among those with 1 fixed point, and so on. The sequence I obtain for n=30,k=0,1,2,3,4,5,6,7, is j=222.8,217.5,212.5,207.5,201.0,195.4,188.9,185.1, which agrees well with your formula. Does the trend change for larger k (which are too low frequency to show up in a simulation of only 100,000 reps)? | |
| Feb 12 at 22:25 | vote | accept | virtuolie | ||
| Feb 12 at 17:06 | history | answered | Peter Taylor | CC BY-SA 4.0 |