Algèbre et géométrie

Combinatoire et dénombrement

Listes, arrangements, permutations, combinaisons et triangle de Pascal

Tout est gratuit et lisible sans compte. Crée ton compte gratuit pour garder ta progression.

Ce que tu dois savoir faire

Reconnaître le bon modèle : ordre ou pas, répétition ou pas
Dénombrer des $k$ -uplets ( $n^{k}$ ), des $k$ -uplets d'éléments distincts et des permutations ( $n!$ )
Calculer et interpréter un coefficient binomial $(k n)$
Utiliser les relations de symétrie et de Pascal, et construire le triangle de Pascal
Dénombrer « au moins un » en passant par le complémentaire

1. Principes de base : additionner ou multiplier

Dénombrer, c'est compter sans tout écrire. Deux principes suffisent à démarrer : on additionne quand on choisit entre des cas qui ne se recouvrent pas, on multiplie quand on enchaîne des choix successifs.

Définition — Cardinal

Le cardinal d'un ensemble fini $E$ , noté $card (E)$ , est son nombre d'éléments. Par exemple, $card ({A, C, G, T}) = 4$ : il y a quatre bases azotées dans l'ADN.

Propriété — Principe additif

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

card (A \cup B) = card (A) + card (B)

Plus généralement, le cardinal d'une réunion d'ensembles deux à deux disjoints est la somme des cardinaux.

Propriété — Principe multiplicatif (produit cartésien)

Le produit cartésien $A \times B$ est l'ensemble des couples $(a; b)$ avec $a \in A$ et $b \in B$ . Si $A$ et $B$ sont finis :

card (A \times B) = card (A) \times card (B)

De même, $card (A_{1} \times A_{2} \times \dots \times A_{k}) = card (A_{1}) \times \dots \times card (A_{k})$ .

Arbre de choix : 2 entrées puis 3 plats

Chaque branche de premier niveau porte le même nombre de sous-branches : le nombre de feuilles est le produit $2 \times 3 = 6$ .

Exemple — Un code génétique en miniature

Un codon est une suite de 3 bases prises dans ${A, C, G, T}$ (ou $U$ pour l'ARN), avec répétition possible. C'est un élément de $E \times E \times E$ avec $card (E) = 4$ : il y a $4 \times 4 \times 4 = 64$ codons. Avec seulement 2 bases par codon, on n'aurait que $16$ combinaisons, trop peu pour coder les $20$ acides aminés.

2. k-uplets et parties d’un ensemble

Définition — $k$ -uplet

Soit $E$ un ensemble à $n$ éléments et $k \geq 1$ un entier. Un $k$ -uplet (ou $k$ -liste) de $E$ est une suite ordonnée $(x_{1}, x_{2}, \dots, x_{k})$ d'éléments de $E$ , avec répétitions possibles. C'est un élément de $E^{k} = E \times \dots \times E$ .

À connaître

card (E^{k}) = n^{k}

Le nombre de $k$ -uplets d'un ensemble à $n$ éléments : $n$ choix pour chacune des $k$ positions.

Exemple — Codes et grilles

Un code de carte bancaire à 4 chiffres : $1 0^{4} = 10000$ codes.
Les réponses à un questionnaire de 12 questions « vrai / faux » : $2^{12} = 4096$ grilles possibles.

Propriété — Nombre de parties

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

Démonstration exigible — Démonstration : un ensemble à

n

éléments a

2^{n}

parties

Notons $E = {e_{1}, e_{2}, \dots, e_{n}}$ . À toute partie $A$ de $E$ , on associe le $n$ -uplet $(x_{1}, \dots, x_{n})$ de ${0, 1}^{n}$ défini par : $x_{i} = 1$ si $e_{i} \in A$ , et $x_{i} = 0$ sinon.

Deux parties différentes donnent deux $n$ -uplets différents (elles diffèrent par au moins un élément $e_{i}$ , donc par la coordonnée $x_{i}$ ).
Tout $n$ -uplet de $0$ et de $1$ provient d'une partie : celle des $e_{i}$ pour lesquels $x_{i} = 1$ .

On a donc une bijection entre l'ensemble des parties de $E$ et ${0, 1}^{n}$ . Ces deux ensembles ont le même cardinal, soit $2^{n}$ .

Piège fréquent

Dans un $k$ -uplet, l'ordre compte : $(1, 2)$ et $(2, 1)$ sont deux couples différents. Dans une partie, il ne compte pas : ${1, 2} = {2, 1}$ .

3. Arrangements et permutations

Définition — $k$ -uplets d'éléments distincts

Un $k$ -uplet d'éléments distincts (ou arrangement) de $E$ est un $k$ -uplet dont tous les termes sont différents : l'ordre compte, mais pas de répétition. Il faut $k \leq n$ .

Définition — Factorielle

Pour tout entier $n \geq 1$ , $n! = n \times (n - 1) \times \dots \times 2 \times 1$ (lire « factorielle $n$ »), et par convention $0! = 1$ .
Valeurs : $3! = 6$ , $4! = 24$ , $5! = 120$ , $6! = 720$ , $10! = 3628800$ .

Propriété — Les formules

Si $E$ a $n$ éléments et $1 \leq k \leq n$ :

nombre de $k$ -uplets d'éléments distincts : $n \times (n - 1) \times \dots \times (n - k + 1) = \frac{n !}{( n - k )!}$ (il y a $k$ facteurs) ;
une permutation de $E$ est un $n$ -uplet d'éléments distincts (on range tous les éléments) : il y en a $n!$ .

Exemple — Un podium

Huit nageurs disputent une finale. Un podium (or, argent, bronze) est un triplet de nageurs distincts, et l'ordre compte : $8 \times 7 \times 6 = 336$ podiums possibles.
Le nombre d'ordres d'arrivée complets est $8! = 40320$ .

Conseil bac

Pense « cases à remplir » : tu écris autant de cases que de positions, puis le nombre de choix possibles dans chacune. Si un élément ne peut pas resservir, le nombre de choix diminue d'une unité à chaque case.

4. Combinaisons et coefficients binomiaux

Définition — Combinaison

Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments : pas d'ordre, pas de répétition. Leur nombre se note $(k n)$ (lire « $k$ parmi $n$ »).

À connaître

(k n) = \frac{n !}{k ! ( n - k )!} = \frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !} (0 \leq k \leq n)

Avec $(0 n) = (n n) = 1$ et $(1 n) = n$ .

Démonstration exigible — Démonstration de l'expression de

(k n)

par les factorielles

Comptons de deux façons les $k$ -uplets d'éléments distincts de $E$ (avec $card (E) = n$ ).

Directement : il y en a $\frac{n !}{( n - k )!}$ .
En deux étapes : on choisit d'abord la partie formée des $k$ éléments ( $(k n)$ choix), puis l'ordre dans lequel on les range ( $k!$ permutations). Le principe multiplicatif donne $(k n) \times k!$ .

Donc $(k n) \times k! = \frac{n !}{( n - k )!}$ , d'où $(k n) = \frac{n !}{k ! ( n - k )!}$ .

Propriété — Symétrie et relation de Pascal

Pour $0 \leq k \leq n$ : $(k n) = (n - k n)$ .
Pour $1 \leq k \leq n - 1$ :

(k - 1 n - 1) + (k n - 1) = (k n)

Démonstration exigible — Démonstration de la symétrie et de la relation de Pascal

Symétrie. Choisir les $k$ éléments qu'on garde revient à choisir les $n - k$ qu'on laisse : l'application $A \mapsto \overline{A}$ (complémentaire) est une bijection entre parties à $k$ éléments et parties à $n - k$ éléments. (Par le calcul : $\frac{n !}{( n - k )! k !}$ est inchangé quand on échange $k$ et $n - k$ .)

Pascal (par dénombrement). Fixons un élément $a$ de $E$ . Les parties de $E$ à $k$ éléments se répartissent en deux groupes disjoints :

celles qui contiennent $a$ : on complète $a$ par $k - 1$ éléments pris parmi les $n - 1$ autres, soit $(k - 1 n - 1)$ parties ;
celles qui ne contiennent pas $a$ : on prend les $k$ éléments parmi les $n - 1$ autres, soit $(k n - 1)$ parties.

Par le principe additif, $(k n) = (k - 1 n - 1) + (k n - 1)$ .

Triangle de Pascal : chaque case est la somme de celle du dessus et de sa voisine de gauche

$n \ k$	$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$

Propriété — Somme d’une ligne

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

En effet, on compte toutes les parties de $E$ en les classant selon leur nombre d'éléments $k$ .

Les coefficients $(k 10)$ pour $k$ de $0$ à $10$ : la symétrie $(k 10) = (10 - k 10)$ se voit, et le maximum est $(5 10) = 252$ . Leur somme vaut $2^{10} = 1024$ .

5. Choisir le bon modèle

Méthode — Deux questions à se poser

L'ordre compte-t-il ? (un podium, un code, un mot : oui ; une main de cartes, un groupe, un prélèvement simultané : non)
Peut-on répéter un élément ? (un code : oui ; des personnes différentes : non)

Puis on lit le tableau ci-dessous.

Récapitulatif (ensemble à n éléments, on en prend k)

Situation	Ordre	Répétition	Nombre
$k$ -uplet (code, mot)	oui	oui	$n^{k}$
$k$ -uplet d'éléments distincts (podium)	oui	non	$\frac{n !}{( n - k )!}$
Permutation (classement complet)	oui	non	$n!$
Combinaison (groupe, main)	non	non	$(k n)$

Méthode — « Au moins un » : passer par le complémentaire

Compter directement « au moins un » oblige à distinguer « exactement 1 », « exactement 2 »… Il est plus rapide de compter tout, puis de retirer les cas où il n'y en a aucun :

(au moins un) = (total) - (aucun)

Exemple — Un comité

Dans un service de 10 soignants, on forme un comité de 3 personnes dont un président. On choisit le président ( $10$ choix), puis les 2 autres membres parmi les 9 restants, sans ordre : $10 \times (2 9) = 10 \times 36 = 360$ comités.

En Python, le module math fournit directement ces nombres :

from math import comb, perm, factorial
print(comb(10, 3))     # 120 : combinaisons de 3 parmi 10
print(perm(8, 3))      # 336 : 3-uplets d'éléments distincts parmi 8
print(factorial(5))    # 120 : permutations de 5 éléments

Piège fréquent

Un tirage simultané (on prend 5 cartes d'un coup) se compte avec $(k n)$ . Un tirage successif sans remise où l'on note l'ordre se compte avec $\frac{n !}{( n - k )!}$ . Ne mélange pas les deux dans un même calcul.

L’essentiel à retenir

On additionne pour des cas disjoints, on multiplie pour des choix successifs.
$k$ -uplets d'un ensemble à $n$ éléments (ordre, répétition) : $n^{k}$ .
$k$ -uplets d'éléments distincts (ordre, sans répétition) : $\frac{n !}{( n - k )!}$ ; permutations : $n!$ .
Combinaisons (sans ordre, sans répétition) : $(k n) = \frac{n !}{k ! ( n - k )!}$ .
Un ensemble à $n$ éléments a $2^{n}$ parties, et $\sum_{k = 0}^{n} (k n) = 2^{n}$ .
Symétrie : $(k n) = (n - k n)$ ; Pascal : $(k - 1 n - 1) + (k n - 1) = (k n)$ .
« Au moins un » = total $-$ « aucun ».
$0! = 1$ , $(0 n) = 1$ , $(1 n) = n$ .

Et pour t’entraîner : 10 QCM corrigés et 4 exercices type bac, avec indices et corrections rédigées.