Dénombrement - Cours et exercices corrigés | 1bac lettres, sciences humaines et enseignement originel

KORASATI · MATHÉMATIQUES

Retrouvez le cours intégral ci-dessous et sa version A4 mise en page, avec toutes les figures et les exercices corrigés.

Ouvrir et télécharger le cours en PDF

Sur téléphone, utilisez le bouton ci-dessus pour agrandir le document. La lecture est accessible sans inscription.

---

Objectifs. Compter sans oublier ni répéter, représenter des choix par un arbre, distinguer ordre et répétition, puis choisir entre produit, arrangement, permutation et combinaison.

Le dénombrement cherche le nombre d’objets possibles dans une situation finie. Il ne demande pas de calculer la chance d’obtenir un objet. Les situations de ce cours sont des exemples pédagogiques construits pour expliquer les méthodes.

Décrire précisément ce que l’on compte

Avant toute formule, on précise ce qu’est un résultat : un code, un classement, un groupe de personnes, une suite de tirages. Deux descriptions représentent-elles le même résultat ? Cette question détermine si l’ordre compte.

Un groupe formé d’Amal et de Bilal est le même groupe que celui formé de Bilal et d’Amal. En revanche, le couple responsable Amal, secrétaire Bilal diffère du couple responsable Bilal, secrétaire Amal. Les rôles rendent l’ordre important.

On précise aussi si un même élément peut être utilisé plusieurs fois. Le code $272$ contient deux fois le chiffre $2$ ; il est possible seulement si la répétition est autorisée. Un comité de personnes distinctes ne contient pas deux fois la même personne.

Deux questions avant de choisir une formule

L’ordre compte-t-il ? Intervertir deux éléments change-t-il le résultat ?

La répétition est-elle autorisée ? Un élément peut-il être réutilisé à une autre étape ?

On vérifie ensuite les contraintes : nombre de positions, éléments disponibles, interdictions et cas particuliers.

Additionner des cas ou multiplier des choix

Principe de la somme

Si les résultats se répartissent en cas disjoints, on additionne les nombres de résultats de ces cas. Si une visite peut se faire par $4$ départs en bus ou par $3$ départs en train, choisir exactement un départ donne $4+3=7$ possibilités.

Il faut éviter les doubles comptes. Parmi $18$ membres, $9$ pratiquent le dessin, $7$ la photographie et $3$ les deux. Le nombre pratiquant au moins l’une de ces activités est $9+7-3=13$ : les $3$ membres communs avaient été comptés deux fois. Ceux ne pratiquant aucune des deux sont $18-13=5$.

Principe du produit

Si un choix se fait en étapes successives, avec $n_1$ possibilités à la première étape, puis $n_2$ à la deuxième pour chaque premier choix, et ainsi de suite, le nombre de résultats est $n_1n_2\cdots n_p$. Il faut que le nombre annoncé à chaque étape soit valable après chaque choix précédent autorisé.

Exemple - Un arbre de choix

Une formule comporte une boisson, thé ou jus, puis un sandwich au fromage, aux légumes ou au thon. Il existe $2\times3=6$ formules : chaque feuille de l’arbre correspond à une formule complète.

Figure disponible dans la version PDF ci-dessus.

Si le thé n’autorise que deux sandwichs et le jus en autorise trois, le nombre devient $2+3=5$, et non $2\times3$. L’arbre doit représenter les contraintes réelles, même lorsque ses branches n’ont pas toutes le même nombre de suites possibles.

Choix ordonnés : listes, arrangements et permutations

Listes avec répétition

Pour remplir $p$ positions distinctes avec $n$ éléments disponibles à chaque position, en autorisant les répétitions, on obtient $n^p$ listes. Par exemple, un code de quatre chiffres, zéro autorisé en première position, a $10^4=10\,000$ possibilités. Un nombre à quatre chiffres ne commence pas par zéro : il en existe $9\times10^3=9\,000$.

Arrangements sans répétition

Un arrangement de $p$ éléments parmi $n$ est une liste ordonnée de $p$ éléments distincts. Pour $0\leq p\leq n$, leur nombre est noté $A_n^p$ : $$A_n^p=n(n-1)\cdots(n-p+1)=\frac{n!}{(n-p)!}.$$ Le symbole factorielle est défini par $n!=1\times2\times\cdots\times n$ pour $n\geq1$, et $0!=1$. Une liste vide est unique : $A_n^0=1$.

Exemple - Trois fonctions différentes

Parmi $7$ candidats, on désigne une présidente ou un président, puis un secrétaire, puis un trésorier, sans cumul de fonctions. Le nombre de désignations est $$A_7^3=7\times6\times5=210.$$ Après le premier choix, il reste $6$ personnes ; après le deuxième, il en reste $5$. Choisir seulement le groupe de trois personnes ne suffirait pas, car les fonctions restent à attribuer.

Permutations de tous les éléments

Une permutation ordonne les $n$ éléments distincts d’un ensemble : il y en a $A_n^n=n!$. Ainsi, $5$ ouvrages distincts peuvent être rangés sur une étagère de $5!=120$ façons.

Ces formules supposent des éléments distinguables. Si plusieurs objets sont considérés identiques, les échanger ne crée pas un nouveau résultat : la formule $n!$ ne peut alors être appliquée sans analyser ce que l’on compte.

Choix sans ordre : les combinaisons

Une combinaison de $p$ éléments parmi $n$ est un sous-ensemble contenant $p$ éléments. On ne retient aucun ordre entre eux. Pour $0\leq p\leq n$, le nombre de combinaisons est $$\boxed{C_n^p=\binom np=\frac{n!}{p!(n-p)!}=\frac{A_n^p}{p!}.}$$ En effet, chaque groupe de $p$ éléments donne exactement $p!$ listes ordonnées. Diviser le nombre d’arrangements par $p!$ retire ce comptage répété.

Exemple - Un comité sans fonctions

Parmi $7$ candidats, un comité de $3$ membres peut être choisi de $\binom73=210/6=35$ façons. Les six listes obtenues en permutant les trois membres décrivent toutes le même comité. C’est pourquoi la réponse n’est pas $210$.

Propriétés des nombres de combinaisons

Pour $n\geq1$, on a $$\binom n0=\binom nn=1,\qquad \binom n1=n,\qquad \binom np=\binom n{n-p}.$$ Choisir $p$ personnes revient à désigner les $n-p$ personnes qui restent. La symétrie précédente exprime cette correspondance.

Pour $1\leq p\leq n-1$, la relation de Pascal s’écrit $$\binom np=\binom{n-1}{p-1}+\binom{n-1}p.$$ On distingue un élément particulier. Les groupes qui le contiennent se complètent avec $p-1$ éléments parmi les $n-1$ autres ; ceux qui ne le contiennent pas se choisissent entièrement parmi ces $n-1$ éléments. Les deux cas sont disjoints et couvrent tous les groupes.

$n\backslash p$	$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

Dans cette table, une case intérieure est la somme des deux cases situées au-dessus, dans sa colonne et dans la colonne précédente. Par exemple, $\binom63=\binom52+\binom53=10+10=20$. Les cases laissées vides correspondent ici à $p>n$.

Tirages et contraintes : choisir le bon modèle

Trois modèles de tirage

On dispose de $n$ objets tous distinguables et l’on effectue $p$ choix. Un tirage successif enregistre la suite dans l’ordre. Un tirage simultané choisit un groupe sans ordre. Avec remise, l’objet tiré est replacé avant l’étape suivante ; sans remise, il n’est plus disponible.

Modèle	Condition	Nombre
Successif avec remise	$n\geq1$, $p\geq0$	$n^p$
Successif sans remise	$0\leq p\leq n$	$A_n^p$
Simultané sans remise	$0\leq p\leq n$	$\binom np$

Cette table ne traite pas un choix simultané avec répétition. Elle s’utilise seulement lorsque la description de l’expérience correspond exactement à l’une de ses lignes.

Exemple - Les objets ne sont pas leurs couleurs

Une boîte contient trois jetons distincts $R_1,R_2,B_1$. Tirer successivement deux jetons sans remise produit $3\times2=6$ suites de jetons : $$(R_1,R_2),\ (R_1,B_1),\ (R_2,R_1),\ (R_2,B_1),\ (B_1,R_1),\ (B_1,R_2).$$ Si l’on enregistre seulement les couleurs, on observe trois suites possibles : $RR$, $RB$, $BR$. La suite $BB$ est impossible. Le nombre de suites de couleurs n’est donc pas le nombre de suites de jetons.

Exactement, au moins, aucun

Pour former un groupe avec exactement $r$ éléments d’une première catégorie et $s$ d’une seconde catégorie disjointe, on choisit séparément les deux parties, puis on multiplie les nombres de choix.

Pour compter les groupes contenant au moins un élément d’une catégorie, il peut être plus simple de compter tous les groupes puis de retirer ceux qui n’en contiennent aucun. Cette soustraction est valide parce que les groupes exclus forment précisément le complément des groupes recherchés.

Contrôler une réponse

Une réponse est un entier positif ou nul. Elle ne dépasse pas le nombre total de résultats sans contrainte. On peut vérifier les petits cas par une liste ou un arbre. Une formule correcte appliquée à un modèle mal choisi donne une réponse incorrecte.

Exercices entièrement corrigés

Exercice 1 - Combiner somme et produit

Pour aller à une exposition, on choisit l’un de $4$ départs en bus ou l’un de $2$ départs en train. Pour chaque départ, $3$ visites guidées différentes sont proposées. Combien de programmes composés d’un départ et d’une visite peut-on former ? Si un départ précis en bus ne permet qu’une seule visite, quel devient le total ?

Correction. Les départs en bus et en train sont des choix distincts : il y en a $4+2=6$. Au départ, chaque choix permet trois visites, donc le total est $6\times3=18$ programmes. Après la restriction, cinq départs permettent trois visites et un seul départ permet une visite : $5\times3+1=16$. On a retiré exactement les deux programmes devenus impossibles.

Exercice 2 - Des codes et leurs contraintes

Un code comporte deux lettres choisies parmi $A,B,C,D,E,F$, suivies de trois chiffres parmi $0,1,\ldots,9$. Le zéro est autorisé en première position numérique. Compter les codes lorsque toutes les répétitions sont autorisées, puis lorsque les lettres doivent être différentes et les trois chiffres deux à deux différents.

Correction. Les positions sont distinctes, donc l’ordre compte. Avec répétition, on obtient $6^2\times10^3=36\,000$ codes. Dans le second cas, les lettres donnent $6\times5$ possibilités et les chiffres $10\times9\times8$. Le nombre est $$(6\times5)(10\times9\times8)=21\,600.$$ Les contraintes portent séparément sur les lettres et les chiffres. Il n’y a aucune raison d’interdire le chiffre $0$, car l’objet demandé est un code, pas un entier à trois chiffres.

Exercice 3 - Nombres pairs à trois chiffres

Avec les chiffres $0,1,2,3,4,5,6$, combien peut-on former de nombres pairs à trois chiffres distincts ?

Correction. Le chiffre des unités doit être $0$, $2$, $4$ ou $6$. On sépare deux cas, car la présence de zéro modifie le choix des centaines.

Si les unités valent $0$, les centaines ont $6$ choix non nuls, puis les dizaines $5$ choix parmi les chiffres restants : $6\times5=30$ nombres.

Si les unités valent $2$, $4$ ou $6$, il y a $3$ choix pour cette position. Les centaines ont $5$ choix : ni zéro ni le chiffre déjà utilisé. Les dizaines ont ensuite $5$ choix, zéro compris. On obtient $3\times5\times5=75$ nombres. Les deux cas sont disjoints, donc le total est $30+75=105$.

Exercice 4 - Un podium

Huit personnes participent à un concours sans égalité de classement. Compter les podiums de trois personnes. Combien contiennent Amal ? Combien placent Amal en première position ?

Correction. Les places sont ordonnées, sans répétition : le total est $A_8^3=8\times7\times6=336$. Si Amal est sur le podium, sa place a $3$ choix ; les deux places restantes se remplissent avec deux personnes distinctes parmi les $7$ autres, soit $7\times6$ choix. On obtient $3\times7\times6=126$. Si Amal est première, sa place est fixée : il reste $7\times6=42$ podiums. Les $126$ podiums se répartissent bien en trois cas disjoints de $42$ selon sa place.

Exercice 5 - Deux ouvrages voisins

On range six ouvrages distincts sur une étagère, dont deux ouvrages nommés $A$ et $B$. Compter les rangements où $A$ et $B$ sont côte à côte, puis ceux où ils ne le sont pas. Compter enfin tous les rangements où $A$ se trouve avant $B$, sans condition de voisinage.

Correction. Lorsque $A$ et $B$ restent voisins, on traite leur paire comme un bloc. Avec les quatre autres ouvrages, cela donne cinq objets à ordonner, soit $5!$ rangements de blocs. Dans le bloc, l’ordre est $AB$ ou $BA$ : il y a donc $2\times5!=240$ rangements. Sans contrainte, il existe $6!=720$ rangements ; ceux où les deux ouvrages sont séparés sont $720-240=480$.

Pour la dernière question, échanger les positions de $A$ et $B$ associe chaque rangement où $A$ précède $B$ à un unique rangement où $B$ précède $A$. Les deux nombres sont égaux et leur somme vaut $720$. Chacun vaut donc $360$.

Exercice 6 - Choisir un comité

Un groupe comporte $4$ élèves d’un atelier de théâtre et $5$ élèves d’un atelier d’écriture. Ces deux catégories sont disjointes. On choisit un comité de trois membres sans fonctions distinctes. Compter tous les comités, ceux contenant exactement deux élèves de théâtre, puis ceux contenant au moins un élève d’écriture.

Correction. L’ordre n’intervient pas : il y a $\binom93=84$ comités. Pour avoir exactement deux élèves de théâtre, on choisit deux personnes parmi les quatre, puis une parmi les cinq de l’autre atelier : $$\binom42\binom51=6\times5=30.$$ Pour avoir au moins un élève d’écriture, on exclut seulement les comités formés de trois élèves de théâtre. Leur nombre est $\binom43=4$. Le nombre recherché est $84-4=80$. Le complément évite d’additionner séparément les cas avec un, deux ou trois élèves d’écriture.

Exercice 7 - Trois descriptions d’un tirage

Une boîte contient neuf jetons numérotés, dont cinq rouges et quatre bleus. On en choisit trois. Compter les résultats possibles et ceux contenant exactement deux rouges dans chacun des modèles : tirage simultané sans remise ; tirage successif sans remise ; tirage successif avec remise.

Correction. Les numéros distinguent les jetons, même lorsqu’ils ont la même couleur.

Simultanément, sans remise : le total est $\binom93=84$. Choisir deux rouges et un bleu donne $\binom52\binom41=10\times4=40$ groupes.

Successivement, sans remise : le total est $9\times8\times7=504$ suites. On choisit la position du bleu de trois façons, le jeton bleu de quatre façons, puis les deux rouges ordonnés de $5\times4$ façons. Le nombre est $3\times4\times5\times4=240$. Il vaut aussi $40\times3!$, car chacun des groupes précédents comporte trois jetons distincts.

Successivement, avec remise : le total est $9^3=729$. Pour exactement deux rouges, on choisit la position du bleu ($3$), le bleu ($4$), puis chaque rouge ($5$ à chaque fois, car le premier est remis). Le nombre est $3\times4\times5^2=300$. On ne multiplie pas le nombre de groupes du premier modèle par $3!$ : les répétitions autorisées ont changé les objets possibles.

Si l’on ne conserve que les couleurs, exactement deux rouges donnent seulement trois suites : $RRB$, $RBR$, $BRR$. Ce sont des objets différents des suites de jetons numérotés.

Exercice 8 - Exploiter les combinaisons

Une association peut former $45$ binômes distincts avec ses $n$ membres, où $n\geq2$. Déterminer $n$. Puis vérifier $\binom63$ à l’aide de la relation de Pascal et expliquer $\binom{10}8=\binom{10}2$ sans développer de factorielles.

Correction. Un binôme est un groupe sans ordre, donc $$\binom n2=45\iff\frac{n(n-1)}2=45\iff n^2-n-90=0.$$ Comme $n^2-n-90=(n-10)(n+9)$, les solutions algébriques sont $10$ et $-9$. La condition $n\geq2$ impose $n=10$. La vérification donne $10\times9/2=45$.

La relation de Pascal donne $\binom63=\binom52+\binom53=10+10=20$. Enfin, choisir huit membres parmi dix revient à choisir les deux membres absents. Ainsi $\binom{10}8=\binom{10}2=45$.

Exercice 9 - Un groupe puis un rôle distinct

Parmi six personnes, on choisit deux délégués sans distinction entre eux, puis un secrétaire parmi les quatre personnes restantes. Combien de désignations obtient-on ? Pourquoi $A_6^3$ n’est-il pas la bonne réponse ?

Correction. Le groupe des deux délégués se choisit de $\binom62=15$ façons. Pour chaque groupe, quatre personnes peuvent être secrétaires : le total est $15\times4=60$.

Le calcul $A_6^3=120$ attribuerait un premier rôle et un second rôle distincts aux deux délégués. Chaque désignation réelle serait comptée deux fois, en échangeant ces deux personnes. Diviser $120$ par $2!$ redonne $60$. On peut aussi choisir d’abord le secrétaire ($6$ choix), puis deux délégués parmi les cinq autres : $6\binom52=60$.

Exercice 10 - Chemins sur un quadrillage

On va de $O(0;0)$ à $B(4;3)$ par des déplacements d’une unité vers la droite ou vers le haut. Compter tous les chemins, ceux passant par $P(2;1)$, puis ceux évitant $P$.

Figure disponible dans la version PDF ci-dessus.

Le tracé bleu illustre un chemin autorisé passant par $P$.

Correction. Chaque chemin comporte exactement quatre pas vers la droite et trois vers le haut, donc sept pas. Il est entièrement déterminé par les trois positions des pas vers le haut parmi les sept : il y a $\binom73=35$ chemins.

Pour atteindre $P$, il faut deux pas vers la droite et un vers le haut, soit $\binom31=3$ préfixes possibles. De $P$ à $B$, il reste deux pas vers la droite et deux vers le haut, soit $\binom42=6$ suffixes. Chaque préfixe peut se combiner avec chaque suffixe ; cette décomposition est unique. Il y a donc $3\times6=18$ chemins passant par $P$. Ceux qui l’évitent sont les autres : $35-18=17$.

Méthode de travail

Définir les résultats et leurs différences ; préciser ordre et répétition ; organiser les choix ou les cas ; appliquer la formule avec ses conditions ; terminer par une phrase donnant ce qui a été compté. Une liste courte, un arbre ou une deuxième méthode permet souvent de contrôler le résultat.