Skip to main content
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