I. Des permutations d'éléments à un seul indice

t. DirangemerUs. De toutes les permutations d'un certain nombre d'éléments

(1, 2, 3, 4,) (a„ «2, fls, «4) ou {a, b, c, d), il y en a une seule, savoir :

1234, aia^a^UA, aicd, où les éléments sont dans l'ordre naturel. Dans toutes les autres, par exemple, dans

4231, a^a^azai dbca, (1)

les éléments sont dans un ordre différent.

On appelle dérangement ou inversion, dans une permutation, la combinaison d'un élément avec un élément qui le suit dans cette permutation, mais qui le précède dans Tordre naturel ou alphabétique des éléments. Ainsi les permutations (1) contiennent cinq dérangements, savoir : [42, 43, 41, 21, 31], [«4^2, a^az, a^Ut, a^ai, as^i], [rfJ, de, da, la, ca].

Exercices 1. Déduire une permutation quelconque, 52143, de la permutation 1*2345, où les éléments sont rangés dans l'ordre naturel, par un nombre d'échanges d'éléments égal à celui des dérangements de cette permutation, et de, deux manières différentes.

2. On peut déduire une permutation de n éléments, d'une autre quelconque, par (n — 1) échanges d'éléments au plus.

3. Une permutation de n éléments et la permutation inverse contiennent A « (« — 1) inversions. Les P» = 1. 2. 3... w permutations de n éléments en contiennent ~n{n ~Ï)1?H (FoNïEBASSo).

**4. Si ri rj ... r,„ Al Aa ... A„ „ est une permutation de 12 3...*?, contenant a -+- ^ -i- V iïi versions, dont a sont dans ri r» ... r„., /S dans Ai Aj ... A„w, y ne change pas si l'on range ri r% ,.,rm dans l'ordre naturel et est égal à (ri — 1) -+- (ri — Z)-^ ••• -+■ (r„, — m) (Trudi).

9. Permuiatiani paires ou impaires. Cramer a divisé les pennntations en deux classes : les permutations paires, qui contiennent un nombre pair de dérangements, .comme 1234, 4321; les permutations impaires, qui en contiennent un nombre impair, comme 4231, 4123. On peut diviser en deux classes les permutations d'éléments tels que m, 7, Ui, S, en posant

m = ai, 7 = tf«, «fj==^3, S =«4.

La différence entre les nombres de dérangements de deux permutations est paire ou impaire, selon qu'elles sont ou ne sont pas de même classe.

8. Théorème de Cramer et Bbzout Une permutation change de classe si Von échange deux éléments {ou deux indices). 1«' Cas. Échange de deux éléments adjacents aiy aty i < h. Désignons Tensemble des éléments qui précèdent a^ et a^ par M; lensemble de ceux qui suivent, par N- Des permutations

MâJ*éi,N, Mfl,«*N, la première contient un dérangement de plus que la seconde, savoir : auah puisque i < k. Donc elles sont de classes différentes.

2^ Cas. Échange de deux éléments quelconques. Désignons par 1 Tensemble des éléments, en nombre m, compris entre a» et ak. On déduit, de

MOilttAN, (1)

la permutation

MIa,a*N, (2)

par m échanges d'éléments adjacents, en faisant passer successivement a\ au delà des m éléments de I. De (2), on tire

MIajta,N, (3)

par un échange d'éléments adjacents,' savoir : a, et a^. Enfin on passe de cette permutation (3) à

MaJaiN. (4)

en faisant reculer ak en deçà des m éléments de I, au moyen de m échanges d'éléments adjacents. On passe donc de la permutation (1) à la permutation (4), qui n'en diffère que par l'échange des éléments a,, «/t, au moyen de (2w -t- 1) échanges d'éléments adjacents; ce qui équivaut à (2»i -♦- 1) changements de classe, ou à un seul changement de classe. Le théorème est donc démontré. On remarquera que la différence entre les nombres de dérangements des permutations (1) et (4) est impaire (n'*2).

On peut aussi établir directement le théorème de Bézout, dans ce second cas (BALTZER-HoiJEL, Déterminants, I, n" 2, n° 4).

Exemple. Les permutations marquées I et II, dans les tableaux suivants, sont de classes différentes :

1 1234. adcd mluiS

II 4231, abdc mlSui

I 4321, adic mSlUi

II 4123, dadc SmlUi

Exercices. 5. 1® Deux permutations de n éléments, qui ont (n — 2) éléments à la même place, ne dififèrent que par l'échange des deux autres et, par suite, sont de classes différentes. 2*» Si on supprime les deux derniers éléments des X, permutations différentes paires de n éléments, les Xn arrangements restants de (n — 2) lettres seront tous différents. 3° Des X» permutations paires différentes, on déduira Xn permutations impaires différentes, par échange des deux derniers éléments; et inversement. 4° Le nombre X» des permutations des deux classes est donc le même. **6. Si on supprime un élément dans une permutation, la permutation nouvelle est ou n'est pas de même classe que la première suivant que l'indice de l'élément supprimé est ou n'est pas de même parité que son rang dans la permutation primitive (Suabez).

4. Permutations circulaires. Le résultat de réchange des éléments d'une permutation est appelé permutation circulaire de la première lorsque chaque élément est remplacé par le suivant et le dernier par le premier, une ou plusieurs fois. L'opération effectuée porte le même nom, ou bien s'appelle substitution circulaire. Ex. : 43125, 12543 sont des permutations circulaires de 54312.

Pour effectuer une permutation circulaire de n éléments, il suffit de mettre le premier élément après les {n — 1) autres, ou d'effectuer {n — 1) échanges d'éléments adjacents, une ou plusieurs fois. La permutation primitive, et celle qu'on en déduit en faisant une fois cette opération sont donc, ou ne sont pas de même classe, selon que {n — 1) est pair ou impair. Ainsi 54312 et 43125 sont de même classe; car (n -— 1) =4. * D'une permutation donnée de n éléments (725438169), on peut déduire une autre quelconque (293874156), par des permutations circulaires effectuées sur p groupes d'éléments adjacents ou non (726953,48,1). Ces groupes sont appelés cycles, La permutation primitive et la permutation dérivée sont, ou ne sont pas, de même classe, selon que (» — p) est pair ou impair (Baltzer, I, 5). En effet, soient »i, n^, »s, ..., np les nombres d'éléments de chacun des p cycles, de sorte que n ^=^ ni -^ n^ -*- ^3 H- ..• -*- np. On déduira la seconde permutation de la première, au moyen de (ni — 1) -+- (n^ — 1) -h (ws — 1) -*- ••• -*- (^p — - 1)= % — p échanges d'éléments (adjacents ou non) deux à deux.

Exercices. *7. Deux permutations sont ou ne sont pas de même classe suivant que le nombre des cycles au moyen desquels on les déduit d'une autre permutation sont ou ne sont pas de même parité.

*8. La permutation circulaire àe axa% ... On qui commence par flp + i contient p{n — p) inversions. Le nombre total des inversions contenu dans les n permutations circulaires de ûTi a» ... an est | (n — 1) n (« -4- 1) (Fontebasso).