Fehlstände einer Permutation bestimmen

Question

1	2	3	4	5	6
6	2	1	5	3	4

Die Fehlstände sind (1, 2),(1, 3),(1, 4),(1, 5),(1, 6),(2, 3),(4, 5),(4, 6).

Ich verstehe nicht wie man darauf kommt. :/

Comments

Bezeichne die Permutation mit \(\pi\). Ein Paar \((i,j)\) ist ein Fehlstand, wenn \(i< j\) und \(\pi(i)>\pi(j)\) gilt. Diese Bedingung ist hier wie man leicht nachprüft für die genannten Paare erfüllt. Z.B ist \((4,5)\) wegen \(4<5\) und \(\pi(4)=5>3=\pi(5)\) ein Fehlstand.

Answer 1

1	2	3	4	5	6
6	2	1	5	3	4

Die Fehlstände sind (1, 2) weil 6>2 ,(1, 3) weil 6> 1,(1, 4) weil 6>5,(1, 5) weil 6>3,(1, 6) weil 6>4,(2, 3) weil 2>1,(4, 5) weil 5>3,(4, 6) weil 5>4.

Man schaut, ob in der unteren Zeile > gilt, wenn oben < gilt. Wenn das so ist, ist das ein Fehlstand.