Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$

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.$

• Are you sure this is stated correctly? if i is to the left of j, then there is exactly one LESS inversion. – Per Alexandersson Mar 15 '16 at 20:51
• Not necessarily. Swapping just 1 and n can give an inversion count of 2n-3. Gerhard "Depends On What You're Counting" Paseman, 2016.03.15. – Gerhard Paseman Mar 15 '16 at 21:08
• For $m=4,$ and $k=1$ the permutations are $2134, 1324, 1243$. So, $d^{12}(4,1)=2$ and $d^{21}(4,1)=1.$ I hope this example clarifies the statement. – sankha Mar 15 '16 at 21:15
• @Per, OP is not making a claim about the number of inversions, but about the number of permutations with a given number of inversions. – Gerry Myerson Mar 15 '16 at 22:00
• @GerryMyerson : Ah, that makes stuff way more interesting. – Per Alexandersson Mar 15 '16 at 23:02

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).

• In view of the methods, I would assume that a generating functions approach may simplify everything... – Ilya Bogdanov Mar 16 '16 at 11:36
• Thanks for the proof. Can you please explain how did you get the formula for $d^{ij}(m,k)$ in terms of $n(m,k)$ ? – sankha Mar 16 '16 at 12:38
• I've added some words on this. Recall that these formulas work only in the base case, where $i=1$ and $j=m$. – Ilya Bogdanov Mar 16 '16 at 12:51