Beilage zum Jahresbericht der Groszherzoglichen Realschule zu Oppenheim. Ostern 1906.

H. Hirsch,

UÜber gerade und ungerade Permutat

T.

Eine endliche Menge von Dingen läßt sich auf verschiedene Weisen abzählen; man kann sie auf mehrere Arten anordnen.

Sind als Elemente die beiden natürlichen Zahlen l und 2 gegeben, so sind 2 Anordnungen möglich. Bei den 3 natürlichen Zahlen 1, 2 und 3 kann jedes Element an die erste Stelle treten, und die beiden übrigen können auf 2 verschiedene Arten folgen. Es gibt dann 6 Anordnungen. 4

Eine solche Anordnung heißt eine Permutation. Bein natürlichen Zahlen ist die Anzahl der Permutationen gleich dem Produkt der Zahlen von l bis n

= l 2 3.... n= n!

Folgt in einer Permutation auf eine höhere Ziffer eine niedere, so heißt diese Aufeinanderfolge eine Inversion. Es ist dabei einerlei, ob zwischen diesen Ziffern noch andere stehen; die Permutation hat soviele Inversionen, als höhere Ziffern vor niederen stehen. Z. B. die Permutation 1746352 hat die Inversionen 74, 76, 73, 75, 72, 43, 42, 63, 65, 62, 32, 52.

Folgen in der Permutation die Zahlen in der natürlichen Reihenfolge, so ist die Inversionenzahl gleich Null, da alsdann nur niedere Zahlen vor höheren stehen; z. B. 1234567 hat keine Inversionen. Sind die Elemente in umgekehrter Ordnung gegeben, so haben wir die größtmöglichste Zahl von Inversionen, nämlich bein Fle-

menten n6=h(e). da sichen Elemente zu(2

2 wollen sie die Maximalzahl der Inversionen nennen. Für unsere als Beispiel erwählte Permutation ergibt sich: 7654321 hat 6+ 5+ 4+ s3S+ͤ2+ 1=(2)= 21 Inversionen.

Es lassen sich bei den Permutationen solche unterscheiden, die eine gerade Anzahl von Inversionen haben, und solche, die eine ungerade Anzahl haben. Erstere sind die geraden und letztere die ungeraden Permutationen. 7432615 mit 14 In- versionen ist eine gerade Permutation, während 5162347 mit 7 Inversionen zu den un- geraden zu rechnen ist.

Vertauscht man in einer Permutation zwei aufeinanderfolgende Elemente, so wird aus einer geraden eine ungerade Permutation und umgekehrt. Durch diese Vertauschung wird in den Inversionen mit den Elementen vor und nach den beiden vertauschten nichts geändert, dagegen ändert sich die Inversion der beiden ver- tauschten Elemente. Beispiel: die Permutation 5162347 hat 7 Inversionen, ist also eine ungerade Permutation. Andert man durch Vertauschung der Elemente 6 und 2 in 5126347, so ist die Anzahl der Inversionen 6, die Permutation also gerade. Das- selbe gilt, wenn man zwei beliebige Elemente miteinander vertauscht. Denn es ist leicht einzusehen, daß jede Transposition nur durch eine ungerade Anzahl von Ver- tauschungen aufeinanderfolgender Elemente möglich ist*).

) Paaren vereinigen lassen. Wir

*) Vgl. Netto, Kombinatorik. Kap. 54.

N. 3lI.