Permutations

disposition ordonnée de tous les $n$ objets distincts.

l'ordre compte (changer l'ordre donne une autre permutation).

$P_n$ = nombre de permutations de $n$ objets distincts.

pour $n\in \mathbb{N}$, on note $n!$ le produit $n\cdot (n-1)\cdot \dots \cdot 2\cdot 1$.

$0!=1$.

certains objets sont identiques (indiscernables).

• Si $n$ objets contiennent $r_1$ objets identiques d'un type, $r_2$ d'un autre, …, $r_k$ d'un autre, avec $r_1+\cdots +r_k=n$,
• on note $P_n(r_1,\dots ,r_k)$ le nombre de permutations distinctes.

anagramme = permutation des lettres d'un mot (en tenant compte des répétitions).

• Conditions : $n\in \mathbb{N}$.
• Convention : $0!=1$.
• Récurrence utile : $n!=n\cdot (n-1)!$ pour $n\ge 1$.

• Conditions : $n$ objets tous différents, on place tous les objets, ordre important.

• Conditions : $n$ objets dont $r_1$ sont identiques entre eux, $r_2$ identiques entre eux, etc., et $r_1+\cdots +r_k=n$.
• Mini-commentaire : on divise par $r_i!$ car permuter entre eux des objets identiques ne change pas la disposition.

• Condition : on compte seulement la position relative (les rotations sont considérées identiques).
• Astuce : fixer une personne, puis permuter les $n-1$ autres.

.

• Identifier $n$ (nombre total d'objets).
• Vérifier que l'on place tous les objets et que l'ordre compte.
• Répondre : $P_n=n!$.

• Compter $n$ = nombre total de lettres.
• Repérer les répétitions : $r_1,r_2,\dots ,r_k$.
• Appliquer : $P_n(r_1,\dots ,r_k)=\frac{n!}{r_1!\cdots r_k!}$.
• Simplifier (si possible) et donner le résultat.

(positions imposées, voisins, etc.) :

Décrire clairement la contrainte (ex. ``ces objets ensemble'', ``ces positions réservées'').

chronologiques indépendantes.

Compter chaque étape, puis multiplier (principe multiplicatif).

Si des objets doivent rester ensemble : utiliser la méthode du bloc

• remplacer le groupe par un bloc,
• permuter les blocs/objets,
• multiplier par les permutations internes du bloc.

• Vérifier que les rotations sont considérées identiques.
• Fixer une personne (ou un objet repère).
• Permuter les $n-1$ restants : $(n-1)!$.
• Avec contrainte de voisinage : faire un bloc puis appliquer la logique circulaire.

nombre de façons d'ordonner $n$ objets distincts.

• 1er choix : $n$ possibilités,
• 2e choix : $n-1$ possibilités,
• …,
• dernier choix : $1$ possibilité,
• donc : $n\cdot (n-1)\cdot \dots \cdot 1=n!$.

• Si $r$ objets sont identiques, permuter ces $r$ objets ne crée pas une nouvelle disposition.
• On a donc $r!$ sur-comptages à corriger $\Rightarrow$ division par $r!$ (et pareil pour chaque type identique).

$n!$ augmente très vite (même pour des $n$ modestes).

Graphique : valeurs de $n!$ pour $n=0$ à $7$.

Calculer le nombre d'anagrammes de mots avec et sans répétitions de lettres.

Mot ART : 3 lettres toutes distinctes.

Mot ARA : 3 lettres dont 2 A identiques.

ART a $6$ anagrammes, ARA en a $3$.

Le mot PROFESSIONS contient 11 lettres :

$S$ apparaît $3$ fois,

$O$ apparaît $2$ fois,

les autres lettres sont distinctes.

Donc le nombre d'anagrammes est

Un étudiant a :

5 livres de math,

3 livres de géographie,

8 livres d'histoire de l'art.

On veut les ranger sur une étagère en gardant chaque matière ensemble.

(Math, Géo, Art). Les 3 blocs peuvent être ordonnés de

$3!\cdot 5!\cdot 3!\cdot 8!$ rangements possibles.

a) 9 personnes autour d'une table ronde : seules les positions relatives comptent.

b) Un couple doit être voisin :

• On regroupe le couple en bloc : on a alors $8$ ``objets'' (le bloc + 7 autres personnes).
• En cercle : $(8-1)!=7!$ dispositions.
• Dans le bloc, le couple peut être dans 2 ordres : $2!$.
  $$\text{Total}=2\cdot 7!.$$

Conclusion : a) $8!$ dispositions, b) $2\cdot 7!$ dispositions.

si l'ordre n'a pas d'importance, ce n'est pas une permutation.

pour un mot comme ARA, $3!$ est faux (sur-comptage), il faut $\frac{3!}{2!}$.

• si deux objets sont indiscernables $\Rightarrow$ on doit corriger le comptage (division).
• si les objets sont distincts (même couleur mais étiquetés, par exemple) $\Rightarrow$ pas de division.

ne pas oublier $0!=1$ (important pour éviter des incohérences dans certaines formules).

• si les rotations sont identiques $\Rightarrow (n-1)!$,
• si les places sont numérotées (table avec places fixes) $\Rightarrow n!$.

• toujours multiplier par les permutations internes du bloc,
• attention à ne pas compter deux fois la même contrainte.

$n!$ devient vite énorme ; utiliser une calculatrice et garder une écriture exacte (avec $!$) si nécessaire.

Ai-je vérifié que l'ordre compte ?

Est-ce qu'on place tous les objets (permutation) ?

Les objets sont-ils tous distincts ? Sinon, quelles répétitions $r_1,\dots ,r_k$ ?

Ai-je appliqué la bonne formule : $n!$ ou $\frac{n!}{r_1!\cdots r_k!}$ ?

Ai-je utilisé le principe multiplicatif (décomposition en étapes) si contrainte ?

Y a-t-il un bloc à former (objets voisins / regroupés) ?

Est-ce une table ronde (rotations identiques) $\Rightarrow (n-1)!$ ?

Ai-je géré correctement le cas $0!=1$ si besoin ?

Le résultat est-il cohérent (ordre de grandeur, pas d'oubli de division) ?