52 A AiGNER Gerade und ungerade Permutationen in geordneter Reihenfolge

Gerade und ungerade Permutationen in geordneter Reihenfolge

Man ordnet einerseits die n ' Permutationen von n verschiedenen Elementen lexiko- graphisch an, so daß jede eine bestimmte Nummer N erhalt, andererseits scheidet man zwischen geraden und ungeraden Permutationen Die vorliegende Arbeit gilt nun dem Zusammenhang zwischen diesen beiden Gesichtspunkten

Es ist nun keineswegs so, daß eine Permutation mit gerader lexikographischer mer auch eine gerade Permutation im Sinne der Theorie ist Wohl aber ergibt sich der Charakter der Permutation eindeutig aus ihrer Nummer iV, und zwar als alleinige Funktion dieser Zahl, unabhängig von der Anzahl der Elemente n (Wir denken uns n so groß genommen, daß n^ ^ N wird ) Das sei im Folgenden gezeigt

Der Einfachheit halber nehmen wir als permutierte Elemente die Zahlen 1, 2, 3,

, n selbst und als Grundstellung ihre natürliche Reihenfolge Ferner bezeichnen wir die Permutation mit der lexikographischen Nummer N kurz mit P^, dann ist P^ die Identität, das Einheitselement der symmetrischen Gruppe Weiterhin ordnen wir, wie es auch sonst üblich ist, den geraden Permutationen das Vorzeichen -b, den raden das Vorzeichen — zu

Ist nun Ui a^ ^3 a^

irgendeine Permutation der Zahlen von 1 bis n, so ergibt sich die Nummer N dieser Permutation nach der bekannten Formel der Kombinatorik

wobei k^ die Anzahl der Vorganger von a^^ in der natürlichen Reihe ist, ^2 die Anzahl der Vorganger von ag unter den übrigen n — 1 Zahlen ohne a^, k^ die Anzahl der ganger von Äg unter den Zahlen außer a^ und a^ usw (im besonderen also stets ^1 == ^1 ~" 1) Diese Koeffizienten k bilden em eindeutiges System, und zwar geht k^ von 0 bis w 1, ^2 von 0 bis ^ — 2, allgemein k^ von Obis n — г

Zugleich ist aber k^ die Anzahl der Inversionen, welche dadurch entstehen, daß das Element a^ an erster Stelle steht, k^ weitere Inversionen kommen beim Vergleich mit a2 zustande usw , so daß die Gesamtzahl der Inversionen der betreffenden tion ^1 H- ^2 + • • • + ^n = -^ ^ betragt Daher ergibt sich ihr Vorzeichen

sign P^ = (- 1)*^ + ** + -^ ^« = (- 1)^^

aus der durch die Nummer N eindeutig gegebenen obigen Darstellung So ergibt z B. fur A^ = 43 die Formel

42 - 1 24-ЬЗ 6 + 0 2 + 0 1

sign P,3^(-1)1+3^+1, oder fur N -- 178

177 - 1 120 + 2 24 + 1 6+1 2+1 1

sign Pi78=(™ 1)1 + 2 M + l-l^+l

Die 43 und die 178 sind also gerade Permutationen