Première C · Leçon 9
Dénombrement
Ce que dit le programme officiel (11 points)
- Cardinal d’un ensemble fini
- Utilisation d’arbres de choix et de tableaux pour dénombrer
- Calculer le cardinal de la réunion de deux ensembles, du produit cartésien de deux ensembles, de l’ensemble des parties d’un ensemble fini
- Arrangements ; permutations (notation des arrangements de p éléments parmi n ; notation factorielle n!)
- Combinaisons (notation des combinaisons de p éléments parmi n)
- Reconnaître les notions : p-liste, arrangements, permutations, combinaisons
- Utiliser les notions de p-liste, arrangements, permutations, combinaisons pour résoudre des problèmes de dénombrement
- Formule du binôme
- Triangle de Pascal
- Reconnaître la formule du binôme
- Utiliser le triangle de Pascal
Source : Programme de mathématiques, classe de Première C, ministère des Enseignements secondaires (Niger)
Cardinal d'un ensemble fini, réunion et complémentaire
Pour un ensemble fini \(E\), on note \(\mathrm{Card}(E)\) (ou \(|E|\)) son cardinal, le nombre de ses éléments. \(A\cup B\) est la réunion (éléments de \(A\) ou de \(B\)), \(A\cap B\) l'intersection (éléments communs), \(\overline A\) le complémentaire de \(A\) dans \(E\). Une partition de \(E\) est une famille de parties non vides, deux à deux disjointes, dont la réunion est \(E\).
Si \(A\) et \(B\) sont disjoints (\(A\cap B=\varnothing\)) : \(\mathrm{Card}(A\cup B)=\mathrm{Card}(A)+\mathrm{Card}(B)\). On soustrait le cardinal de l'intersection pour ne pas compter deux fois les éléments communs.
Dans un lycée, 120 élèves font des maths renforcées, 80 font de la physique renforcée, et 35 font les deux. Combien suivent au moins l'une des deux options ?
\[ \mathrm{Card}(A\cup B)=120+80-35=165\ \text{élèves}. \]Figure — Diagramme de Venn de l'exemple ci-dessus
\(120+80-35=165\) : la zone commune (35) n'est comptée qu'une seule fois.
Dénombrer avec un arbre de choix ou un tableau
Dénombrer, c'est compter sans rien oublier et sans rien compter deux fois. Avant toute formule, deux outils permettent d'y parvenir en organisant les possibilités : l'arbre de choix et le tableau. Ils restent indispensables dans les situations où aucune formule ne s'applique.
Un arbre de choix représente une situation où l'on fait plusieurs choix l'un après l'autre.
- On part d'un point, la racine.
- Chaque étape de choix est un niveau de l'arbre : de chaque point partent autant de branches qu'il y a de choix possibles à cette étape.
- Un chemin va de la racine à une extrémité de l'arbre ; il correspond à un résultat complet, c'est-à-dire à une suite de choix.
Le nombre de résultats possibles est le nombre de chemins, c'est-à-dire le nombre d'extrémités de l'arbre.
Lorsque le nombre de branches est le même en chaque point d'un niveau, on dit que l'arbre est régulier ; sinon il est irrégulier, et il faut le dessiner en entier pour compter.
Si une situation se décompose en étapes successives, avec \(n_1\) choix à la première étape, puis \(n_2\) choix à la deuxième quel que soit le premier choix, puis \(n_3\) choix à la troisième quels que soient les deux premiers, et ainsi de suite, alors le nombre total de résultats est le produit
\[n_1\times n_2\times n_3\times\cdots\]Justification. Dans l'arbre, il y a \(n_1\) branches au premier niveau ; de chacune partent \(n_2\) branches, ce qui donne \(n_1\times n_2\) chemins de deux étapes ; chacun se prolonge de \(n_3\) façons, et ainsi de suite.
Ce principe suppose un arbre régulier. Il dispense de dessiner toutes les branches : on en trace quelques-unes pour comprendre, puis on multiplie.
Lorsqu'un résultat est formé de deux composantes, on peut le ranger dans un tableau : les lignes correspondent aux valeurs de la première composante, les colonnes aux valeurs de la seconde. Chaque case représente un résultat et un seul. Avec \(n\) lignes et \(p\) colonnes, le tableau compte \(n\times p\) cases : c'est le cardinal du produit cartésien de deux ensembles à \(n\) et \(p\) éléments.
Un tableau sert aussi à répartir une population selon deux critères (fille ou garçon, sportif ou non, par exemple). On écrit alors dans chaque case un effectif, avec une ligne et une colonne de totaux : les effectifs manquants s'obtiennent par addition ou soustraction.
1. Décrire un résultat. Se demander ce qu'est exactement un résultat : une suite de choix ordonnés ? un couple ? une personne classée selon deux critères ?
2. Choisir l'outil. Des choix successifs (trois étapes ou plus, ou des choix qui dépendent des précédents) : un arbre. Deux composantes seulement : un tableau à double entrée, plus rapide à remplir. Une population et deux critères : un tableau d'effectifs.
3. Compter. Si l'arbre est régulier, multiplier les nombres de branches de chaque niveau. S'il est irrégulier, le dessiner entièrement et compter ses extrémités. Dans un tableau, compter les cases qui conviennent.
4. Contrôler. Vérifier que chaque résultat apparaît une fois et une seule, et relire l'énoncé : l'ordre des choix compte-t-il ?
Énoncé. Une cantine propose 2 entrées (salade, soupe), 3 plats (poulet, poisson, riz) et 2 desserts (fruit, gâteau). Un menu comporte une entrée, un plat et un dessert. a) Combien de menus différents peut-on composer ? b) Combien contiennent du poisson ? c) On interdit d'associer la soupe et le riz : combien de menus reste-t-il ?
Solution : a) L'arbre a trois niveaux : 2 branches pour l'entrée, puis 3 pour le plat, puis 2 pour le dessert. Il est régulier : \(2\times 3\times 2=12\) menus.
b) Le plat est imposé : il reste \(2\times 1\times 2=4\) menus.
c) Les menus interdits sont ceux qui passent par « soupe » puis « riz » : il y en a 2 (un par dessert). Il reste \(12-2=10\) menus. L'arbre n'est plus régulier : après « soupe », il n'y a que 2 plats possibles, alors qu'il y en a 3 après « salade ». On peut aussi compter \(1\times 3\times 2+1\times 2\times 2=6+4=10\).
Énoncé. On lance un dé rouge et un dé vert, numérotés de 1 à 6, et l'on note la somme des deux numéros. a) Combien y a-t-il de résultats possibles ? b) Combien donnent une somme égale à 8 ? une somme au moins égale à 10 ? c) Quelle somme est obtenue le plus souvent ?
Solution : a) Un résultat est un couple (numéro rouge ; numéro vert). On dresse le tableau des sommes : 6 lignes et 6 colonnes, donc \(6\times 6=36\) résultats.
| + | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
b) La somme 8 apparaît dans 5 cases : \((2\,;6)\), \((3\,;5)\), \((4\,;4)\), \((5\,;3)\), \((6\,;2)\). Les sommes 10, 11 et 12 occupent \(3+2+1=6\) cases.
c) La somme 7 occupe toute une diagonale du tableau : 6 cases. C'est la somme la plus fréquente.
Énoncé. Deux joueurs, A et B, s'affrontent. Le premier qui gagne deux manches remporte le match, et l'on arrête alors de jouer. Combien de déroulements différents le match peut-il avoir ? Dans combien de cas A est-il vainqueur ?
Solution : On note à chaque manche le nom du gagnant. Après « A puis A » ou « B puis B », le match s'arrête : ces branches ne se prolongent pas. Après « A puis B » ou « B puis A », une troisième manche est nécessaire. L'arbre est irrégulier ; on le dessine en entier (figure ci-dessous) et l'on compte ses extrémités : AA, ABA, ABB, BAA, BAB, BB, soit 6 déroulements.
Le joueur A gagne dans 3 cas : AA, ABA et BAA. Le produit \(2\times 2\times 2=8\) serait faux ici : il compterait des manches jouées après la fin du match.
Figure — L'arbre du match en deux manches gagnantes
Chaque niveau est une manche et chaque branche porte le nom du gagnant. Les deux branches du haut et du bas s'arrêtent au deuxième niveau : le match est terminé. Les six extrémités sont les six déroulements possibles ; en or, les trois où le joueur A l'emporte, en bleu les trois où c'est le joueur B.
Énoncé. Dans une classe de 30 élèves, 18 pratiquent le football. La classe compte 12 filles, dont 5 pratiquent le football. Combien de garçons ne pratiquent pas le football ?
Solution : On dresse un tableau à deux critères et l'on y place d'abord les quatre nombres de l'énoncé : 30, 18, 12 et 5. Les autres s'obtiennent par soustraction.
| Football | Pas de football | Total | |
|---|---|---|---|
| Filles | 5 | 7 | 12 |
| Garçons | 13 | 5 | 18 |
| Total | 18 | 12 | 30 |
Garçons : \(30-12=18\). Garçons qui pratiquent le football : \(18-5=13\). Filles qui ne le pratiquent pas : \(12-5=7\). Garçons qui ne le pratiquent pas : \(18-13=5\). Contrôle par la colonne : \(7+5=12=30-18\). Cinq garçons ne pratiquent pas le football.
Multiplier alors que l'arbre est irrégulier. Le principe multiplicatif exige le même nombre de choix à chaque étape, quels que soient les choix précédents. Dans le match de l'exemple 3, ce n'est pas le cas : il faut compter les extrémités une à une.
Compter un ordre qui n'existe pas. Un arbre range les choix dans un ordre. Si l'on doit désigner deux délégués parmi trois élèves A, B et C, l'arbre « premier choisi, second choisi » donne \(3\times 2=6\) chemins, mais « A puis B » et « B puis A » désignent la même paire de délégués : il n'y a que 3 paires. Avant de conclure, il faut toujours se demander si deux chemins différents donnent ou non le même résultat.
Produit cartésien, parties d'un ensemble et p-uplets
\(A\times B\) est l'ensemble des couples \((a,b)\) avec \(a\in A\), \(b\in B\) : pour chaque choix de \(a\) (\(\mathrm{Card}(A)\) possibilités), il y a \(\mathrm{Card}(B)\) choix pour \(b\).
Un menu propose 4 entrées et 6 plats. Le nombre de menus (entrée, plat) possibles : \(4\times6=24\).
Si \(\mathrm{Card}(E)=n\), l'ensemble \(\mathcal P(E)\) des parties de \(E\) (y compris \(\varnothing\) et \(E\) lui-même) a pour cardinal \(\mathrm{Card}(\mathcal P(E))=2^n\) — chaque élément de \(E\) est soit dans la partie, soit hors d'elle, indépendamment (2 choix par élément, \(n\) éléments). L'ensemble \(E^p\) des \(p\)-uplets d'éléments de \(E\) (avec répétition possible) a pour cardinal \(\mathrm{Card}(E^p)=n^p\).
\(E=\{a,b,c\}\) : \(\mathrm{Card}(\mathcal P(E))=2^3=8\) parties (dont \(\varnothing\) et \(E\)). Un code à 4 chiffres (chiffres \(0\) à \(9\), répétitions autorisées) : \(\mathrm{Card}(\{0,\dots,9\}^4)=10^4=10\,000\) codes possibles.
- Ne pas oublier de soustraire \(\mathrm{Card}(A\cap B)\) dans une réunion — l'erreur la plus fréquente consiste à additionner sans corriger le double-comptage.
- \(2^n\) compte les parties (sous-ensembles), \(n^p\) compte les \(p\)-uplets (listes ordonnées avec répétition) — deux notions très différentes à ne pas confondre.
Arrangements
Pour \(n\) entier naturel non nul, \(n!\) (« factorielle \(n\) ») est le produit des entiers de \(1\) à \(n\) : \(n!=1\times2\times\cdots\times n\), et \(0!=1\) par convention. \(n!\) compte le nombre de façons d'ordonner \(n\) objets distincts.
Un arrangement de \(p\) éléments pris parmi \(n\) (\(0\leqslant p\leqslant n\)) est une liste ordonnée de \(p\) éléments distincts choisis parmi \(n\) — leur nombre se note \(A_n^p\) :
\[ A_n^p=n(n-1)(n-2)\cdots(n-p+1)=\frac{n!}{(n-p)!}. \]Une permutation de \(n\) éléments est un arrangement de tous les \(n\) éléments (\(p=n\)) : leur nombre est \(A_n^n=n!\).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresCombinaisons
Une combinaison de \(p\) éléments pris parmi \(n\) est une partie non ordonnée à \(p\) éléments choisie parmi \(n\) — leur nombre se note \(C_n^p\) (ou \(\binom{n}{p}\)) :
\[ C_n^p=\frac{A_n^p}{p!}=\frac{n!}{p!\,(n-p)!}. \]À la différence de l'arrangement, l'ordre ne compte pas : on divise par \(p!\), le nombre de façons de réordonner les \(p\) éléments choisis.
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresLa première relation traduit : choisir \(p\) éléments à garder revient à choisir \(n-p\) éléments à écarter. La seconde (relation de Pascal) permet de construire chaque ligne du triangle de Pascal à partir de la précédente, sans recalculer les factorielles.
Figure — Triangle de Pascal, lignes \(n=0\) à \(n=6\)
Chaque valeur est la somme des deux valeurs juste au-dessus (relation de Pascal) : \(C_n^p+C_n^{p+1}=C_{n+1}^{p+1}\).
Les coefficients \(C_n^k\) sont exactement les valeurs de la ligne \(n\) du triangle de Pascal.
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresRéservé aux abonnés Premium et Élève-Classe.
Voir les offresRésumé
Un niveau par étape, une branche par choix ; un résultat est un chemin de la racine à une extrémité.
Arbre régulier : on multiplie les nombres de choix, \(n_1\times n_2\times n_3\times\cdots\)
Aucune formule : on dessine tout l'arbre et l'on compte ses extrémités.
Pour des résultats à deux composantes : \(n\) lignes et \(p\) colonnes donnent \(n\times p\) cases.
Tableau d'effectifs avec totaux : les cases manquantes se trouvent par soustraction.
\(\mathrm{Card}(A\cup B)=\mathrm{Card}A+\mathrm{Card}B-\mathrm{Card}(A\cap B)\).
\(\mathrm{Card}(A\times B)=\mathrm{Card}A\times\mathrm{Card}B\).
\(\mathrm{Card}(\mathcal P(E))=2^n\).
\(\mathrm{Card}(E^p)=n^p\).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresSujet type devoir
Question 1. Sur 200 élèves, 130 aiment les maths, 90 aiment la physique, 45 aiment les deux. Combien n'aiment ni l'une ni l'autre ?
\(\mathrm{Card}(A\cup B)=130+90-45=175\). Aucune des deux : \(200-175=25\) élèves.
Question 2. Une plaque d'immatriculation est formée de 3 lettres (parmi 26) suivies de 4 chiffres (parmi 10), toutes répétitions autorisées. Combien de plaques distinctes ?
\(26^3\times10^4=17\,576\times10\,000=175\,760\,000\) plaques.
Question 3. Combien l'ensemble \(\{1,2,3,4,5\}\) a-t-il de parties de cardinal quelconque ? Combien de parties non vides ?
\(2^5=32\) parties en tout ; \(32-1=31\) parties non vides (on retire \(\varnothing\)).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offres