Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

Une permutation, également appelée “numéro d’arrangement” ou “ordre”, est un réarrangement des éléments d’une liste ordonnée S en une correspondance individuelle avec S lui-même. Le nombre de permutations sur un ensemble de n éléments est donné par n ! (n factoriel ; Uspensky 1937, p. 18). Par exemple, il y a 2!=2-1=2 permutations de {1,2}, à savoir {1,2} et {2,1}, et 3!=3-2-1=6 permutations de {1,2,3}, à savoir {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} et {3,2,1}. Les permutations d’une liste peuvent être trouvées dans le langage Wolfram en utilisant la commande Permutations [list]. Une liste de longueur n peut être testée pour voir s’il s’agit d’une permutation de 1, …, n dans le langage Wolfram en utilisant la commande PermutationListQ [list].

Sedgewick (1977) résume un certain nombre d’algorithmes de génération de permutations, et identifie l’algorithme de permutation à changement minimum de Heap (1963) comme étant généralement le plus rapide (Skiena 1990, p. 10). Une autre méthode d’énumération des permutations a été donnée par Johnson (1963 ; Séroul 2000, p. 213-218).

Le nombre de façons d’obtenir un sous-ensemble ordonné de k éléments à partir d’un ensemble de n éléments est donné par

(Uspensky 1937, p. 18), où n ! est une factorielle. Par exemple, il y a 4!/2!=12 2-sous-ensembles de {1,2,3,4}, à savoir {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2} et {4,3}. Les sous-ensembles non ordonnés contenant k éléments sont appelés les k-sous-ensembles d’un ensemble donné.

La représentation d’un changement résultant de cycles d’étapes est nouvelle (jusqu’à la demande des cycles). Un cas de dégradation cyclique est le stade {4,2,1,3} de {1,2,3,4}. Il s’agit de l’étape (2)(143), relative aux cycles de changement disjoints (2) et (143). Il y a beaucoup de possibilités de représenter une désintégration cyclique puisque (1) les cycles sont disjoints et peuvent donc être déterminés dans toute requête, et (2) tout pivot d’un cycle donné indique un cycle similaire (Skiena 1990, p. 20). Ainsi, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314), et (2)(143) présentent tous un changement similaire.

Une autre documentation qui reconnaît expressément les positions impliquées par les composants lorsque l’utilisation d’un changement sur n composants utilise un cadre 2×n, où la ligne primaire est (123…n) et la ligne suivante est la nouvelle ligne d’action. Par exemple, la modification qui change les composants 1 et 2 et fixe 3 serait composée comme suit

Toute permutation est également le produit de transpositions. Les permutations sont généralement désignées dans l’ordre lexicographique ou de transposition. Il existe une correspondance entre une permutation et une paire de tableaux de Young connue sous le nom de correspondance Schensted.

Le nombre de permutations erronées de n objets est [n!/e] où [x] est la fonction entière la plus proche. Une permutation de n objets ordonnés dans laquelle aucun objet n’est à sa place naturelle est appelée un dérangement (ou parfois, une permutation complète) et le nombre de ces permutations est donné par le sous-factoriel !n.

En utilisant

 (x+y)^n=somme_(r=0)^n(n ; r)x^(n-r)y^r                   

(3)

avec x=y=1 donne

 2^n=sum_(r=0)^n(n ; r),                  

(4)

donc le nombre de façons de choisir 0, 1, …, ou n à la fois est de 2^n.

L’ensemble de toutes les permutations d’un ensemble d’éléments 1, …, n peut être obtenu en utilisant la procédure récursive suivante

 1 2 ; / ; 2 1           

(5)

 1  2 3 ;     / ; 1 3 2 ; /    ; 3 1 2 ; |     ; 3 2 1 ; \    ; 2 3 1 ; \     ; 2  1 3           

(6)

Considérez les permutations dans lesquelles aucune paire d’éléments consécutifs (c’est-à-dire les successions ascendantes ou descendantes) ne se produit. Pour n=1, 2, … éléments, les nombres de ces permutations sont 1, 0, 0, 2, 14, 90, 646, 5242, 47622, … (OEIS A002464).

On permute l’ensemble des entiers 1, 2, …, N et on divise la séquence résultante en séries croissantes. Désigner la longueur moyenne de la nième suite lorsque N s’approche de l’infini, L_n. Les premières valeurs sont résumées dans le tableau suivant, où e est la base du logarithme naturel (Le Lionnais 1983, pp. 41-42 ; Knuth 1998).

nL_nOEISapproximité

1e-1A0911311  .7182818…

                  2e^2-2eA0911321           .9524…

                  3e^3-3e^2+3/2eA0911331          .9957…