Permutation - Définition

Introduction

En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l'ordre de succession de ces n objets.

La permutation est une des notions fondamentales en combinatoire, c'est-à-dire pour des problèmes de dénombrement et de probabilités discrètes. Elle sert ainsi à définir et à étudier le carré magique, le carré latin, le sudoku, ou le Rubik's cube. Les permutations servent également à fonder la théorie des groupes, celle des déterminants, à définir la notion générale de symétrie, etc.

Définition et exemples

Définition

Une permutation d'un ensemble X est une bijection de X sur lui-même.

Notamment, une permutation de n éléments ( ) est une bijection d'un ensemble fini de cardinal n sur lui-même.

Exemples

Une permutation de l'alphabet de 26 lettres est un mot de 26 lettres contenant chaque lettre une fois et une seule ; et il est clair que cette définition reste valable pour n'importe quel alphabet de n lettres, avec des mots de longueur n.

Il y a beaucoup d'ordres différents (sept cent vingt) dans lesquels six cloches, de différentes notes, peuvent être sonnées les unes après les autres. Si les cloches sont numérotées de 1 à 6, alors chaque ordre possible peut être représenté par une liste de 6 nombres, sans répétition, comme par exemple (3,2,6,5,1,4).

De la même façon, six livres posés sur un rayonnage et numérotés de 1 à 6, peuvent être permutés de différentes manières : rangement par ordre alphabétique, ordre alphabétique inverse, ordre de préférence, ou ordre choisi « au hasard ». Chacun de ces réarrangements peut être vu comme une bijection de l'ensemble des six livres, ou de façon identique, une bijection de l'ensemble sur lui-même. En effet, si l'ordre final des livres est 3,2,6,5,1,4, on peut définir l'application f : « est remplacé par » ainsi

1 est remplacé par 3 soit f(1)=3

2 est remplacé par 2 soit f(2)=2

3 est remplacé par 6 soit f(3)=6

4 est remplacé par 5 soit f(4)=5

5 est remplacé par 1 soit f(5)=1

6 est remplacé par 4 soit f(6)=4

Finalement, les objets effectivement permutés comptent peu : la permutation peut être ramenée à une permutation de nombres : les numéros des livres, ou les numéros de cloches.

Supposons que n personnes s'assoient sur n chaises différentes numérotées de 1 à n disposées sur une même rangée. Nous pouvons considérer un placement de ces n personnes sur les chaises, comme une bijection de l'ensemble des n personnes sur lui-même, indiquant la façon dont les personnes sont placées les unes par rapport aux autres sur les chaises.

Une permutation de n éléments est aussi appelée permutation sans répétition de ces éléments. Signalons qu'autrefois une permutation était appelée substitution.

Dénombrement des permutations

Soit E un ensemble à n éléments. Le problème est de compter les permutations de E, c'est-à-dire les bijections de E dans lui-même. Comme pour les exemples précédents, on peut toujours numéroter les éléments de E de 1 à n. Dénombrer les permutations de E revient à dénombrer tous les réarrangements possibles de la liste, c'est-à-dire tous les n-uplets formés des chiffres de 1 à n dans un certain ordre.

Il est possible de donner une liste de tous ces réarrangements, sous forme d'une représentation arborescente : il y a n choix pour le premier terme de la liste. Puis pour chacun de ces premiers choix, il y a n-1 possibilités pour le deuxième choix, n-2 pour le troisième, ainsi de suite. Finalement il y a n! (factorielle de n) choix possibles pour constituer une liste. Cette méthode permet d'énumérer une et une seule fois chaque permutation.

Théorème

Si X est un ensemble fini de cardinal n ( ), alors l'ensemble des permutations de X est fini et card =n!.

Lorsque n = 0, le résultat reste encore valable puisqu'il existe une seule application de dans qui de plus est bijective.

Il est possible de dénombrer plus généralement les p-arrangements de n éléments, ou encore les applications injectives d'un ensemble de cardinal fini p dans un ensemble de cardinal fini n. Ce nombre d'arrangements se note et le cas des permutations apparaît comme le cas particulier n=p.

Notation des permutations

Soit E un ensemble fini, de n éléments. Quitte à effectuer une numérotation, permuter les éléments de E revient à permuter les entiers de 1 à n. La notation traditionnelle des permutations place les éléments qui vont être permutés dans l'ordre naturel sur une première ligne, et les images en correspondance, sur une deuxième ligne. Par exemple

est l'application σ définie par

σ(1) = 2,σ(2) = 5,σ(3) = 4,σ(4) = 3,σ(5) = 1,

ou schématiquement

.

Toutefois, la notation la plus pratique est la forme canonique. Sous cette forme, la permutation précédente s'écrit :

(1 2 5)(3 4)

ce qui signifie 1 donne 2 (c.-à-d., 2 est l'image de 1) qui donne 5 qui donne 1 ; 3 donne 4 qui donne 3. Cette écriture correspond à une sous la forme d'une de permutations circulaires (voir ci-dessous).

Le support d'une permutation σ est l'ensemble des éléments x tel que σ(x) est différent de x. La permutation σ se restreint donc en l'identité sur le complémentaire de son support, et en une permutation sans point fixe sur son support.

Permutations particulières

L'identité 

Si une permutation laisse le premier élément à la première place, le deuxième élément à la deuxième place, et ainsi de suite, alors elle ne change pas du tout la position des éléments. En tant qu'application, cette permutation est l'application identique, et elle est appelée permutation identique. Elle est le plus souvent notée e.

Transposition

Une permutation qui se contente d'échanger deux éléments i et j en laissant tous les autres inchangés est appelée transposition. On utilise fréquemment une notation allégée pour désigner cette permutation : (i,j). Il convient de noter qu'avec ce choix de notations (i,j)=(j,i).

Permutation circulaire

Plus généralement, il est possible de définir les permutations circulaires ou cycles. Le p-cycle associé aux éléments a₁, ..., a_p envoie l'élément a₁ sur a₂, puis a₂ sur a₃ etc, et enfin a_p sur a₁. Tous les autres éléments restent inchangés. Un tel cycle se note habituellement sous la forme (a₁, ..., a_p). Là encore (a₁, ..., a_p)=(a₂, ..., a_p, a₁).