Terminale : Dénombrement
📚 Table des matières
1. Introduction et notions de base
1.1. Ensembles finis et cardinal
Définition 1.
Un ensemble \(E\) est dit fini si le nombre de ses éléments est un entier naturel; ce nombre s’appelle le cardinal de \(E\), noté \(\mathrm{Card}(E)\) ou \(|E|\).
Propriété 1.
Si \(E\) et \(F\) sont deux ensembles finis et disjoints (c.-à-d. \(E \cap F = \varnothing\)), alors
\[ \mathrm{Card}(E \cup F) = \mathrm{Card}(E) + \mathrm{Card}(F). \]Plus généralement, pour des ensembles deux à deux disjoints \(E_1, \ldots, E_p\) :
\[ \mathrm{Card}\left(\bigcup_{i=1}^p E_i\right) = \sum_{i=1}^p \mathrm{Card}(E_i). \]1.2. Couples, triplets, k-uplets et produit cartésien
Définition 2. (Produit cartésien)
Soient \(E\) et \(F\) deux ensembles finis non vides. Leur produit cartésien \(E \times F\) est l’ensemble des couples \((x,y)\) avec \(x\in E\) et \(y\in F\).
Son cardinal vérifie :
On définit de même le produit cartésien de trois ensembles \(E \times F \times G\), puis de \(k\) ensembles.
2. Principe multiplicatif et additif
Théorème 1. (Principe multiplicatif)
Si une expérience ou un procédé se décompose en deux étapes successives, la première pouvant se réaliser de \(n\) façons, la deuxième de \(m\) façons, alors le nombre total de façons de réaliser l’ensemble des deux étapes est \(n \times m\).
Exemple : On compose un code à deux caractères : le premier est une lettre parmi 26, le second un chiffre parmi 10.
Nombre total de codes possibles : \(26 \times 10 = 260\).
Principe additif.
Si on a plusieurs procédures alternatives disjointes (i.e. qui ne peuvent pas se produire ensemble), le nombre total est la somme des nombres de cas de chaque procédure.
Exemple : On dispose de deux procédures disjointes pour composer un code :
- soit on choisit un mot de longueur 2 parmi l'alphabet \(\{A,B\}\) (donc \(2^2=4\) possibilités),
- soit on choisit un chiffre parmi \(\{0,1,2,3\}\) (donc \(4\) possibilités).
Ces deux procédures sont disjointes, donc le nombre total de codes possibles est \(4+4=8\).
3. k-listes, arrangements, permutations
3.1. k-uplets
Définition 3.
Soit \(E\) un ensemble non vide, \(n = \mathrm{Card}(E)\). Un \(k\)-uplet (ou \(k\)-liste) de \(E\) est une suite ordonnée de \(k\) éléments de \(E\), où la répétition est possible.
Propriété 2.
Le nombre de \(k\)-uplets d’un ensemble de cardinal \(n\) est \(n^k\).
Exemple : On lance un dé équilibré à 6 faces, trois fois. Le nombre de suites (d’ordre des résultats) possibles est \(6^3 = 216\).
3.2. Arrangements
Définition 4.
Un arrangement de \(k\) éléments parmi \(n\) (sans répétition) est une suite ordonnée de \(k\) éléments distincts choisis parmi \(n\) éléments.
Formule.
Le nombre d’arrangements de \(k\) éléments parmi \(n\) est
\[ A_n^k = n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}, \]pour \(0 \le k \le n\).
Exemple : Nombre de manières de faire un podium (1ᵉʳ, 2ᵉ, 3ᵉ) parmi 10 coureurs : \(A_{10}^3 = 10 \times 9 \times 8 = 720\).
Exemple illustratif :
- Dans un arrangement, on choisit des éléments et on les place dans un ordre précis (ex. podium).
- Dans une combinaison, on choisit seulement l'ensemble des éléments, sans tenir compte de l'ordre (ex. une équipe).
3.3. Permutations
Définition 5.
Une permutation d’un ensemble de \(n\) éléments est un arrangement de tous les \(n\) éléments ; autrement dit une suite ordonnée de longueur \(n\) sans répétition et contenant tous les éléments.
Formule.
Le nombre de permutations d’un ensemble à \(n\) éléments est \(n!\).
4. Combinaisons et parties
4.1. Parties d’un ensemble
Définition 6.
Si \(E\) est un ensemble fini de cardinal \(n\), une partie (ou sous-ensemble) de \(E\) est tout ensemble constitué d’éléments de \(E\).
Propriété 3.
Le nombre de parties de \(E\) est \(2^n\).
Lien avec d'autres représentations : Chaque partie de \(E=\{1,\dots,n\}\) correspond à :
- un mot binaire de longueur \(n\) (1 = élément choisi, 0 = élément non choisi) ;
- un chemin dans un arbre de Bernoulli de profondeur \(n\) (choix / non-choix) ;
- un \(n\)-uplet d'éléments de \(\{0,1\}\).
Ainsi on obtient \(2^n\) parties.
4.2. Combinaisons sans ordre
Définition 7.
Une combinaison de \(k\) éléments parmi \(n\) est le choix d’un sous-ensemble de \(k\) éléments parmi \(n\), sans tenir compte de l’ordre.
Formule.
\[ \binom{n}{k} = C_n^k = \frac{n!}{k!(n-k)!}, \quad 0 \le k \le n. \]Cas particuliers :
\[ \binom{n}{0} = 1, \quad \binom{n}{1} = n, \quad \binom{n}{2} = \frac{n(n-1)}{2}. \]Symétrie : On a l’égalité fondamentale :
\[ \binom{n}{k} = \binom{n}{n-k}. \]5. Formules d'inclusion-exclusion
Théorème 2. (Deux ensembles)
Soient \(A\) et \(B\) deux ensembles finis. Alors
\[ |A \cup B| = |A| + |B| - |A\cap B|. \]6. Binôme de Newton et relations fondamentales
Théorème 3. (Binôme de Newton)
Pour tout réel \(a, b\) et tout entier \(n\) :
\[ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k. \]Preuve
On veut montrer par récurrence que pour tout entier \(n\ge 0\) et tous réels \(a,b\) :
\[ (a+b)^n=\sum_{k=0}^n \binom{n}{k} a^{\,n-k} b^{\,k}. \]Initialisation : Pour \(n=0\) : \((a+b)^0=1\) et \(\displaystyle\sum_{k=0}^{0}\binom{0}{k}a^{0-k}b^{k}=\binom{0}{0}a^0b^0=1\). La formule est vraie pour \(n=0\).
Hérédité : Supposons la formule vraie pour un entier \(n\ge0\). Nous montrons qu'elle est alors vraie pour \(n+1\).
On multiplie les deux membres par \((a+b)\) :
\[ (a+b)^{n+1}=(a+b)\sum_{k=0}^n \binom{n}{k} a^{\,n-k} b^{\,k} \]En développant et en effectuant des changements d'indices (voir cours détaillé), on utilise la relation de Pascal :
\[ \binom{n}{j} + \binom{n}{j-1} = \binom{n+1}{j} \]Pour finalement obtenir :
\[ (a+b)^{n+1} = \sum_{j=0}^{n+1} \binom{n+1}{j}\, a^{\,n+1-j} b^{\,j}. \]Ceci montre que si la formule est vraie pour \(n\) elle est vraie pour \(n+1\). Par le principe de récurrence, la formule vaut pour tout entier \(n\ge0\).
6.1. Somme des coefficients binomiaux
Propriété 4.
On a l'égalité :
\[ \sum_{k=0}^n \binom{n}{k} = 2^n. \]Preuve combinatoire : Considérons un ensemble \(E\) à \(n\) éléments. Chaque partie de \(E\) a une taille \(k\) (avec \(0 \le k \le n\)). Le nombre de parties de taille \(k\) est \(\binom{n}{k}\). En sommant sur toutes les tailles, on obtient le nombre total de parties : \(\sum_{k=0}^n \binom{n}{k}\).
Mais on sait aussi que chaque élément peut être choisi ou non : il y a \(2\) choix par élément, indépendants, donc \(2^n\) parties au total.
Preuve via le binôme de Newton : Prendre \(a=1\) et \(b=1\) dans l'identité du binôme de Newton donne directement \((1+1)^n = \sum_{k=0}^n \binom{n}{k} = 2^n\).
6.2. Relation de Pascal
Théorème 4. (Relation de Pascal)
Pour tout \(n\ge 1\) et \(1\le k \le n\) :
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \]Preuve combinatoire : Pour choisir \(k\) éléments parmi \(n\), regardons un élément fixé \(x\). On distingue deux cas : soit \(x\) est choisi (alors il reste à choisir \(k-1\) parmi \(n-1\) éléments), soit \(x\) n'est pas choisi (alors il faut choisir \(k\) parmi \(n-1\)). D'où la relation.
7. Approfondissement : combinaisons avec répétition
Formule.
Le nombre de combinaisons avec répétitions (choisir \(k\) éléments parmi \(n\) avec répétition, sans ordre) est :
\[ \binom{n+k-1}{k}. \]Remarque : Cette formule se démontre en représentant la sélection comme une distribution de \(k\) objets identiques dans \(n\) cases distinctes ("barres et étoiles").
8. Exemples algorithmiques
- Génération de la liste des coefficients \(\binom{n}{k}\) par la relation de Pascal (itératif) ;
- Génération aléatoire d’une permutation de \(n\) éléments (algorithme de Fisher-Yates) ;
- Génération des parties à \(k\) éléments (méthode par combinatoire lexicographique).