LES ÉCHANGES

Il est facile devoir que si l'on échange dans une permutation les places de deux nombres consécutifs, on produit un changement de classe, puisque l'on a ainsi augmenté ou diminué le

Le jeu du taquin. 2ox

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ê;ne parité que p ; en d'autres termes, si Ton déplace un élément en lui faisant franchir 2, 4, 6, 8, ... autres, la classe de la permutation n'est pas modifiée, et si l'ondéplace un élément en lui faisant franchir i, 3,5, y,. . . 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é^out.

Théorème IL — 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 l'échange de deux éléments quelconques produit un changement de classe. Supposons que l'on échange dans la permutation

... Rabc... kl S...,

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

...RSabc ...kl...;

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

,..Sabc... klR...;

202 Huitième récréation.

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

On peut encore démontrer le théorème suivant : Le nombre total de<i iywersions pour toutes les permutatioyis de n lettres est la moitié du produit du nombre P„ des permutations de n lettres par le nombre C„,2 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 (n -h i) fois le tableau des permutations de n lettres ; nous avons ainsi (n -~ i ) D„ dérangements; plaçons maintenant le (?2+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

nouveaux dérangements, ou en tout ; on a aonc

^ n (n -^- i) D«+i = {n -^ i) Dn -\-Pn

Posons D/i == P/i Q.«, il vient la formule

Par suite, pour n --^ 1,2, 3, ..., on a successivement

Q2 = Qi -i- - > Q3 = Q2 4- ^ ' .-•, Qyt = Q«-i H ~ ;

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 l'ordre renversé est égal au nombre

des combinaisons de n objets pris deux à deux, ou €«, 2 ^ - n[n—i)'.

Le jeu du taquin. 2o3

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 i, 2, 3, 4, 5 est