Transposition/Fehlstände/Anzahl/Aufgabe/Lösung

Wir bestimmen für ein Paar ${\displaystyle {}(i,j)}$, ${\displaystyle {}i<j}$, ob ein Fehlstand vorliegt. Bei ${\displaystyle {}i<k}$ liegt wegen

${\displaystyle {}\tau (i)=i<\operatorname {min} \left(k,\,j\right)=\tau (j)\,}$

kein Fehlstand vor. Entsprechend liegt bei ${\displaystyle {}j>\ell }$ kein Fehlstand vor. Es sei also

${\displaystyle {}k\leq i<j\leq \ell \,.}$

Bei

${\displaystyle {}k<i<j<\ell \,}$

ist ${\displaystyle {}\tau (i)=i<j=\tau (j)}$ und es liegt kein Fehlstand vor. Bei

${\displaystyle {}k=i<j<\ell \,}$

liegt wegen

${\displaystyle {}\tau (k)=\ell >j=\tau (j)\,}$

ein Fehlstand vor und ebenso liegt bei

${\displaystyle {}k<i<j=\ell \,}$

ein Fehlstand vor. Ferner ist ${\displaystyle {}k<\ell }$ ein Fehlstand. Dies ergibt insgesamt

${\displaystyle {}(\ell -k-1)+(\ell -k-1)+1=2\ell -2k-1\,}$