Voir la source de Combinatoire/Exercices/Permutations

{{Exercice
  | idfaculté = mathématiques
  | numéro    = 3
  | chapitre  = [[../../Permutations sans répétition/]] et [[../../Permutations avec répétition/]]
  | précédent = [[../Arrangements/]]
  | suivant   = [[../Combinaisons/]]
  | niveau    = 13
}}

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

== 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|contenu= 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|contenu= 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 [[w:Signature d'une permutation#Définition de la signature|inversion d'une permutation]] <math>\sigma\in\mathrm S_n</math> est un couple <math>(i,j)</math> d'entiers tels que <math>1\le i<j\le n</math> et <math>\sigma(i)>\sigma(j)</math>.

On note <math>I(\sigma)</math> le nombre d'inversions de <math>\sigma</math> et l'on définit <math>I_n</math> comme le nombre total d'inversions dans le groupe symétrique <math>\mathrm S_n</math> :
:<math>I_n:=\sum_{\sigma\in\mathrm S_n}I(\sigma)</math>.

#Démontrer la relation de récurrence : <math>I_n=nI_{n-1}+n!\,\frac{n-1}2</math>.
#En déduire que <math>\frac{I_n}{n!}=\frac{n(n-1)}4</math>. Comment interpréter cette valeur ?
{{Solution|contenu=
#Considérons la bijection de <math>\mathrm S_{n-1}\times\{1,\dots,n\}</math> dans <math>\mathrm S_n</math> qui, à <math>(\sigma,j)</math>, associe la permutation <math>\sigma'</math> de <math>\{1,\dots,n\}</math> (vue comme un <math>n</math>-uplet d'éléments de <math>\{1,\dots,n\}</math> distincts) formée en intercalant, dans <math>\sigma</math> (vue de même comme un uplet), l'entier <math>n</math> en position <math>j</math>. On peut même (sans que ce soit vraiment utile pour la suite) expliciter cela :
#::<math>\sigma'(k)=\begin{cases}\sigma(k)&\text{si }k<j,\\
n&\text{si }k=j,\\
\sigma(k-1)&\text{si }k>j.\end{cases}
</math>
#:Alors, <math>I(\sigma')=I(\sigma)+n-j</math>. Par conséquent,
#::<math>\begin{align}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{align}
</math>
#La suite <math>J_n=\frac{I_n}{n!}</math> (valeur moyenne du nombre d'inversions pour une permutation de <math>\mathrm S_n</math>) vérifie donc :
#::<math>J_n=J_{n-1}+\frac{n-1}2</math>.
#:Comme <math>J_0=0</math>, on en déduit aisément (par récurrence) que <math>J_n=\frac{n(n-1)}4</math>.
}}

== Permutations avec répétitions  ==
Combien existe-t-il d'anagrammes du mot :
*BAOBAB ?
*MISSISSIPI ?
{{Solution|contenu=
*<math>\binom6{1,2,3}=\frac{6!}{2!\,3!}=\frac{6\times5\times4}2=60</math>.
*<math>\binom{10}{1,1,4,4}=\frac{10!}{4!^2}=\frac{10\times9\times8\times7\times6\times5}{4\times3\times2}=6300</math>.
}}

== Permutations et arrangements  ==
{{...}}

{{Bas de page
  | idfaculté = mathématiques
  | précédent = [[../Arrangements/]]
  | suivant   = [[../Combinaisons/]]
}}