Combinatoire/Exercices/Permutations
Cette liste d'exercices porte sur les permutations, à la fois avec et sans répétition.
Exercices introductifs
[modifier | modifier le wikicode]Un mot est une anagramme (le mot est féminin) d'un autre si les deux mots sont composés d'exactement les mêmes lettres, répétées un nombre identique de fois. Par exemple, "LOUPE" est une anagramme de "POULE" (mais pas de "POULPE", ni de "LOUP").
Dans le cadre de ce cours, on ne se préoccupera pas du fait que les mots aient ou pas un sens ; par exemple "OLUPE" ou "PLOUE" sont des anagrammes de LOUPE également.
3.1. En guise d'exercices d'introduction, comptez les anagrammes de :
- A. ANE
- B. LOUP
- C. OMEGA
A. ANE a 3 lettres donc, 3 ! = 6 anagrammes. LOUP a 4 lettres donc, 4 ! = 24 anagrammes. OMEGA a 5 lettres donc, 5 ! = 120 anagrammes.
3.2. Même exercice, mais avec les mots suivants :
- D. BOB
- E. BOBO
- F. LILLE
D. BOB a 3 lettres donc, il devrait y avoir 3 ! = 6 anagrammes mais, il y a 2 B donc, le nombre d'anagrammes doit être divisé par 2 soit 3. En effet si l'on pouvait discerner les 2 b, on aurait : B_1OB_2 et B_2OB_1 qui ont été comptées mais, ne représentent qu'une seule et même permutation.
E. BOBO a 4 lettres mais, il y a 2B et 2"O" donc, il y a 4 !/(2 ! 2 !) = 24/4 = 6 anagrammes.
F. LILLE a 5 lettres mais, 3 L donc, il y a 5 !/3 8 = 120/6 = 20 anagrammes.
Permutations sans répétitions
[modifier | modifier le wikicode]Une inversion d'une permutation est un couple d'entiers tels que et .
On note le nombre d'inversions de et l'on définit comme le nombre total d'inversions dans le groupe symétrique :
- .
- Démontrer la relation de récurrence : .
- En déduire que . Comment interpréter cette valeur ?
- Considérons la bijection de dans qui, à , associe la permutation de (vue comme un -uplet d'éléments de distincts) formée en intercalant, dans (vue de même comme un uplet), l'entier en position . On peut même (sans que ce soit vraiment utile pour la suite) expliciter cela :
- Alors, . Par conséquent,
- La suite (valeur moyenne du nombre d'inversions pour une permutation de ) vérifie donc :
- .
- Comme , on en déduit aisément (par récurrence) que .
Permutations avec répétitions
[modifier | modifier le wikicode]Combien existe-t-il d'anagrammes du mot :
- BAOBAB ?
- MISSISSIPI ?
- .
- .
Permutations et arrangements
[modifier | modifier le wikicode]