Dénombrement et choix combinatoires - Cours et exercices corrigés | 1re Bac Sciences économiques et gestion

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 omission ni répétition, utiliser les principes de somme et de produit, choisir entre listes, arrangements, permutations et combinaisons, puis appliquer les identités combinatoires et la formule du binôme. Les situations de commandes, d’équipes et de services sont des modèles scolaires.

Compter les éléments d’un ensemble fini

Le cardinal d’un ensemble fini $E$, noté $|E|$ ou $\operatorname{card}(E)$, est son nombre d’éléments. L’ensemble vide a pour cardinal $0$. Un élément n’est compté qu’une fois, même s’il possède plusieurs propriétés.

Additionner des cas disjoints

Si deux ensembles $A$ et $B$ n’ont aucun élément commun, alors $|A\cup B|=|A|+|B|$. Pour plusieurs cas, on vérifie qu’ils sont deux à deux disjoints et qu’ils couvrent toutes les possibilités à compter.

Si les ensembles se recouvrent, la somme compte les éléments communs deux fois. On corrige par $$\boxed{|A\cup B|=|A|+|B|-|A\cap B|}.$$ Le mot ou est inclusif : appartenir à $A$ ou à $B$ autorise l’appartenance aux deux.

Exemple - Deux canaux de commande

Parmi $200$ clients distincts, $120$ ont commandé en ligne, $95$ en magasin, et $40$ ont utilisé les deux canaux. Le nombre ayant utilisé au moins un canal est $120+95-40=175$.

Il y a $120-40=80$ clients ayant utilisé uniquement le canal en ligne, et $95-40=55$ uniquement le magasin. Les $40$ clients communs ne doivent pas être comptés dans ces catégories exclusives.

Passer par le complément

Si $A\subseteq E$, alors $|E\setminus A|=|E|-|A|$. Dans l’exemple, $200-175=25$ clients n’ont utilisé aucun de ces deux canaux pendant la période étudiée.

Dire exactement ce qui constitue un résultat

Compter des clients, des commandes ou des visites ne donne pas nécessairement le même nombre. Définir les objets comptés, distinguer les objets différents et préciser si plusieurs descriptions représentent un même résultat.

Produit cartésien, choix successifs et arbre

Multiplier des nombres de choix

Si $A$ possède $p$ éléments et $B$ en possède $q$, le produit cartésien $A\times B$ contient les couples $(a,b)$, avec $a\in A$, $b\in B$. Son cardinal est $pq$.

Plus généralement, si chaque étape laisse toujours le même nombre de choix à l’étape suivante, on multiplie les nombres de choix. Une configuration composée de $3$ formats, $2$ couleurs et $4$ modes de livraison donne $3\times2\times4=24$ possibilités.

Exemple - Deux emballages et trois livraisons

Figure disponible dans la version PDF ci-dessus.

Chaque chemin complet décrit exactement une configuration. Il y a $2\times3=6$ feuilles. Si la livraison express était indisponible avec l’emballage cadeau, le total serait $3+2=5$ ; on ne pourrait plus multiplier par $3$ pour chaque emballage.

Listes avec répétition

Une liste ordonnée de longueur $p$ dont chaque terme est choisi parmi $n\ge1$ éléments, avec répétition autorisée, possède $n^p$ possibilités. Chaque position offre $n$ choix indépendants des valeurs déjà utilisées.

Un code de quatre chiffres, avec zéro initial et répétitions autorisés, possède $10^4=10000$ possibilités. Un nombre entier à quatre chiffres en possède seulement $9\times10^3=9000$, car son premier chiffre ne peut pas être zéro.

Une contrainte modifie les étapes

Avant de multiplier, vérifier le nombre de possibilités réellement restantes à chaque étape. Les mots distincts , sans répétition ou premier chiffre non nul changent le calcul.

Arrangements et permutations

Listes ordonnées sans répétition

Un arrangement de $p$ éléments parmi $n$ est une liste ordonnée de $p$ éléments distincts. Pour $0\le p\le n$, $$\boxed{A_n^p=n(n-1)\cdots(n-p+1)=\frac{n!}{(n-p)!}}.$$ La factorielle est $n!=1\times2\times\cdots\times n$ pour $n\ge1$, et on pose $0!=1$. Il existe un arrangement vide, donc $A_n^0=1$. Si $p>n$, aucun arrangement sans répétition n’est possible.

Exemple - Trois fonctions distinctes

Choisir un responsable, un secrétaire et un trésorier parmi $8$ personnes, sans cumul de fonctions, donne $$8\times7\times6=A_8^3=336$$ attributions. L’ordre correspond aux fonctions : échanger le responsable et le secrétaire produit une autre attribution.

Ranger tous les éléments : permutations

Une permutation de $n$ éléments distincts est un arrangement de longueur $n$. Il y en a $A_n^n=n!$. Ainsi, ranger cinq dossiers distincts donne $5!=120$ ordres possibles.

Exemple - Deux dossiers doivent rester voisins

Parmi six dossiers distincts, deux dossiers précis doivent être côte à côte. On les regroupe en un bloc ; ce bloc et les quatre autres dossiers donnent cinq objets à ranger, soit $5!$ ordres. À l’intérieur du bloc, les deux dossiers peuvent être rangés de deux façons. Le total est $2\times5!=240$.

Un premier chiffre particulier

Avec les dix chiffres de $0$ à $9$, un code de trois chiffres distincts possède $10\times9\times8=720$ possibilités si le zéro initial est autorisé. Pour un nombre à trois chiffres distincts, le premier choix n’a que neuf possibilités, puis il reste neuf chiffres dont zéro, puis huit : $9\times9\times8=648$.

Les objets doivent être distincts

La formule $n!$ suppose des objets distinguables. Si certaines lettres ou certains objets deviennent indiscernables, plusieurs permutations décrivent le même résultat. Il faut alors justifier une correction, comme dans le complément de l’exercice 8.

Combinaisons : choisir sans attribuer d’ordre

Une combinaison de $p$ éléments parmi $n$ est une partie de $p$ éléments d’un ensemble à $n$ éléments. Changer l’ordre d’énumération ne change pas la partie choisie.

Passer des arrangements aux parties

Chaque partie de $p$ éléments distincts peut être ordonnée de $p!$ façons. Diviser le nombre d’arrangements par ce nombre donne, pour $0\le p\le n$, $$\boxed{C_n^p=\binom np=\frac{A_n^p}{p!}=\frac{n!}{p!(n-p)!}}.$$ Il existe une partie vide et une partie contenant tout l’ensemble : $\binom n0=\binom nn=1$.

Exemple - Même groupe, objets comptés différents

Choisir trois personnes parmi huit pour former une équipe sans rôles particuliers donne $\binom83=56$ équipes. Attribuer trois rôles distincts donnait $336$ possibilités. Chaque équipe de trois correspond à $3!=6$ attributions, et $56\times6=336$.

Séparer des catégories

Une équipe de trois personnes doit contenir exactement deux personnes parmi cinq comptables et une parmi quatre commerciaux. Les personnes sont toutes distinctes et l’ordre ne compte pas. On choisit les deux catégories successivement : $$\binom52\binom41=10\times4=40.$$ Le mot exactement impose ici une composition précise ; il ne signifie pas au moins .

Compter au moins un par complément

Pour choisir une équipe de trois parmi ces neuf personnes avec au moins un comptable, on peut compter toutes les équipes puis retirer celles composées seulement de commerciaux : $$\binom93-\binom43=84-4=80.$$ Les équipes retirées sont exactement celles qui échouent à la condition. Ce complément évite d’additionner séparément les cas contenant un, deux ou trois comptables.

Ne pas multiplier par un ordre absent du problème

Une équipe, une sélection ou un lot d’objets distincts sans positions ni fonctions est une partie. On ne multiplie par $p!$ que si l’on attribue réellement des rôles ou des places qui rendent les ordres différents.

Identités combinatoires et triangle de Pascal

Choisir les retenus ou les exclus

Dans un ensemble à $n$ éléments, choisir les $p$ éléments retenus détermine exactement les $n-p$ exclus. Cette correspondance donne $$\boxed{\binom np=\binom n{n-p}}.$$ Par exemple, choisir sept produits parmi dix revient à choisir les trois produits exclus : $\binom{10}7=\binom{10}3=120$.

L’identité de Pascal

Pour $1\le p\le n-1$, fixons un élément particulier d’un ensemble à $n$ éléments. Les parties de taille $p$ se répartissent en deux cas disjoints :

• celles contenant cet élément : choisir $p-1$ éléments parmi les $n-1$ autres ;

• celles ne le contenant pas : choisir $p$ éléments parmi les $n-1$ autres.

On obtient $$\boxed{\binom np=\binom{n-1}{p-1}+\binom{n-1}p}.$$ Les nombres du triangle se construisent en additionnant les deux nombres situés au-dessus, avec des $1$ sur les bords :

$n\backslash p$	$0$	$1$	$2$	$3$	$4$	$5$
$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$

Une équipe avec un responsable

Pour $1\le p\le n$, on peut choisir une équipe de $p$ personnes puis son responsable de $p$ façons, ou choisir d’abord le responsable parmi $n$, puis les $p-1$ autres membres. Les deux méthodes comptent les mêmes résultats : $$p\binom np=n\binom{n-1}{p-1}.$$ Ce type de double comptage justifie une identité en définissant précisément les objets, sans dépendre seulement d’un calcul de factorielles.

Binôme et nombre de parties

Développer une puissance d’une somme

Pour $n\ge0$ entier et $a,b$ réels, $$\boxed{(a+b)^n=\sum_{p=0}^n\binom np a^{n-p}b^p}.$$ Pour comprendre les coefficients, on développe les $n$ facteurs $(a+b)$. Un terme contenant $p$ facteurs $b$ et $n-p$ facteurs $a$ s’obtient en choisissant les $p$ positions de $b$ parmi $n$, soit $\binom np$ choix. Le cas $n=0$ correspond à l’identité $1=1$.

Exemple - Une puissance quatrième

$$(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4.$$ Avec $a=2x$ et $b=-1$, $$(2x-1)^4=16x^4-32x^3+24x^2-8x+1.$$ Les signes alternent à cause des puissances de $-1$ ; les puissances de $2$ doivent aussi être conservées.

Toutes les parties d’un ensemble

Pour chacun des $n$ éléments d’un ensemble, on choisit de le retenir ou de ne pas le retenir. Ces deux choix successifs donnent $2^n$ parties, en comptant la partie vide et l’ensemble entier.

Les parties se répartissent aussi par taille $p=0,1,\ldots,n$, d’où $$\boxed{\sum_{p=0}^n\binom np=2^n}.$$ Cette identité se retrouve en posant $a=b=1$ dans le binôme. Pour $n\ge1$, poser $a=1$, $b=-1$ donne également $\sum_{p=0}^n(-1)^p\binom np=0$.

Choisir le bon modèle

Objet compté	Nombre
Liste de $p$ choix, répétition autorisée	$n^p$
Liste de $p$ éléments distincts	$A_n^p$
Ordre de tous les $n$ éléments distincts	$n!$
Partie de $p$ éléments parmi $n$	$\binom np$
Partie de taille quelconque	$2^n$

Les formules de listes et de parties supposent les conventions précisées dans leurs définitions. Une contrainte supplémentaire peut imposer une séparation en cas, un complément ou un regroupement en blocs.

Exercices corrigés

Exercice 1 - Deux listes de clients

Parmi $240$ clients distincts, $150$ reçoivent un courriel, $120$ un SMS et $55$ reçoivent les deux. Combien reçoivent au moins un message, aucun message, ou exactement un des deux types ?

Solution. La réunion contient $150+120-55=215$ clients. Il en reste $240-215=25$ sans message. Ceux recevant seulement un courriel sont $150-55=95$, et ceux recevant seulement un SMS sont $120-55=65$. Les deux catégories sont disjointes : exactement un type de message concerne $95+65=160$ clients. Vérification : $160+55+25=240$.

Exercice 2 - Une option facultative

Une offre prévoit trois plats, deux boissons et deux desserts. Combien de menus peut-on former avec un choix de chaque catégorie ? Et si l’on peut choisir de ne pas prendre de dessert ?

Solution. Avec un dessert obligatoire, le principe du produit donne $3\times2\times2=12$ menus. Avec le dessert facultatif, la dernière étape a trois choix : dessert 1, dessert 2 ou aucun dessert. Il y a $3\times2\times3=18$ menus. On peut aussi compter $12$ menus avec dessert et $3\times2=6$ sans dessert ; ces deux cas sont disjoints.

Exercice 3 - Codes distincts et chiffre zéro

On forme des codes de quatre chiffres distincts pris parmi $0,1,\ldots,9$. Le zéro initial est autorisé. Compter tous les codes, puis ceux contenant zéro. Combien existe-t-il de nombres à quatre chiffres distincts ?

Solution. L’ordre compte et les répétitions sont interdites : il existe $10\times9\times8\times7=5040$ codes. Ceux sans zéro utilisent les neuf autres chiffres : $9\times8\times7\times6=3024$. Le complément donne $5040-3024=2016$ codes contenant zéro.

Pour les nombres à quatre chiffres distincts, le premier chiffre a neuf choix non nuls, puis il reste neuf chiffres dont zéro, puis huit, puis sept : $9\times9\times8\times7=4536$. Parmi eux, $4536-3024=1512$ contiennent zéro, nécessairement à une position autre que la première.

Exercice 4 - Attribuer trois fonctions

Dix personnes distinctes peuvent occuper trois fonctions différentes, sans cumul. Compter les attributions totales, celles où une personne désignée $A$ est responsable de la première fonction, puis celles où $A$ occupe l’une quelconque des trois fonctions.

Solution. Le total est $A_{10}^3=10\times9\times8=720$. Si $A$ occupe la première fonction, il reste $9\times8=72$ choix pour les deux autres.

Si $A$ peut occuper n’importe laquelle des trois fonctions, on choisit sa fonction de trois façons, puis les deux autres titulaires de $9\times8$ façons : $3\times9\times8=216$. Par complément, les attributions sans $A$ sont $9\times8\times7=504$, et $720-504=216$ confirme le résultat.

Exercice 5 - Deux dossiers voisins ou séparés

Sept dossiers distincts doivent être alignés. Combien d’ordres placent deux dossiers désignés $A$ et $B$ côte à côte ? Combien les séparent par au moins un autre dossier ?

Solution. Regrouper $A$ et $B$ en un bloc donne six objets à ranger : le bloc et cinq autres dossiers. Le bloc possède deux ordres internes. Le nombre d’alignements où ils sont voisins est $2\times6!=1440$.

Il existe $7!=5040$ alignements au total. Le complément contient ceux où $A$ et $B$ ne sont pas voisins : $5040-1440=3600$. Dans chaque alignement favorable, le bloc est unique, donc le comptage ne crée pas de double description.

Exercice 6 - Une équipe répartie entre deux services

On choisit quatre personnes parmi six du service $A$ et cinq du service $B$, toutes distinctes. Compter les équipes avec exactement deux personnes de chaque service, puis celles avec au moins une personne de $B$.

Solution. Pour exactement deux de chaque service, on choisit deux personnes parmi six et deux parmi cinq : $$\binom62\binom52=15\times10=150.$$ Pour au moins une de $B$, on retire des $\binom{11}4=330$ équipes totales celles prises uniquement dans $A$, au nombre de $\binom64=15$. Il reste $330-15=315$ équipes. Les membres n’ont pas de fonctions distinctes : aucun facteur $4!$ n’est ajouté.

Exercice 7 - Deux personnes incompatibles

Une équipe de trois est choisie parmi huit personnes, dont deux personnes désignées $A$ et $B$. Elles ne doivent pas être ensemble. Combien d’équipes sont possibles ? Combien contiennent exactement l’une d’elles ?

Solution. Il existe $\binom83=56$ équipes. Les équipes interdites contiennent déjà $A$ et $B$ ; leur troisième membre est choisi parmi les six autres, soit $6$ équipes. Le nombre autorisé est $56-6=50$.

Pour exactement l’une des deux, choisir $A$ ou $B$ de deux façons, puis deux personnes parmi les six autres : $2\binom62=30$. Les équipes ne contenant ni $A$ ni $B$ sont $\binom63=20$. La somme $30+20=50$ contrôle le premier résultat.

Exercice 8 - Complément : lettres répétées

Combien de suites de lettres différentes obtient-on en réordonnant toutes les lettres de COMMERCE , sans exiger de former un mot existant ?

Solution. Il y a huit lettres : deux $C$, deux $M$, deux $E$, un $O$ et un $R$. Si les lettres répétées étaient temporairement étiquetées, on aurait $8!$ permutations.

Pour une même suite visible, on peut échanger les deux étiquettes des $C$, celles des $M$ et celles des $E$, soit $2!\times2!\times2!=8$ descriptions. Toutes les suites visibles ont exactement ce nombre de descriptions. Le nombre recherché est donc $$\frac{8!}{2!\,2!\,2!}=\frac{40320}{8}=5040.$$ La division est justifiée par une multiplicité constante ; diviser sans identifier cette multiplicité pourrait produire un comptage faux.

Exercice 9 - Coefficients du binôme

Développer $(1+2x)^5$, puis donner le coefficient de $x^3$ et la somme de tous les coefficients du polynôme obtenu.

Solution. Le terme de degré $p$ est $\binom5p(2x)^p$. On obtient $$(1+2x)^5=1+10x+40x^2+80x^3+80x^4+32x^5.$$ Le coefficient de $x^3$ vaut $\binom53\,2^3=10\times8=80$. La somme des coefficients est la valeur du polynôme en $x=1$, donc $3^5=243$. Vérification : $1+10+40+80+80+32=243$.

Exercice 10 - Construire des offres de services

Une offre peut contenir n’importe quelle partie de sept services distincts. Compter toutes les offres, celles contenant exactement trois services, celles non vides et celles contenant au moins deux services. Si un service principal doit obligatoirement être inclus, combien d’offres restent possibles ? Parmi elles, combien contiennent au moins trois services au total ?

Solution. Chaque service peut être inclus ou exclu : il existe $2^7=128$ offres, en comptant l’offre vide. Les offres de trois services sont au nombre de $$\binom73=\frac{7\times6\times5}{3\times2\times1}=35.$$ Retirer la partie vide laisse $128-1=127$ offres non vides. Pour au moins deux services, on retire aussi les sept offres à un seul service : $128-1-7=120$.

Si le service principal est imposé, il reste six services pour lesquels le choix inclusion/exclusion est libre. Il y a donc $2^6=64$ offres. Pour avoir au moins trois services au total, il faut choisir au moins deux de ces six services supplémentaires. On retire la sélection vide et les six sélections à un seul service : $$64-1-6=57.$$

Vérification par un autre découpage

Les offres de taille quelconque se répartissent par cardinal : $$\binom70+\binom71+\binom72+\binom73+\binom74+\binom75+\binom76+\binom77 =1+7+21+35+35+21+7+1=128.$$ Avec le service principal fixé et au moins deux autres services, le même raisonnement donne $$\binom62+\binom63+\binom64+\binom65+\binom66=15+20+15+6+1=57.$$ Les deux découpages comptent les mêmes objets et confirment les résultats.

Une méthode fiable de dénombrement

Définir un résultat ; décider si l’ordre et les répétitions comptent ; identifier les contraintes ; choisir un produit, une somme de cas disjoints ou un complément ; vérifier que chaque résultat est compté exactement une fois. Une formule sans modèle explicite est difficile à contrôler.