Première D · 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 D, ministère des Enseignements secondaires (Niger)
Cardinal d'un ensemble fini, réunion et complémentaire
Pour deux ensembles finis \(A\) et \(B\) :
\[ \text{card}(A\cup B)=\text{card}(A)+\text{card}(B)-\text{card}(A\cap B). \]On retranche \(\text{card}(A\cap B)\) car les éléments communs à \(A\) et \(B\) seraient sinon comptés deux fois. Si \(A\) et \(B\) sont disjoints (\(A\cap B=\varnothing\)), on retrouve simplement \(\text{card}(A\cup B)=\text{card}(A)+\text{card}(B)\) — c'est le principe de partition. Pour le complémentaire \(\overline A\) de \(A\) dans un ensemble \(E\) : \(\text{card}(\overline A)=\text{card}(E)-\text{card}(A)\).
Dans une classe de \(30\) élèves, \(18\) pratiquent le football (\(F\)), \(12\) pratiquent le basketball (\(B\)), et \(6\) pratiquent les deux. Combien pratiquent au moins un des deux sports ? Combien n'en pratiquent aucun ?
\[ \text{card}(F\cup B)=18+12-6=24. \]Élèves ne pratiquant aucun des deux sports : \(30-\text{card}(F\cup B)=30-24=6\).
Figure — Diagramme de Venn de l'exemple (classe de 30 élèves)
\(12\) élèves ne pratiquent que le football, \(6\) que le basketball, \(6\) les deux, \(6\) aucun des deux — total \(12+6+6+6=30\).
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
Pour \(E\) et \(F\) finis, de cardinaux \(n\) et \(m\), et \(p\) un entier naturel :
\[ \text{card}(E\times F)=n\times m, \qquad \text{card}\bigl(\mathcal P(E)\bigr)=2^n, \qquad \text{card}(E^p)=n^p. \]\(\mathcal P(E)\) désigne l'ensemble des parties de \(E\) (sous-ensembles de \(E\), \(\varnothing\) et \(E\) inclus). \(E^p\) désigne l'ensemble des \(p\)-uplets d'éléments de \(E\) (des \(p\)-listes ordonnées, avec répétitions possibles).
Produit cartésien. Un menu propose \(4\) entrées et \(3\) plats. Nombre de menus (entrée, plat) possibles : \(4\times3=12\).
Parties. Un ensemble \(E\) à \(5\) éléments possède \(2^5=32\) parties (dont \(\varnothing\) et \(E\) lui-même).
\(p\)-uplets. Un digicode comporte \(4\) chiffres, chacun choisi parmi \(\{0,1,\dots,9\}\), avec répétitions autorisées : nombre de codes possibles \(=10^4=10\,000\).
Arrangements
Un arrangement de \(p\) éléments pris parmi \(n\) (\(p\leqslant n\)) est une liste ordonnée de \(p\) éléments distincts choisis parmi les \(n\). Leur nombre, noté \(A_n^p\), vaut :
\[ A_n^p=n\times(n-1)\times\cdots\times(n-p+1)=\dfrac{n!}{(n-p)!}. \]C'est aussi le nombre d'applications injectives d'un ensemble à \(p\) éléments vers un ensemble à \(n\) éléments. Une permutation est le cas particulier \(p=n\) : \(A_n^n=n!\).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresFigure — Arbre des arrangements de 2 lettres parmi \(\{A,B,C\}\)
3 choix pour la première lettre, puis 2 choix restants pour la seconde : \(A_3^2=3\times2=6\) arrangements, un par branche finale.
Factorielle et permutations
Une permutation d'un ensemble à \(n\) éléments est un rangement ordonné de ces \(n\) éléments, chacun utilisé une seule fois. Le nombre de permutations est \(n!\) (« factorielle \(n\) »), défini par \(n!=n\times(n-1)\times\cdots\times2\times1\), avec \(0!=1\).
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 à \(p\) éléments d'un ensemble à \(n\) éléments — contrairement à l'arrangement, l'ordre n'intervient pas. Leur nombre, noté \(\binom np\) (ou \(C_n^p\)), s'obtient en divisant le nombre d'arrangements par le nombre \(p!\) de façons de réordonner chaque groupe de \(p\) éléments :
\[ \binom np=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!\,(n-p)!}. \]Réservé aux abonnés Premium et Élève-Classe.
Voir les offresTriangle de Pascal et formule du binôme
La première traduit le fait que choisir \(p\) éléments à garder revient à choisir les \(n-p\) éléments à écarter. La seconde (« relation de Pascal ») permet de construire le triangle de Pascal, où chaque nombre est la somme des deux nombres juste au-dessus.
Les coefficients \(\binom nk\) se lisent directement sur la ligne \(n\) du triangle de Pascal.
Figure — Triangle de Pascal (\(n=0\) à \(5\))
Chaque valeur est la somme des deux valeurs juste au-dessus (relation \(\binom np+\binom n{p+1}=\binom{n+1}{p+1}\)).
Ré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.
\(\text{card}(A\cup B)=\text{card}(A)+\text{card}(B)-\text{card}(A\cap B)\).
\(\text{card}(\overline A)=\text{card}(E)-\text{card}(A)\).
\(\text{card}(E\times F)=\text{card}(E)\times\text{card}(F)\).
\(\text{card}(\mathcal P(E))=2^n\) ; \(\text{card}(E^p)=n^p\).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresRéservé aux abonnés Premium et Élève-Classe.
Voir les offresSujet type devoir
Question 1. Dans un groupe de \(50\) personnes, \(28\) parlent anglais, \(15\) parlent espagnol, \(8\) parlent les deux langues. Combien parlent au moins une des deux langues ? Combien n'en parlent aucune ?
\(\text{card}(A\cup E)=28+15-8=35\). Aucune des deux langues : \(50-35=15\).
Question 2. Un cadenas à combinaison comporte \(3\) anneaux, chacun réglable sur un chiffre de \(0\) à \(9\). Combien de combinaisons différentes existe-t-il ?
\(10^3=1\,000\) combinaisons.
Question 3. Soit \(E\) un ensemble à \(6\) éléments. Combien \(E\) a-t-il de parties au total ? Combien de parties propres non vides (on exclut \(\varnothing\) et \(E\)) ?
\(2^6=64\) parties au total. En retirant \(\varnothing\) et \(E\) : \(64-2=62\).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresRéservé aux abonnés Premium et Élève-Classe.
Voir les offres