LES ECHANGES

Il est facile de voir que si l'on échange d?ms une permutation les places de deux nombres consécutifs, on produit un changement de classe, puisque Ton a ainsi augmenté qu diminué le

Le jeu du taquin. 201

nombre des inversions d'une unité. Plus généralement, si l'on déplace un élément de manière à lui faire franchir un nombre quelconque p d'autres éléments, le nombre des inversions est modifié d'une quantité qui est de même parité que p ; en d'autres termes, si Ton déplace un élément en lui faisant franchir 2, 4, 6, 8, f . , autres, la classe de la permutation n'est pas modifiée, et si Ton déplace un élément en lui faisant franchir 1 , 3, 5 ,7, . . . autres éléments consécutifs, la classe de la permutation est changée. Cela posé, on a la proposition suivante, connue sous le nom de théorème de Béqout.

Théorème II. — L'échange de deux éléments quelconques d'une permutation change la classe de la permutation. Plus généralement, un nombre pair d'échanges d' éléments quelconques d'une permutation n'en modifie pas la classe ; un nombre impair d'échanges produit sur la permutation primitive un changement de classe.

En effet, il suffit évidemment de démontrer que réchange de deux éléments quelconques produit un changement de classe. Supposons que l'on échange dans la permutation

. . . Rabc. . . klS. ..,

les éléments R et S séparés par/? éléments; si Ton fait franchir à S les p éléments qui précèdent, on obtient

. . . RS abc . . . kl ... ;

puis, si l'on fait franchir à R les (p-\- j) éléments qui suivent, on obtient

> ... S abc ... kl R . . , \

202 Huitième récréation.

le nombre des inversions est donc modifié d'un nombre de même parité que (2p -m) et, par suite, d'un nombre impair.

On peut encore démontrer le théorème suivant : Le nombre total des inversions pour toutes les permutations de n lettres est la moitié du produit du nombre P n des permutations de n lettres par le nombre C H , t des combinaisons des n lettres prises deux à deux. On peut arriver à ce résultat de deux manières différentes : par la méthode analytique ou par la méthode synthétique.

Méthode analytique. — Désignons par D„ le nombre total des dérangements ou des inversions pour toutes les permutations de n lettres. Écrivons d'abord (« -+- 1) fois le tableau des permutations de n lettres; nous avons ainsi (w.-t-ijty, dérangements; plaçons maintenant le (« -+- i)**"* élément à la dernière place, à l'avant- dernière, ..., à la seconde, à la première place dans chacune des permutations précédentes, nous produisons successivement

o, i, 2, ..., («—i), n nouveaux dérangements, ou en tout - ; on a donc

Dn-Hi = (W + i) T> n -+■ Pn

Posons D» = P» Qn, il vient la formule

Q*+i=Q./»+£- Par suite, pour n = i, 2, 3, . .., on a successivement

Qi = Qi 4- - > Qa = Qj -+- - > —, Qjt = Q»-i -+- w ~~ ' ; 2 2 2

et en ajoutant toutes ces égalités

Méthode synthétique. — Le nombre total des inversions d'une permutation et de la permutation écrite dans Tordre renversé est égal au nombre

çles combinaisons de n objets pris deux à deux, ou C», s = - n(n — 1 ) ;

Le jeu du taquin. 20 3

par conséquent, en réunissant les deux permutations, on trouve au total

Remarque. — On trouverait de même la somme de tous les nombres formés par les permutations des deux, trois, quatre,..., neuf premiers chiffres. Ainsi la somme des nombres formés par les permutations des cinq chiffres 1, 2, 3, 4, 5 est

ip s x 66666 .

*$Hfr