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

3.2. Même exercice, mais avec les mots suivants :

D. BOB

E. BOBO

F. LILLE

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\le i<j\le 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=n{I}_{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 ?

Permutations avec répétitions

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

• BAOBAB ?
• MISSISSIPI ?