Première D · Leçon 10
Dénombrement
Ce que dit le programme officiel (15 points)
- Cardinal d’un ensemble fini.
- 𝑐𝑎𝑟𝑑(𝐴 ∪ 𝐵) = 𝑐𝑎𝑟𝑑(𝐴) + 𝑐𝑎𝑟𝑑(𝐵) −𝑐𝑎𝑟𝑑(𝐴 ∩ 𝐵)
- 𝑐𝑎𝑟𝑑(𝐴 × 𝐵) = 𝑐𝑎𝑟𝑑(𝐴) × 𝑐𝑎𝑟𝑑(𝐵)
- 𝑐𝑎𝑟𝑑(𝐴^𝑝) = [𝑐𝑎𝑟𝑑(𝐴)]^𝑝 𝑝 ∈ ℕ∗
- Complémentaire d’un ensemble fini - Définition et notation - Cardinal du complémentaire
- Listes à p éléments : 𝑝-listes - Nombre de 𝑝-listes d’un ensemble à 𝑛 éléments (avec répétition) : 𝑛^𝑝 - Nombre de 𝑝-listes d’un ensemble à 𝑛 éléments (sans répétition) : nombre d’arrangements : 𝐴𝑛^𝑝 = 𝑛!/(𝑛−𝑝)! , 𝑛 ≥ 𝑝
- Nombre d’arrangements à 𝑛 éléments d’un ensemble à 𝑛 éléments (permutation) : nombre d’arrangements : 𝐴𝑛^𝑝 = 𝑛!
- Nombre de combinaisons à 𝑝 éléments d’un ensemble à 𝑛 éléments 𝐶𝑛^𝑝 = 𝑛!/(𝑝! (𝑛−𝑝)!) , (𝑛 ≥ 𝑝)
- Propriétés de 𝐶𝑛^𝑝 = 𝐴𝑛^𝑝/𝑝!
- 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 𝑐𝑎𝑟𝑑(𝐴 ∪ 𝐵) et 𝑐𝑎𝑟𝑑(𝐴 × 𝐵) 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 D, DPFC, version CND 0923
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\).
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 offresRésumé
\(\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