Combinatoire & Dénombrement – Fiche de cours Terminale

Sommaire

Partie 1 — Dénombrer un ensemble fini
Partie 2 — Produit cartésien & principe multiplicatif
Partie 3 — Arrangements et permutations
Partie 4 — Combinaisons et triangle de Pascal

Cardinal · principe additif · formule du crible · diagrammes
p-uplets · $n^p$ · nombre de parties $2^n$
Factorielle · arrangements $\frac{n!}{(n-p)!}$ · permutations $n!$
Coefficients binomiaux · symétrie · relation de Pascal

Un peu d'histoire

Le triangle qui porte le nom de Blaise Pascal (1623–1662) était en réalité déjà connu bien avant lui : on le trouve chez les mathématiciens persans, indiens, et chez le Chinois Zhu Shijie dès le XIV^e siècle. Pascal en fit une étude systématique dans son Traité du triangle arithmétique, motivé par les problèmes de jeux de hasard et de paris — à l'origine, avec Fermat, du calcul des probabilités.

Objectifs du chapitre

Déterminer le cardinal d'un ensemble fini à l'aide des principes additif et multiplicatif.
Reconnaître une situation de p-uplet, d'arrangement, de permutation ou de combinaison.
Distinguer les cas selon que l'ordre compte ou non, avec ou sans répétition.
Calculer et manipuler les coefficients binomiaux $\binom{n}{p}$ .
Connaître la symétrie, la relation de Pascal et le triangle de Pascal.
Démontrer que le nombre de parties d'un ensemble à $n$ éléments est $2^n$ .

1 Dénombrer un ensemble fini

Définition — Cardinal

Un ensemble $E$ est fini s'il possède un nombre fini d'éléments. Ce nombre est le cardinal de $E$ , noté $\operatorname{Card}(E)$ ou $|E|$ . Par convention, $\operatorname{Card}(\varnothing) = 0$ . Dénombrer, c'est déterminer le cardinal d'un ensemble.

1.1 Le principe additif

Définition — Ensembles disjoints

Deux ensembles sont disjoints lorsqu'ils n'ont aucun élément commun : $A \cap B = \varnothing$ .

Propriété — Principe additif

Si $E_1, E_2, \dots, E_n$ sont des ensembles finis deux à deux disjoints, alors :

\operatorname{Card}(E_1 \cup E_2 \cup \dots \cup E_n) = \operatorname{Card}(E_1) + \operatorname{Card}(E_2) + \dots + \operatorname{Card}(E_n).

Propriété — Complémentaire et formule du crible

Si $A$ est une partie de $E$ , son complémentaire $\overline{A}$ vérifie :

\operatorname{Card}(\overline{A}) = \operatorname{Card}(E) - \operatorname{Card}(A).

Pour deux ensembles quelconques (pas forcément disjoints) :

\operatorname{Card}(A \cup B) = \operatorname{Card}(A) + \operatorname{Card}(B) - \operatorname{Card}(A \cap B).

Pour trois ensembles :

\operatorname{Card}(A \cup B \cup C) = \operatorname{Card}(A)+\operatorname{Card}(B)+\operatorname{Card}(C) - \operatorname{Card}(A\cap B) - \operatorname{Card}(A\cap C) - \operatorname{Card}(B\cap C) + \operatorname{Card}(A\cap B\cap C).

Exemple — Dénombrer avec un diagramme

Dans une classe, $16$ élèves font du latin ( $L$ ), $14$ du théâtre ( $T$ ), $5$ font les deux et $8$ n'en font aucun.

Élèves faisant seulement latin : $16 - 5 = 11$ ; seulement théâtre : $14 - 5 = 9$ ; les deux : $5$ ; aucun : $8$ .

\text{Effectif} = 11 + 5 + 9 + 8 = 33 \text{ élèves.}

On retrouve $\operatorname{Card}(L \cup T) = 16 + 14 - 5 = 25$ , puis $25 + 8 = 33$ .

2 Produit cartésien & principe multiplicatif

2.1 Produit cartésien et p-uplets

Définition — Produit cartésien, p-uplets

Soit $E_1, E_2, \dots, E_p$ des ensembles finis.

$E_1 \times E_2$ est l'ensemble des couples $(a_1, a_2)$ avec $a_1 \in E_1$ et $a_2 \in E_2$ .
$E_1 \times E_2 \times E_3$ est l'ensemble des triplets $(a_1, a_2, a_3)$ .
Plus généralement, $E_1 \times \dots \times E_p$ est l'ensemble des p-uplets $(a_1, \dots, a_p)$ .

Lorsqu'on multiplie un ensemble $E$ par lui-même $p$ fois, on note $E^p = E \times E \times \dots \times E$ .

Propriété — Principe multiplicatif

Pour des ensembles finis $E_1, \dots, E_p$ :

\operatorname{Card}(E_1 \times E_2 \times \dots \times E_p) = \operatorname{Card}(E_1) \times \operatorname{Card}(E_2) \times \dots \times \operatorname{Card}(E_p).

En particulier, si $E$ possède $n$ éléments :

\boxed{\;\operatorname{Card}(E^p) = n^p\;}

Exemple — Un menu de restaurant

Une carte propose $3$ entrées, $4$ plats et $2$ desserts. Le nombre de menus (entrée + plat + dessert) est :

3 \times 4 \times 2 = 24 \text{ menus.}

Si le dessert est imposé, il n'en reste que $3 \times 4 = 12$ .

Exemple — Un p-uplet (avec répétition, ordre compte)

Un digicode est formé de $2$ lettres puis $10$ chiffres. Il y a $26$ lettres et $10$ chiffres, chacun pouvant se répéter :

26^2 \times 10^{10} = 676 \times 10^{10} \approx 6{,}76 \times 10^{12} \text{ possibilités.}

2.2 Nombre de parties d'un ensemble

Propriété — Nombre de sous-ensembles

Le nombre de parties (sous-ensembles) d'un ensemble $E$ à $n$ éléments est :

\boxed{\;2^n\;}

Démonstration (exigible)

Pour construire une partie de $E$ , on parcourt les $n$ éléments un par un : pour chacun, deux choix — le prendre ou ne pas le prendre. On effectue donc $n$ choix binaires indépendants. Par le principe multiplicatif :

\underbrace{2 \times 2 \times \dots \times 2}_{n \text{ facteurs}} = 2^n.

Exemple

Pour $E = \{1, 2, 3\}$ , les parties sont $\varnothing,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\},\ \{1,3\},\ \{2,3\},\ \{1,2,3\}$ : il y en a bien $2^3 = 8$ .

3 Arrangements et permutations

3.1 La factorielle

Définition — Factorielle

Pour $n \in \mathbb{N}^*$ , la factorielle de $n$ est le produit de tous les entiers de $1$ à $n$ :

n! = 1 \times 2 \times 3 \times \dots \times n, \qquad \text{avec par convention } 0! = 1.

Par exemple $5! = 120$ et $10! = 3\,628\,800$ .

3.2 Arrangements

Définition — Arrangement

Soit $E$ un ensemble à $n$ éléments et $p \leqslant n$ . Un arrangement de $p$ éléments de $E$ est un p-uplet d'éléments distincts de $E$ : l'ordre compte et il n'y a pas de répétition.

Propriété — Nombre d'arrangements

Le nombre d'arrangements de $p$ éléments parmi $n$ , noté $A_n^p$ , vaut :

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

Intuition : $n$ choix pour la 1^re place, $n-1$ pour la 2^e (un élément déjà pris), etc., jusqu'à $n-p+1$ pour la $p$ -ième.

Exemple — Un podium

Combien de podiums (or, argent, bronze) avec $12$ athlètes ? L'ordre compte, sans répétition :

A_{12}^{3} = \frac{12!}{9!} = 12 \times 11 \times 10 = 1\,320.

3.3 Permutations

Définition — Permutation

Une permutation de $E$ (à $n$ éléments) est un arrangement des $n$ éléments : une façon d'ordonner tous les éléments de $E$ .

Propriété — Nombre de permutations

\text{Nombre de permutations de } E = A_n^n = n!.

Exemple

$3$ personnes sur un banc à $3$ places : $3! = 6$ dispositions possibles. $12$ scientifiques sur un rang : $12! = 479\,001\,600$ façons.

4 Combinaisons et triangle de Pascal

4.1 Combinaisons et coefficients binomiaux

Définition — Combinaison

Soit $E$ un ensemble à $n$ éléments et $p \leqslant n$ . Une combinaison de $p$ éléments de $E$ est un sous-ensemble à $p$ éléments : l'ordre ne compte pas et il n'y a pas de répétition. Ainsi $\{1,2\}$ et $\{2,1\}$ sont la même combinaison.

Propriété — Coefficient binomial

Le nombre de combinaisons de $p$ éléments parmi $n$ se note $\binom{n}{p}$ (« $p$ parmi $n$ ») et vaut :

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

On divise le nombre d'arrangements par $p!$ car chaque sous-ensemble de $p$ éléments donne $p!$ arrangements (ses ordres possibles).

Cas particuliers

\binom{n}{0} = 1, \qquad \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{n-1} = n.

Exemple — Une élection de délégués

Dans une classe de $34$ élèves, on élit $4$ délégués (sans distinction de rôle). L'ordre ne compte pas :

\binom{34}{4} = \frac{34!}{4!\,30!} = \frac{31 \times 32 \times 33 \times 34}{1 \times 2 \times 3 \times 4} = 46\,376.

4.2 Quel outil choisir ?

Trois questions suffisent : l'ordre compte-t-il ? Les répétitions sont-elles permises ?

	Avec répétition	Sans répétition
L'ordre compte	p-uplets $n^p$	Arrangements $A_n^p = \dfrac{n!}{(n-p)!}$
L'ordre ne compte pas	(hors programme)	Combinaisons $\dbinom{n}{p} = \dfrac{n!}{p!\,(n-p)!}$

4.3 Symétrie et relation de Pascal

Propriété — Symétrie

Pour tout $p$ tel que $0 \leqslant p \leqslant n$ :

\binom{n}{n-p} = \binom{n}{p}.

Choisir les $p$ éléments présents ou les $n-p$ éléments absents revient au même.

Propriété — Relation de Pascal

Pour $0 \leqslant p \lt n$ :

\binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}.

Démonstration par le calcul (exigible)

\binom{n}{p} + \binom{n}{p+1} = \frac{n!}{p!\,(n-p)!} + \frac{n!}{(p+1)!\,(n-p-1)!}.

On met au même dénominateur en factorisant $\dfrac{n!}{p!\,(n-p-1)!}$ :

= \frac{n!}{p!\,(n-p-1)!}\left(\frac{1}{n-p} + \frac{1}{p+1}\right) = \frac{n!}{p!\,(n-p-1)!}\cdot\frac{(p+1)+(n-p)}{(n-p)(p+1)}.

Or $(p+1) + (n-p) = n+1$ , donc :

= \frac{n!\,(n+1)}{p!\,(p+1)\,(n-p-1)!\,(n-p)} = \frac{(n+1)!}{(p+1)!\,(n-p)!} = \binom{n+1}{p+1}.

Exemple — Calcul par la relation de Pascal

\binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3 = 6, \qquad \binom{25}{24} = \binom{25}{1} = 25.

4.4 Le triangle de Pascal

Chaque coefficient s'obtient en additionnant les deux qui sont juste au-dessus de lui (relation de Pascal).

$p$ $n$	0	1	2	3	4	5	6
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

Lecture : $\binom{4}{1} + \binom{4}{2} = 4 + 6 = 10 = \binom{5}{2}$ (relation de Pascal).

4.5 Somme des coefficients : retour aux parties

Propriété — Somme d'une ligne du triangle

\sum_{p=0}^{n} \binom{n}{p} = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n.

Chaque partie de $E$ a un nombre d'éléments compris entre $0$ et $n$ : la somme des $\binom{n}{p}$ compte toutes les parties, soit $2^n$ .

À retenir

Comptage de base

Additif (disjoints) : on somme les cardinaux.
Crible : $\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B)$ .
Multiplicatif : $\operatorname{Card}(E^p)=n^p$ ; parties $=2^n$ .

Les trois modèles

p-uplets (ordre + répétition) : $n^p$ .
Arrangements (ordre, sans rép.) : $\frac{n!}{(n-p)!}$ .
Combinaisons (sans ordre) : $\binom{n}{p}$ .

Binomiaux

Symétrie : $\binom{n}{n-p}=\binom{n}{p}$ .
Pascal : $\binom{n}{p}+\binom{n}{p+1}=\binom{n+1}{p+1}$ .
Somme d'une ligne : $\sum_p \binom{n}{p}=2^n$ .