5
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Are you sure this is stated correctly? if i is to the left of j, then there is exactly one LESS inversion. $\endgroup$ Mar 15, 2016 at 20:51
  • $\begingroup$ 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. $\endgroup$ Mar 15, 2016 at 21:08
  • $\begingroup$ 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. $\endgroup$
    – sankha
    Mar 15, 2016 at 21:15
  • 2
    $\begingroup$ @Per, OP is not making a claim about the number of inversions, but about the number of permutations with a given number of inversions. $\endgroup$ Mar 15, 2016 at 22:00
  • 1
    $\begingroup$ @GerryMyerson : Ah, that makes stuff way more interesting. $\endgroup$ Mar 15, 2016 at 23:02

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ In view of the methods, I would assume that a generating functions approach may simplify everything... $\endgroup$ Mar 16, 2016 at 11:36
  • $\begingroup$ 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)$ ? $\endgroup$
    – sankha
    Mar 16, 2016 at 12:38
  • $\begingroup$ I've added some words on this. Recall that these formulas work only in the base case, where $i=1$ and $j=m$. $\endgroup$ Mar 16, 2016 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.