Comment savoir s'il faut utiliser un k-uplet, un arrangement ou une combinaison ?

On se demande si l'ordre compte et si les répétitions sont possibles. Ordre et répétitions : k-uplets, $n^k$. Ordre sans répétition : k-uplets d'éléments distincts, $n(n-1)\cdots(n-k+1)$. Sans ordre ni répétition (on choisit une partie) : combinaisons, $\binom{n}{k}$.

Pourquoi un ensemble à $n$ éléments a-t-il $2^n$ parties ?

Pour construire une partie, on décide pour chaque élément s'il est pris (1) ou non (0). Une partie correspond donc à un mot de longueur $n$ sur $\{0,1\}$, et il y a $2^n$ tels mots par le principe multiplicatif.

Comment retenir la relation de Pascal ?

Pour choisir $k$ éléments parmi $n+1$, on regarde un élément fixé $a$ : soit on le prend et on complète par $k-1$ éléments parmi les $n$ autres ($\binom{n}{k-1}$ choix), soit on ne le prend pas et on choisit $k$ éléments parmi les $n$ autres ($\binom{n}{k}$ choix). D'où $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$.

Dénombrement, combinatoire

Définitions

Définition 1 — produit cartésien, couple, k-uplet. Le produit cartésien $A \times B$ est l’ensemble des couples $(a, b)$ avec $a \in A$ et $b \in B$ . Plus généralement, un $k$ -uplet (ou $k$ -liste) de $A$ est une suite ordonnée $(a_1, \ldots, a_k)$ d’éléments de $A$ , avec répétitions possibles ; leur ensemble est noté $A^k$ .

Définition 2 — factorielle. Pour $n \geq 1$ , $n! = n \times (n-1) \times \cdots \times 2 \times 1$ , et par convention $0! = 1$ . Valeurs : $3! = 6$ , $4! = 24$ , $5! = 120$ , $6! = 720$ .

Définition 3 — permutation. Une permutation d’un ensemble à $n$ éléments est un $n$ -uplet de ses éléments tous distincts (un ordre total sur l’ensemble).

Définition 4 — combinaison. Une combinaison de $k$ éléments d’un ensemble $E$ à $n$ éléments est une partie de $E$ à $k$ éléments : l’ordre n’intervient pas. Leur nombre se note $\binom{n}{k}$ (« $k$ parmi $n$ »).

Théorèmes et propriétés

Théorème 1 (principe additif). Si $A_1, \ldots, A_p$ sont des ensembles finis deux à deux disjoints, alors $\text{Card}(A_1 \cup \cdots \cup A_p) = \text{Card}(A_1) + \cdots + \text{Card}(A_p).$ C’est le dénombrement par cas.

Théorème 2 (principe multiplicatif). $\text{Card}(A \times B) = \text{Card}(A) \times \text{Card}(B)$ , et plus généralement $\text{Card}(A_1 \times \cdots \times A_k) = \text{Card}(A_1) \times \cdots \times \text{Card}(A_k)$ : des choix successifs se multiplient.

Théorème 3 (nombre de k-uplets). Si $\text{Card}(A) = n$ , alors $\text{Card}(A^k) = n^k$ .

Théorème 4 (nombre de parties d’un ensemble). Un ensemble à $n$ éléments possède $2^n$ parties (y compris $\varnothing$ et l’ensemble lui-même). Une partie correspond, par bijection, à un $n$ -uplet de $\{0, 1\}$ (1 si l’élément est pris), donc aussi à un mot de longueur $n$ sur un alphabet à deux lettres, à un chemin dans un arbre binaire de profondeur $n$ , à une issue d’une succession de $n$ épreuves de Bernoulli.

Théorème 5 (k-uplets d’éléments distincts). Le nombre de $k$ -uplets d’éléments distincts d’un ensemble à $n$ éléments ( $k \leq n$ ) est $n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}.$

Théorème 6 (nombre de permutations). Un ensemble à $n$ éléments admet $n!$ permutations.

Théorème 7 (formules des combinaisons). Pour $0 \leq k \leq n$ : $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!\,(n-k)!}.$

Théorème 8 (valeurs particulières et symétrie). $\binom{n}{0} = \binom{n}{n} = 1$ , $\binom{n}{1} = n$ , $\binom{n}{2} = \dfrac{n(n-1)}{2}$ , et pour $0 \leq k \leq n$ : $\binom{n}{k} = \binom{n}{n-k}$ (choisir les $k$ éléments pris revient à choisir les $n-k$ éléments laissés).

Théorème 9 (relation de Pascal). (démonstrations exigibles : par le calcul et par une méthode combinatoire) Pour $1 \leq k \leq n$ : $\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}.$ Idée combinatoire : on fixe un élément $a$ ; les parties à $k$ éléments contenant $a$ sont $\binom{n}{k-1}$ , celles ne le contenant pas sont $\binom{n}{k}$ , et le principe additif conclut.

Théorème 10 (somme d’une ligne du triangle de Pascal). (démonstration exigible, par dénombrement) $\sum_{k=0}^{n} \binom{n}{k} = 2^n.$ Les $2^n$ parties d’un ensemble à $n$ éléments se répartissent selon leur cardinal $k$ ; il y a $\binom{n}{k}$ parties à $k$ éléments.

Tableau des formules de dénombrement (ensemble à $n$ éléments) :

Objet	Ordre	Répétitions	Nombre	Référence
$k$ -uplet	oui	oui	$n^k$	Théorème 3
$k$ -uplet d’éléments distincts	oui	non	$\dfrac{n!}{(n-k)!}$	Théorème 5
permutation ( $k = n$ )	oui	non	$n!$	Théorème 6
combinaison (partie à $k$ éléments)	non	non	$\dbinom{n}{k}$	Théorème 7

Méthodes

Méthode 1 — choisir le bon modèle de dénombrement.

L’ordre des éléments compte-t-il ?
Les répétitions sont-elles permises ?
Conclure avec le tableau : ordre et répétitions $\to n^k$ (Théorème 3) ; ordre sans répétition $\to \dfrac{n!}{(n-k)!}$ (Théorème 5) ; tous les éléments ordonnés $\to n!$ (Théorème 6) ; sans ordre ni répétition $\to \dbinom{n}{k}$ (Théorème 7).

Exemple : un podium (or, argent, bronze) parmi 8 coureurs : ordre, sans répétition, $8 \times 7 \times 6 = 336$ .

Méthode 2 — dénombrer avec contraintes (cas disjoints et choix successifs).

Découper l’ensemble à dénombrer en cas deux à deux disjoints (Théorème 1).
Dans chaque cas, décomposer en choix successifs et multiplier (Théorème 2).
Additionner les résultats des cas.

Exemple : tirages simultanés de 3 boules parmi 5 rouges et 4 bleues avec exactement 2 rouges : $\binom{5}{2} \times \binom{4}{1} = 40$ .

Méthode 3 — calculer un coefficient binomial.

Si $k$ est proche de $n$ , appliquer la symétrie $\binom{n}{k} = \binom{n}{n-k}$ (Théorème 8).
Calculer avec $\binom{n}{k} = \dfrac{n(n-1)\cdots(n-k+1)}{k!}$ (Théorème 7), ou de proche en proche par la relation de Pascal (Théorème 9).

Exemple : $\binom{10}{8} = \binom{10}{2} = \dfrac{10 \times 9}{2} = 45$ .

Méthode 4 — dénombrer les parties par codage binaire.

Associer à chaque partie le mot de longueur $n$ sur $\{0, 1\}$ qui indique les éléments pris.
Compter les mots : $2^n$ en tout (Théorème 4) ; $\binom{n}{k}$ mots contenant exactement $k$ fois le chiffre 1 (Théorème 7).

Exemple : un ensemble à 6 éléments a $2^6 = 64$ parties, dont $\binom{6}{2} = 15$ parties à 2 éléments.

À retenir contre les pièges. Un couple $(a, b)$ est ordonné, une paire $\{a, b\}$ ne l’est pas (10 joueurs : $\binom{10}{2} = 45$ matchs, pas $90$ ). Un ensemble à $n$ éléments a $2^n$ parties, ensemble vide compris. On multiplie des choix successifs, on additionne des cas disjoints.

Définitions

Théorèmes et propriétés

Méthodes

Reste informé