4

Bei wiederholter Anwendung dieser Rekursionsformel findet man, da J(1)= 0 ist,

1[a = 4(3) a1" Bedeutet Is(a) die Summe aller Inversionen, die in den Permutationen P,(a) mit

gerader Inversionszahl vorkommen, und I.(a) die Anzahl aller Inversionen der P,(a), so lässt sich mit Hilfe des obigen Bildungsgesetzes leicht die Beziehung ableiten

1.(a)= 1,()= 5 1a) für a>3. Für die drei ersten Systeme P(1), P(2), P(3) ergeben sich die Werte 0 0 4 LU)=9 KA)| U9)=;, wobei überall der obere Wert für I;, der untere für I, zu lesen ist.

Im folgenden soll nun der Fall untersucht werden, dass unter den gegebenen Elementen auch gleiche Elemente einer oder mehrerer Arten vorhanden sind. Kommen unter den gegebenen z Elementen k gleiche der ersten Art, I gleiche der zweiten, m gleiche der dritten Art,... endlich.t. gleiche Elemente a vor, wobei z=k+1+m-+...+t und die Anzahl der von einander verschiedenen Elemente gleich a ist, so bezeichnen wir die Gesamtzahl aller aus diesen z Elementen gebildeten Permutationen mit Wiederholung mit P(1%,2,3”,...a‘), die Zahl der in diesem System enthaltenen Permutationen mit gerader Inversionszahl mit P,(1",2),3”,.... a), diejenige der ungeraden Permutationen mit Pu(1",21,3”,...a‘). Entsprechend nennen wir die Summe aller Inversionen dieses Systems I(1K,2,3”,...a‘), die Inversionssumme der geraden Permutationen P; ist I,(1*, 21, 3”,...a'), die der ungeraden Permutationen Pı. heisst I,(1*, 21, 3”,...at).

Abschnitt 1.

Systeme(1",2)). (k) Wir gehen aus von der einzigen Permutation des Systems P(1*), nämlich 111...1 mit O0 Inversionen. Ein dazukommendes neues Element 2 kann auf k+1 verschiedene Arten in diese Permutation eintreten, wodurch wir alle k+1 Permutationen des neuen Systems P(1*,2!) erhalten. Dabei ergeben sich folgende Inversionszahlen:

1. Steht 2 am Ende, so tritt keine Änderung ein, d. h.:+0 Inversionen

2. Tritt 2 vor das letzte Element, also vor ein niedrigeres+1„

3.0, 2,„ diebeidenletztenEl., ,„, 2 niedrigere+2„

3.„ 2„„ 3”„ 794.93”„ 3„+3”„ (k-+1).„ 2 an den Anfang der Perm., also vor k niedrigere+k r

Mit Hilfe dieser Bildungsweise lässt sich für I=1 die Zahl der geraden Permutationen und der in ihnen enthaltenen Inversionen leicht bestimmen.

*) Vgl. Netto:|. c. p. 94.