2

Daraus folgt: Die Anzahl der geraden Permutationen ist gleich der der ungeraden.

Denn wenn man in allen Permutationen irgend zwei Elemente miteinander vertauscht, so geht stets die gerade in eine ungerade und die ungerade in eine gerade Permutation über, aber nie eine gerade in eine gerade und eine ungerade in eine ungerade. Das ist aber nur möglich, wenn die Anzahl der geraden Permutationen gleich der der ungeraden ist.

Liest man in einer gegebenen Komplexion die Elemente von rechts nach links, bildet also eine Permutation, bei der die Elemente in umgekehrter Reihenfolge angeordnet sind, so erhält man die umgekehrte oder inverse Permutation, z. B. 5163427 ist die inverse von 7243615. Alle Elemente, die in der einen Permutation eine Inversion miteinander gebildet haben, bilden in der inversen keine. Dagegen sind in beiden alle Möglichkeiten, Inversionen zu bilden, erschöpft. Mithin ist die Summe

der Inversionen beider Permutationen gleich der Maximalzahl von Inversionen=(2). Daraus läßt sich die Summe aller Inversionen aller Permutationen des Systems P(1, 2,...„n) berechnen. Alle Permutationen lassen sich in 2 n! Paare inverser Per-

mutationen zerlegen. Daraus folgt:

21(1, 2, n)= 2(a)n¹)

—

In diesem Abschnitte wollen wir uns mit geraden und ungeraden Permutationen beschäftigen, in denen sich Elemente wiederholen.

Betrachten wir zunächst das System P(Im, 2), worin das Element lum mal und 2 einmal auftritt. Mit P(1, 2) bezeichnen wir die Anzahl der geraden und mit Pa(19, 2) die der ungeraden Permutationen. Die Zahl der vorkommenden Kom-

:(m+† 1)) ſm+

plexionen=( m)

Alle Permutationen sind erschöpft, wenn die Ziffer 2 von der letzten Stelle bis zur ersten variiert. jede Permutation hat soviele Inversionen, als Einser hinter 2 stehen; es kommt demnach jede Inversionenzahl nur einmal vor. Es lassen sich die beiden Fälle unterscheiden: m gerade und m ungerade.

I. m= 2v. Es sind also 2“+† 1 Permutationen, und die Anzahl der Inver- sionen läuft von 0 bis 2v. Es folgt P(1²⁰, 2)= v Tl und Pn(1²⁰, 2)= v.

Dafür kann man schreiben

P= 2(2.)* 200)

II. m= 2»+ 1. Hier haben wir 2“+ 2 Permutationen, wobei die Anzahl der Inversionen von 0 bis 2+ 1 läuft.

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