LES CYCLES

On peut encore déterminer la classe d'une permutation par la méthode plus expéditive, dite des cycles^ due à Cauchy. Considérons une permutation quelconque,

8, 6, 12, 1,5, 14, 2, II, i3, i5, 4, 9, 3, 10, 7;

plaçons au-dessus de chacun de ses termes les nombres de la suite naturelle, ainsi qu'il suit :

Nombres : i, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, i3, 14, i5; Pions: 8,6,12,1,5,14,2,11,13,15,4, 9, 3, 10,7.

Au-dessous du nombre i se trouve le numéro 8; au-dessous de 8 le numéro 1 1 ; au-dessous de 1 1 le numéro 4, au-dessous de 4 nous retrouvons le numéro i . On forme ainsi

Premier cycle : i, 8, 11,4;

en partant du nombre 2, on forme

Second cycle : 2, 6, 14, 10, i5, 7;

204 Huitième récréation.

en partant du nombre 3, qui ne figure pas dans les cycles précédents, on forme

Troisième cycle : 3, 12, 9, i3',

enfin il reste le cycle formé par un seul nombre

Quatrième cycle : 5.

Il est facile de voir que l'échange de deux pions quelconques augmente ou diminue d'une unité le nombre des cycles de la permutation, suivant que les pions échangés appartiennent au même cycle ou à des cycles différents. Par suite, la variacion du nombre des cycles est de même parité que le nombre des échanges entre les termes de la permutation. Donc :

Théorème III. — Deux permutations appartiennent à une même classe ou à deux classes distinctes, suiuant que les nombres de leurs cycles sont ou ne sont pas de même parité.

Pour déterminer la classe, on remarquera que la permutation suivant l'ordre naturel contient un nombre de cycles égal au nombre des éléments de la permutation ( ' ) .

(') Le numéro du 2b septembre 1880 du journal la Nature contient un article intitulé : Le dernier mot du taquin, par M. Piarron de Mondésir. On y retrouve, sous une forme peu différente, le procédé des cycles. Si l'on range les cycles en deux ordres, suivant qu'ils contiennent un nombre pair ou impair de termes, on a le théorème suivant : Deux permutations appartiennent à la première classe ou à la seconde, suivant que le nombre des cycles d'ordre pair est pair ou impair. D'un autre côté, ce résultat m'a été indiqué par M. Delannoy, ancien élève de l'École Polytechnique.

Le jeu du taquin. 2o5

LTÎS ECARTS.

Considérons une permutation quelconque des n premiers nombres

appelons écart d'un terme la différence entre sa valeur numérique et le rang qu'il occupe; désignons-le par e, nous aurons

ep =ap—p.

Cela posé, on a le théorème suivant :

Théorème IV. — Si^ dans une permutation des n premiers nombres, on supprime un terme quelconque^ la variation du nombre des inversions est de même parité que l'écart du terme.

Soient ap le terme enlevé, Cp et Sp le nombre des inversions commandées et subies par lui; la variation du nombre des inversions est évidemment Cp + Sp. Mais le nombre des termes qui précèdent ap est {p — i), parmi lesquels Sp sont plus grands que lui, et (^ — I — Sp ) sont plus petits que lui. D'autre part, le nombre des termes plus petits qui le suivent est c^; en ajoutant les deux dernières expressions, on trouve le nombre total des nombres plus petits que a^, c'est-à-dire {ap — i); on a donc

ap~i = p — i—Sp-\-Cp, ou bien

dp P "^^^ Cp —— Sp y

2o6 Huitième récréation.

par suite, en ajoutant le nombre pair 2Sp, on a

Cp ^ Cp -h Sp, (Mod. 2). c. Q. F. D.