LES ECHANGES

Il est facile de voir 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.

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 l'on 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'on déplace un élément en lui faisant franchir i , 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é:{out,

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

. . . Kabc . . . klS . . .,

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

...ïiSabc ...kl...;

puis, si l'on fait franchir à R les (/? -f- 1 ) éléments qui suivent, on obtient

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

Huitième récréation.

le nombre des inversions est donc moditié d'un nombre de même parité que (2/7 + i) et, par suite, d'un nombre impair. * ■ c. Q. F. D.

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„ des permutations de n lettres par le nombre C„,g 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 (h -4- i) fois le tableau des permut:itions de n lettres; nous avons ainsi {n ~ 1 } D„ dérangements; plaçons maintenant le (n -h 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

n ' n -f- I ] nouveaux dérangements, ou en tout ; on a donc

D„+i = (;j -M) D« + P„ îî-ll±L> .

Posons Drt = P« Q.«, il vient la formule

Q.rt-i-i=Q.rtH

Par suite, pour « = 1,2, 3, ..., on a successivement

Q2 = Qi + - , Q3 = Q2 + ^ > ■■■, Qji == Qn-l +

et en ajoutant toutes ces égalités ^

^ I -f- 2 -4- . . . -4- (■»? — t) w (« — l) (In = ■■ — .

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 «objets pris deux à deux, ou Cw, 2 = - h(k— i);

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

i Pj X 66666.