Dénombrement et combinatoire — leçon d'oral du CAPES

Prérequis

Niveaux concernés et situation dans les programmes : le dénombrement est un chapitre de terminale spécialité (principes additif et multiplicatif, $k$ -uplets, $k$ -uplets d'éléments distincts, permutations, factorielle, combinaisons, triangle de Pascal, nombre de parties d'un ensemble), réinvesti dans la loi binomiale ; il prépare en mathématiques expertes l'arithmétique et la formule du binôme dans $\mathbb{C}$ . Des situations de dénombrement par arbres ou tableaux apparaissent dès le collège et en seconde en probabilités. Le candidat vérifiera dans les programmes en vigueur, y compris après le BO n° 14 du 2 avril 2026 pour la seconde et la première, ce qui relève de chaque niveau.
Plan de leçon possible : I. Principes de dénombrement et $k$ -uplets ; II. Arrangements, permutations, factorielle ; III. Combinaisons, triangle de Pascal et formule du binôme. Le développement peut être la formule de Pascal et la formule du binôme (théorème clé), le nombre de parties d'un ensemble par deux méthodes, ou une démonstration combinatoire d'une identité (Vandermonde).
Prérequis des élèves : vocabulaire des ensembles (réunion, intersection, produit cartésien, cardinal), arbres, raisonnement par récurrence, suites, probabilités en situation d'équiprobabilité.
Recul attendu du candidat : bijections et cardinaux (principe des bergers), double comptage, principe d'inclusion-exclusion, applications injectives et surjectives, coefficients multinomiaux, lien avec la loi binomiale et la loi hypergéométrique, nombres de Catalan et chemins dans un quadrillage.

Proposition de plan en trois parties

I. Principes de dénombrement et k-uplets

Principe additif : si $A$ et $B$ sont des ensembles finis disjoints, $\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B)$ ; plus généralement $\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B)$ . Principe multiplicatif : $\mathrm{card}(A \times B) = \mathrm{card}(A) \times \mathrm{card}(B)$ , ce qu'illustre un arbre dont chaque nœud d'un même niveau a le même nombre de branches. Un $k$ -uplet (ou $k$ -liste) d'éléments de $E$ est un élément de $E^k$ : l'ordre compte et les répétitions sont permises. Si $\mathrm{card}(E) = n$ , il y a $n^k$ $k$ -uplets d'éléments de $E$ (récurrence sur $k$ ). Exemple : il y a $10^4$ codes à quatre chiffres et $26^3 \times 10^3$ plaques formées de trois lettres suivies de trois chiffres. Nombre de parties : un ensemble à $n$ éléments a $2^n$ parties, car une partie s'identifie à un $n$ -uplet de $\{0 ; 1\}$ (on code 1 si l'élément appartient à la partie). Contre-exemple : le principe multiplicatif ne s'applique pas directement lorsque le nombre de choix à une étape dépend des choix précédents de manière non uniforme (par exemple, les nombres de trois chiffres distincts ne commençant pas par 0 se comptent en traitant d'abord le premier chiffre : $9 \times 9 \times 8 = 648$ ).

II. Arrangements, permutations et factorielle

Un $k$ -uplet d'éléments distincts de $E$ (ou arrangement) est un $k$ -uplet dont les composantes sont deux à deux distinctes. Si $\mathrm{card}(E) = n$ et $1 \le k \le n$ , leur nombre est $n(n - 1)\cdots(n - k + 1) = \frac{n!}{(n - k)!}$ , avec $n! = 1 \times 2 \times \cdots \times n$ et $0! = 1$ (démonstration exigible, par le principe multiplicatif ou par récurrence). Une permutation de $E$ est un $n$ -uplet d'éléments distincts de $E$ , c'est-à-dire un rangement de tous ses éléments : il y en a $n!$ . Exemple : le podium d'une course de 8 coureurs peut être occupé de $8 \times 7 \times 6 = 336$ façons ; les anagrammes du mot MATHS sont au nombre de $5! = 120$ . Anagrammes avec répétitions : le mot RADAR a $\frac{5!}{2!\,2!} = 30$ anagrammes (on divise par les permutations des lettres identiques). Contre-exemple : si $k \gt n$ , il n'existe aucun $k$ -uplet d'éléments distincts (principe des tiroirs) : dans un groupe de 367 personnes, deux ont nécessairement le même jour anniversaire.

III. Combinaisons, triangle de Pascal et formule du binôme

Une combinaison de $k$ éléments de $E$ est une partie de $E$ à $k$ éléments : l'ordre ne compte pas et il n'y a pas de répétition. Leur nombre est noté $\binom{n}{k}$ et vaut $\frac{n!}{k!\,(n - k)!}$ pour $0 \le k \le n$ , car chaque partie à $k$ éléments correspond à exactement $k!$ arrangements (démonstration exigible). Propriétés : $\binom{n}{0} = \binom{n}{n} = 1$ , symétrie $\binom{n}{k} = \binom{n}{n - k}$ (passage au complémentaire), relation de Pascal $\binom{n}{k} + \binom{n}{k + 1} = \binom{n + 1}{k + 1}$ , triangle de Pascal, $\sum_{k=0}^{n}\binom{n}{k} = 2^n$ . Formule du binôme : $(a + b)^n = \sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}$ pour des réels ou complexes $a$ et $b$ . Lien avec les probabilités : dans un schéma de Bernoulli à $n$ épreuves, $\binom{n}{k}$ est le nombre de chemins de l'arbre comportant $k$ succès, d'où $P(X = k) = \binom{n}{k}p^k(1 - p)^{n-k}$ . Exemple : une main de 5 cartes d'un jeu de 32 : $\binom{32}{5} = 201\,376$ mains ; mains contenant exactement 2 as : $\binom{4}{2}\binom{28}{3} = 6 \times 3276 = 19\,656$ . Contre-exemple : pour un comité comprenant un président et un trésorier, l'ordre (le rôle) compte : on dénombre des arrangements et non des combinaisons.

Théorème clé et démonstration

Relation de Pascal et formule du binôme

(i) Pour tous entiers $n \ge 0$ et $0 \le k \le n - 1$ , $\binom{n}{k} + \binom{n}{k + 1} = \binom{n + 1}{k + 1}$ . (ii) Pour tous nombres complexes $a$ et $b$ et tout entier naturel $n$ , $(a + b)^n = \sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k}$ .

Démonstration

1. Démonstration combinatoire de (i). Soit $E$ un ensemble à $n + 1$ éléments et $x$ un élément fixé de $E$ . Les parties de $E$ à $k + 1$ éléments se répartissent en deux catégories disjointes : celles qui contiennent $x$ , déterminées par le choix de $k$ éléments parmi les $n$ autres, au nombre de $\binom{n}{k}$ , et celles qui ne contiennent pas $x$ , formées de $k + 1$ éléments parmi les $n$ autres, au nombre de $\binom{n}{k + 1}$ . Le principe additif donne (i).
2. Démonstration calculatoire de (i). $\binom{n}{k} + \binom{n}{k + 1} = \frac{n!}{k!\,(n - k)!} + \frac{n!}{(k + 1)!\,(n - k - 1)!} = \frac{n!\,\left[(k + 1) + (n - k)\right]}{(k + 1)!\,(n - k)!} = \frac{(n + 1)!}{(k + 1)!\,(n - k)!} = \binom{n + 1}{k + 1}$ .
3. Initialisation de (ii). Pour $n = 0$ , les deux membres valent $1$ .
4. Hérédité. Supposons la formule vraie au rang $n$ . Alors $(a + b)^{n+1} = (a + b)\sum_{k=0}^{n}\binom{n}{k}a^kb^{n-k} = \sum_{k=0}^{n}\binom{n}{k}a^{k+1}b^{n-k} + \sum_{k=0}^{n}\binom{n}{k}a^kb^{n+1-k}$ . Dans la première somme, on pose $j = k + 1$ : elle vaut $\sum_{j=1}^{n+1}\binom{n}{j - 1}a^jb^{n+1-j}$ .
5. Regroupement. On isole les termes $j = n + 1$ (égal à $a^{n+1}$ ) et $j = 0$ (égal à $b^{n+1}$ ), puis on applique la relation de Pascal aux termes $1 \le j \le n$ : $\binom{n}{j - 1} + \binom{n}{j} = \binom{n + 1}{j}$ . On obtient $(a + b)^{n+1} = \sum_{j=0}^{n+1}\binom{n + 1}{j}a^jb^{n+1-j}$ , car $\binom{n + 1}{0} = \binom{n + 1}{n + 1} = 1$ .
6. Remarque. La preuve n'utilise que la commutativité et la distributivité : la formule vaut pour des matrices qui commutent, mais elle est fausse en général pour deux matrices $A$ et $B$ telles que $AB \neq BA$ . On peut aussi la lire combinatoirement : développer $(a + b)^n$ revient à choisir, dans chacun des $n$ facteurs, $a$ ou $b$ , et le monôme $a^kb^{n-k}$ apparaît autant de fois qu'il y a de façons de choisir les $k$ facteurs fournissant $a$ .

Développements possibles pour l’oral

Exercice de terminale (codes) : un code d'accès est formé de 4 chiffres. Combien y a-t-il de codes ? de codes à chiffres tous distincts ? de codes comportant au moins deux chiffres identiques ? Corrigé : $10^4 = 10\,000$ codes ; $10 \times 9 \times 8 \times 7 = 5040$ codes à chiffres distincts ; par passage au complémentaire, $10\,000 - 5040 = 4960$ codes comportent au moins une répétition.
Exercice de terminale (comités) : une association compte 7 femmes et 5 hommes. Combien de comités de 4 personnes peut-on former ? avec exactement 2 femmes ? avec au moins une femme ? Corrigé : $\binom{12}{4} = 495$ ; $\binom{7}{2}\binom{5}{2} = 21 \times 10 = 210$ ; $\binom{12}{4} - \binom{5}{4} = 495 - 5 = 490$ , l'événement contraire étant « aucune femme ».
Exercice de terminale (chemins) : dans un quadrillage, on va du point $(0 ; 0)$ au point $(5 ; 3)$ par des pas unitaires vers la droite ou vers le haut. Combien y a-t-il de chemins ? Combien passent par le point $(2 ; 1)$ ? Corrigé : un chemin est une suite de 8 pas dont 3 vers le haut, déterminée par la position de ces 3 pas : $\binom{8}{3} = 56$ chemins. Par le principe multiplicatif, $\binom{3}{1} \times \binom{5}{2} = 3 \times 10 = 30$ chemins passent par $(2 ; 1)$ .
Exercice de terminale (binôme) : déterminer le coefficient de $x^3$ dans le développement de $(2x - 1)^6$ , puis calculer $\sum_{k=0}^{n}\binom{n}{k}(-1)^k$ pour $n \ge 1$ . Corrigé : le terme en $x^3$ est $\binom{6}{3}(2x)^3(-1)^3 = -160x^3$ ; la formule du binôme avec $a = -1$ et $b = 1$ donne $\sum\binom{n}{k}(-1)^k = (1 - 1)^n = 0$ : un ensemble non vide a autant de parties de cardinal pair que de cardinal impair.
Prolongements : identité de Vandermonde $\sum_{k}\binom{p}{k}\binom{q}{n - k} = \binom{p + q}{n}$ par double comptage ; formule du crible ; nombre de surjections ; coefficients multinomiaux ; loi hypergéométrique ; nombres de Catalan ; applications en arithmétique ( $p$ premier divise $\binom{p}{k}$ pour $1 \le k \le p - 1$ , petit théorème de Fermat).

Remarques et questions du jury

Erreur fréquente d'élève : ne pas identifier si l'ordre compte et si les répétitions sont permises, et donc confondre $n^k$ , $\frac{n!}{(n - k)!}$ et $\binom{n}{k}$ . Le candidat peut proposer un tableau de décision à deux questions (ordre ? répétitions ?) en le complétant par des exemples.
Erreur fréquente d'élève : compter deux fois les mêmes configurations, par exemple pour « au moins un as » en choisissant d'abord un as puis 4 cartes quelconques ( $4 \times \binom{31}{4}$ ), ce qui compte plusieurs fois les mains contenant plusieurs as. Le passage au complémentaire évite cette erreur.
Erreur fréquente d'élève : additionner au lieu de multiplier (ou l'inverse) ; on multiplie pour des choix successifs (« et puis »), on additionne pour des cas disjoints (« ou bien »).
Erreur fréquente d'élève : oublier les conventions $0! = 1$ et $\binom{n}{0} = 1$ , ou croire que $\binom{n}{k}$ peut ne pas être entier ; la définition combinatoire montre au contraire que c'est un entier, ce qui n'est pas évident sur la formule avec les factorielles.
Le jury apprécie les démonstrations combinatoires (double comptage, bijection) à côté des démonstrations calculatoires, et une réflexion sur l'outil numérique : calcul de factorielles, construction du triangle de Pascal par un programme utilisant la relation de Pascal.
Question fréquente : quelle définition de $\binom{n}{k}$ adopter ? En terminale, on la définit comme nombre de parties à $k$ éléments, puis on démontre la formule factorielle ; le candidat doit pouvoir expliquer le lien avec le nombre de chemins à $k$ succès dans un arbre de Bernoulli.

Exercices corrigés

Exercice 1 Nombre de k-uplets

Palier 1 · découverte

Combien existe-t-il de mots de 3 lettres (ayant un sens ou non) formés avec les lettres A, B, C, D, chaque lettre pouvant être répétée ?

$64$
$24$
$12$
$4$

Un indice

Pour chacune des trois positions, compter le nombre de choix possibles, puis appliquer le principe multiplicatif.

Voir la correction

Bonne réponse : A. $64$

Chaque mot est un triplet d'éléments d'un ensemble à 4 éléments : il y en a $4^3 = 64$ . La réponse $24 = 4 \times 3 \times 2$ correspond aux mots à lettres distinctes ; $4$ correspond au nombre de parties à 3 éléments, sans ordre ni répétition.

Exercice 2 Podium et arrangements

Palier 2 · application

Dix athlètes participent à une finale. De combien de façons le podium (or, argent, bronze) peut-il être composé ?

$720$
$120$
$1000$
$30$

Un indice

L'ordre des trois premiers compte et un athlète ne peut occuper qu'une place.

Voir la correction

Bonne réponse : A. $720$

On compte les triplets d'athlètes distincts : $10 \times 9 \times 8 = 720$ . La réponse $120 = \binom{10}{3}$ ne tient pas compte de l'ordre (elle compte les groupes de trois médaillés) ; $1000 = 10^3$ autorise les répétitions.

Exercice 3 Comité avec contrainte

Palier 3 · approfondissement

Une classe compte 12 filles et 8 garçons. Combien de délégations de 3 élèves comportant exactement 2 filles peut-on former ?

$528$
$1140$
$74$
$1056$

Un indice

Choisir séparément les filles et le garçon, sans tenir compte de l'ordre, puis appliquer le principe multiplicatif.

Voir la correction

Bonne réponse : A. $528$

On choisit 2 filles parmi 12 et 1 garçon parmi 8 : $\binom{12}{2}\binom{8}{1} = 66 \times 8 = 528$ . La réponse $1140 = \binom{20}{3}$ compte toutes les délégations ; $1056 = 12 \times 11 \times 8$ ordonne les deux filles ; $74 = 66 + 8$ additionne au lieu de multiplier.

Exercice 4 Coefficient dans un développement

Palier 4 · défi

Quel est le coefficient de $x^2$ dans le développement de $(1 + 2x)^5$ ?

$40$
$10$
$20$
$80$

Un indice

Utiliser la formule du binôme : le terme en $x^2$ provient de $\binom{5}{2}(2x)^2$ .

Voir la correction

Bonne réponse : A. $40$

D'après la formule du binôme, $(1 + 2x)^5 = \sum_{k=0}^{5}\binom{5}{k}(2x)^k$ . Le terme en $x^2$ est $\binom{5}{2}(2x)^2 = 10 \times 4x^2 = 40x^2$ . La réponse $10$ oublie la puissance de $2$ ; $20$ ne l'élève pas au carré ; $80$ correspond au coefficient de $x^3$ .