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$ – Per Alexandersson Mar 15 '16 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$ – Gerhard Paseman Mar 15 '16 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 '16 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$ – Gerry Myerson Mar 15 '16 at 22:00
  • 1
    $\begingroup$ @GerryMyerson : Ah, that makes stuff way more interesting. $\endgroup$ – Per Alexandersson Mar 15 '16 at 23:02
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$ – Ilya Bogdanov Mar 16 '16 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 '16 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$ – Ilya Bogdanov Mar 16 '16 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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