LES DEUX CLASSES DES PERMUTATIONS

Cela posé, on divise les permutations de n nombres en deux classes; on range dans \a première classe, avec celle qui ne contient aucun dérangement, en écrivant les nombres dans l'ordre naturel, toutes les permutations qui contiennent un nombre

Le jeu du taquin. iqg

pair de dérangements ; on range dans la seconde classe toutes les permutations qui contiennent un nombre impair de dérangements. Pour indiquer qu'une permutation est de la première classe, nous la ferons précéder du signe -h, et pour indiquer qu'une permutation est de la seconde classe, nous la ferons précéder du signe — ■. Ainsi la permutation m- 12 donne

et la permutation — 21 donne

On constate que les classes des permutations de Jeux ou de trois nombres sont également partagées; il en est toujours ainsi. En effet pour former les permutations de quatre éléments 1,2,3,4, on place d'abord le nombre 4 à la fin de chacune des permutations de trois éléments, ce qui ne change pas la classe de la permutation ; en faisant rétrograder le chiffre 4 successivement vers la gauche, on change successivement le signe de la permutation ; ainsi -h 231 donne successivement, pour quatre éléments,

Le tableau suivant renferrne toutes les permutations de quatre éléments, avec le signe de la classe à laquelle elles appartiennent; nous indiquons, dans les deux premières lignes, les deux permutations de deux éléments, et les six permutations de trois éléments, qui permettent d'établir la généalogie des permutations des quatre éléments. - ; ,. j, ;, r. '] £• ;- ; ^ . v J;^^^^-;

Huitième récréation.

Généalogie des permutations.

On voit que le nombre des signes H- est égal au nombre des signes — ; par suite, le nombre des permutations de chaque classe est le même. Il est facile de généraliser et de voir qu'il en est toujours ainsi. On a donc la proposition suivante, dans laquelle on considère zéro comme un nombre pair :

Théorème I. — Les permutations de n objets se divisent en deux classes également nombreuses, suivant que le nombre des inversions est pair ou impair.

On détermine facilement la classe d'une permutation en calculant le nombre de ses inversions, ainsi qu'il a été dit plus haut, et en supprimant continuellement les multiples de 2.