Première C · Leçon 10
Dénombrement
Ce que dit le programme officiel (18 points)
- Cardinal d’un ensemble fini.
- card(A ∪ B) = card(A) + card(B) − card(A ∩ B)
- card(A × B) = card(A) × card(B)
- card(A^p) = [card(A)]^p, p ∈ ℕ*
- Complémentaire d’un ensemble fini - Définition et notation
- Cardinal du complémentaire
- Listes à p éléments : p-listes
- Nombre de p-listes d’un ensemble à n éléments (avec répétition) : n^p
- Nombre de p-listes d’un ensemble à n éléments (sans répétition) : nombre d’arrangements : A_n^p = n!/(n−p)! , n ≥ p
- Nombre d’arrangements à n éléments d’un ensemble à n éléments (permutation) : nombre d’arrangements : A_n^n = n!
- Nombre de combinaisons à p éléments d’un ensemble à n éléments C_n^p = n!/(p!(n−p)!) , (n ≥ p)
- Propriétés de C_n^p = A_n^p/p!
- Utiliser des arbres de choix, des diagrammes, des tableaux etc.
- Apprendre à choisir l’outil de dénombrement approprié pour résoudre des problèmes.
- Utiliser quelques résultats combinatoires de base
- On évitera l’utilisation abusive et mécanique des formules.
- La détermination de card(A ∪ B) et card(A × B) se fera sur des exemples concrets.
- On reformulera soigneusement les énoncés des exercices chaque fois que c’est nécessaire en relevant les ambiguïtés ou les implicites.
Source : Programme éducatif Première C, DPFC, version CND 0923
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.
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é
\(\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