Combinatoire/Exercices/Permutations

Cette liste d'exercices porte sur les permutations, à la fois avec et sans répétition.

Exercices introductifs

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

Solution

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

Solution

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

Une inversion d'une permutation $\sigma \in \mathrm {S} _{n}$ est un couple $(i,j)$ d'entiers tels que $1\leq i<j\leq n$ et $\sigma (i)>\sigma (j)$.

On note $I(\sigma )$ le nombre d'inversions de $\sigma$ et l'on définit $I_{n}$ comme le nombre total d'inversions dans le groupe symétrique $\mathrm {S} _{n}$ :

$I_{n}:=\sum _{\sigma \in \mathrm {S} _{n}}I(\sigma )$.

1. Démontrer la relation de récurrence : $I_{n}=nI_{n-1}+n!\,{\frac {n-1}{2}}$.
2. En déduire que ${\frac {I_{n}}{n!}}={\frac {n(n-1)}{4}}$. Comment interpréter cette valeur ?

Solution

1. Considérons la bijection de $\mathrm {S} _{n-1}\times \{1,\dots ,n\}$ dans $\mathrm {S} _{n}$ qui, à $(\sigma ,j)$, associe la permutation $\sigma '$ de $\{1,\dots ,n\}$ (vue comme un $n$-uplet d'éléments de $\{1,\dots ,n\}$ distincts) formée en intercalant, dans $\sigma$ (vue de même comme un uplet), l'entier $n$ en position $j$. On peut même (sans que ce soit vraiment utile pour la suite) expliciter cela :

   $\sigma '(k)={\begin{cases}\sigma (k)&{\text{si }}k<j,\\n&{\text{si }}k=j,\\\sigma (k-1)&{\text{si }}k>j.\end{cases}}$

   Alors, $I(\sigma ')=I(\sigma )+n-j$. Par conséquent,

   ${\begin{aligned}I(n)&=\sum _{j=1}^{n}\sum _{\sigma \in \mathrm {S} _{n-1}}{\bigl (}I(\sigma )+n-j{\bigr )}\\&=\sum _{j=1}^{n}{\bigl (}I_{n-1}+(n-1)!\,(n-j){\bigr )}\\&=nI_{n-1}+(n-1)!\,{\frac {n(n-1)}{2}}\\&=nI_{n-1}+n!\,{\frac {n-1}{2}}.\end{aligned}}$

2. La suite $J_{n}={\frac {I_{n}}{n!}}$ (valeur moyenne du nombre d'inversions pour une permutation de $\mathrm {S} _{n}$) vérifie donc :

   $J_{n}=J_{n-1}+{\frac {n-1}{2}}$.

   Comme $J_{0}=0$, on en déduit aisément (par récurrence) que $J_{n}={\frac {n(n-1)}{4}}$.

 

Permutations avec répétitions

Combien existe-t-il d'anagrammes du mot :

• BAOBAB ?
• MISSISSIPI ?

Solution

• ${\binom {6}{1,2,3}}={\frac {6!}{2!\,3!}}={\frac {6\times 5\times 4}{2}}=60$.
• ${\binom {10}{1,1,4,4}}={\frac {10!}{4!^{2}}}={\frac {10\times 9\times 8\times 7\times 6\times 5}{4\times 3\times 2}}=6300$.

 

Permutations et arrangements

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?