17

Abschnitt II. Systeme P(1,2,3,...a—1,a').

Da unter den sämtlichen n+a—1 Elementen n gleiche vorkommen, ist Zt P(,2,3,...a 1,)- Fa nta1)...a+l)

Die n gleichen Elemente a können höchstens vor a— 1 niedrigere Elemente treten, das Element a— 1 vor a— 2 niedrigere, das Element a— 2 höchstens vor a—3 niedrigere, usw. Für die grösstmögliche Anzahl von Inversionen in einer Permutation ergiebt sich daher

ulL, 2,3%... Ma-+(53): Folglich ist auch; i K1,2,3,...a—1,2)=-P(1,2,3,...a— 1,2") a—1

5-ata—D...n+ 5-n+ta=1)...a+N).

Rekursionsformeln für P, und]..

Wir haben oben gefunden, dass wir die Multiplizitäten zweier Elemente ver- tauschen dürfen; es ist also P(1,2,3,...a—1,a)=P(1,2,3,,...(a— 1),"a). Diese Beziehung benutzen wir, um die Permutationen des Systems P(1,2,3,...a") aus denjenigen des Systems P(1, 2, 3,...(a— 1)") abzuleiten, indem wir das neue Element a auf alle möglichen Arten in die sämtlichen Permutationen dieses letzteren Systems einfügen. Steht das Element a überall 1. am Ende der früheren Permutationen, so liefern die neuen Permutationen I(1,2,...(a— 1)") Inversionen. vor dem letzten Element der früh. Permut., so lief. die neuen Permutationen I(1,2,...(a—1)")+1-P(1,2,...(a— 1)") Inversionen, . vor den beiden letzten Elementen der früh. Permut., so lief. die neuen Permut. I, 23,...(a— 1)+ 2-P(1,2,...(a—1)") Inversionen, 4.„„ drei letzten Elementen der früh. Permut., so lief. die neuen Permut. I(1,2,...(@a—1)°)+ 3-P(1,2,...(a— 1)") Inversionen,

ID

&

(n+a—2).„„ n-+a-s3letzten Elementen der früh. Permut., so lief. dieneuen Permut. I1,2,...(a—1))+(n+a— 3)- P(1,2,...(a— 1)") Inversionen, (n+a-—1).„„.n-+a-2letzten Elementen der früh. Permut., so lief. dieneuen Permut. I(,2,...(a—1)")+(n+a-—2).P(1,2,...(a— 1)") Inversionen. Demnach findet man zunächst P(1,2,3,...2—1,a)=(n+a-— 1)» P(1,2,3,...(a— 2),(a—1)"),

11,23,3....0)-(a fa—1).1,2,3...(a- 1)+(RF2 TV). PA,2,3...@- 19),