Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
En mathématiques, la notion de permutation exprime
l'idée que des objets discernables peuvent être arrangés dans différents ordres. Une permutation de n objets distincts
rangés dans un certain ordre, correspond à un changement de l'ordre de succession de ces n objets. Par exemple, pour
faire deux pas en avant, un homme peut avancer le pied gauche puis le pied droit, ou avancer le pied droit puis le pied gauche;
ce qui donne deux permutations différentes des pieds. Un autre exemple plus complexe est celui des sonneurs de cloches. 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 forme une liste de 6 nombres, sans
répétition.
Il y a un certain nombre de façons d'introduire formellement la notion de permutation.
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. C'est-à-dire, une permutation est simplement un n-uplet formé de tous les éléments distincts d'un ensemble donné. Notons la différence essentielle entre une permutation et un ensemble fini : les éléments d'une permutation sont rangés dans un certain ordre.
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.
Définitions :
Une permutation d'un ensemble X est une bijection de l'ensemble X sur lui-même, y compris le cas où X est
infini. Une permutation de n éléments est une bijection d'un ensemble fini de cardinal n (
) sur lui-même. Une permutation de n élément est
aussi un n-uplet de n éléments distincts.
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.
Remarque :
La notion de permutation est essentielle en combinatoire.
| Sommaire |
(n! se lit factorielle de n)..
Lorsque n=0, le résultat reste encore valable, puisque par convention, il existe une seule application de ∅ dans ∅ qui
de plus est bijective.D'où
Théorème :
Si X est un ensemble fini de cardinal n (n∈ℕ⁎), alors l'ensemble Ϭ(X) des permutations de X est fini et card Ϭ(X)=n!.
En algèbre et dans d'autres domaines mathématiques, une permutation (d'un ensemble quelconque) est une application bijective d'un ensemble sur lui-même. Par exemple une permutation de 10 livres sur une étagère se représente par une bijection de l'ensemble {1, ..., 10 } sur lui-même. Soit X un ensemble quelconque. L'ensemble des permutations de X se note habituellement Ϭ(X). Dans le cas particulier où X={1, 2, ..., n} avec n∈ℕ⁎, cet ensemble se note Ϭn ou Sn.
Il y a deux notations principales pour de telles permutations. Dans la notation de relation, nous plaçons les éléments qui vont être permutés dans l'ordre naturel sur une première ligne, et les images de ces éléments par la permutation en dessous sur une seconde ligne. Par exemple
est l'application σ définie par
ou schématiquement
.Ainsi pour former le 5-uplet, image du 5-uplet naturel, nous plaçons en première position, le deuxième élément de l'ensemble, en deuxième position le cinquième élément de l'ensemble, et ainsi de suite.
Par ailleurs, si nous considérons un ensemble fini E (formé d'éléments qui ne sont pas nécessairement des entiers) de
cardinal n (n entier naturel non nul), nous pouvons construire une application bijective f:
E→{1, 2, ..., n}, et associer à une permutation σ de {1, 2, ..., n}, la permutation de
E 
. Nous obtenons
ainsi une correspondance biunivoque (bijection) entre l'ensemble des permutations de {1, 2, ..., n} et celui des
permutations de E. Nous pouvons alors interpréter la permutation de {1, 2, ..., 5} 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(5), et ainsi de suite.
Alternativement, nous pouvons écrire les permutations en utilisant une notation indiquant la façon dont les éléments changent lorsque la permutation est successivement appliquée. Par exemple, reprenons la permutation ci-dessus, et plaçons le premier élément 1 en première position, plaçons ensuite l'image de cet élément par la permutation en deuxième position, et enfin l'image par la permutation de ce dernier résultat en troisième position. Si nous devions appliquer la permutation encore une fois, nous obtiendrions l'élément de la première position. Nous obtenons un cycle, et nous pouvons écrire ce cycle sous la forme (1 2 5), ou alternativement (2 5 1) ou encore (5 1 2), mais pas par exemple (1 5 2). Ensuite nous prenons n'importe quel autre élément non considéré jusqu'à maintenant, et nous complétons jusqu'à ce que chaque élément apparaisse dans un nouveau cycle. De cette façon, nous pouvons décomposer la permutation en un ensemble de cycles. Par exemple, la permutation précédente peut s'écrire sous la forme d'une juxtaposition de cycles (1 2 5)(3 4). L'ordre des cycles n'importe pas mais nous l'avons dit avant, 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 (4 3)(2 5 1). 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 (1 3)(2)(4 5) s'écrit simplement (1 3)(4 5), puisqu'un cycle d'un seul élément n'a aucun effet.
Une permutation formée d'un seul cycle s'appelle un cycle. Le nombre d'éléments d'un cycle s'appelle la longueur du cycle. Par exemple, la longueur de (1 2 5) est égale à trois. Un cycle de longueur deux est plus particulièrement appelé une transposition, puisque par application d'un cycle de longueur deux les éléments sont simplement transposés.
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.
Notons I la permutation identique. Une permutation σ étant donnée, nous pouvons considérer la permutation notée σ-1 qui défait l'action de σ une fois appliquée. En tant qu'application, cette application σ-1, est l'application réciproque de σ, puisqu'appliquer σ puis σ-1 revient à appliquer la permutation identique et qu'une permutation est bijective. La permutation σ-1 s'appelle la permutation réciproque ou permutation inverse.
Nous pouvons définir le produit de deux permutations. Si nous considérons des permutations, σ et , appliquer puis σ revient à appliquer une permutation appelée le produit de σ et . En tant qu'application le produit de σ et est la composée de σ et . Pour avoir davantage d'information, voyez le groupe symétrique.
Une permutation paire est une permutation qui peut être exprimée comme produit d'un nombre pair de transpositions, et la permutation identique est une permutation paire car elle peut être considérée comme le produit de 0 transposition. Une permutation impaire est une permutation qui peut être exprimée comme produit d'un nombre impair de transpositions. Il est possible de démontrer que toute permutation est paire ou impaire mais ne peut pas être tous deux à la fois.
