Chaque rangée est une permutation des trois billes de couleur.

En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation d'objets distincts rangés dans un certain ordre correspond à un changement de l'ordre de succession de ces 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 (où n est un entier naturel) 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 (720) 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, 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 {1, 2, … ,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 X un ensemble fini à n éléments. Le problème est de compter les permutations de X, c'est-à-dire les bijections de X dans lui-même. Comme pour les exemples précédents, on peut toujours numéroter les éléments de X de 1 à n. Dénombrer les permutations de X revient à dénombrer tous les réarrangements possibles de la liste, c'est-à-dire tous les n-uplets formés d'entiers 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.

Si X est un ensemble fini de cardinal n, alors l'ensemble des permutations de X est fini, de cardinal n!.

Lorsque n=0, le résultat reste encore valable puisqu'il existe une seule application de l'ensemble vide dans lui-même et qu'elle 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 An et le cas des permutations apparaît comme le cas particulier n=p.

Notation des permutations

Soit X un ensemble fini, de n éléments. Quitte à effectuer une numérotation, permuter les éléments de X 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

,

ou schématiquement

.

Toutefois, la notation la plus pratique est la forme « canonique » (voir ci-dessous). 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 à la décomposition sous la forme d'une composition de permutations circulaires de supports disjoints.

Le support d'une permutation σ est l'ensemble des éléments x tels 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

Identité :

La permutation de X qui envoie chaque élément sur lui-même est l'application identité de X.

Transposition :

Une permutation qui échange deux éléments distincts 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 remarquer qu'avec ce choix de notations, (i j)=(j i). Une transposition élémentaire échange deux éléments voisins, (i i+1).

Permutation circulaire :

Plus généralement, on définit les permutations circulaires ou cycles. Le p-cycle associé aux éléments distincts a1, … , ap (pris dans cet ordre) 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 X sont définies comme des applications de X dans X, il est donc possible de définir leur produit de composition, qui se note ∘ (mais ce signe est le plus souvent omis). Précisément, pour deux permutations σ et σ', appliquer σ' puis σ revient à appliquer une permutation σ"=σ∘σ' 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

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 .

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

Il est à rappeler que la loi de composition n'est pas commutative (dès que l'ensemble X a au moins 3 éléments) mais deux permutations de supports disjoints commutent.

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 σ. Plus généralement, cette application σ, est la bijection réciproque de σ, puisqu'appliquer σ puis σ, ou σ puis σ, revient à appliquer la permutation identique. La permutation σ s'appelle la permutation réciproque ou permutation inverse de σ.

Soit X un ensemble quelconque. L'ensemble S(X) des permutations de X est un groupe pour la loi de composition ∘, appelé groupe symétrique de X. Dans le cas particulier où X={1, …, n} avec n entier naturel, cet ensemble se note Sn.

Si nous considérons un ensemble fini X de cardinal n (formé d'éléments qui ne sont pas nécessairement des entiers), nous pouvons numéroter les éléments de X et identifier les permutations des éléments de X avec les permutations des n premiers entiers.

Décompositions des permutations

Décomposition en produit de transpositions

Toute permutation de support fini 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.

Comme deux transpositions (i j) et (k l) concernant quatre éléments différents commutent, une telle décomposition n'est pas unique. De plus, une transposition est une involution, on peut donc également 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.

Une permutation paire 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 de longueurs paires. 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.

La permutation circulaire (1 2 … p) est le produit des transpositions (1 p)(1 p-1)…(1 3)(1 2). La décomposition en produits de cycles disjoints (voir ci-dessous) implique donc la décomposition en produit de transpositions.

La transposition (i j) est la composition des transpositions élémentaires (i i+1)(i+1 i+2)…(j-1 j)(j-2 j-1)…(i i+1) ce qui montre que toute permutation est décomposable en un produit de transpositions élémentaires. C'est un outil utile pour visualiser une permutation.

Algorithme de décomposition

Voici l'étape générale d'un algorithme de décomposition d'une permutation σ de support fini {1,…,n}.

si la permutation est l'identité elle est produit de 0 transposition.

sinon il est possible de considérer le premier point non fixe par σ

Alors en appelant τ la transposition qui échange k et σ(k), on forme σ₁=τ∘σ et on reprend l'algorithme avec σ₁.

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

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. En outre, le nombre minimum de transpositions nécessaires pour écrire une permutation donnée est exactement celui obtenu avec cet algorithme.

L'algorithme ci-dessus correspond à l'algorithme de décomposition en produit de cycles disjoints suivi de l'écriture de chaque cycle comme un produit de transpositions. Le nombre minimum de transpositions nécessaires est donc égal à n–p, où p est le nombre de cycles disjoints (en comptant les points fixes comme cycles de longueur 1).

Décomposition en produit de cycles à supports disjoints

Orbite d'un élément

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 σ

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.

Le diagramme de la permutation σ comme produit de transpositions élémentaires se lit de haut en bas.

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

Dans cette notation on omet souvent le symbole de composition ∘ 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.

Si, au contraire, on place le plus petit nombre en dernière position dans chaque cycle, sans omettre les points fixes, on obtient une suite de nombres, liée aux nombres de Stirling, qui permet l'analyse combinatoire du nombre de cycles et de la taille des cycles d'une permutation : c'est la correspondance fondamentale de Foata.

Applications

De nombreuses propriétés de la permutation σ peuvent se lire facilement sur la décomposition en cycles disjoints :

la signature de σ est le produit des signatures : elle vaut (-1)=(-1), où p est le nombre de cycles disjoints (en comptant les points fixes comme cycles de longueur 1) et q est le nombre de cycles de longueur paire.

l'ordre de σ (en tant qu'élément du groupe symétrique) est le plus petit entier k>0 tel que σ est l'identité. Il est égal au PPCM des longueurs des cycles.

le théorème des restes chinois est clairement illustré par les puissances de σ. Il est plus facile à énoncer quand les longueurs des cycles sont premières entre elles : dans ce cas, l'ordre de σ est le produit des longueurs des cycles et le groupe engendré par les puissances de σ est isomorphe à ℤ/nℤ qui lui-même est décomposable en produit des ℤ/niℤ, chaque cycle avançant à son rythme pour ne retomber en phase qu'au produit.

la conjuguée d'une permutation π par une permutation σ est la permutation σ∘π∘σ. On peut aisément calculer cette permutation, en remplaçant chaque élément i dans la décomposition en cycles disjoints de π par σ(i).

Articles connexes

Permutation avec répétition

Permutation aléatoire

Matrice de permutation

Nombre de Stirling

Théorème de réarrangement de Riemann

Code de Lehmer

Correspondance fondamentale de Foata

Matrice de Costas

Portail des mathématiques

P(3,3)=6

排列（英语：Permutation）是将相异对象或符号根据确定的顺序重排。每个顺序都称作一个排列。例如，从一到六的数字有720种排列，对应于由这些数字组成的所有不重复亦不阙漏的串行，例如"4, 5, 6, 1, 2, 3" 与1, 3, 5, 2, 4, 6。

置换的广义概念在不同语境下有不同的形式定义：

在集合论中，一个集合的置换是从该集合映至自身的双射；在有限集的情况，便与上述定义一致。

在组合数学中，置换一词的传统意义是一个有序串行，其中元素不重复，但可能有阙漏。例如1,2,4,3可以称为1,2,3,4,5,6的一个置换，但是其中不含5,6。此时通常会标明为「从n个对象取r个对象的置换」。

置换的数算

此节使用置换的传统定义。从个相异元素中取出个元素，个元素的排列数量为： 其中P意为Permutation（排列），!表示阶乘运算。 以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为： 因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是： 不过，中国大陆的教科书则是把从n取k的情况记作或（A代表Arrangement，即排列）。

重复置换

上面的例子是创建在取出元素不重复出现状况。 从个元素中取出个元素，个元素可以重复出现，这排列数量为： 以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为： 这时的一次性添入中奖的概率就应该是：

抽象代数

在集合论与抽象代数等领域中，「置换」一词被保留为集合（通常是有限集）到自身的双射的一个称呼。例如对于从一到十的数字构成的集合，其置换将是从集合 到自身的双射。一个集合上的置换在函数合成运算下构成一个群，称为对称群或置换群。

符号

特殊置换

在上节的轮换表法中，长度等于二的轮换称为换位，这种轮换 不外是将元素 交换，并保持其它元素不变。对称群可以由换位生成。 轮换长度为偶数之轮换称为偶轮换，反之则为奇轮换；由此可定义任一置换的奇偶性，并可证明：一个置换是偶置换的充要条件是它可以由偶数个换位生成。偶轮换在置换群中构成一个正规子群，称为交错群。

计算理论中的置换

某些旧课本将置换视为变量值的赋值。在计算机科学中，这就是将值 1, 2, ..., n 赋予变量 x1, x2, ..., xn 的赋值运算子，并要求每个值只能赋予一个变量。 赋值/代入的差别表明函数式编程与指令式编程之差异。纯粹的函数式编程并不提供赋值机制。现今数学的惯例是将置换看作函数，其间运算看作函数合成，函数式编程也类似。就赋值语言的观点，一个代入是将给定的值「同时」重排，这是个有名的问题。

置换图

(2,5,1,4,3,6)的置换图 取一个无向图G，将图G的n个顶点标记v1,...,vn，对应一个置换( s(1) s(2) ... s(n) )，若且唯若s(i) < s(j) 而 i > j，则图的vi和vj相连，这样的图称为置换图。 置换图的补图必是置换图。

使用计算机

多数计算机都有个计算置换数的 nPr 键。然而此键在一些最先进的桌面型机种中却被隐藏了。例如：在 TI-83 中，按 MATH、三次右键、再按二。在卡西欧的图形计算机中，按 OPTN，一次右键（F6）、PROB（F3）、nPr（F2）。

试算表语法

多数试算表软件都有函式 PERMUT(Number，Number chosen)，用以计算置换。Number 是描述对象数量的一个整数，Number chosen 是描述每个置换中所取对象数的整数。

演算范例

#include <iostream>using namespace std;bool arrsame(int* arr, int len, int num) {int i;for (i = 0; i < len; i++)if (arr[i] == num)break;return i != len;}bool next_perm(int* perm, const int k, const int n) {int i = k - 1;doperm[i]++;while (arrsame(perm, i, perm[i]) || (perm[i] >= n && i--));if (perm[0] >= n)return 0;for (int num = 0, seat = i + 1; seat < k; num++)if (!arrsame(perm, i + 1, num))perm[seat++] = num;return 1;}int main() {int n, k;cout << "perm(n,k):" << endl;cin >> n >> k;if (n < k || k <= 0)return 0;int* perm = new int[k];for (int i = 0; i < k; i++)perm[i] = i;dofor (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))cout << perm[i] + 1;while (next_perm(perm, k, n));delete[] perm;return 0;}