Table des matières
Dénombrement
1ère Année Baccalauréat – Sciences Mathématiques
Principes fondamentaux du dénombrement
Cardinal d’un ensemble
Définition
Pour un ensemble fini \(E\), on note \(\mathrm{Card}(E)\) ou \(|E|\) le nombre d’éléments de \(E\).
Principe additif
Théorème
(Principe additif) Si \(A\) et \(B\) sont deux ensembles finis disjoints (\(A \cap B = \emptyset\)) :
\[\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B).\]
Plus généralement, pour des ensembles deux à deux disjoints \(A_1, \ldots, A_n\) :
\[\mathrm{Card}(A_1 \cup A_2 \cup \cdots \cup A_n) = \mathrm{Card}(A_1) + \mathrm{Card}(A_2) + \cdots + \mathrm{Card}(A_n).\]
Théorème
(Formule de Poincaré, cas \(n = 2\)) Pour deux ensembles finis quelconques \(A, B\) :
\[\mathrm{Card}(A \cup B) = \mathrm{Card}(A) + \mathrm{Card}(B) - \mathrm{Card}(A \cap B).\]
Exemple
Dans un lycée de \(200\) élèves, \(120\) font du sport, \(80\) font de la musique, \(50\) font les deux.
Combien font au moins l’une des deux activités ?
Principe multiplicatif
Théorème
(Principe multiplicatif) Si l’on effectue \(p\) choix successifs, et que le \(i\)-ème choix peut être fait de \(n_i\) façons (indépendamment des autres), alors le nombre total de possibilités est :
\[n_1 \times n_2 \times \cdots \times n_p.\]
Exemple
Combien de codes à \(4\) chiffres peut-on former (chiffres \(0\)–\(9\), répétitions autorisées) ?
Arbre des choix
Remarque
Un arbre des choix (ou diagramme en arbre) est une représentation graphique des possibilités. Chaque niveau correspond à un choix ; le nombre total de feuilles est le nombre de possibilités.
Cardinal d’un produit cartésien
Théorème
Pour deux ensembles finis \(E, F\) : \(\mathrm{Card}(E \times F) = \mathrm{Card}(E) \times \mathrm{Card}(F)\).
Plus généralement, \(\mathrm{Card}(E_1 \times E_2 \times \cdots \times E_n) = \mathrm{Card}(E_1) \times \cdots \times \mathrm{Card}(E_n)\).
En particulier, \(\mathrm{Card}(E^n) = \mathrm{Card}(E)^n\).
\(p\)-listes (arrangements avec répétition)
Définition
Soit \(E\) un ensemble fini à \(n\) éléments. Une \(p\)-liste de \(E\) (ou \(p\)-uplet) est un élément de \(E^p\) : une suite ordonnée de \(p\) éléments de \(E\), avec répétitions possibles.
Théorème
Le nombre de \(p\)-listes de \(E\) (avec \(\mathrm{Card}(E) = n\)) est :
\[n^p.\]
Exemple
Combien de mots de \(5\) lettres (avec ou sans signification) peut-on former avec les \(26\) lettres de l’alphabet ?
Arrangements (sans répétition)
Définition
Soit \(E\) un ensemble à \(n\) éléments et \(p \leq n\). Un arrangement de \(p\) éléments de \(E\) est une liste ordonnée de \(p\) éléments distincts de \(E\) (sans répétition).
Le nombre d’arrangements se note \(A_n^p\).
Théorème
Pour \(0 \leq p \leq n\) :
\[A_n^p = n (n-1)(n-2) \cdots (n - p + 1) = \frac{n!}{(n-p)!}.\]
Démonstration
Pour former un arrangement, on choisit le 1er élément parmi \(n\), le 2ème parmi les \(n - 1\) restants, …, le \(p\)-ème parmi \(n - p + 1\) restants. Par principe multiplicatif : \(n(n-1)\cdots(n-p+1)\). \(\square\)
Exemple
Une classe de \(30\) élèves élit un président, un vice-président et un trésorier. Combien de bureaux possibles ?
Permutations
Définition
Une permutation d’un ensemble \(E\) à \(n\) éléments est un arrangement de tous les \(n\) éléments de \(E\).
Théorème
Le nombre de permutations de \(E\) (avec \(\mathrm{Card}(E) = n\)) est :
\[n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1.\]
Par convention \(0! = 1\) et \(1! = 1\).
Exemple
Combien d’anagrammes du mot « MATH » ?
Remarque
Cas de répétitions. Pour « MAMA » : \(4!/(2! \cdot 2!) = 6\) permutations distinctes (les deux M et les deux A sont indiscernables).
Formule générale. Si un mot compte \(n\) lettres avec \(n_1\) occurrences de la 1ère, \(n_2\) de la 2ème, …, le nombre d’anagrammes est :
\[\frac{n!}{n_1! \cdot n_2! \cdots n_k!}.\]
Combinaisons
Définition
Soit \(E\) un ensemble à \(n\) éléments et \(p \leq n\). Une combinaison de \(p\) éléments de \(E\) est un sous-ensemble de \(E\) à \(p\) éléments (l’ordre ne compte pas, pas de répétitions).
Le nombre de combinaisons se note \(\binom{n}{p}\) ou \(C_n^p\).
Théorème
Pour \(0 \leq p \leq n\) :
\[\binom{n}{p} = \frac{A_n^p}{p!} = \frac{n!}{p! \, (n - p)!}.\]
Démonstration
À chaque combinaison de \(p\) éléments correspondent \(p!\) arrangements (les \(p!\) ordres possibles). Donc \(A_n^p = p! \binom{n}{p}\). \(\square\)
Propriétés des \(\binom{n}{p}\)
Proposition
\[\binom{n}{0} = 1 \quad ; \quad \binom{n}{n} = 1 \quad ; \quad \binom{n}{1} = n.\]
\[\binom{n}{p} = \binom{n}{n - p} \quad (\text{symétrie}).\]
\[\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p} \quad (\text{formule de Pascal}).\]
Démonstration
Symétrie. Choisir \(p\) éléments dans \(E\) revient à choisir les \(n - p\) éléments exclus.
Pascal. Soit \(a \in E\) fixé. Les sous-ensembles à \(p\) éléments de \(E\) se répartissent en deux catégories :
-
ceux qui contiennent \(a\) : il y en a \(\binom{n-1}{p-1}\) (choix des \(p-1\) autres).
-
ceux qui ne contiennent pas \(a\) : il y en a \(\binom{n-1}{p}\) (choix des \(p\) dans \(E \setminus \{a\}\)).
Total : \(\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}\). \(\square\)
Triangle de Pascal
| \(n \backslash p\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) |
|---|---|---|---|---|---|---|---|---|
| \(0\) | \(1\) | |||||||
| \(1\) | \(1\) | \(1\) | ||||||
| \(2\) | \(1\) | \(2\) | \(1\) | |||||
| \(3\) | \(1\) | \(3\) | \(3\) | \(1\) | ||||
| \(4\) | \(1\) | \(4\) | \(6\) | \(4\) | \(1\) | |||
| \(5\) | \(1\) | \(5\) | \(10\) | \(10\) | \(5\) | \(1\) | ||
| \(6\) | \(1\) | \(6\) | \(15\) | \(20\) | \(15\) | \(6\) | \(1\) | |
| \(7\) | \(1\) | \(7\) | \(21\) | \(35\) | \(35\) | \(21\) | \(7\) | \(1\) |
Exemple
Une classe compte \(30\) élèves. On forme un comité de \(4\). Combien de comités possibles ?
Formule du binôme de Newton
Théorème
(Binôme de Newton) Pour tous réels \(a, b\) et \(n \in \mathbb{N}\) :
\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}.\]
Démonstration
Par récurrence sur \(n\).
Init (\(n = 0\)). \((a+b)^0 = 1 = \binom{0}{0} a^0 b^0\).
Hér. Supposons la formule vraie au rang \(n\). Alors :
\[\begin{align*} (a + b)^{n+1} &= (a + b)(a+b)^n = (a + b) \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} \\ &= \sum_{k=0}^n \binom{n}{k} a^{k+1} b^{n-k} + \sum_{k=0}^n \binom{n}{k} a^k b^{n-k+1}. \end{align*}\]
Après réindexation et utilisation de la formule de Pascal, on obtient le résultat au rang \(n+1\). \(\square\)
Exemple
Développer \((2x + 3)^4\).
Identités notables
Proposition
\[\sum_{k=0}^n \binom{n}{k} = 2^n \quad (\text{en prenant } a = b = 1).\]
\[\sum_{k=0}^n (-1)^k \binom{n}{k} = 0 \quad (\text{en prenant } a = -1, b = 1).\]
Synthèse
Récapitulatif des formules
| Notion | Caractérisation | Nombre |
|---|---|---|
| \(p\)-liste | ordre + répétition | \(n^p\) |
| Arrangement | ordre, sans répétition | \(A_n^p = \dfrac{n!}{(n-p)!}\) |
| Permutation | ordre, tous les éléments | \(n!\) |
| Combinaison | sans ordre, sans répétition | \(\binom{n}{p} = \dfrac{n!}{p! \, (n-p)!}\) |
Méthodologie
Méthode
Pour identifier le bon modèle :
-
Y a-t-il un ordre ? Oui \(\to\) arrangement/\(p\)-liste/permutation. Non \(\to\) combinaison.
-
Y a-t-il des répétitions possibles ? Oui \(\to\) \(p\)-liste (\(n^p\)). Non \(\to\) arrangement/combinaison.
-
Choisit-on tous les éléments ? Oui \(\to\) permutation (\(n!\)). Non \(\to\) arrangement/combinaison.
Pièges classiques
Remarque
-
Confondre \(A_n^p\) et \(\binom{n}{p}\). \(A\) pour ordonné, \(\binom{}{}\) pour non ordonné.
-
Permutations avec répétition. Diviser par les factorielles des effectifs des éléments répétés.
-
Principe additif et ensembles non disjoints. Soustraire l’intersection.
-
Mauvaise distinction « au moins / au plus » . Penser au complémentaire.
Fin du chapitre 3 – Dénombrement