Zum Inhalt springen

Permutation/Zyklus/Signumsberechnung/Aufgabe/Lösung


  1. Gemäß der Definition des Signums ist
    sgn⁡(π)=∏1≤i<j≤nπ(j)−π(i)j−i=∏1≤i<j≤n−1π(j)−π(i)j−i⋅∏1≤i<j=nπ(n)−π(i)n−i=∏1≤i<j≤n−1j+1−(i+1)j−i⋅∏1≤i<n1−(i+1)n−i=∏1≤i<j≤n−1j−ij−i⋅∏1≤i<n−in−i=1⋅∏1≤i<j=n(−1)n−1in−i=∏1≤i<j=n(−1)n−11⋅2⋯(n−2)(n−1)(n−1)(n−2)⋯2⋅1=(−1)n−1.
  2. Wir bestimmen die Fehlstände der Permutation. Zu i<j<n liegt kein Fehlstand vor. Dagegen liegt zu i<n stets ein Fehlstand vor. Es gibt also insgesamt n−1 Fehlstände, und das Signum ist (−1)n−1.
  3. Die Permutation π kann man als Produkt der Transpositionen
    π=⟨1,2⟩∘⟨2,3⟩∘⋯∘⟨n−1,n⟩

    darstellen, da ja n mit jeder Transposition um 1 nach unten transportiert wird und jede Zahl i<n durch die Transposition ⟨i,i+1⟩ auf i+1 abgebildet wird, was von den Transpositionen weiter links nicht mehr verändert wird. Es liegt also eine Zerlegung in n−1 Transpositionen vor und das Signum ist (−1)n−1.