Combinatoire et Dénombrement

Cours complet · mathématiques (terminale), chapitre 7 · terminale, spécialité mathématiques

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

Ce chapitre traite du dénombrement, c'est-à-dire de l'art de compter le nombre d'éléments d'un ensemble fini sans pour autant les énumérer tous. Les outils développés ici (permutations, arrangements, combinaisons) sont fondamentaux pour le calcul des probabilités.

7.1 Principes Fondamentaux du Dénombrement

Soit $E$ un ensemble fini. On note $Card (E)$ (ou $# E$ ) le cardinal de $E$ , c'est-à-dire le nombre d'éléments de $E$ .

7.1.1 Principe additif

Le principe additif concerne la réunion d'ensembles disjoints.

◆Théorème 7.1Principe additif

Si $A$ et $B$ sont deux sous-ensembles d'un ensemble $E$ , disjoints ( $A \cap B = \emptyset$ ), alors :

$Card (A \cup B) = Card (A) + Card (B)$

Plus généralement, si $A_{1}, A_{2}, \dots, A_{k}$ sont deux à deux disjoints :

$Card (A_{1} \cup A_{2} \cup \dots \cup A_{k}) = Card (A_{1}) + Card (A_{2}) + \dots + Card (A_{k})$

Enfin, si $A$ et $B$ sont quelconques :

$Card (A \cup B) = Card (A) + Card (B) - Card (A \cap B)$

7.1.2 Produit cartésien et principe multiplicatif

Définition 7.2Couple,

k

-uplet, produit cartésien

Un couple $(x, y)$ est la donnée de deux éléments dans un ordre déterminé ; un $k$ -uplet $(x_{1}, \dots, x_{k})$ est la donnée ordonnée de $k$ éléments.
Le produit cartésien de deux ensembles $E$ et $F$ , noté $E \times F$ , est l'ensemble des couples $(x, y)$ avec $x \in E$ et $y \in F$ . On définit de même $E_{1} \times E_{2} \times \dots \times E_{k}$ (ensemble des $k$ -uplets).
On note $E^{k} = E \times E \times \dots \times E$ ( $k$ facteurs) l'ensemble des $k$ -uplets d'éléments de $E$ .

◆Théorème 7.3Principe multiplicatif

Si $E$ et $F$ sont finis :

$Card (E \times F) = Card (E) \times Card (F)$

Plus généralement, pour une succession de choix où le premier choix offre $n_{1}$ possibilités, le deuxième $n_{2}$ possibilités, ..., et le $k$ -ième choix $n_{k}$ possibilités, le nombre total de configurations est :

$N = n_{1} \times n_{2} \times \dots \times n_{k}$

Deux images rendent ce principe évident, et il faut savoir passer de l'une à l'autre : le produit cartésien $E \times F$ est un rectangle de couples (autant de lignes que d'éléments de $E$ , autant de colonnes que d'éléments de $F$ ) ; la même situation vue comme une succession de choix devient un arbre, dont on compte les feuilles.

Définition 7.4

p

-uplet ou liste d'un ensemble

Soit $E$ un ensemble à $n$ éléments. Un $p$ -uplet (ou liste de longueur $p$ ) d'éléments de $E$ est une suite ordonnée de $p$ éléments de $E$ , avec répétitions possibles — c'est un élément de $E^{p}$ . D'après le principe multiplicatif, le nombre de $p$ -uplets d'un ensemble à $n$ éléments est :

$Card (E^{p}) = n^{p}$

7.1.3 Nombre de parties d'un ensemble

◆Théorème 7.5Nombre de parties

Un ensemble $E$ à $n$ éléments possède exactement $2^{n}$ parties (sous-ensembles), y compris l'ensemble vide $\emptyset$ et $E$ lui-même.

Démonstration

Notons $E = {e_{1}, e_{2}, \dots, e_{n}}$ . Se donner une partie $A$ de $E$ revient à décider, pour chaque élément $e_{i}$ , s'il appartient à $A$ (codé $1$ ) ou non (codé $0$ ). Une partie correspond donc exactement à un $n$ -uplet de ${0, 1}^{n}$ — un mot de longueur $n$ sur l'alphabet ${0, 1}$ . D'après le principe multiplicatif, il y a $2 \times 2 \times \dots \times 2 = 2^{n}$ tels mots, donc $2^{n}$ parties.

Cette correspondance se visualise par un arbre : à chaque niveau, on décide si l'élément est retenu ( $1$ ) ou non ( $0$ ). Chaque chemin de la racine à une feuille désigne une partie. Pour $n = 3$ :

iRemarque

Les issues d'une succession de $n$ épreuves de Bernoulli (succès/échec) se représentent par les mêmes mots de longueur $n$ sur ${0, 1}$ : ce lien sera exploité au chapitre 9 (schéma de Bernoulli).

7.2 Arrangements et Permutations

7.2.1 Arrangements

Un arrangement est un choix ordonné d'éléments distincts.

Définition 7.6Arrangement

Soit $E$ un ensemble à $n$ éléments. Un arrangement de $p$ éléments de $E$ ( $0 \leq p \leq n$ ) est un $p$ -uplet d'éléments distincts de $E$ . Le nombre d'arrangements de $p$ éléments parmi $n$ est noté $A_{n}^{p}$ et vaut :

$A_{n}^{p} = n \times (n - 1) \times \dots \times (n - p + 1) = \frac{n !}{( n - p )!}$

7.2.2 Permutations

Définition 7.7Permutation et factorielle

Soit $E$ un ensemble à $n$ éléments. Une permutation de $E$ est un arrangement de $n$ éléments de $E$ (c'est-à-dire un ordre sur tous les éléments de $E$ ). Le nombre de permutations d'un ensemble à $n$ éléments est noté $n!$ (lire « factorielle $n$ ») et vaut :

$n! = n \times (n - 1) \times \dots \times 2 \times 1$

Par convention, $0! = 1$ .

7.3 Combinaisons

Contrairement aux arrangements, l'ordre n'importe pas dans une combinaison (comme pour une main de cartes).

7.3.1 Définition

Définition 7.8Combinaison

Soit $E$ un ensemble à $n$ éléments. Une combinaison de $p$ éléments de $E$ ( $0 \leq p \leq n$ ) est un sous-ensemble de $E$ contenant $p$ éléments (sans ordre, sans répétition). Le nombre de combinaisons de $p$ éléments parmi $n$ est noté $(p n)$ (lire « $p$ parmi $n$ ») et vaut :

$(p n) = \frac{A _{n}^{p}}{p !} = \frac{n !}{p ! ( n - p )!}$

iRemarqueCombinaisons, mots et chemins

$(p n)$ compte aussi les mots de longueur $n$ sur ${0, 1}$ comportant exactement $p$ fois le chiffre $1$ (on choisit les $p$ positions des $1$ parmi les $n$ positions), et les chemins d'un quadrillage effectuant $p$ pas dans une direction parmi $n$ pas au total (voir le problème 2).

Listes, arrangements, combinaisons : trois mots que l'on confond aisément. Le tableau exhaustif des choix de deux lettres dans ${$ A, B, C, D $}$ les sépare une fois pour toutes. On part de toutes les cases, puis chaque contrainte en supprime.

7.3.2 Propriétés des coefficients binomiaux

Proposition 7.9Relations de symétrie et Pascal

Pour tous entiers $n$ et $p$ tels que $0 \leq p \leq n$ :

Symétrie : $(p n) = (n - p n)$
Cas particuliers : $(0 n) = 1$ , $(1 n) = n$ , $(2 n) = \frac{n ( n - 1 )}{2}$ , $(n n) = 1$
Formule de Pascal (pour $0 \leq p \leq n - 1$ ) :

$(p n) + (p + 1 n) = (p + 1 n + 1)$

Démonstration ((exigible) — formule de Pascal, par une méthode combinatoire)

Comptons les parties à $p + 1$ éléments de l'ensemble $E = {1, 2, \dots, n + 1}$ , qui sont au nombre de $(p + 1 n + 1)$ , en les classant selon qu'elles contiennent ou non l'élément $n + 1$ :

celles qui contiennent $n + 1$ : il reste à choisir $p$ éléments parmi ${1, \dots, n}$ , soit $(p n)$ parties ;
celles qui ne contiennent pas $n + 1$ : il faut choisir les $p + 1$ éléments parmi ${1, \dots, n}$ , soit $(p + 1 n)$ parties.

Ces deux familles sont disjointes et recouvrent toutes les parties à $p + 1$ éléments : le principe additif donne

$(p + 1 n + 1) = (p n) + (p + 1 n)$

La démonstration par le calcul (avec les factorielles) fait l'objet de l'exercice 7.

◆Théorème 7.10Somme des coefficients binomiaux

Pour tout entier naturel $n$ :

$k = 0 \sum n (k n) = 2^{n}$

Démonstration ((exigible) — par dénombrement)

Comptons de deux façons les parties d'un ensemble $E$ à $n$ éléments :

d'une part, $E$ possède $2^{n}$ parties (théorème de la section précédente) ;
d'autre part, classons les parties selon leur taille : pour chaque $k$ de $0$ à $n$ , il y a $(k n)$ parties à $k$ éléments. Ces familles étant deux à deux disjointes, le principe additif donne $\sum_{k = 0}^{n} (k n)$ parties au total.

Les deux comptages portant sur le même ensemble, on conclut $\sum_{k = 0}^{n} (k n) = 2^{n}$ .

7.3.3 Le Triangle de Pascal

La formule de Pascal permet de calculer de proche en proche les coefficients binomiaux sous forme triangulaire :

7.4 Méthodes Clés

Méthode : Choisir le bon outil de dénombrement

Pour savoir quelle formule utiliser pour dénombrer les tirages ou configurations :

L'ordre compte-t-il ?

Non : Il s'agit de combinaisons $⟹ (p n)$ .
Oui : Passer à la question 2.

Y a-t-il des répétitions ?

Oui : Il s'agit de $p$ -uplets (listes) $⟹ n^{p}$ .
Non : Il s'agit d'un arrangement ( $A_{n}^{p}$ ) ou d'une permutation ( $n!$ si $p = n$ ).

Exemple 7.11Application des méthodes

Un digicode est composé d'une lettre parmi A, B, C suivie de 4 chiffres distincts ou non.

Le choix de la lettre : 3 possibilités.
Le choix des 4 chiffres : C'est une liste ordonnée avec répétitions possibles de 4 chiffres parmi les 10 chiffres (0 à 9). Le nombre de choix est donc $1 0^{4} = 10000$ .
Par le principe multiplicatif, le nombre total de codes est : $3 \times 1 0^{4} = 30000$ .

7.5 Algorithmique et Programmation

Les trois algorithmes du programme pour ce chapitre : générer les coefficients binomiaux par la relation de Pascal, tirer une permutation au hasard et générer les parties à 2 éléments d'un ensemble.


def ligne_pascal(n):
    # Renvoie [C(n,0), C(n,1), ..., C(n,n)] via la relation de Pascal
    ligne = [1]
    for _ in range(n):
        nouvelle = [1]
        for i in range(len(ligne) - 1):
            nouvelle.append(ligne[i] + ligne[i + 1])
        nouvelle.append(1)
        ligne = nouvelle
    return ligne

# ligne_pascal(4) renvoie [1, 4, 6, 4, 1]

Ligne n du triangle de Pascal


from random import randint

def permutation_aleatoire(liste):
    # Melange de Fisher-Yates : chaque permutation est equiprobable
    n = len(liste)
    for i in range(n - 1, 0, -1):
        j = randint(0, i)
        liste[i], liste[j] = liste[j], liste[i]
    return liste

def parties_deux(liste):
    # Genere toutes les parties a 2 elements
    resultat = []
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            resultat.append({liste[i], liste[j]})
    return resultat

# parties_deux([1, 2, 3]) renvoie [{1, 2}, {1, 3}, {2, 3}] : C(3,2) = 3

Tirage aléatoire d'une permutation et parties à 2 éléments

Continuer sur Adloun : animation, QCM, fiches, exercices