Permutation - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets...) est une des notions fondamentales en combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les...), 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é (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses...) magique, le carré latin (Un carré latin est un tableau carré de n lignes et n colonnes remplies de n éléments distincts...), le sudoku, ou le Rubik's cube (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées....). Les permutations servent (Servent est la contraction du mot serveur et client.) également à fonder la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer,...) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) X est une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y...) de X sur lui-même.

Notamment, une permutation de n éléments (n\in\mathbb N^*) est une bijection d'un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement s'il existe un entier n et une...) 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 (La longueur d’un objet est la distance entre ses deux extrémités les plus...) 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 (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de...), 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 \{1, 2,\cdots,6\} 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 (n\in\mathbb{N}), alors l'ensemble \mathfrak{S}(X) des permutations de X est fini et card \mathfrak{S}(X)=n!.

Lorsque n = 0, le résultat reste encore valable puisqu'il existe une seule application de \varnothing dans \varnothing 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 (La notion de nombre en linguistique est traitée à l’article « Nombre...) d'arrangements se note A_n^p 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 (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...), sur une deuxième ligne. Par exemple

\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 5 & 4 & 3 & 1\end{pmatrix}

est l'application σ définie par

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

ou schématiquement

\begin{matrix}1\longmapsto 2\\2\longmapsto 5\\3\longmapsto 4\\4\longmapsto 3\\5\longmapsto 1\end{matrix}.

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 (En mathématiques, pour une application f d’un ensemble E dans lui-même, un élément x de E...) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) la position des éléments. En tant qu'application, cette permutation est l'application identique (En mathématiques, une application identique ou fonction identique f est une application qui n'a...), 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 a1, ..., ap envoie l'élément a1 sur a2, puis a2 sur a3 etc, et enfin ap sur a1. Tous les autres éléments restent inchangés. Un tel cycle se note habituellement sous la forme (a1, ..., ap). Là encore (a1, ..., ap)=(a2, ..., ap, a1).
Page générée en 0.182 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique