Pass Matu 2027 Tout MatuMath jusqu’à la matu : 89.– une seule fois Tout jusqu’à la matu : 89.– une fois Voir le Pass →

Fiches › Analyse combinatoire

Analyse combinatoire · niveau commun

Permutations

Fiche de niveau commun · Analyse combinatoire · chapitre 2 · 3 notions : Permutation (objets distincts), Idée clé, Notation

Définition

▾

Permutation (objets distincts)

disposition ordonnée de tous les nn objets distincts.

Idée clé

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

Notation

PnP_n = nombre de permutations de nn objets distincts.

Factorielle

pour n∈Nn\in\N, on note n!n! le produit n⋅(n−1)⋅…⋅2⋅1n\cdot(n-1)\cdot\ldots\cdot 2\cdot 1.

Convention

0!=10! = 1.

Permutation avec répétitions

certains objets sont identiques (indiscernables).

  • Si nn objets contiennent r1r_1 objets identiques d'un type, r2r_2 d'un autre, …, rkr_k d'un autre, avec r1+⋯+rk=nr_1+\cdots+r_k=n,
  • on note Pn(r1,…,rk)P_n(r_1,\dots ,r_k) le nombre de permutations distinctes.

Vocabulaire fréquent

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

Formules essentielles

▾

Produit factoriel

n!=n⋅(n−1)⋅(n−2)⋅…⋅2⋅1n! = n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot 2\cdot 1

  • Conditions : n∈Nn\in\N.
  • Convention : 0!=10!=1.
  • Récurrence utile : n!=n⋅(n−1)!n! = n\cdot (n-1)! pour n≥1n\ge 1.

Permutations d'objets distincts

Pn=n!P_n = n!

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

Permutations avec répétitions

Pn(r1,…,rk)=n!r1! r2!⋯rk!P_n(r_1,\dots ,r_k) = \frac{n!}{r_1!\,r_2!\cdots r_k!}

  • Conditions : nn objets dont r1r_1 sont identiques entre eux, r2r_2 identiques entre eux, etc., et r1+⋯+rk=nr_1+\cdots+r_k=n.
  • Mini-commentaire : on divise par ri!r_i! car permuter entre eux des objets identiques ne change pas la disposition.

Cas particulier (table ronde)

Dispositions circulaires de n personnes distinctes=(n−1)!\text{Dispositions circulaires de $n$ personnes distinctes} = (n-1)!

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

.

Méthodes

▾

Pour compter des permutations d'objets tous distincts :

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

Pour compter des anagrammes (lettres avec répétitions) :

  • Compter nn = nombre total de lettres.
  • Repérer les répétitions : r1,r2,…,rkr_1, r_2, \ldots, r_k.
  • Appliquer : Pn(r1,…,rk)=n!r1!⋯rk!\displaystyle P_n(r_1,\dots ,r_k)=\frac{n!}{r_1!\cdots r_k!}.
  • Simplifier (si possible) et donner le résultat.

Pour des permutations avec contraintes

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

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

Décomposer en étapes

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.

Pour une table ronde (positions relatives seulement) :

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

Interprétations et graphiques

▾

Lecture combinatoire de n!n!

nombre de façons d'ordonner nn objets distincts.

  • 1er choix : nn possibilités,
  • 2e choix : n−1n-1 possibilités,
  • …,
  • dernier choix : 11 possibilité,
  • donc : n⋅(n−1)⋅…⋅1=n!n\cdot(n-1)\cdot\ldots\cdot 1 = n!.

Pourquoi on divise avec des répétitions ?

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

Croissance rapide de la factorielle

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

Figure : Permutations (Analyse combinatoire, niveau commun)

Graphique : valeurs de n!n! pour n=0n=0 à 77.

Exemples-types

▾

Exemple 1 — Anagrammes simples (ART et ARA)

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

Mot ART : 3 lettres toutes distinctes.

P3=3!=6P_3 = 3! = 6

Mot ARA : 3 lettres dont 2 A identiques.

P3(2,1)=3!2!=62=3P_3(2,1) = \frac{3!}{2!} = \frac{6}{2} = 3

Conclusion :

ART a 66 anagrammes, ARA en a 33.

Exemple 2 — Anagrammes avec répétitions (PROFESSIONS)

Le mot PROFESSIONS contient 11 lettres :

P, R, O, F, E, S, S, I, O, N, S\text{P, R, O, F, E, S, S, I, O, N, S}

On a :

SS apparaît 33 fois,

OO apparaît 22 fois,

les autres lettres sont distinctes.

Donc le nombre d'anagrammes est

P11(3,2,1,1,1,1,1,1)=11!3! 2!.P_{11}(3,2,1,1,1,1,1,1) = \frac{11!}{3!\,2!}.

Calcul :
11!3! 2!=399168006⋅2=3991680012=3326400.\frac{11!}{3!\,2!}=\frac{39916800}{6\cdot 2}=\frac{39916800}{12}=3326400.

Conclusion : il y a 3 326 4003\,326\,400 anagrammes différentes.

Exemple 3 — Ranger des livres par matières (méthode du bloc)

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.

Former 3 blocs

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

3!=6 fac¸ons.3! = 6 \text{ façons.}

Permutations à l'intérieur de chaque bloc

5! (math),3! (geˊo),8! (art).5! \text{ (math)},\quad 3! \text{ (géo)},\quad 8! \text{ (art)}.

Principe multiplicatif

Total=3!⋅5!⋅3!⋅8!.\text{Total} = 3!\cdot 5!\cdot 3!\cdot 8!.

Conclusion :

  3!⋅5!⋅3!⋅8!\;3!\cdot 5!\cdot 3!\cdot 8! rangements possibles.

Exemple 4 — Table ronde : 9 personnes, puis un couple veut être voisin

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

(9−1)!=8!(9-1)! = 8!

b) Un couple doit être voisin :

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

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

Pièges et cas particuliers

▾

Oublier que l'ordre compte

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

Oublier de diviser en cas de répétitions

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

Confondre objets identiques et objets distincts

  • 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.

Cas 0!0!

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

Table ronde

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

Méthode du bloc mal appliquée

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

Très grands nombres

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

À retenir

▾

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 r1,…,rkr_1,\dots ,r_k ?

Ai-je appliqué la bonne formule : n!n! ou n!r1!⋯rk!\dfrac{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) ⇒(n−1)!\Rightarrow (n-1)! ?

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

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

Étape suivante Flashcards : Analyse combinatoire Mémorise les définitions et formules de ce chapitre, carte par carte. →
Télécharger l'app · gratuit