Timeline for Relationship between fixed points and inversions in permutations
Current License: CC BY-SA 4.0
13 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Feb 13 at 21:10 | comment | added | Steven Stadnicki | @virtuolie Isn't the relationship you described pretty straightforward? The natural map from permutations of size $n$ with $k$ fixed points to derangements of size $(n-k)$ (just remove all the fixed elements and renumber) maintains the inversion count, it's clearly an $(n$ choose $k)$ to $1$ mapping, and one would certainly expect the average number of inversions in a derangement to be an increasing function of its size. | |
Feb 13 at 19:07 | history | edited | virtuolie | CC BY-SA 4.0 |
Added a note pointing out the implication is false
|
Feb 12 at 22:25 | vote | accept | virtuolie | ||
Feb 12 at 17:23 | comment | added | JP McCarthy | Is the fact that multiplying by suitable transpositions increases the number of fixed points and decreases the number of inversions relevant? | |
Feb 12 at 17:06 | answer | added | Peter Taylor | timeline score: 2 | |
Feb 8 at 23:35 | comment | added | virtuolie | @PeterTaylor if you post your comment as an answer, I'll upvote it. I've posted my own answer, but it doesn't get full credit: it answers a revised question, which interprets the relationship between fixed points and inversions probabilistically. | |
Feb 8 at 23:33 | answer | added | virtuolie | timeline score: 1 | |
Feb 8 at 17:01 | comment | added | virtuolie | 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. | |
Feb 8 at 16:46 | comment | added | virtuolie | No, you're right. Interestingly (to me), if you plot the mean $k$ at each $j$ for $n = 4$, you see a bump at $j = 4$, the only $j$ where mean $k$ decreases from $j$ to $j - 1$. For $n=30$ (simulated), $k$ decreases on average between $j$ and $j-1$ about $47$% of the time. The *trend* is positive, $\beta = .75$, for what it's worth. I've clearly oversimplified my model by translating it into a combinatorial problem... | |
Feb 8 at 15:38 | comment | added | Peter Taylor | In that case I still need clarification as to what the conjecture is. Take $n=4, j=4$. Then $k=1$ is possible (take $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 \}$. Either I've misunderstood the conjecture or this is a counterexample. | |
Feb 8 at 15:30 | comment | added | virtuolie | Yeah, I questioned whether to include that line, but the thing is, the number of permissible fixed points depends on the number of inversions. Knowing there are j inversions to begin with determines the range of k. This was the most succinct way I could think of to define k. I shall think more on it. | |
Feb 8 at 14:51 | comment | added | Peter Taylor | I think there must be some typo in the problem statement: you define $S_\alpha$ but don't use it. My guesses for the corrected conjecture don't hold for even $n=4$, so I'm clearly not guessing correctly. | |
Feb 7 at 17:39 | history | asked | virtuolie | CC BY-SA 4.0 |