Principe multiplicatif, k-uplets · Permutations, arrangements, combinaisons et parties d'un ensemble
Compter, c'est facile quand il y a cinq objets ; c'est un art quand il y a des millions de codes possibles, de mains de cartes ou de classements. Le dénombrement donne des méthodes pour compter sans énumérer, à partir d'un seul principe : quand une situation se décompose en étapes successives, le nombre de possibilités se multiplie. De ce principe découlent trois familles de nombres : les $k$-uplets (on peut répéter, l'ordre compte), les arrangements et permutations (pas de répétition, l'ordre compte) et les combinaisons (pas de répétition, l'ordre ne compte pas). Toute la difficulté est de reconnaître la bonne famille : deux questions suffisent, « peut-on répéter ? » et « l'ordre compte-t-il ? ». Ce chapitre prolonge la loi binomiale, dont les coefficients sont précisément des combinaisons, et il alimente le calcul des probabilités dans les situations d'équiprobabilité.
si une situation se décompose en $k$ étapes successives offrant respectivement $n_1$, $n_2$, …, $n_k$ possibilités (indépendamment des choix précédents), le nombre total de possibilités est le produit $n_1 \times n_2 \times \cdots \times n_k$.
Produit cartésien :
si $A$ a $n$ éléments et $B$ en a $p$, l'ensemble $A \times B$ des couples $(a \,;\, b)$ a $n \times p$ éléments.
$k$-uplets :
le nombre de listes ordonnées de $k$ éléments choisis parmi $n$, avec répétition possible, est $n^{k}$. Exemple : $10^{4}$ codes à quatre chiffres.
Parties d'un ensemble :
un ensemble à $n$ éléments possède $2^{n}$ parties (pour chaque élément, deux choix : le prendre ou non).
Exercice 1 — Compter avec le principe multiplicatif (Tle)
Un menu propose $3$ entrées, $4$ plats et $2$ desserts. Combien de menus complets peut-on composer ?
Combien y a-t-il de codes de carte bancaire à $4$ chiffres ? de mots de passe formés de $3$ lettres (parmi $26$) suivies de $2$ chiffres ?
Un questionnaire comporte $10$ questions à $4$ réponses possibles. De combien de façons peut-on le remplir au hasard ? Quelle est la probabilité d'obtenir tout juste ?
Combien de parties possède un ensemble à $5$ éléments ? Combien de sous-ensembles non vides ?
▶ Solution — Exercice 1
$3 \times 4 \times 2 = 24$ menus.
Codes : $10^{4} = 10\,000$. Mots de passe : $26^{3} \times 10^{2} = 17\,576 \times 100 = 1\,757\,600$.
$4^{10} = 1\,048\,576$ façons. Une seule est entièrement juste : probabilité $\dfrac{1}{4^{10}} \approx 9{,}5 \times 10^{-7}$.
$2^{5} = 32$ parties, dont l'ensemble vide : $31$ sous-ensembles non vides.
Permutations et arrangements (Tle)
Factorielle :
pour $n \geqslant 1$, $n! = n \times (n - 1) \times \cdots \times 2 \times 1$, et par convention $0! = 1$. Exemples : $3! = 6$, $5! = 120$, $10! = 3\,628\,800$.
Permutations :
le nombre de façons d'ordonner $n$ éléments distincts (de les ranger tous) est $n!$.
Arrangements :
le nombre de listes ordonnées de $k$ éléments distincts choisis parmi $n$ (sans répétition, l'ordre compte) est $n \times (n - 1) \times \cdots \times (n - k + 1) = \dfrac{n!}{(n - k)!}$.
Lecture :
$k$ facteurs décroissants à partir de $n$ : $n$ choix pour la première place, $n - 1$ pour la deuxième, etc.
Podium (or, argent, bronze) parmi $8$ coureurs : $8 \times 7 \times 6 = 336$ podiums possibles. Ordre d'arrivée complet des $8$ coureurs : $8! = 40\,320$.
Exercice 2 — Permutations et arrangements, étape par étape (Tle)
Compléter : pour former un podium avec $3$ des $8$ coureurs, il y a $…$ choix pour la première place, puis $…$ pour la deuxième, puis $…$ pour la troisième : $… \times … \times … = …$ podiums.
Combien d'anagrammes (mots ayant un sens ou non) peut-on former avec les lettres du mot MATHS ?
De combien de façons peut-on ranger $6$ livres différents sur une étagère ? Et si un livre précis doit être à gauche ?
On tire successivement et sans remise $3$ boules dans une urne qui en contient $10$, toutes différentes. Combien de tirages ordonnés ?
De combien de façons peut-on attribuer $4$ rôles différents à $4$ personnes choisies parmi $7$ ?
▶ Solution — Exercice 2
$8$ choix, puis $7$, puis $6$ : $8 \times 7 \times 6 = 336$ podiums.
Les $5$ lettres sont distinctes : $5! = 120$ anagrammes.
$6! = 720$ rangements. Si un livre est fixé à gauche, il reste $5! = 120$ rangements pour les autres.
$10 \times 9 \times 8 = 720$ tirages ordonnés (arrangements de $3$ parmi $10$).
$7 \times 6 \times 5 \times 4 = 840$ (arrangements de $4$ parmi $7$ : les rôles sont distincts, l'ordre compte).
Combinaisons (Tle)
Définition :
une combinaison de $k$ éléments parmi $n$ est une partie à $k$ éléments d'un ensemble à $n$ éléments : pas de répétition, et l'ordre ne compte pas. Leur nombre est le coefficient binomial
$$
\dbinom{n}{k} = \dfrac{n \times (n - 1) \times \cdots \times (n - k + 1)}{k!} = \dfrac{n!}{k!\,(n - k)!}.
$$
Pourquoi diviser par $k!$ :
chaque partie à $k$ éléments correspond à $k!$ arrangements (ses différents ordres). On compte les arrangements, puis on retire l'ordre.
Test pratique : si échanger deux éléments choisis donne la même issue (même comité, même main), l'ordre ne compte pas.
Choisir $3$ délégués parmi $25$ élèves (tous les délégués ont le même rôle) : $\dbinom{25}{3} = \dfrac{25 \times 24 \times 23}{3 \times 2 \times 1} = 2\,300$. Si les trois rôles étaient différents (titulaire, premier et second suppléants), on compterait $25 \times 24 \times 23 = 13\,800$.
Exercice 3 — Calculer des combinaisons (Tle)
Calculer $\dbinom{10}{3}$, $\dbinom{6}{2}$, $\dbinom{7}{7}$, $\dbinom{9}{8}$ et $\dbinom{12}{10}$ (utiliser la symétrie pour ce dernier).
Combien de mains de $5$ cartes peut-on former avec un jeu de $32$ cartes ?
Un comité de $5$ personnes doit comporter exactement $2$ filles choisies parmi $12$ et $3$ garçons choisis parmi $15$. Combien de comités ?
Vérifier la relation de Pascal sur l'exemple $\dbinom{5}{2} + \dbinom{5}{3} = \dbinom{6}{3}$, puis retrouver $\sum_{k=0}^{4} \dbinom{4}{k} = 2^{4}$ en calculant chaque terme.
$\dbinom{5}{2} = 10$, $\dbinom{5}{3} = 10$ et $\dbinom{6}{3} = 20 = 10 + 10$. ✓{} Ensuite $1 + 4 + 6 + 4 + 1 = 16 = 2^{4}$ : c'est le nombre total de parties d'un ensemble à $4$ éléments, classées selon leur taille. ✓
Exercice 4 — L'ordre compte-t-il ? (Tle)
Pour chaque situation, identifier le modèle ($k$-uplets, arrangements, permutations ou combinaisons) et calculer le nombre de possibilités.
Tiercé dans l'ordre : les trois premiers chevaux, dans l'ordre, d'une course à $15$ partants.
Tiercé dans le désordre : les trois premiers chevaux, sans tenir compte de l'ordre.
Un code de $3$ chiffres tous différents.
Un code de $3$ chiffres quelconques.
Une équipe de $5$ joueurs choisis parmi $12$.
Le classement final complet de $12$ équipes.
▶ Solution — Exercice 4
Arrangements de $3$ parmi $15$ : $15 \times 14 \times 13 = 2\,730$.
Combinaisons : $\dbinom{15}{3} = \dfrac{2\,730}{6} = 455$. On retrouve le résultat précédent divisé par $3!$.
Arrangements de $3$ parmi $10$ : $10 \times 9 \times 8 = 720$.
$3$-uplets de chiffres : $10^{3} = 1\,000$.
Combinaisons (les joueurs ont le même statut) : $\dbinom{12}{5} = 792$.
Permutations : $12! = 479\,001\,600$.
Exercice 5 — Dénombrer pour calculer des probabilités (Tle)
Une urne contient $5$ boules rouges et $3$ boules vertes, indiscernables au toucher. On tire simultanément $3$ boules.
Combien y a-t-il de tirages possibles ? Pourquoi sont-ils équiprobables ?
Calculer la probabilité de tirer $3$ boules rouges, puis celle de tirer exactement $2$ rouges.
Calculer la probabilité de tirer au moins une verte.
Sur un quadrillage, on va du point $(0 \,;\, 0)$ au point $(4 \,;\, 3)$ en ne faisant que des pas vers la droite ou vers le haut. Combien de chemins ? Expliquer le lien avec la loi binomiale.
▶ Solution — Exercice 5
$\dbinom{8}{3} = 56$ tirages (parties à $3$ éléments de l'ensemble des $8$ boules). Les boules étant indiscernables au toucher, chaque partie a la même chance d'être tirée.
L'événement contraire est « 3 rouges » : $P(\text{au moins une verte}) = 1 - \dfrac{5}{28} = \dfrac{23}{28}$.
Un chemin est une suite de $7$ pas dont exactement $3$ vers le haut : il est déterminé par le choix des positions des $3$ pas « haut » parmi $7$, soit $\dbinom{7}{3} = 35$ chemins. De même, dans un arbre à $n$ épreuves de Bernoulli, le nombre de chemins comportant $k$ succès est $\dbinom{n}{k}$ : c'est l'origine du coefficient dans $P(X = k) = \dbinom{n}{k} p^{k} (1 - p)^{n - k}$.
Exercice 6 — Problème en contexte : la force d'un mot de passe (Tle)
Un mot de passe utilise des caractères pris parmi $26$ minuscules, $26$ majuscules et $10$ chiffres, soit $62$ caractères. Un attaquant teste $10^{9}$ mots de passe par seconde.
Combien de mots de passe de $8$ caractères existe-t-il ? Combien de temps faut-il, au plus, pour les essayer tous ? (Donner le résultat en jours.)
Combien de mots de passe de $8$ caractères contiennent au moins un chiffre ?
Reprendre la question 1 avec $12$ caractères. Conclure.
Un site impose $8$ caractères exactement, tous différents. Cela augmente-t-il ou diminue-t-il le nombre de mots de passe possibles ? Le calculer.
▶ Solution — Exercice 6
$62^{8} \approx 2{,}18 \times 10^{14}$ mots de passe. Temps : $\dfrac{2{,}18 \times 10^{14}}{10^{9}} \approx 2{,}18 \times 10^{5}$ s, soit environ $60$ heures, c'est-à-dire $2{,}5$ jours.
On compte le contraire (aucun chiffre : $52$ caractères possibles) : $62^{8} - 52^{8} \approx 2{,}18 \times 10^{14} - 5{,}35 \times 10^{13} \approx 1{,}65 \times 10^{14}$.
$62^{12} \approx 3{,}23 \times 10^{21}$ ; temps $\approx 3{,}23 \times 10^{12}$ s, soit environ $102\,000$ années. Passer de $8$ à $12$ caractères multiplie le nombre de possibilités par $62^{4} \approx 1{,}5 \times 10^{7}$ : la longueur compte bien plus que la complexité des règles.
Interdire les répétitions diminue le nombre de possibilités : arrangements de $8$ parmi $62$, soit $62 \times 61 \times \cdots \times 55 \approx 1{,}36 \times 10^{14}$, contre $2{,}18 \times 10^{14}$. Une telle règle affaiblit légèrement le mot de passe.
Exercice 7 — Problème en contexte : poignées de main, matchs et diagonales (Tle)
Dans une réunion de $15$ personnes, chacun serre la main de tous les autres une fois. Combien de poignées de main ?
Un tournoi réunit $10$ équipes ; chaque équipe rencontre chacune des autres une fois. Combien de matchs ? Et si chaque rencontre se joue en aller-retour ?
Combien de diagonales possède un polygone convexe à $n$ sommets ? Vérifier pour le pentagone ($5$ diagonales) et calculer pour un polygone à $20$ sommets.
On place $8$ points dans le plan, trois quelconques jamais alignés. Combien de triangles ont pour sommets trois de ces points ?
▶ Solution — Exercice 7
Une poignée de main est une paire de personnes : $\dbinom{15}{2} = 105$.
Un match est une paire d'équipes : $\dbinom{10}{2} = 45$ matchs. En aller-retour, l'ordre (qui reçoit) compte : $10 \times 9 = 90$ matchs, soit le double.
Une diagonale ou un côté relie deux sommets : $\dbinom{n}{2}$ segments, dont $n$ côtés : $\dbinom{n}{2} - n = \dfrac{n(n - 1)}{2} - n = \dfrac{n(n - 3)}{2}$ diagonales. Pentagone : $\dfrac{5 \times 2}{2} = 5$. ✓{} Pour $n = 20$ : $\dfrac{20 \times 17}{2} = 170$.
Un triangle est une partie à $3$ éléments de l'ensemble des $8$ points : $\dbinom{8}{3} = 56$ triangles.
Faux. Un comité n'est pas ordonné : $\dbinom{10}{3} = 120$ comités. Le nombre $720$ compte chaque comité $3! = 6$ fois.
Vrai. En classant les $2^{n}$ parties d'un ensemble à $n$ éléments selon leur nombre d'éléments $k$, on obtient $\dbinom{n}{k}$ parties de chaque taille.