Les permutations (En Cours)

(sujet adapté de l'article [TAN HS 39 p 32])

Les permutations sont les différentes manières d'agencer des objets, tous différents.

Ces objets sont généralement identifiés au nombre entiers : objet 1, objet 2,… objet n

Une permutation de l'ensemble {1,2,…,n} à n éléménts consiste donc à réarranger les n nombres dans un ordre différent.

L'ensemble des permutations d'un ensemble à n éléments est noté S_n.

Question : Quel est le cardinal de S_n ?

Considérons l'ensemble à 4 éléments {1,2,3,4}. Il y a 24 permutations qu'on peut représenter en indiquant l'ordre d'apparition des éléments :

• 1234
• 1243
• 1324
• 1342
• 1423
• 1423
• 2134
• …
• 4321

Chacun de ces éléments de S₄ peut être représenté par un tableau de 4 cases, chaque case contenant un élément de l'ensemble de départ (1, 2, 3 ou 4).

Il est possible de composer les permutations. Composons par exemple (2,1,3,4) avec (4,3,1,2). La première permutation transforme 1 en 2, 2 en 1, et laisse inchangé 3 et 4. La seconde permutation transforme 1 en 4, 2 en 3, 3 en 1 et 4 en 2.

Si on applique successivement les deux permutations :

• 1 est donc transformé en 2, puis 3
• 2 est transformé en 1 puis 4
• 3 est transformé en 3 puis 1
• 4 est transformé en 4 puis 2

Appliquer successivement (2134) puis (4312) (notation (4312)o(2134)) revient donc à appliquer (3412).

Cette opération n'est pas commutative.

Question : Écrivez une fonction/procédure qui réalise cette composition

Une permutation est une application bijective. Son inverse est une autre permutation. Par exemple, l'inverse de (2314) est : (3124)

Question : Écrivez une fonction/procédure qui calcul l'inverse d'une permutation

Question : Utilisez la composition pour vérifier que l'inversion d'une permutation fonctionne correctement

Les permutations de S_n qui laissent inchangés tous les éléments sauf exacetement 2 (qui sont donc échangés) sont des transpositions.

Par exemple, (4231) est une transposition qui échange 1 et 4. On la note plus simplement [1,4]

Cette notation nous indique qu'une transposition est une cycle de longueur 2.

On note un cycle ainsi : [1,3,2] Ce cycle, de longueur 3, est une permutation qui envoie 1 sur 3, 3 sur 2 et 2 sur 1. C'est donc la permutation (3,1,2,4)

Question : Écrivez une procédure/fonction qui prend en cycle de longueur quelconque en paramètre et clacul la permutation associée.

Si on compose une permutation quelconque avec elle-même, on finit nécessairement par tomber sur l'identité. En effet, notons les configurations successives obtenues par l'application d'une permutation p : A -> B -> C -> D ...

On finira nécessairement par retomber une configuration passée, car le nombre de configuration est fini. La première configuration que l'on retrouvera sera nécessairement A. En effet, supposons que ce ne soit pas le cas, et qu'on ait par exemple la situation suivante où C est la première configuration obtenue une seconde fois : A … B … C … …. -> C. Une permutation étant bijective, ça implique qu'avant d'obtenir C pour la seconde fois, on ait obtenu B, qui a été déjà obtenu. La supposition est donc absurde est la première configuration obtenue à nouveau est donc A.

Question : Écrivez une fonction qui calcule l'ordre d'une permutation en calculant ses puissances successives.

Une inversion de la permutation p est un couple (i,j) tel que i<j et p(i)>p(j)

Par exemple, la permutation (4132) présente 4 inversions, pour les couples : 14, 23, 24, 34

Question : Écrivez une fonction qui calcule le nombre d'inversions d'une permutation

Toute permutation peut être écrite comme la composition de cycles. Programmez cette décomposition en cycles (pas évident).