Mathématiques — Terminale

Combinatoire et dénombrement — Maths Terminale (chapitre 1)

Cours complet de combinatoire en Terminale spécialité maths : k-uplets, permutations, combinaisons, coefficients binomiaux, triangle et relation de Pascal,…

Par ProfBot

Combinatoire et dénombrement

Chapitre 1 — Algèbre et géométrie · Terminale, spécialité mathématiques

Dénombrer, c'est compter sans énumérer. Une grille de Loto, c'est 5 numéros choisis parmi 49, plus un numéro chance parmi 10 : cela fait 19 068 840 grilles possibles. Personne ne les listera une par une — il faut une méthode qui donne le nombre sans écrire la liste. Ce chapitre construit cette méthode, et il sert de fondation à tout le programme de probabilités : la loi binomiale du chapitre 13 repose entièrement sur le coefficient $\binom{n}{k}$ défini ici.

Au programme officiel. Principes additif et multiplicatif ; nombre de $k$-uplets ; nombre de parties d'un ensemble à $n$ éléments ; permutations ; combinaisons et coefficients binomiaux ; triangle de Pascal.

Deux démonstrations sont exigibles au sens du programme : celle de la relation $\sum_{k=0}^{n} \binom{n}{k} = 2^n$ par dénombrement, et celle de la relation de Pascal (par le calcul et par une méthode combinatoire). Elles sont toutes les deux rédigées ci-dessous, signalées par la mention Démonstration exigible.

1. Le vocabulaire des ensembles

Avant de compter, il faut nommer précisément ce que l'on compte.

Cardinal. Un ensemble $E$ est dit fini s'il possède un nombre fini d'éléments. Ce nombre s'appelle le cardinal de $E$ et se note $\operatorname{Card}(E)$, ou parfois $|E|$.

Couple, triplet, $k$-uplet. Un $k$-uplet (ou $k$-liste) d'éléments de $E$ est une liste ordonnée de $k$ éléments de $E$, notée $(x_1, x_2, \dots, x_k)$. Deux points sont essentiels :

• l'ordre compte : $(a, b)$ et $(b, a)$ sont deux couples différents ;
• les répétitions sont permises : $(a, a)$ est un couple parfaitement légitime.

Pour $k = 2$ on dit couple, pour $k = 3$ triplet.

Produit cartésien. Le produit cartésien $A \times B$ est l'ensemble de tous les couples $(a, b)$ avec $a \in A$ et $b \in B$. L'ensemble des $k$-uplets d'éléments de $E$ se note $E^k$.

Partie d'un ensemble. Une partie (ou sous-ensemble) de $E$ est un ensemble dont tous les éléments appartiennent à $E$. Ici, au contraire du $k$-uplet, l'ordre ne compte pas et il n'y a pas de répétition : $\{a, b\}$ et $\{b, a\}$ désignent la même partie, et $\{a, a\}$ n'a pas de sens — c'est $\{a\}$.

La distinction à ne jamais perdre de vue. $(a,b)$ avec des parenthèses : une liste, l'ordre compte. $\{a,b\}$ avec des accolades : un ensemble, l'ordre ne compte pas. Toute la suite du chapitre n'est que l'exploitation de cette différence.

2. Les deux principes du dénombrement

Tout le chapitre repose sur deux règles, que l'on peut énoncer en une phrase chacune.

Principe additif. Si $A$ et $B$ sont deux ensembles finis disjoints (c'est-à-dire $A \cap B = \varnothing$), alors $\operatorname{Card}(A \cup B) = \operatorname{Card}(A) + \operatorname{Card}(B).$

Autrement dit : quand les cas s'excluent, on additionne. L'hypothèse « disjoints » est indispensable — sans elle, les éléments communs seraient comptés deux fois.

Principe multiplicatif. Si $A$ et $B$ sont deux ensembles finis, alors $\operatorname{Card}(A \times B) = \operatorname{Card}(A) \times \operatorname{Card}(B).$

Plus généralement, si l'on construit un objet par une suite de $k$ choix successifs, le premier offrant $n_1$ possibilités, le deuxième $n_2$, …, le $k$-ième $n_k$, et si le nombre de possibilités à chaque étape ne dépend pas des choix précédents, alors le nombre total d'objets construits est $n_1 \times n_2 \times \cdots \times n_k.$

Cette dernière condition est celle que l'on oublie le plus souvent. Elle est vérifiée dans tous les exemples ci-dessous, mais il faut prendre l'habitude de se la poser.

L'arbre rend visible le principe multiplicatif : chaque branche du premier niveau se ramifie en trois, d'où $3 \times 3$ feuilles.

3. Compter des listes : les $k$-uplets

Propriété. Soit $E$ un ensemble à $n$ éléments et $k$ un entier naturel. Le nombre de $k$-uplets d'éléments de $E$ est $\operatorname{Card}(E^k) = n^k.$

Justification. Construire un $k$-uplet, c'est choisir successivement $x_1$, puis $x_2$, …, puis $x_k$. À chaque étape, les $n$ éléments de $E$ sont disponibles — les répétitions étant permises, le choix précédent ne retire rien. Le principe multiplicatif donne $\underbrace{n \times n \times \cdots \times n}_{k \text{ facteurs}} = n^k$. $\blacksquare$

Exemple. Un code d'immeuble comporte 4 caractères, chacun étant un chiffre de 0 à 9. Il y a $10^4 = 10\,000$ codes possibles.

Application importante : le nombre de parties.

Propriété. Un ensemble à $n$ éléments possède exactement $2^n$ parties.

Justification. Se donner une partie $A$ de $E$, c'est décider pour chacun des $n$ éléments de $E$ s'il appartient à $A$ ou non : deux possibilités par élément, indépendamment des autres. On construit ainsi un $n$-uplet de « oui / non », et il y en a $2^n$. Cette correspondance est bijective : deux décisions différentes donnent deux parties différentes, et toute partie provient d'une décision. $\blacksquare$

Pour $n = 3$ : $2^3 = 8$ parties, l'ensemble vide et l'ensemble entier compris.

4. Compter des listes sans répétition

On s'interdit maintenant de réutiliser un élément déjà choisi.

Propriété. Soit $E$ un ensemble à $n$ éléments et $k$ un entier tel que $0 \leqslant k \leqslant n$. Le nombre de $k$-uplets d'éléments deux à deux distincts de $E$ est $n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}.$

Justification. Pour $x_1$, les $n$ éléments sont disponibles. Pour $x_2$, l'élément déjà utilisé est exclu : il reste $n-1$ possibilités, et ce nombre ne dépend pas de l'élément choisi en premier — la condition du principe multiplicatif est bien remplie. En continuant, le $k$-ième choix offre $n - (k-1) = n-k+1$ possibilités. Le produit compte exactement $k$ facteurs, du plus grand $n$ au plus petit $n-k+1$. $\blacksquare$

Rappel de notation. Pour $n \in \mathbb{N}^*$, $n! = 1 \times 2 \times \cdots \times n$, et par convention $0! = 1$. Cette convention n'est pas un caprice : elle rend les formules ci-dessous valables jusqu'aux cas extrêmes $k = 0$ et $k = n$.

Exemple. Dans une course de 8 chevaux, un tiercé dans l'ordre est un 3-uplet d'éléments distincts : il y a $8 \times 7 \times 6 = 336$ tiercés possibles.

5. Les permutations

Définition. Une permutation d'un ensemble $E$ à $n$ éléments est un $n$-uplet d'éléments deux à deux distincts de $E$ : c'est un rangement de tous les éléments de $E$ dans un certain ordre.

Propriété. Le nombre de permutations d'un ensemble à $n$ éléments est $n!$.

Justification. C'est le cas $k = n$ de la propriété précédente : $\dfrac{n!}{(n-n)!} = \dfrac{n!}{0!} = n!$. $\blacksquare$

Exemple. Le nombre de façons de ranger 5 livres distincts sur une étagère est $5! = 120$.

6. Les combinaisons

On abandonne enfin l'ordre.

Définition. Soit $E$ un ensemble à $n$ éléments et $k$ un entier tel que $0 \leqslant k \leqslant n$. Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments. Leur nombre se note $\binom{n}{k}$, qui se lit « $k$ parmi $n$ » et s'appelle un coefficient binomial.

Théorème. Pour $0 \leqslant k \leqslant n$, $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.$

Justification. Comptons de deux façons les $k$-uplets d'éléments distincts de $E$ : il y en a $\dfrac{n!}{(n-k)!}$ d'après la partie 4. Mais on peut aussi les construire en deux temps : choisir d'abord quels $k$ éléments on retient — c'est une partie à $k$ éléments, il y a $\binom{n}{k}$ possibilités — puis les ordonner, ce qui offre $k!$ rangements. Chaque $k$-uplet d'éléments distincts est obtenu ainsi une fois et une seule, donc $\binom{n}{k} \times k! = \frac{n!}{(n-k)!},$ d'où le résultat en divisant par $k! \neq 0$. $\blacksquare$

Valeurs à connaître par cœur. $\binom{n}{0} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{n} = 1, \qquad \binom{n}{n-1} = n.$

Symétrie. Pour $0 \leqslant k \leqslant n$, $\binom{n}{k} = \binom{n}{n-k}.$

Justification. Choisir les $k$ éléments que l'on garde revient exactement à choisir les $n-k$ éléments que l'on écarte. La formule factorielle le confirme, puisque l'échange de $k$ et $n-k$ laisse $k!\,(n-k)!$ inchangé. $\blacksquare$

Cette symétrie est un outil de calcul : pour obtenir $\binom{20}{18}$, on calcule $\binom{20}{2} = 190$, ce qui est bien plus rapide.

Exemple. Au Loto, on choisit 5 numéros parmi 49, sans ordre et sans répétition : il y a $\binom{49}{5} = 1\,906\,884$ tirages possibles pour les cinq numéros principaux. Le numéro chance, choisi séparément parmi 10, se combine à ce choix par le principe multiplicatif : $1\,906\,884 \times 10 = 19\,068\,840$ grilles — le nombre annoncé en introduction.

7. Le triangle de Pascal

7.1 La somme des coefficients binomiaux

Démonstration exigible. Pour tout entier naturel $n$,

$\sum_{k=0}^{n} \binom{n}{k} = 2^n.$

Démonstration (par dénombrement). Soit $E$ un ensemble à $n$ éléments. Comptons ses parties de deux manières.

D'une part, on a établi en partie 3 que $E$ possède $2^n$ parties.

D'autre part, classons ces parties selon leur nombre d'éléments. Pour chaque entier $k$ compris entre $0$ et $n$, il y a par définition $\binom{n}{k}$ parties à $k$ éléments. Ces catégories sont deux à deux disjointes — une partie a un nombre d'éléments et un seul — et leur réunion est l'ensemble de toutes les parties. Le principe additif donne donc un total de $\sum_{k=0}^{n} \binom{n}{k}$ parties.

Les deux comptages portant sur le même ensemble, ils coïncident : $\sum_{k=0}^{n} \binom{n}{k} = 2^n. \qquad \blacksquare$

Vérification pour $n = 4$ : $1 + 4 + 6 + 4 + 1 = 16 = 2^4$. ✓

7.2 La relation de Pascal

Démonstration exigible. Pour tous entiers $n$ et $k$ tels que $1 \leqslant k \leqslant n-1$,

$\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k}.$

Première démonstration (méthode combinatoire). Soit $E$ un ensemble à $n$ éléments et fixons un élément particulier $a$ de $E$. Répartissons les parties de $E$ à $k$ éléments en deux catégories, selon qu'elles contiennent $a$ ou non.

• Celles qui contiennent $a$ : il reste à choisir les $k-1$ autres éléments parmi les $n-1$ éléments de $E$ privé de $a$, soit $\binom{n-1}{k-1}$ parties.
• Celles qui ne contiennent pas $a$ : leurs $k$ éléments sont tous pris parmi les $n-1$ éléments restants, soit $\binom{n-1}{k}$ parties.

Ces deux catégories sont disjointes et leur réunion forme toutes les parties à $k$ éléments, dont le nombre est $\binom{n}{k}$. Le principe additif conclut. $\blacksquare$

Seconde démonstration (par le calcul). En réduisant au même dénominateur $k!\,(n-k)!$ : $\binom{n-1}{k-1} = \frac{(n-1)!}{(k-1)!\,(n-k)!} = \frac{k \times (n-1)!}{k!\,(n-k)!},$ $\binom{n-1}{k} = \frac{(n-1)!}{k!\,(n-1-k)!} = \frac{(n-k) \times (n-1)!}{k!\,(n-k)!}.$ En ajoutant, le numérateur devient $(n-1)!\,\big(k + (n-k)\big) = n \times (n-1)! = n!$, donc $\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}. \qquad \blacksquare$

7.3 Le triangle

La relation de Pascal permet de construire tous les coefficients binomiaux de proche en proche, sans jamais calculer une seule factorielle : chaque nombre est la somme des deux situés juste au-dessus de lui.

Ligne $n$, colonne $k$ : la case contient $\binom{n}{k}$. Les flèches illustrent $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$, soit $4 + 6 = 10$.

On lit aussi sur la figure les deux propriétés démontrées plus haut : chaque ligne est symétrique, et la somme de la ligne $n$ vaut $2^n$ (ligne 4 : $1+4+6+4+1 = 16$).

8. Méthode : choisir le bon modèle

C'est le seul vrai obstacle du chapitre. Devant un énoncé, deux questions suffisent, dans cet ordre.

1. L'ordre compte-t-il ? Autrement dit : si j'échange deux éléments, est-ce que j'obtiens un résultat différent ?
2. Les répétitions sont-elles permises ? Puis-je reprendre un élément déjà utilisé ?

Les mots qui trahissent le modèle. « Un code », « un mot », « un classement », « dans l'ordre » : l'ordre compte. « Une main », « un comité », « un groupe », « une poignée », « choisir simultanément » : l'ordre ne compte pas.

Exemple traité. Une classe de 30 élèves doit élire un délégué et un suppléant, puis, séparément, désigner une équipe de 3 élèves pour un projet.

• Délégué et suppléant : les deux rôles sont distincts, donc l'ordre compte, et une même personne ne peut occuper les deux postes, donc pas de répétition. C'est un 2-uplet d'éléments distincts : $30 \times 29 = 870$ possibilités.
• Équipe de 3 : aucun rôle n'est distingué, l'ordre ne compte pas. C'est une combinaison : $\binom{30}{3} = 4060$ possibilités.

9. Erreurs classiques

Confondre $\binom{n}{k}$ et $\dfrac{n!}{(n-k)!}$. Le coefficient binomial comporte un $k!$ au dénominateur, précisément parce qu'il efface l'ordre. Sans ce $k!$, on compte des listes, pas des parties.

Oublier que le principe multiplicatif exige une indépendance du nombre de choix. « Choisir un délégué puis un suppléant » fonctionne ($30$ puis $29$, quel que soit le premier choix). En revanche, un énoncé du type « choisir un premier chiffre non nul, puis un chiffre inférieur au premier » ne se traite pas ainsi : le nombre de possibilités de la deuxième étape dépend de la première. Il faut alors découper les cas et additionner.

Additionner des cas qui se recouvrent. Le principe additif suppose des ensembles disjoints. « Les mains contenant un as ou un roi » n'est pas la somme « mains avec un as » + « mains avec un roi » : les mains contenant les deux seraient comptées deux fois.

Écrire $\binom{n}{k}$ pour $k > n$. Il n'existe aucune partie à $k$ éléments dans un ensemble qui en compte $n < k$ : ce nombre vaut $0$, et la formule factorielle n'a plus de sens (elle ferait apparaître la factorielle d'un entier négatif).

Croire que $0! = 0$. Par convention $0! = 1$, ce qui donne bien $\binom{n}{0} = 1$ : il existe exactement une partie à zéro élément, l'ensemble vide.

10. Exercices corrigés

Exercice 1 — Les trois questions de base

Un sac contient 10 jetons numérotés de 1 à 10. Combien y a-t-il de façons de :

a. tirer successivement 3 jetons avec remise ; b. tirer successivement 3 jetons sans remise ; c. tirer simultanément 3 jetons ?

Correction. a. Successivement, donc l'ordre compte ; avec remise, donc répétitions permises. C'est un 3-uplet : $10^3 = 1000$. b. L'ordre compte, sans répétition : $10 \times 9 \times 8 = 720$. c. Simultanément : aucun ordre. C'est une combinaison : $\binom{10}{3} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$.

On remarque que $720 = 120 \times 3!$ : les tirages sans remise sont les tirages simultanés, chacun compté dans ses $3! = 6$ ordres possibles. C'est exactement la démonstration de la partie 6.

Exercice 2 — Un comité avec contrainte

Un club compte 12 femmes et 8 hommes. On forme un comité de 5 personnes.

a. Combien de comités possibles ? b. Combien de comités comptant exactement 3 femmes ? c. Combien de comités comptant au moins une femme ?

Correction. a. Le club compte 20 membres et un comité est une partie à 5 éléments : $\binom{20}{5} = 15\,504$.

b. On choisit les 3 femmes parmi 12, puis les 2 hommes parmi 8. Ces deux choix sont indépendants, le principe multiplicatif s'applique : $\binom{12}{3} \times \binom{8}{2} = 220 \times 28 = 6160.$

c. Passer par l'événement contraire est ici bien plus court. Les comités sans aucune femme sont ceux formés uniquement d'hommes : $\binom{8}{5} = 56$. D'où $15\,504 - 56 = 15\,448 \text{ comités comptant au moins une femme.}$

Exercice 3 — Manipuler la relation de Pascal

a. Calculer $\binom{7}{3}$ à l'aide de la formule factorielle. b. Retrouver ce résultat par la relation de Pascal, connaissant $\binom{6}{2} = 15$ et $\binom{6}{3} = 20$. c. Sans calculer, donner $\binom{7}{4}$.

Correction. a. $\binom{7}{3} = \dfrac{7!}{3!\,4!} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = \dfrac{210}{6} = 35$. b. La relation de Pascal avec $n = 7$ et $k = 3$ s'écrit $\binom{6}{2} + \binom{6}{3} = \binom{7}{3}$, soit $15 + 20 = 35$. ✓ c. Par symétrie, $\binom{7}{4} = \binom{7}{7-4} = \binom{7}{3} = 35$.

Exercice 4 — Anagrammes

Combien de mots, ayant un sens ou non, peut-on former en utilisant toutes les lettres du mot MATHS ?

Correction. Les cinq lettres M, A, T, H, S sont deux à deux distinctes : un tel mot est une permutation de ces cinq lettres, il y en a $5! = 120$.

Remarque. Si une lettre était répétée, ce raisonnement tomberait en défaut : les permutations échangeant deux lettres identiques donnent le même mot, et il faudrait diviser. Ce cas dépasse le programme de terminale, mais il montre bien pourquoi l'hypothèse « éléments distincts » figure dans l'énoncé des propriétés.

Exercice 5 — Chemins dans un quadrillage

Un pion part du coin inférieur gauche d'un quadrillage $4 \times 3$ et doit rejoindre le coin supérieur droit en se déplaçant uniquement d'une case vers la droite (D) ou d'une case vers le haut (H). Combien de trajets différents ?

Correction. Tout trajet comporte nécessairement 4 déplacements D et 3 déplacements H, soit 7 déplacements au total. Un trajet est entièrement déterminé par le choix des positions des 3 déplacements H parmi les 7 places de la liste. C'est donc une partie à 3 éléments d'un ensemble à 7 éléments : $\binom{7}{3} = 35 \text{ trajets.}$

Ce résultat éclaire le triangle de Pascal : le nombre de chemins pour atteindre une case est la somme des nombres de chemins des deux cases dont elle est accessible — exactement la relation de Pascal.

À retenir

Les trois relations à savoir démontrer

$\binom{n}{k} = \binom{n}{n-k} \qquad \binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k} \qquad \sum_{k=0}^{n} \binom{n}{k} = 2^n$

Le réflexe. Avant tout calcul : l'ordre compte-t-il ? puis les répétitions sont-elles permises ? Le modèle découle des réponses, jamais l'inverse.

Chapitre suivant : les vecteurs, droites et plans de l'espace. Ce chapitre 1 sera directement réutilisé au chapitre 13, où le coefficient $\binom{n}{k}$ apparaît dans l'expression de la loi binomiale.

Le programme complet de terminale

Algèbre et géométrie

1. Combinatoire et dénombrement
2. Vecteurs, droites et plans de l'espace
3. Orthogonalité et distances dans l'espace
4. Représentations paramétriques et équations cartésiennes

Analyse

1. Suites et limites
2. Limites de fonctions
3. Dérivation et convexité
4. Continuité et théorème des valeurs intermédiaires
5. Fonction logarithme népérien
6. Fonctions sinus et cosinus
7. Primitives et équations différentielles
8. Calcul intégral

Probabilités

1. Schéma de Bernoulli et loi binomiale
2. Sommes de variables aléatoires
3. Concentration et loi des grands nombres

Chapitre 2 · Vecteurs, droites et plans de l'espace →

Tous les cours · coursDeLion · La chaîne YouTube