Ressources · Terminale · Spécialité Mathématiques

Combinatoire et dénombrement

Principes additif et multiplicatif, k-uplets, factorielle et permutations, k-uplets d’éléments distincts, combinaisons, coefficients binomiaux, triangle de Pascal, mots et chemins.

À propos de cette page

Ce cours de spécialité maths de Terminale sur la combinatoire suit cinq parties : principes additif et multiplicatif avec les k-uplets, k-uplets d’éléments distincts et permutations avec la factorielle, combinaisons et coefficients binomiaux, relation de Pascal et nombre de parties, mots, chemins et choix du modèle. Les démonstrations demandées au bac (relation de Pascal par le calcul et par dénombrement, somme d’une ligne égale à 2ⁿ, formule de « k parmi n », symétrie) y sont rédigées.

Principes additif et multiplicatif, k-uplets

Ce qu’il faut savoir

Cardinal. Le nombre d’éléments d’un ensemble fini $E$ est son cardinal, noté $card (E)$ . Dénombrer, c’est calculer un cardinal sans dresser la liste des éléments.

Principe additif. Si $A_{1}, \dots, A_{p}$ sont des ensembles finis deux à deux disjoints, alors $card (A_{1} \cup \dots \cup A_{p})$ $= card (A_{1}) + \dots + card (A_{p})$ . Si $A$ et $B$ ne sont pas disjoints : $card (A \cup B)$ $= card (A) + card (B) - card (A \cap B)$ .

Complémentaire. Si $A \subset E$ , le complémentaire $\overset{―}{A}$ vérifie $card (\overset{―}{A}) = card (E) - card (A)$ .

Principe multiplicatif. $card (A \times B) = card (A) \times card (B)$ . Plus généralement, un choix fait en $p$ étapes qui offrent successivement $n_{1}, n_{2}, \dots, n_{p}$ possibilités (ces nombres ne dépendent pas des choix déjà faits) conduit à $n_{1} \times n_{2} \times \dots \times n_{p}$ issues. Un arbre de choix illustre ce principe.

$k$ -uplets. Un $k$ -uplet (ou $k$ -liste) d’éléments de $E$ est une suite ordonnée $(x_{1}, \dots, x_{k})$ d’éléments de $E$ , répétitions permises : c’est un élément de $E^{k} = E \times \dots \times E$ . Si $card (E) = n$ , il y a $n^{k}$ $k$ -uplets : $n$ choix pour chacun des $k$ termes (principe multiplicatif).

Exemples

Additif et multiplicatif. Un numéro de casier est soit une lettre suivie de deux chiffres, soit un nombre de trois chiffres (de $000$ à $999$ ). Premier type : $26 \times 10 \times 10 = 2 600$ . Second type : $10^{3} = 1 000$ . Un numéro ne peut pas être des deux types (il commence ou non par une lettre) : les deux ensembles sont disjoints et il y a $2 600 + 1 000 = 3 600$ numéros.

$k$ -uplets. Un questionnaire compte $10$ questions, chacune avec les réponses A, B, C ou D. Une grille de réponses est un $10$ -uplet de ${A, B, C, D}$ : il y en a $4^{10} = 1 048 576$ .

« Au moins un » : le complémentaire. Combien de codes de $4$ chiffres contiennent au moins un $0$ ? Il y a $10^{4} = 10 000$ codes, dont $9^{4} = 6 561$ sans aucun $0$ (chaque chiffre parmi $1, \dots, 9$ ). Donc $10 000 - 6 561 = 3 439$ codes contiennent au moins un $0$ .

Réflexe — Je découpe le comptage : en étapes successives, je multiplie ; en cas qui ne se recouvrent pas, j’additionne. Pour « au moins un », je compte tout, puis je retire le cas contraire « aucun ».

Attention — Le principe additif ne vaut que pour des ensembles disjoints : sinon, les éléments communs sont comptés deux fois et il faut retirer $card (A \cap B)$ . Et un $k$ -uplet est ordonné : $(1, 2)$ et $(2, 1)$ sont deux couples différents.

1 / 5

k-uplets d’éléments distincts, factorielle et permutations

Ce qu’il faut savoir

Factorielle. Pour $n ⩾ 1$ , $n! = 1 \times 2 \times \dots \times n$ (« factorielle $n$ ») ; par convention, $0! = 1$ . Pour tout $n ⩾ 0$ : $(n + 1)! = (n + 1) \times n!$ .

$k$ -uplets d’éléments distincts (ou arrangements). Si $card (E) = n$ et $0 ⩽ k ⩽ n$ , le nombre de $k$ -uplets d’éléments deux à deux distincts de $E$ est $n (n - 1) \dots (n - k + 1)$ (produit de $k$ facteurs), qui s’écrit $\frac{n!}{(n - k)!}$ .

Permutations. Une permutation de $E$ est un $n$ -uplet d’éléments distincts de $E$ : c’est une façon de ranger tous ses éléments. Il y en a $n!$ .

Tirages. Des tirages successifs sans remise de $k$ objets parmi $n$ donnent des $k$ -uplets d’éléments distincts ; avec remise, des $k$ -uplets quelconques ( $n^{k}$ ).

Exemples

Démonstration de la formule. On construit le $k$ -uplet terme à terme : $n$ choix pour $x_{1}$ ; $x_{2}$ doit être différent de $x_{1}$ , soit $n - 1$ choix ; … ; $x_{k}$ doit éviter les $k - 1$ termes déjà choisis, soit $n - (k - 1) = n - k + 1$ choix. Ces nombres ne dépendent pas des choix faits : par le principe multiplicatif, il y a $n (n - 1) \dots (n - k + 1)$ $k$ -uplets d’éléments distincts. En multipliant et divisant par $(n - k)! = (n - k) (n - k - 1) \dots 1$ , ce produit vaut $\frac{n!}{(n - k)!}$ . Avec $k = n$ , on obtient $\frac{n!}{0!} = n!$ permutations.

Podium. Une finale réunit $8$ nageurs (sans ex æquo). Un podium (or, argent, bronze) est un $3$ -uplet de nageurs distincts : $8 \times 7 \times 6 = 336$ podiums possibles.

Permutation. L’ordre de passage de $5$ relayeurs est une permutation de l’équipe : $5! = 120$ ordres possibles.

Simplifier sans tout calculer. $\frac{10!}{7!} = 10 \times 9 \times 8 = 720$ , car $10! = 10 \times 9 \times 8 \times 7!$ . De même, $\frac{12!}{10! \times 2} = \frac{12 \times 11}{2} = 66$ .

Contrainte « côte à côte ». $7$ amis s’alignent pour une photo ; Alix et Basile veulent être côte à côte. On colle Alix et Basile en un bloc : on range $6$ objets ( $6!$ façons), puis on ordonne le bloc ( $2$ façons) : comme $6! = 720$ , il y a $720 \times 2 = 1 440$ photos.

Réflexe — L’ordre compte et il n’y a pas de répétition (places, rangs, podium, tirages successifs sans remise) : je multiplie $k$ facteurs décroissants à partir de $n$ . On range tous les éléments : $n!$ .

Attention — $\frac{n!}{(n - k)!}$ n’est pas $\frac{n!}{k!}$ : le produit compte exactement $k$ facteurs. Et $0! = 1$ , pas $0$ . Les factorielles grandissent très vite ( $10! = 3 628 800$ ) : on simplifie un quotient avant de calculer.

2 / 5

Combinaisons et coefficients binomiaux

Ce qu’il faut savoir

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. Si $card (E) = n$ , leur nombre se note $(\binom{n}{k})$ et se lit « $k$ parmi $n$ » : c’est un coefficient binomial.

Formule. Pour $0 ⩽ k ⩽ n$ : $(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k!}$ $= \frac{n!}{k! (n - k)!}$ .

Cas usuels. $(\binom{n}{0}) = (\binom{n}{n}) = 1$ ; $(\binom{n}{1}) = n$ ; $(\binom{n}{2}) = \frac{n (n - 1)}{2}$ .

Symétrie. Pour $0 ⩽ k ⩽ n$ : $(\binom{n}{k}) = (\binom{n}{n - k})$ .

Tirage simultané. Tirer $k$ objets simultanément parmi $n$ , c’est choisir une partie à $k$ éléments : $(\binom{n}{k})$ tirages.

Exemples

Démonstration de la formule. Chaque partie à $k$ éléments peut être ordonnée de $k!$ façons (ses permutations), et chaque $k$ -uplet d’éléments distincts s’obtient ainsi à partir d’une seule partie : celle de ses termes. Donc $k! \times (\binom{n}{k}) = \frac{n!}{(n - k)!}$ , d’où $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ .

Démonstration de la symétrie. L’application qui, à une partie $A$ de $E$ à $k$ éléments, associe son complémentaire $\overset{―}{A}$ (à $n - k$ éléments) est sa propre réciproque, car $\overset{―}{\overset{―}{A}} = A$ : c’est une bijection entre les parties à $k$ éléments et les parties à $n - k$ éléments. Les deux ensembles ont donc le même cardinal. Par le calcul : échanger $k$ et $n - k$ ne change pas le produit $k! (n - k)!$ .

Paires. Dans un tournoi de tennis de table, chacun des $15$ joueurs rencontre une fois chacun des autres. Un match est une paire de joueurs : $(\binom{15}{2}) = \frac{15 \times 14}{2} = 105$ matchs.

Symétrie. $(\binom{30}{28}) = (\binom{30}{2}) = \frac{30 \times 29}{2} = 435$ .

« Exactement » : par catégories. Une main de $5$ cartes d’un jeu de $32$ cartes (dont $8$ cœurs) contient exactement $2$ cœurs : on choisit $2$ cœurs parmi $8$ , puis $3$ cartes parmi les $24$ autres. Il y a $(\binom{8}{2}) \times (\binom{24}{3})$ $= 28 \times 2 024$ $= 56 672$ mains.

« Au moins un » : complémentaire. Un comité de $4$ personnes est choisi parmi $8$ filles et $6$ garçons. Au total : $(\binom{14}{4}) = 1 001$ comités. Sans aucune fille : $(\binom{6}{4}) = 15$ . Avec au moins une fille : $1 001 - 15 = 986$ .

Algorithme. La fonction ci-dessous liste les parties à $2$ éléments de ${0, \dots, n - 1}$ ; la boucle intérieure ne prend que les $j > i$ , donc chaque paire est écrite une seule fois :

def paires(n):
    P = []
    for i in range(n):
        for j in range(i+1, n):
            P.append((i, j))
    return P

paires(5) renvoie les $10$ paires de $(0, 1)$ à $(3, 4)$ ; en général, len(paires(n)) vaut n*(n-1)//2, c’est-à-dire $(\binom{n}{2})$ .

Réflexe — « Simultanément », « un groupe », « une équipe », « une main » : l’ordre ne compte pas, je compte des parties avec $(\binom{n}{k})$ . Pour « exactement $j$ objets d’une catégorie », je choisis séparément dans chaque catégorie et je multiplie.

Attention — Choisir « d’abord un cœur, puis $4$ cartes quelconques » pour compter les mains avec au moins un cœur est faux : une main à deux cœurs est comptée deux fois. Pour « au moins un », on passe par le complémentaire.

3 / 5

Relation de Pascal et nombre de parties

Ce qu’il faut savoir

Relation de Pascal (démonstration exigible). Pour $0 ⩽ k ⩽ n - 1$ : $(\binom{n}{k}) + (\binom{n}{k + 1}) = (\binom{n + 1}{k + 1})$ .

Triangle de Pascal. Ligne $n$ , colonne $k$ : $(\binom{n}{k})$ . Les bords valent $1$ ; chaque autre coefficient est la somme de celui qui est juste au-dessus et de celui qui est au-dessus à 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

Nombre de parties. Un ensemble à $n$ éléments possède $2^{n}$ parties (la partie vide et $E$ comprises).

Somme d’une ligne (démonstration exigible, par dénombrement). $(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n}$ .

Exemples

Démonstration de la relation de Pascal (par dénombrement). Soit $E$ un ensemble à $n + 1$ éléments et $a$ un élément fixé de $E$ . Les parties de $E$ à $k + 1$ éléments se rangent en deux familles disjointes :

• celles qui contiennent $a$ : on choisit leurs $k$ autres éléments parmi les $n$ éléments de $E$ autres que $a$ , soit $(\binom{n}{k})$ parties ;

• celles qui ne contiennent pas $a$ : leurs $k + 1$ éléments sont pris parmi ces $n$ éléments, soit $(\binom{n}{k + 1})$ parties.

Par le principe additif, $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ .

Démonstration de la relation de Pascal (par le calcul). Pour $0 ⩽ k ⩽ n - 1$ : $(\binom{n}{k}) + (\binom{n}{k + 1})$ $= \frac{n!}{k! (n - k)!}$ $+ \frac{n!}{(k + 1)! (n - k - 1)!}$ . On réduit au même dénominateur $(k + 1)! (n - k)!$ , car $(k + 1)! = (k + 1) \times k!$ et $(n - k)! = (n - k) \times (n - k - 1)!$ : la somme vaut $\frac{n! (k + 1) + n! (n - k)}{(k + 1)! (n - k)!}$ $= \frac{(n + 1) \times n!}{(k + 1)! (n - k)!}$ $= \frac{(n + 1)!}{(k + 1)! ((n + 1) - (k + 1))!}$ $= (\binom{n + 1}{k + 1})$ .

Démonstration : $2^{n}$ parties. Notons $E = {e_{1}, \dots, e_{n}}$ . À une partie $A$ , on associe le $n$ -uplet $(x_{1}, \dots, x_{n})$ de ${0; 1}^{n}$ où $x_{i} = 1$ si $e_{i} \in A$ et $x_{i} = 0$ sinon. Deux parties différentes donnent deux $n$ -uplets différents, et tout $n$ -uplet vient d’une partie (celle des $e_{i}$ tels que $x_{i} = 1$ ) : c’est une bijection. Le nombre de parties est donc $card ({0; 1}^{n}) = 2^{n}$ .

Démonstration : somme d’une ligne. On range les parties de $E$ selon leur nombre d’éléments $k \in {0, \dots, n}$ : ces $n + 1$ familles sont disjointes, et la famille $k$ compte $(\binom{n}{k})$ parties. Par le principe additif, leur somme est le nombre total de parties, $2^{n}$ .

Utiliser la relation. $(\binom{7}{3}) = (\binom{6}{2}) + (\binom{6}{3})$ $= 15 + 20 = 35$ .

Parties avec une contrainte. Un ensemble à $10$ éléments a $2^{10} = 1 024$ parties ; parmi elles, $1$ est vide et $10$ ont un seul élément. Il y a donc $1 024 - 1 - 10 = 1 013$ parties d’au moins $2$ éléments.

Algorithme. La fonction ci-dessous reçoit une ligne L du triangle et renvoie la ligne suivante, grâce à la relation de Pascal :

def suivante(L):
    n = len(L)
    M = [1]
    for k in range(n-1):
        s = L[k]+L[k+1]
        M.append(s)
    return M + [1]

Appliquée à la ligne $5$ ( $1$ , $5$ , $10$ , $10$ , $5$ , $1$ ), elle renvoie la ligne $6$ : $1$ , $6$ , $15$ , $20$ , $15$ , $6$ , $1$ . En partant de [1] et en l’appliquant $n$ fois, on obtient la ligne $n$ .

Réflexe — Pour démontrer une égalité de coefficients binomiaux : je cherche un ensemble que je peux compter de deux façons (en fixant un élément, en séparant selon le cardinal…), ou je calcule avec les factorielles. Pour remplir le triangle, j’additionne deux voisins de la ligne précédente.

Attention — La relation de Pascal additionne deux coefficients voisins de la même ligne : $(\binom{n}{k}) + (\binom{n}{k + 1})$ donne $(\binom{n + 1}{k + 1})$ , pas $(\binom{n + 1}{k})$ ni $(\binom{2 n}{2 k + 1})$ . Et les $2^{n}$ parties comptent la partie vide et $E$ lui-même.

4 / 5

Mots, chemins et choix du modèle

Ce qu’il faut savoir

Mots à deux lettres. Le nombre de mots de longueur $n$ formés de $k$ lettres A et de $n - k$ lettres B est $(\binom{n}{k})$ : un tel mot est déterminé par l’ensemble des $k$ positions occupées par A.

Chemins. Dans un quadrillage, un chemin de $(0; 0)$ à $(p; q)$ par pas unitaires vers la droite (D) ou vers le haut (H) est un mot de $p + q$ lettres contenant $q$ lettres H : il y en a $(\binom{p + q}{q})$ .

Mots avec lettres répétées. On place les lettres identiques groupe par groupe : on choisit les positions du premier groupe, puis celles du deuxième parmi les positions restantes, et on multiplie.

Choisir le modèle d’un tirage de $k$ objets parmi $n$ .

Tirage	Modèle	Nombre
successif avec remise (ordre, répétitions)	$k$ -uplet	$n^{k}$
successif sans remise (ordre, pas de répétition)	$k$ -uplet d’éléments distincts	$\frac{n!}{(n - k)!}$
simultané (ni ordre ni répétition)	partie à $k$ éléments	$(\binom{n}{k})$

Groupes sans nom. Pour répartir des personnes en groupes de même taille qui ne portent pas de numéro, on compte les groupes numérotés puis on divise par le nombre d’ordres possibles des groupes.

Double dénombrement. Pour démontrer une égalité, on compte un même ensemble de deux façons.

Lien avec les probabilités. En situation d’équiprobabilité, $P (A) = \frac{card (A)}{card (Ω)}$ : dénombrer donne les probabilités.

Exemples

Chemins. De $(0; 0)$ à $(7; 3)$ , un chemin compte $10$ pas dont $3$ vers le haut : $(\binom{10}{3}) = 120$ chemins.

Pile ou face. On lance $10$ fois une pièce. Les suites contenant exactement $4$ « pile » sont des mots de $10$ lettres avec $4$ lettres P : $(\binom{10}{4}) = 210$ suites, sur $2^{10} = 1 024$ suites possibles.

Lettres répétées. Le mot RADAR a $5$ lettres : deux R, deux A, un D. On choisit les $2$ places des R ( $(\binom{5}{2}) = 10$ ), puis les $2$ places des A parmi les $3$ restantes ( $(\binom{3}{2}) = 3$ ) ; le D prend la dernière. Il y a $10 \times 3 = 30$ anagrammes.

Double dénombrement. Montrons que $k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})$ pour $1 ⩽ k ⩽ n$ . Dans un groupe de $n$ personnes, on compte les comités de $k$ membres munis d’un président choisi dans le comité. Comité d’abord ( $(\binom{n}{k})$ choix), puis président ( $k$ choix) : $k (\binom{n}{k})$ . Président d’abord ( $n$ choix), puis les $k - 1$ autres membres parmi les $n - 1$ personnes restantes : $n (\binom{n - 1}{k - 1})$ . Les deux nombres comptent le même ensemble : ils sont égaux. Contrôle : $5 (\binom{9}{5}) = 5 \times 126 = 630$ et $9 (\binom{8}{4}) = 9 \times 70 = 630$ .

Réflexe — Je décris un résultat type par un objet précis (liste, partie, mot, chemin), je me demande si l’ordre compte et si les répétitions sont possibles, puis j’applique la formule. Je contrôle sur un petit cas.

Attention — Dans un mot, les lettres identiques ne se distinguent pas : RADAR n’a pas $5! = 120$ anagrammes. Et un chemin de $(0; 0)$ à $(p; q)$ compte $p + q$ pas, pas $p \times q$ .

5 / 5

Pour aller plus loin

Loi binomiale. Dans un schéma de Bernoulli de $n$ épreuves, le nombre de chemins de l’arbre qui comptent exactement $k$ succès est $(\binom{n}{k})$ : c’est ce qui donne $P (X = k) = (\binom{n}{k}) p^{k} (1 - p)^{n - k}$ , étudié dans le chapitre Loi binomiale.

Formule du binôme. Pour tous nombres $a$ , $b$ et tout entier naturel $n$ , $(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k}$ : en développant le produit des $n$ facteurs $(a + b)$ , le terme $a^{k} b^{n - k}$ apparaît une fois pour chaque choix des $k$ facteurs qui fournissent $a$ . Cette formule n’est pas au programme de la spécialité ; elle est traitée en option maths expertes, dans le chapitre Nombres complexes : forme algébrique.

Par récurrence. Le résultat « $2^{n}$ parties » se démontre aussi par récurrence (une partie de $E \cup {a}$ contient $a$ ou non) : la rédaction est celle du chapitre Raisonnement par récurrence.

À retenir

Étapes successives : je multiplie (principe multiplicatif) ; cas disjoints : j’additionne ; « au moins un » : tout moins « aucun ».
$k$ -uplets d’un ensemble à $n$ éléments (ordre, répétitions) : $n^{k}$ . $k$ -uplets d’éléments distincts : $\frac{n!}{(n - k)!}$ . Permutations : $n!$ , avec $0! = 1$ .
Parties à $k$ éléments (ni ordre ni répétition) : $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ , avec $(\binom{n}{k}) = (\binom{n}{n - k})$ .
Relation de Pascal : $(\binom{n}{k}) + (\binom{n}{k + 1}) = (\binom{n + 1}{k + 1})$ . Un ensemble à $n$ éléments a $2^{n}$ parties.
Mots de $n$ lettres avec $k$ lettres A et $n - k$ lettres B, chemins de $(0; 0)$ à $(p; q)$ : $(\binom{n}{k})$ et $(\binom{p + q}{q})$ .

Questions fréquentes

Quand faut-il additionner et quand faut-il multiplier en dénombrement ?

On multiplie quand un résultat se construit en étapes successives (principe multiplicatif) : 4 pains, puis 6 garnitures, puis 3 sauces donnent 4 × 6 × 3 sandwichs. On additionne quand on sépare les résultats en cas qui ne se recouvrent pas (principe additif). Pour « au moins un », on compte tout et on retire le cas « aucun ».

Quelle est la différence entre un arrangement et une permutation ?

Un arrangement (ou k-uplet d’éléments distincts) range k éléments distincts choisis parmi n : il y en a n(n − 1)…(n − k + 1) = n!/(n − k)!. Une permutation range tous les n éléments : c’est le cas k = n, il y en a n!.

Comment savoir s’il faut utiliser un coefficient binomial ?

On utilise « k parmi n » quand on choisit k éléments sans ordre et sans répétition : un groupe, une équipe, une main de cartes, un tirage simultané. Si l’ordre compte (rôles, places, tirages successifs), on utilise un k-uplet. Chaque partie à k éléments donne k! k-uplets d’éléments distincts.

Comment démontrer la relation de Pascal ?

Par dénombrement : on fixe un élément a d’un ensemble à n + 1 éléments. Les parties à k + 1 éléments qui contiennent a sont au nombre de « k parmi n », celles qui ne le contiennent pas de « k + 1 parmi n ». Ces deux familles sont disjointes, d’où « k parmi n » + « k + 1 parmi n » = « k + 1 parmi n + 1 ». Par le calcul : on réduit les deux fractions au même dénominateur (k + 1)!(n − k)! ; le numérateur vaut n!(k + 1 + n − k) = (n + 1)!.

Comment compter les chemins dans un quadrillage ?

Un chemin de (0 ; 0) à (p ; q) par pas vers la droite ou vers le haut est un mot de p + q lettres contenant q lettres H. Il est déterminé par les positions des pas vers le haut : il y en a « q parmi p + q ». Pour un chemin passant par un point C, on multiplie le nombre de chemins jusqu’à C par le nombre de chemins après C.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs