Matières › 📐 Mathématiques › Lycée › Dénombrement et combinatoire
🔢

Dénombrement et combinatoire

Arrangements, permutations, combinaisons

Voici deux questions qui se ressemblent au mot près, et qui n'ont pas la même réponse.

Dans une course de 88 coureurs, combien de podiums différents peut-on obtenir ? Et combien de groupes de 33 coureurs peut-on former ?

Dans les deux cas, on choisit trois personnes parmi huit. La langue emploie le même verbe. Et pourtant il y a 336336 podiums possibles, contre seulement 5656 groupes — six fois moins.

Pourquoi ? Parce qu'un podium attribue des rangs. Si Alice est première et Bob deuxième, ce n'est pas le même podium que l'inverse ; mais c'est bien le même groupe de trois personnes.

Vérifie-le toi-même sur un cas assez petit pour être écrit en entier : trois coureurs — Alice, Bob, Chloé — et deux places. Tu trouveras six podiums, mais seulement trois duos. Le rapport est 22, et ce n'est pas un hasard : chaque duo peut être ordonné de deux façons.

Tout le chapitre découle de cette observation. Avant chaque calcul, une seule question à se poser : est-ce que changer l'ordre change le résultat ?

Si oui, on compte les arrangements. Si non, on compte les combinaisons, et il faut alors corriger les doublons — c'est ce que fait la division par k!k! dans la formule (nk)=n!k! (n−k)!\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}.

📖 Vocabulaire clé

Factorielle n!n! : n!=n×(n−1)×⋯×2×1n! = n \times (n-1) \times \cdots \times 2 \times 1. Convention : 0!=10! = 1. Interprétation : n!n! est le nombre de façons d'ordonner nn objets distincts (permutations).
Arrangement AnkA_n^k : Nombre de façons de choisir et ordonner kk éléments parmi nn : Ank=n!(n−k)!=n(n−1)⋯(n−k+1)A_n^k = \dfrac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1). L'ordre compte.
Combinaison (nk)\binom{n}{k} : Nombre de façons de choisir kk éléments parmi nn sans tenir compte de l'ordre : (nk)=Ankk!=n!k!(n−k)!\binom{n}{k} = \dfrac{A_n^k}{k!} = \dfrac{n!}{k!(n-k)!}.
Formule du binôme de Newton : (a+b)n=∑k=0n(nk)an−kbk(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k. Les coefficients (nk)\binom{n}{k} apparaissent dans le triangle de Pascal.

📋 Choisir la bonne formule

  1. 1 Arrangements de kk éléments parmi nn (ordre compte) : Ank=n!(n−k)!A_n^k = \frac{n!}{(n-k)!}.
  2. 2 Permutations de nn éléments : n!n!.
  3. 3 Combinaisons de kk éléments parmi nn (ordre ne compte pas) : (nk)=n!k!(n−k)!\binom{n}{k}=\frac{n!}{k!(n-k)!}.
  4. 4 Multiplication des choix : si un choix comporte pp façons puis qq façons, le total est p×qp\times q.

✅ Exemple résolu

Énoncé : Au loto, on tire 55 numéros parmi 4949 (l'ordre ne compte pas). Combien de combinaisons possibles ?
Démarche :
  1. L'ordre ne compte pas : c'est une combinaison, pas un arrangement.
  2. (495)=49!5!×44!=49×48×47×46×455!\binom{49}{5} = \dfrac{49!}{5! \times 44!} = \dfrac{49 \times 48 \times 47 \times 46 \times 45}{5!}.
  3. Numérateur : 49×48×47×46×45=228 673 20049 \times 48 \times 47 \times 46 \times 45 = 228\,673\,200.
  4. Dénominateur : 5!=1205! = 120.
  5. (495)=228 673 200120=1 906 884\binom{49}{5} = \dfrac{228\,673\,200}{120} = 1\,906\,884.
Réponse : (495)=1 906 884\binom{49}{5} = 1\,906\,884 combinaisons possibles. La probabilité de gagner est d'environ 11 chance sur 1,91{,}9 million.

📐 Formules clés

n!=n×(n−1)×⋯×1n! = n\times(n-1)\times\cdots\times1
Ank=n!(n−k)!A_n^k = \dfrac{n!}{(n-k)!}
(nk)=n!k!(n−k)!\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}
(nk)=(nn−k)\dbinom{n}{k}=\dbinom{n}{n-k}

🎨 Illustration

Ordre compte vs ordre ne compte pas
Du groupe de 4 aux rôles chef/secrétaire : arrangement contre combinaison

Reprise de l'exemple du cours (le groupe de 4 élèves du problème) : en haut, on désigne un chef puis un secrétaire — l'ordre compte, A42=12A_4^2=12. En bas, les mêmes 4 élèves forment simplement un duo sans rôle — l'ordre ne compte pas, (42)=6\binom{4}{2}=6.

Arbre comparant arrangement et combinaison sur un groupe de 4 élèves En haut, un arbre a deux niveaux part d'un groupe de 4 eleves A, B, C, D. Le premier niveau choisit le chef parmi les 4, soit 4 branches. Le second niveau choisit le secretaire parmi les 3 eleves restants, soit 3 branches par chef, pour un total de 12 feuilles ordonnees comme A vers B ou B vers A. En bas, les memes 4 eleves sont regroupes en 6 duos non ordonnes AB, AC, AD, BC, BD, CD. Deux lignes en pointilles relient les feuilles A vers B et B vers A du haut vers le meme duo AB en bas, montrant que chaque duo non ordonne regroupe deux issues ordonnees. Ordre compte : arrangement A(4,2) — chef puis secrétaire Groupe : A, B, C, D Chef = A Chef = B Chef = C Chef = D A→B A→C A→D B→A B→C B→D C→A C→B C→D D→A D→B D→C 12 issues ordonnées (4 × 3) Ordre ne compte pas : combinaison C(4,2) — un duo, sans rôle {A,B} {A,C} {A,D} {B,C} {B,D} {C,D} 6 duos non ordonnés = 12 ÷ 2! (A→B et B→A se regroupent en {A,B})
  • 1 Arrangement A42A_4^2 : 44 choix de chef puis 33 choix de secrétaire parmi les élèves restants, soit 4×3=124\times3=12 issues où l'ordre (qui est chef, qui est secrétaire) compte.
  • 2 Combinaison (42)\binom{4}{2} : en oubliant les rôles, (A,B)(A,B) et (B,A)(B,A) désignent le même duo {A,B}\{A,B\} — chaque paire non ordonnée regroupe 2!=22!=2 issues ordonnées de l'arbre du haut.
  • 3 Vérification : (42)=A422!=122=6\binom{4}{2}=\dfrac{A_4^2}{2!}=\dfrac{12}{2}=6, ce qui correspond bien aux 66 duos {A,B},{A,C},{A,D},{B,C},{B,D},{C,D}\{A,B\},\{A,C\},\{A,D\},\{B,C\},\{B,D\},\{C,D\} affichés en bas.
Ce qu'il faut lire : En haut, l'arbre des 1212 façons ordonnées de désigner un chef puis un secrétaire parmi les 44 élèves du problème du cours. En bas, les mêmes 44 élèves regroupés en 66 duos non ordonnés : chaque duo apparaît deux fois dans l'arbre du haut (une fois par ordre des rôles), d'où la division par 2!2!.
Exemple du cours (problème : groupe de 4 élèves, tâche « chef et secrétaire ») : A42=4×3=12A_4^2=4\times3=12 façons ordonnées, regroupées en (42)=122!=6\binom{4}{2}=\frac{12}{2!}=6 duos non ordonnés.

❌ Une erreur, une suggestion

❌ L'erreur fréquente

Ne pas confondre arrangements et combinaisons.

✅ La suggestion

Former un comité (ordre non important) → combinaisons. Classer des coureurs (ordre important) → arrangements.

💡 À retenir

  • Question clé : l'ordre compte-t-il ? Oui → arrangement (AnkA_n^k). Non → combinaison ((nk)\binom{n}{k}).
  • (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k} : choisir kk éléments revient à exclure n−kn-k éléments.
  • Règle du produit (principe multiplicatif) : si une opération comporte pp étapes avec n1,n2,…,npn_1, n_2, \ldots, n_p choix, le total est n1×n2×⋯×npn_1 \times n_2 \times \cdots \times n_p.
  • Triangle de Pascal : (n+1k)=(nk−1)+(nk)\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. Chaque coefficient est la somme des deux au-dessus.
← Suites — compléments 33 / 36 → Lois de probabilité continues