How can I prove the following:
$d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$
where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ with $k$ inversions and where $i$ is on the left of $j.$ Similarly $d^{ji}(m,k)$ denotes the number of permutations where $i$ is on the right to $j.$
Example: $m=4$, $k=1.$ We have the following permutations $2134,1243,1324.$ So, $d^{12}(4,1)=2$ and $d^{21}(4,1)=1.$
Denote $\Delta^{ij}(m,k)=d^{ij}(m,k)-d^{ji}(m,k)$. By reverting the permutation we observe that $d^{ij}(m,k)=d^{ji}(m,{m\choose 2}-k)$, so $$ \Delta^{ij}(m,k)=-\Delta^{ij}(m,{m\choose 2}-k). \qquad (*) $$
Now we prove the statement by the induction on $m$. Firstly, we present the step, and then we establish the base case (which is $i=1$, $j=m$).
For the step from $m$ to $m+1$, assume that $j\leq m$ and $k<{m+1\choose 2}$. Take any permutation counted in $d^{ij}(m+1,k)$ and remove the number $m+1$ (say, from the $(m+1-t)$th position); the number of inversions decreases by $t$. Thus, $$ d^{ij}(m+1,k)=d^{ij}(m,k)+d^{ij}(m,k-1)+\dots+d^{ij}(m,k-m). $$ Similarly, we write the formula for $d^{ji}(m+1,k)$; this gives us $$ \Delta^{ij}(m+1,k)=\Delta^{ij}(m,k)+\Delta^{ij}(m,k-1)+\dots+\Delta^{ij}(m,k-m). $$ If $k\leq {m\choose 2}$, then the induction hypothesis immediately yields $\Delta^{ij}(m+1,k)>0$. Otherwise, several first terms cancel due to $(*)$, but there are still some remaining terms, and they are positive in view of the induction hypothesis again.
If $j=m+1$ but $i>1$, then we may similarly remove $1$ from the permutation. So we are left with the base case only.
Denote by $n(m,k)$ the total number of permutations on $m$ elements with $k$ inversions. Now, if we remove $i=1$ and $j=m$ from the permutations counted in $d^{1m}(m,k)$ and $d^{m1}(m,k)$, the number of inversions reduces controllably, provided that the positions of $i$ and $j$ are known. Indeed, if $I$ and $J$ are their positions, then the number of inversions reduces by $(I-1)+(m-J)$ (if $I<J$) and by $(I-1)+(m-J)+1$ otherwise. This way, we obtain $$ d^{1m}(m,k)=n(m-2,k)+2n(m-2,k-1)+\dots+(m-1)n(m-2,k-(m-2)) $$ and $$ d^{m1}(m,k)=n(m-2,k-(2m-3))+2n(m-2,k-(2m-2))+\dots+(m-1)n(m-2,k-(m-1)). $$ Now the inequality $\Delta^{1m}(m,k)>0$ follows from the unimodularity (and symmetry) of the sequence $n(m-2,0), n(m-2,1),\dots,n(m-2,{m-2\choose 2})$. This unimodularity can be proved similarly to our step above (and, as I assume, is well-known).
