Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Permutation

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 discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l'ordre de...) est une des notions fondamentales en combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.), 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 (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus remarquables de l'espace. C'est un des cinq solides...). Les permutations servent (Servent est la contraction du mot serveur et client.) é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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut...) X est une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition X tel que...) de l'ensemble 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 si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) 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 éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est...) 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 composition interne · notée multiplicativement, est un élément y tel que x·y = y·x = 1, si 1 désigne...), 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, puisque par convention, 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 finin. Ce nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 terme désigne des échanges de courrier personnels plutôt qu'administratifs.), 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 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 décompositon sous la forme d'une composition de permutations circulaires (voir ci-dessous).

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 l'univers.) 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 aucun effet lorsqu'elle est appliquée à un élément : elle renvoie toujours la...), 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).

Propriétés algébriques

Composition de permutations

Les permutations de E sont définies comme des applications de E dans E, il est donc possible de définir leur produit de composition, qui se note \circ (mais ce signe est le plus souvent omis). Précisément, pour deux permutations σ et σ', appliquer σ' puis σ revient à appliquer une permutation \sigma''=\sigma\circ\sigma' appelée le produit de σ et σ'.

La notation des permutations est bien adaptée au calcul du produit de composition. Ainsi en prenant par exemple

\sigma=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 5 & 4 & 3 & 1\end{pmatrix}\qquad  \sigma'=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\3&5&2&4&1\end{pmatrix}

Le calcul du produit peut être présenté sur trois lignes. La première et la deuxième ligne présentent l'effet de la première permutation σ', puis on fait correspondre aux éléments de la deuxième ligne leur image par σ.

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

Soit, finalement, en rayant la ligne de calcul intermédiaire

\sigma''=\sigma\circ\sigma'= \begin{pmatrix}1 & 2 & 3 & 4 & 5\\4&1&5&3&2\end{pmatrix}

Structure de groupe

Soient n éléments distincts dans un certain ordre. Appliquer une permutation σ revient à en modifier l'ordre. Revenir à l'ordre initial se fait aussi par une permutation ; celle-ci est notée σ-1. Plus généralement, cette application σ-1, est l'application réciproque de la bijection σ, puisqu'appliquer σ puis σ-1 revient à appliquer la permutation identique. La permutation σ-1 s'appelle la permutation réciproque ou permutation inverse de σ.

Soit E un ensemble quelconque. L'ensemble \mathfrak{S}(E) des permutations de E est un groupe pour la loi de composition (En mathématiques, une loi de composition, ou loi tout court, est une relation ternaire qui est aussi une application. C’est donc une application d’un produit cartésien de deux ensembles E et F dans un troisième...) \circ, appelé groupe symétrique de E. Dans le cas particulier où E=\{1,\cdots,n\} avec n \in \mathbb{N}, cet ensemble se note \mathfrak{S}_n.

Si nous considérons un ensemble fini E (formé d'éléments qui ne sont pas nécessairement des entiers) de cardinal n \in \mathbb N^{*}, nous pouvons numéroter les éléments de E et identifier les permutations des éléments de E avec les permutations des n premiers entiers.

Démonstration formelle
Numéroter revient à introduire une application bijective f : E \longrightarrow \{1, 2,\cdots,n\}. Il est alors possible d'associer à une permutation σ de \{1, 2,\cdots,n\}, la permutation de E définie par f^{-1}\circ \sigma\circ f. Nous obtenons ainsi une correspondance biunivoque (bijection) entre l'ensemble des permutations de \{1,2,\cdots,n\} et celui des permutations de E. Nous pouvons alors interpréter la permutation de \{1, 2,\cdots,n\} précédente comme l'application (bijective) qui envoie l'élément f − 1(1) sur l'élément f − 1(2), l'élément f − 1(2) sur l'élément f − 1(3), et ainsi de suite.
Plus précisément l'application qui à σ associe f^{-1}\circ \sigma\circ f est un isomorphisme de groupes.

Décompositions des permutations

Décomposition en produit de transpositions

Toute permutation peut être décomposée en un produit de transpositions. Par exemple, cela signifie qu'on peut, par des échanges deux à deux, modifier à volonté l'ordre des cartes d'un paquet.

Une telle décomposition n'est pas unique : on peut par exemple ajouter un échange de deux cartes, puis l'échange des deux mêmes cartes. En revanche on démontre que la parité du nombre de transpositions nécessaire reste la même. Ceci permet de définir la parité et la signature d'une permutation (voir groupe symétrique).

Une permutation paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) est une permutation qui peut être exprimée comme le produit d'un nombre pair de transpositions. Une définition équivalente est que sa décomposition en cycles disjoints donne un nombre pair (éventuellement nul) de cycles pairs. Une permutation impaire est une permutation qui peut être exprimée comme produit d'un nombre impair de transpositions.

La permutation identique est une permutation paire car elle peut être considérée comme le produit de 0 transposition, selon la convention sur le produit vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.).

Algorithme de décomposition

Voici l'étape générale de l'algorithme de décomposition d'une permutation σ

  • si la permutation est l'identité elle est produit de 0 transposition.
  • sinon il est possible de considérer le premier point (Graphie) non fixe par σ
k=\min\{s, 1\leq s \leq n, \sigma(s)\neq s\}

Alors en appelant τ la transposition qui échange k et σ(k), on forme \sigma_1=\tau \circ \sigma et on reprend l'algorithme avec σ1.

On forme ainsi des permutations σ1, σ2 etc. obtenues en multipliant σ par une succession de transpositions τ1, τ2 etc., jusqu'à atteindre la permutation identique. Alors il vient

(\tau_p \tau_{p-1}\dots\tau_1)\sigma= {\rm Id} \qquad \sigma=\tau_1\tau_2\dots \tau_p

La validité de l'algorithme se justifie en remarquant que la position du premier point non fixe augmente strictement à chaque étape, jusqu'à ce que tous les points soient fixes. L'algorithme se conclut après au plus n-1 opérations, puisque si les n-1 premiers points sont fixes, ils le sont tous. Ainsi il est possible d'affirmer plus précisément que toute permutation peut s'écrire comme produit d'au plus n-1 transpositions.

Décomposition en produit de cycles à supports disjoints

Orbite (En mécanique céleste, une orbite est la trajectoire que dessine dans l'espace un corps autour d'un autre corps sous l'effet de la gravitation.) d'un élément

les deux cycles de la permutation σ
les deux cycles de la permutation σ

L'orbite d'un élément selon une permutation σ est l'ensemble de ses images successives obtenues par applications répétées de σ. Ainsi en introduisant la permutation σ

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

L'élément 1 a pour images successivement 3,5,6 puis de nouveau 1,3,5 etc. L'orbite de 1 est donc l'ensemble {1,3,5,6}. L'orbite de 3 est également l'ensemble {1,3,5,6}, mais l'orbite de 2 est {2,4,7,8}.

Plus généralement, pour une permutation quelconque, les orbites sont disjointes et forment une partition de l'ensemble {1,2,...,n}. En restriction à une orbite donnée de taille p, la permutation se comporte comme une permutation circulaire des p éléments.

Décomposition

Pour décrire la permutation, il suffit de prendre un élément dans chaque orbite et de donner l'ordre de succession de ses images par itération de σ. Ainsi toujours avec le même exemple, la permutation σ peut s'écrire sous la forme d'une succession des deux cycles (1,3,5,6) et (2,4,7,8). L'ordre des cycles n'importe pas mais l'ordre des éléments à l'intérieur d'un cycle doit être respecté jusqu'à l'obtention d'un cycle complet. Ainsi, la même permutation peut être écrite par exemple

\sigma = (1,3,5,6) \circ (2,4,7,8)=(2,4,7,8)\circ (1,3,5,6) =(7,8,2,4)\circ (6,1,3,5)\;

Dans cette notation on omet souvent le symbole de composition \circ pour alléger l'écriture.

La décomposition « canonique » d'une permutation en « produit » de cycles s'obtient en plaçant d'abord le plus petit nombre en première position dans chaque cycle et en ordonnant les cycles selon leur premier élément. Cette notation omet souvent les points fixes, c'est-à-dire les éléments qui sont leur propre image par la permutation; ainsi la permutation (1 3)(2)(4 5) s'écrit simplement (1 3)(4 5), puisqu'un cycle d'un seul élément n'a aucun effet.

Applications

De nombreuses propriétés de la permutation σ peuvent se lire facilement sur la décomposition en cycles disjoints : s'il y a p cycles de longueurs s1, ..., sp (en comptant les points fixes comme cycles de longueur 1)

  • la signature de σ est le produit des signatures : elle vaut (-1)n-p.
  • l'ordre de σ (en tant que membre du groupe symétrique) est le plus petit entier k>0 tel que σk est l'identité. Il est égal au PPCM des longueurs des cycles.
  • la conjuguée d'une permutation π par une permutation σ est la permutation \sigma\circ\pi\circ\sigma^{-1}. On peut aisément calculer cette permutation, en remplaçant chaque élément i dans la décomposition en cycles disjoints de π par σi.
Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.