Première L · Leçon 12
Dénombrement
Ce que dit le programme officiel (4 points)
- Nombre de suites de p éléments d’un ensemble à n éléments (n puissance p)
- Arrangements ; combinaisons ; notations n!, A et C
- Formule du binôme de Newton ; triangle de Pascal
- Diagrammes, tableaux à double entrée, arbres sur des exemples concrets
Source : Programme de mathématiques, séries L (Sénégal), octobre 2006
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 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\).
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\).
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!=n\times(n-1)\times\cdots\times2\times1\), avec \(0!=1\).
Réservé aux abonnés Premium et Élève-Classe.
Voir les offresArrangements
Combien de menus, de codes, de classements sont possibles ? On peut parfois tout écrire, mais le nombre de cas grandit très vite. Deux questions suffisent pour choisir le bon calcul : l'ordre compte-t-il, et peut-on choisir deux fois le même élément ?
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)!}. \]Réservé aux abonnés Premium et Élève-Classe.
Voir les offresFigure — Arbre des podiums (Or, Argent) parmi 3 finalistes
3 finalistes — Awa (A), Boureima (B), Cissé (C) — pour la médaille d'or, puis 2 restants pour l'argent : \(A_3^2=3\times2=6\) podiums.
Si un choix se fait en plusieurs étapes, avec \(n_1\) possibilités pour la première, puis \(n_2\) pour la deuxième, et ainsi de suite, le nombre total de choix est le produit \(n_1\times n_2\times\cdots\). Un arbre permet de le voir : chaque branche finale correspond à un choix complet.
On en déduit, pour \(p\) éléments choisis successivement parmi \(n\) en tenant compte de l'ordre :
- si un même élément peut revenir : \(n\times n\times\cdots\times n=n^p\) choix ;
- si les éléments sont tous différents (arrangement) : \(A_n^p=n\times(n-1)\times\cdots\times(n-p+1)\) choix ;
- si l'on range les \(n\) éléments (permutation) : \(n!\) choix.
1. Que choisit-on, et dans quel ordre ? On écrit un exemple de résultat (un code, un classement, un menu).
2. Un élément peut-il revenir ? Oui pour les lettres d'un code ; non pour des personnes ou des places.
3. Y a-t-il une contrainte ? On place d'abord ce qui est imposé, puis on compte les choix restants.
On applique alors le principe multiplicatif, et l'on vérifie sur un petit cas avec un arbre.
Énoncé. Un restaurant propose 3 entrées, 4 plats et 2 desserts. Un menu comprend une entrée, un plat et un dessert. Combien de menus différents peut-on composer ?
Solution : on choisit en trois étapes : 3 choix d'entrée, puis 4 choix de plat, puis 2 choix de dessert. D'après le principe multiplicatif, il y a \(3\times4\times2=24\) menus. L'arbre aurait 3 branches, puis 4 à partir de chacune, puis 2 : 24 branches finales.
Énoncé. Un code est formé de 3 lettres choisies parmi A, B, C, D, E. Combien de codes existe-t-il si les lettres peuvent se répéter ? Et si elles doivent être toutes différentes ?
Solution : avec répétition, chaque position a 5 choix : \(5^3=125\) codes. Avec des lettres différentes, il y a 5 choix pour la première, 4 pour la deuxième, 3 pour la troisième : \(A_5^3=5\times4\times3=60\) codes. Il y a donc \(125-60=65\) codes contenant au moins deux fois la même lettre.
Énoncé. Combien de mots (ayant un sens ou non) peut-on écrire avec les cinq lettres du mot LIVRE, chacune une fois ? Combien commencent par L et finissent par E ?
Solution : les cinq lettres sont différentes : on les range dans 5 places, soit \(5!=5\times4\times3\times2\times1=120\) mots. Si L est en première place et E en dernière, il reste à ranger I, V, R dans les trois places du milieu : \(3!=6\) mots.
Énoncé. Huit coureurs disputent une course. Combien de podiums (premier, deuxième, troisième) sont possibles ? Combien si l'on sait qu'Ali a gagné ?
Solution : l'ordre compte et un coureur n'occupe qu'une place : \(A_8^3=8\times7\times6=336\) podiums. Si Ali est premier, il reste à choisir le deuxième et le troisième parmi les 7 autres : \(A_7^2=7\times6=42\) podiums.
Additionner au lieu de multiplier. Pour le menu, \(3+4+2=9\) ne compte rien du tout : chaque entrée se combine avec chaque plat, puis avec chaque dessert.
Confondre avec et sans répétition. Pour les codes, \(5^3\) et \(A_5^3\) ne répondent pas à la même question : on relit l'énoncé (« toutes différentes » ?).
Oublier l'ordre quand il compte. Le podium Ali, Bintou, Moussa n'est pas le même que Moussa, Bintou, Ali : on compte des listes ordonnées, d'où \(A_8^3\).
Combinaisons
Choisir 3 délégués dans une classe, tirer 2 boules d'un coup dans un sac, former une équipe : dans toutes ces situations, on prend des objets « en paquet », sans ordre. Compter ces paquets, c'est compter des combinaisons.
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\), vaut :
\[ \binom np=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!\,(n-p)!}. \]Réservé aux abonnés Premium et Élève-Classe.
Voir les offresPour tout entier naturel \(n\) :
- \(\binom n0=1\) : il y a une seule façon de ne rien choisir ;
- \(\binom nn=1\) : une seule façon de tout prendre ;
- \(\binom n1=n\) et \(\binom n2=\dfrac{n(n-1)}2\).
Lien avec les arrangements. Chaque combinaison de \(p\) éléments peut être rangée de \(p!\) façons : on obtient ainsi tous les arrangements. Donc \(A_n^p=p!\times\binom np\).
Interprétation de \(\binom np=\binom n{n-p}\). Choisir les \(p\) éléments que l'on garde revient à choisir les \(n-p\) éléments que l'on laisse : il y a autant de façons de faire l'un que l'autre. Par exemple \(\binom{10}8=\binom{10}2=45\).
On se pose deux questions sur la situation.
1. L'ordre compte-t-il ? Si l'on distingue « Awa puis Issa » de « Issa puis Awa » (podium, code, rôles différents, tirages successifs), l'ordre compte. S'il s'agit d'un groupe, d'une main, d'un tirage simultané, l'ordre ne compte pas.
2. Un même objet peut-il revenir ? Oui pour un tirage avec remise ou un code où un chiffre se répète.
- ordre et répétition possibles : \(n^p\) (listes) ;
- ordre, sans répétition : \(A_n^p\) (arrangements ; \(n!\) si l'on range tout) ;
- sans ordre, sans répétition : \(\binom np\) (combinaisons).
3. Découper la situation : « et » se traduit par une multiplication, « ou » (cas qui ne se recouvrent pas) par une addition, « au moins un » se calcule souvent par le contraire.
Énoncé. Une classe de 12 élèves élit a) un comité de 3 élèves ; b) un bureau formé d'un président, d'un trésorier et d'un secrétaire. Combien de choix possibles dans chaque cas ?
Solution : a) Les 3 membres du comité ont le même rôle : l'ordre ne compte pas. \(\binom{12}3=\dfrac{12\times11\times10}{3\times2\times1}=220\) comités.
b) Les rôles sont différents : l'ordre compte. \(A_{12}^3=12\times11\times10=1\,320\) bureaux. On retrouve \(1\,320=3!\times220\) : chaque comité donne \(6\) bureaux, selon la répartition des rôles.
Énoncé. Une urne contient 5 boules rouges et 3 boules vertes. On tire simultanément 2 boules. Combien de tirages a) possibles ; b) avec deux boules rouges ; c) avec deux boules vertes ; d) avec une boule de chaque couleur ?
Solution : a) Un tirage est une partie à 2 éléments des 8 boules : \(\binom82=28\). b) On choisit 2 rouges parmi 5 : \(\binom52=10\). c) \(\binom32=3\).
d) Une rouge parmi 5 et une verte parmi 3 : \(5\times3=15\). Contrôle : les trois cas b, c, d ne se recouvrent pas et couvrent tout, et \(10+3+15=28\).
Énoncé. Six amis se retrouvent et chacun serre la main de chacun des autres une fois. Combien de poignées de main sont échangées ?
Solution : une poignée de main correspond à une paire de personnes, sans ordre (« Awa serre la main d'Issa » est la même poignée que l'inverse). Il y en a \(\binom62=\dfrac{6\times5}2=15\).
Autre raisonnement : chacun serre 5 mains, ce qui fait \(6\times5=30\), mais chaque poignée est comptée deux fois, d'où \(30\div2=15\). La figure montre les 15 segments qui relient 6 points.
Figure — Les 15 paires parmi 6 personnes
Six points placés sur un cercle représentent les six amis. Chaque segment relie deux d'entre eux : il correspond à une poignée de main, c'est-à-dire à une combinaison de 2 éléments parmi 6. On compte 6 côtés (en bleu marine) et 9 diagonales (en or), soit 15 segments.
Énoncé. Un club compte 7 filles et 5 garçons. On forme une délégation de 4 membres. Combien de délégations a) en tout ; b) avec exactement 2 filles ; c) avec au moins une fille ?
Solution : a) \(\binom{12}4=\dfrac{12\times11\times10\times9}{4\times3\times2\times1}=495\).
b) 2 filles parmi 7 et 2 garçons parmi 5 : \(\binom72\times\binom52=21\times10=210\).
c) Le contraire de « au moins une fille » est « aucune fille », c'est-à-dire 4 garçons parmi 5 : \(\binom54=5\) délégations. Donc \(495-5=490\) délégations comptent au moins une fille.
Utiliser les combinaisons quand l'ordre compte. Pour un podium ou des rôles différents, on compte des arrangements : dans l'exemple 1, \(220\) comités mais \(1\,320\) bureaux.
Additionner au lieu de multiplier. « 2 filles et 2 garçons » donne \(21\times10\), pas \(21+10\) : à chaque choix des filles correspond chacun des choix des garçons.
Compter « au moins une » cas par cas, et en oublier. Passer par le contraire (« aucune ») est plus sûr et plus rapide : \(495-5\) au lieu d'additionner les cas 1, 2, 3 et 4 filles.
Triangle de Pascal et formule du binôme
La seconde relation (« 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