Le dénombrement est la branche des mathématiques qui permet de compter, de façon rigoureuse et sans les énumérer un par un, le nombre de possibilités d’une situation donnée : nombre de mots de passe possibles, nombre de mains au jeu de cartes, nombre de comités que l’on peut former, etc. Ce chapitre introduit les outils de base — principe multiplicatif, factorielle, arrangements et combinaisons — qui serviront ensuite de fondation au chapitre de probabilités. On y présente aussi la formule du binôme de Newton, application directe des combinaisons à l’algèbre.
Principes fondamentaux du dénombrement
Soit E un ensemble fini. Le cardinal de E, noté card(E) ou |E|, est le nombre d’éléments de E. Principe additif : si A et B sont deux parties disjointes d’un ensemble fini (A ∩ B = ∅), alors card(A ∪ B) = card(A) + card(B). Principe multiplicatif : si une situation se décompose en p étapes successives indépendantes, la première offrant n1 possibilités, la deuxième n2 possibilités, …, la p-ième np possibilités, alors le nombre total de résultats possibles est le produit n1 × n2 × … × np.
Exemple : un restaurant propose 4 entrées, 3 plats principaux et 2 desserts. Le choix d’un menu complet (une entrée, un plat, un dessert) se décompose en 3 étapes indépendantes, donc le nombre total de menus possibles est 4 × 3 × 2 = 24.
Factorielle et permutations
Pour tout entier naturel n non nul, on définit la factorielle de n par n! = n × (n − 1) × (n − 2) × … × 2 × 1, et par convention 0! = 1. Une permutation d’un ensemble E à n éléments distincts est un rangement ordonné de ces n éléments (on utilise chaque élément une seule fois). Le nombre de permutations de n éléments distincts est n!, car on a n choix pour la première place, (n − 1) choix pour la deuxième, etc.
Exemple : de combien de façons peut-on aligner 5 personnes sur un banc ? Il s’agit d’une permutation de 5 éléments distincts, donc le nombre de rangements possibles est 5! = 5 × 4 × 3 × 2 × 1 = 120.
Arrangements de p éléments parmi n
Un arrangement de p éléments (0 ≤ p ≤ n) pris parmi n éléments distincts est un choix ordonné de p éléments distincts parmi ces n éléments (sans répétition). Le nombre d’arrangements se note A(n, p) et vaut, par le principe multiplicatif : A(n, p) = n × (n − 1) × … × (n − p + 1) = n! ÷ (n − p)!. On remarque que A(n, n) = n! (une permutation est un arrangement où p = n).
Exemple : lors d’une course de 10 chevaux, on veut prévoir le tiercé dans l’ordre exact (1er, 2e, 3e). Le nombre de tiercés possibles est un arrangement de 3 éléments parmi 10 : A(10, 3) = 10 × 9 × 8 = 720.
Combinaisons — le nombre C(n, p)
Une combinaison de p éléments pris parmi n éléments distincts (0 ≤ p ≤ n) est un choix de p éléments sans tenir compte de l’ordre. Le nombre de combinaisons se note C(n, p) et vaut : C(n, p) = n! ÷ (p! × (n − p)!) = A(n, p) ÷ p!. On a les propriétés suivantes : C(n, 0) = C(n, n) = 1, C(n, 1) = n, la symétrie C(n, p) = C(n, n − p), et la formule de Pascal C(n, p) + C(n, p + 1) = C(n + 1, p + 1).
Exemple : un jury doit choisir un comité de 3 personnes parmi 8 candidats, sans distinction de rôle (l’ordre n’importe pas). Le nombre de comités possibles est C(8, 3) = 8! ÷ (3! × 5!) = (8 × 7 × 6) ÷ (3 × 2 × 1) = 336 ÷ 6 = 56.
Formule du binôme de Newton
Pour tous réels a et b et tout entier naturel n, la formule du binôme de Newton donne le développement de (a + b)n à l’aide des combinaisons : (a + b)n = C(n,0) an + C(n,1) an − 1 b + C(n,2) an − 2 b² + … + C(n,n) bn. Les coefficients C(n, k) qui apparaissent sont appelés coefficients binomiaux et coïncident avec les nombres du triangle de Pascal.
Exemple : développons (x + 1)3. Les coefficients sont C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3) = 1, donc (x + 1)3 = 1×x3 + 3×x² + 3×x + 1 = x3 + 3x² + 3x + 1.
Exercices
1. Calculer 5!, puis A(7, 3) (arrangement de 3 éléments parmi 7), puis C(6, 2).
2. Un jury de sélection doit former une équipe de 4 personnes parmi 10 candidats, sans distinction de rôle. Combien d’équipes différentes peut-on former ?
3. Un digicode utilise des mots de passe formés de 4 chiffres distincts pris parmi les 10 chiffres 0 à 9 (l’ordre des chiffres compte). Combien de mots de passe distincts peut-on créer ?
4. Une urne contient 12 boules indiscernables au toucher : 7 rouges et 5 vertes. On tire simultanément 4 boules. a) Combien de tirages différents peut-on obtenir au total ? b) Combien de tirages contiennent exactement 2 boules rouges et 2 boules vertes ? c) Combien de tirages contiennent au moins 3 boules rouges ?
5. On veut former un comité de 5 personnes à partir d’un groupe de 6 hommes et 4 femmes, en imposant qu’il y ait au moins 2 femmes dans le comité. Combien de comités différents sont possibles ?
6. En utilisant la formule du binôme de Newton, développer (2x − 3)4 et donner le coefficient du terme en x².
7. Démontrer que pour tout entier naturel n, C(n,0) + C(n,1) + … + C(n,n) = 2n (on pourra utiliser la formule du binôme avec a = b = 1). Démontrer ensuite, par un calcul direct sur les factorielles, la formule de Pascal : C(n, p) + C(n, p + 1) = C(n + 1, p + 1).
Corrigés
1.
5! = 5 × 4 × 3 × 2 × 1 = 120.
A(7, 3) = 7 × 6 × 5 = 210 (on multiplie 3 facteurs décroissants à partir de 7).
C(6, 2) = 6! ÷ (2! × 4!) = (6 × 5) ÷ (2 × 1) = 30 ÷ 2 = 15.
2.
Choisir 4 personnes parmi 10 sans distinction de rôle (l’ordre n’a pas d’importance) est une combinaison. Le nombre d’équipes possibles est : C(10, 4) = 10! ÷ (4! × 6!) = (10 × 9 × 8 × 7) ÷ (4 × 3 × 2 × 1) = 5040 ÷ 24 = 210. Il y a donc 210 équipes possibles.
3.
Un mot de passe est constitué de 4 chiffres distincts et l’ordre compte (2413 est différent de 4213) : il s’agit donc d’un arrangement de 4 éléments parmi 10. A(10, 4) = 10 × 9 × 8 × 7 = 5040. Il existe donc 5040 mots de passe possibles.
4.
a) On tire simultanément 4 boules parmi 12 : l’ordre du tirage n’a pas d’importance, c’est une combinaison. Nombre total de tirages : C(12, 4) = 12! ÷ (4! × 8!) = (12 × 11 × 10 × 9) ÷ (4 × 3 × 2 × 1) = 11880 ÷ 24 = 495.
b) Il faut choisir 2 rouges parmi 7 et 2 vertes parmi 5 (principe multiplicatif car les deux choix sont indépendants) : C(7, 2) × C(5, 2) = 21 × 10 = 210.
c) « Au moins 3 rouges » signifie « exactement 3 rouges (et 1 verte) » ou « exactement 4 rouges (et 0 verte) ». Cas 3 rouges + 1 verte : C(7, 3) × C(5, 1) = 35 × 5 = 175. Cas 4 rouges + 0 verte : C(7, 4) × C(5, 0) = 35 × 1 = 35. Ces deux cas étant disjoints, on additionne (principe additif) : 175 + 35 = 210 tirages.
5.
On distingue tous les cas où le nombre de femmes est au moins 2, sachant qu’il n’y a que 4 femmes disponibles (donc au maximum 4 femmes dans un comité de 5).
Cas 2 femmes + 3 hommes : C(4, 2) × C(6, 3) = 6 × 20 = 120.
Cas 3 femmes + 2 hommes : C(4, 3) × C(6, 2) = 4 × 15 = 60.
Cas 4 femmes + 1 homme : C(4, 4) × C(6, 1) = 1 × 6 = 6.
Ces trois cas sont deux à deux disjoints (on ne peut pas avoir à la fois 2 et 3 femmes dans le même comité), donc par le principe additif le nombre total de comités est : 120 + 60 + 6 = 186 comités possibles.
6.
On utilise (a + b)4 = C(4,0)a4 + C(4,1)a3b + C(4,2)a²b² + C(4,3)ab3 + C(4,4)b4, avec a = 2x et b = −3, et les coefficients C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1.
Terme k=0 : 1 × (2x)4 × 1 = 16x4.
Terme k=1 : 4 × (2x)3 × (−3) = 4 × 8x3 × (−3) = −96x3.
Terme k=2 : 6 × (2x)² × (−3)² = 6 × 4x² × 9 = 216x².
Terme k=3 : 4 × (2x) × (−3)3 = 4 × 2x × (−27) = −216x.
Terme k=4 : 1 × 1 × (−3)4 = 81.
Donc (2x − 3)4 = 16x4 − 96x3 + 216x² − 216x + 81. Le coefficient du terme en x² est 216.
7.
Première partie (somme des C(n,k)) : la formule du binôme donne, pour tous réels a, b : (a + b)n = C(n,0)an + C(n,1)an−1b + … + C(n,n)bn. En posant a = 1 et b = 1, on obtient (1 + 1)n = C(n,0) + C(n,1) + … + C(n,n), c’est-à-dire 2n = C(n,0) + C(n,1) + … + C(n,n), ce qui est le résultat demandé.
Deuxième partie (formule de Pascal) : on part de la définition C(n, p) = n! ÷ (p!(n − p)!) et C(n, p+1) = n! ÷ ((p+1)!(n − p − 1)!). On met les deux fractions sur le même dénominateur p!(p+1)(n − p − 1)! : C(n,p) + C(n,p+1) = [n! ÷ (p!(n−p−1)!)] × [1/(n−p) + 1/(p+1)]. On réduit la parenthèse au même dénominateur : 1/(n−p) + 1/(p+1) = (p+1+n−p) ÷ [(n−p)(p+1)] = (n+1) ÷ [(n−p)(p+1)]. Donc C(n,p) + C(n,p+1) = n!(n+1) ÷ [p!(n−p−1)!(n−p)(p+1)] = (n+1)! ÷ [(p+1)!(n−p)!]. Or n − p = (n + 1) − (p + 1), donc cette expression est exactement C(n+1, p+1). On a bien démontré C(n,p) + C(n,p+1) = C(n+1, p+1).
