8

B. b) I.(1%, 2): k= 1 2 3 4 5 1| 1 1 4 4 9 2| 1 4 12 24 45 3| 4 12 48 96 216 4, 4..24 96 256 600 5| 9 45 216 600 1590 B. c) I(1%, 2)= 1,(1%, 2)+ L(1F, 2): k= 1 2 e 4 5 l=1| 1 3 6 10. 15 2 3 12 30 60 105 3| 6 30 90 210 420 4| 10 60 210 560 1260 5| 15 82.105 420 1260 3150

Rekursionsformeln für P;(1*,2!) und I,(1*, 2}).

Von den Permutationen P(1%,2') liefern diejenigen, welche mit dem Element 1 anfangen, dieselben Inversionszahlen wie die P(1*-!,2!) und diejenigen, welche mit 2 be- ginnen, gegenüber den P(1“,2!—!1) eine Vermehrung der Inversionszahl einer jeden Per- mutation um je K Inversionen, weil das höhere Element 2 überall vor k niedrigeren Elementen 1 steht. Dabei ändert sich die Klasse der Komplexionen nicht, wenn k gerade ist, während bei ungeradem k aus den geraden Permutationen ungerade entstehen und umgekehrt. Wir erhalten daher für P,(1",2') und I,(1*,2') Reduktionsformeln, durch die wir diese Grössen bei Permutationen mit z Elementen zurückführen auf die Werte von Systemen mit nur z— 1 Elementen.

I. k gerade: Pie 2 Pte FDP ED Lt, ELTA FI LAS ASN ER» P das, 2,

II. k ungerade: Ps(1*, 2)— P,(1*1,2))+ Pı(1%, 2), 101 2!)— It18 Y 2)+ 1,1% 2 I+ k-Pu(1®, Dir

Beweis für die Richtigkeit der allgemeinen Formeln (durch strenge Induktion).

Wir nehmen an, dass die auf S. 6 zusammengestellten Formeln für beliebige k und 1,2,3,...1 richtig sind, und zeigen mit Hilfe der obigen Rekursionsformeln, dass sie auch für!/=1-+1 gelten. Dies ist der Fall, wenn die aus den allgemeinen Formeln für !’=1-+1 sich ergebenden Werte identisch gleich sind den aus den Reduktionsformeln folgenden Resultaten.

Wir setzen im folgenden z=k+1, 2=k+1+1=kH+!, und entsprechend

sind S und& die grössten Ganzen von, und 5