Dénombrement

Le dénombrement consiste à compter le nombre d’éléments d’un ensemble fini. C’est un outil indispensable en probabilités : pour calculer une probabilité, il faut souvent compter les cas favorables et les cas totaux.

Prérequis

Ensembles et Nombres, Probabilités

Principes fondamentaux§

Principe additif§

Principe additif

Si deux ensembles $A$ et $B$ sont disjoints ( $A \cap B = \emptyset$ ), alors :

\text{Card}(A \cup B) = \text{Card}(A) + \text{Card}(B)

En pratique : quand on fait un choix OU un autre (alternatives exclusives), on additionne.

Principe multiplicatif§

Principe multiplicatif

Si un choix se décompose en étapes successives indépendantes avec $n_1$ possibilités pour la 1ère étape, $n_2$ pour la 2ème, etc. :

\text{Nombre total} = n_1 \times n_2 \times \cdots \times n_k

En pratique : quand on fait un choix ET un autre (étapes successives), on multiplie.

Exemple

Un code est formé de 2 lettres suivies de 3 chiffres.

26 choix pour chaque lettre, 10 choix pour chaque chiffre
Total : $26 \times 26 \times 10 \times 10 \times 10 = 676,000$ codes possibles

flowchart LR
    A["Problème de<br/>dénombrement"] --> B{"Les choix sont..."}
    B -->|"alternatifs (OU)"| C["Additionner"]
    B -->|"successifs (ET)"| D["Multiplier"]

La factorielle§

Définition

Pour tout entier $n \geq 0$ :

n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1

Par convention : $0! = 1$ .

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5 040
8	40 320
10	3 628 800

Propriété fondamentale

$n! = n \times (n-1)!$ pour tout $n \geq 1$ .

Interprétation : $n!$ est le nombre de façons d’ordonner $n$ objets distincts (permutations).

Permutations§

Définition

Une permutation de $n$ éléments est un arrangement ordonné de tous ces éléments.

\text{Nombre de permutations de } n \text{ éléments} = n!

Exemple

De combien de façons peut-on asseoir 5 personnes autour d’une table en ligne ?

$5! = 120$ façons.

Table ronde

Autour d’une table ronde, on fixe une personne et on permute les autres : $(n-1)!$ arrangements.

Arrangements§

Définition

Un arrangement de $p$ éléments parmi $n$ ( $p \leq n$ ) est un choix ordonné de $p$ éléments parmi $n$ éléments distincts.

A_n^p = \frac{n!}{(n-p)!} = n \times (n-1) \times \cdots \times (n-p+1)

C’est le nombre de façons de choisir $p$ éléments en tenant compte de l’ordre.

Exemple

Dans une classe de 30 élèves, on élit un président, un vice-président et un trésorier.

$A_{30}^3 = 30 \times 29 \times 28 = 24,360$ possibilités.

Combinaisons§

Définition

Une combinaison de $p$ éléments parmi $n$ est un choix non ordonné de $p$ éléments parmi $n$ .

\binom{n}{p} = \frac{n!}{p!(n-p)!} = \frac{A_n^p}{p!}

Se lit ” $p$ parmi $n$ ” ou “combinaison de $n$ choose $p$ ”.

L’idée : on divise les arrangements par $p!$ car l’ordre ne compte pas.

Valeurs utiles§

	$p=0$	$p=1$	$p=2$	$p=3$	$p=4$	$p=5$
$n=0$	1
$n=1$	1	1
$n=2$	1	2	1
$n=3$	1	3	3	1
$n=4$	1	4	6	4	1
$n=5$	1	5	10	10	5	1

C’est le triangle de Pascal.

Propriétés essentielles§

Propriétés des combinaisons

Symétrie : $\binom{n}{p} = \binom{n}{n-p}$
Bords : $\binom{n}{0} = \binom{n}{n} = 1$
Formule de Pascal : $\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}$
Somme : $\displaystyle\sum_{p=0}^{n} \binom{n}{p} = 2^n$

Exemple

De combien de façons peut-on choisir une équipe de 3 joueurs parmi 10 ?

L’ordre ne compte pas → $\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Formule du binôme de Newton§

Théorème — Binôme de Newton

Pour tous $a, b \in \mathbb{R}$ et $n \in \mathbb{N}$ :

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}

Exemples

$(a+b)^2 = a^2 + 2ab + b^2$

$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$

$(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$

Cas particuliers utiles

$a = 1, b = 1$ : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ (nombre total de parties d’un ensemble à $n$ éléments)
$a = 1, b = -1$ : $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$

L’arbre de décision : quel outil utiliser ?§

flowchart TD
    A["Je veux choisir p objets<br/>parmi n objets distincts"] --> B{"L'ordre<br/>compte-t-il ?"}
    B -->|Oui| C{"Je prends tous<br/>les objets ?<br/>(p = n)"}
    C -->|Oui| D["Permutation<br/>n!"]
    C -->|Non| E["Arrangement<br/>A(n,p) = n!/(n-p)!"]
    B -->|Non| F["Combinaison<br/>C(n,p) = n!/p!(n-p)!"]

    style D fill:#C8E6C9
    style E fill:#BBDEFB
    style F fill:#E1BEE7

Résumé rapide

Situation	Ordre ?	Formule
Ordonner $n$ objets	Oui	$n!$
Choisir $p$ parmi $n$ , avec ordre	Oui	$A_n^p = \frac{n!}{(n-p)!}$
Choisir $p$ parmi $n$ , sans ordre	Non	$\binom{n}{p} = \frac{n!}{p!(n-p)!}$
$n$ choix successifs avec remise, $p$ fois	Oui	$n^p$

Avec ou sans remise ?§

Attention à la répétition

Sans remise (défaut) : chaque objet est choisi au plus une fois → arrangements et combinaisons classiques
Avec remise : un objet peut être choisi plusieurs fois
- Ordonné avec remise : $n^p$ (p-uplets)
- Non ordonné avec remise : $\binom{n+p-1}{p}$ (combinaisons avec répétition)

Exemple — Tirage avec remise

On lance un dé 4 fois. Nombre de résultats possibles : $6^4 = 1,296$ (ordonné, avec remise).

Exercices types§

Exercice 1 — Mot de passe

Un mot de passe contient 4 caractères choisis parmi 26 lettres et 10 chiffres, sans répétition.

Solution : C’est un arrangement de 4 parmi 36 (l’ordre compte, sans remise) : $A_{36}^4 = 36 \times 35 \times 34 \times 33 = 1,413,720$

Exercice 2 — Comité

On choisit un comité de 4 personnes parmi 12 dont au moins 2 femmes (7 femmes, 5 hommes).

Solution : On décompose par cas :

2F et 2H : $\binom{7}{2} \times \binom{5}{2} = 21 \times 10 = 210$
3F et 1H : $\binom{7}{3} \times \binom{5}{1} = 35 \times 5 = 175$
4F et 0H : $\binom{7}{4} = 35$

Total : $210 + 175 + 35 = 420$

Exercice 3 — Binôme de Newton

Développer $(2x - 3)^4$ .

Solution : $(2x - 3)^4 = \sum_{k=0}^{4} \binom{4}{k} (2x)^k (-3)^{4-k}$

$= 81 - 216x + 216x^2 - 96x^3 + 16x^4$

À retenir§

Les points clés

Principe multiplicatif : le réflexe n°1 en dénombrement
Avec ou sans ordre ? → arrangement ou combinaison
Avec ou sans remise ? → modifie les formules
Triangle de Pascal : $\binom{n}{p} = \binom{n-1}{p-1} + \binom{n-1}{p}$
Binôme de Newton : relie combinaisons et algèbre

Principes fondamentaux§

Principe additif§

Principe multiplicatif§

La factorielle§

Permutations§

Arrangements§

Combinaisons§

Valeurs utiles§

Propriétés essentielles§

Formule du binôme de Newton§

L’arbre de décision : quel outil utiliser ?§

Avec ou sans remise ?§

Exercices types§

À retenir§

Commentaires