Exercices corrigés : combinatoire et dénombrement (Terminale spécialité)

Composer un menu, c'est faire trois choix SUCCESSIFS et indépendants : l'entrée n'influence pas les plats disponibles. Le principe multiplicatif donne $4\times 6\times 3=72$ menus. Le mot clé qui déclenche la multiplication est « et » : une entrée ET un plat ET un dessert.

Les deux formules sont EXCLUSIVES, un client prenant l'une ou l'autre mais pas les deux, et l'on additionne donc les deux comptages : $4\times 6+6\times 3=24+18=42$ formules. Le mot clé est ici « ou ». Il faut retenir la double règle qui structure tout le chapitre : le principe multiplicatif s'applique à l'intérieur d'un cas, entre des choix successifs, et le principe additif entre des cas disjoints. Une vérification s'impose toujours avant d'additionner, celle de la disjonction : si un même objet pouvait relever des deux cas, il serait compté deux fois, comme le montrera l'exercice 9.

Chaque position de lettre offre $26$ choix et chaque position de chiffre en offre $10$, la répétition étant autorisée puisque rien ne l'interdit : $26^{3}\times 10^{3}=17\,576\times 1\,000=17\,576\,000$ plaques. L'exposant compte les POSITIONS et la base compte les VALEURS disponibles ; l'inversion des deux est une erreur si fréquente qu'elle fait l'objet d'une question entière à l'exercice 9.

Les trois lettres forment maintenant une liste SANS répétition : la première offre $26$ choix, la deuxième seulement $25$ puisqu'une lettre est déjà utilisée, la troisième $24$. Cela donne $26\times 25\times 24=15\,600$ possibilités pour les lettres, puis $15\,600\times 1\,000=15\,600\,000$ plaques au total. On en perd donc $1\,976\,000$, soit environ $11{,}2\ \%$ du total.

Trois choix libres parmi $8$, la répétition étant autorisée : $8^{3}=512$ listes. On parle de $p$-uplet, ou de liste avec répétition, et le modèle est celui du tirage AVEC REMISE.

Sans répétition, chaque tirage réduit le réservoir d'une unité : $8\times 7\times 6=336$ listes. En factorielles, ce produit s'écrit $\frac{8!}{5!}=\frac{40\,320}{120}=336$, l'écriture $\frac{n!}{(n-k)!}$ signifiant qu'on prend le produit descendant depuis $n$ et qu'on ÉLAGUE les facteurs de trop. Cette écriture n'est pas plus pratique à calculer que le produit direct, mais elle est indispensable pour la relation démontrée à l'exercice 6.

Un podium est exactement une liste de $3$ coureurs distincts pris parmi $8$, car l'ordre des médailles COMPTE, l'or n'étant pas l'argent, et un coureur ne peut occuper deux places : $8\times 7\times 6=336$ podiums. C'est rigoureusement le même calcul qu'en b), sur un autre habillage. Ce constat est le cœur du chapitre : les énoncés varient à l'infini, les modèles sont au nombre de quatre, et tout l'exercice consiste à reconnaître lequel s'applique.

Il y a $10^{4}=10\,000$ codes au total, chaque position offrant $10$ chiffres avec répétition. Les codes à chiffres deux à deux distincts sont au nombre de $10\times 9\times 8\times 7=5\,040$. La probabilité vaut donc $\frac{5\,040}{10\,000}=0{,}504$, soit à peine plus d'une chance sur deux. La situation étant d'équiprobabilité, on est bien fondé à calculer le quotient des cardinaux.

Ranger $7$ livres différents, c'est les PERMUTER : $7!=5\,040$ rangements. Une permutation n'est qu'un cas particulier de liste sans répétition, celui où l'on prend tous les éléments, avec $k=n$.

Le mot TRIANGLE comptant $8$ lettres deux à deux distinctes, il possède $8!=40\,320$ anagrammes. L'hypothèse de distinction est cruciale : pour un mot comportant des lettres répétées, comme MATHEMATIQUES, il faudrait diviser par les factorielles des multiplicités, sans quoi on compterait plusieurs fois la même anagramme.

Les voyelles de TRIANGLE sont I, A et E, soit $3$ voyelles pour $5$ consonnes. On choisit la première lettre parmi ces $3$, puis on permute librement les $7$ lettres restantes : $3\times 7!=3\times 5\,040=15\,120$ anagrammes. Contrôle de cohérence : cela représente exactement $\frac{3}{8}$ du total, ce qui est conforme à l'intuition puisque chaque lettre a la même chance d'occuper la première place ✓.

On applique la méthode du BLOC, qui est le geste à retenir pour toutes les contraintes d'adjacence. On agglomère les $3$ voyelles en un seul objet ; il reste alors $6$ objets à permuter, à savoir le bloc et les $5$ consonnes T, R, N, G et L, soit $6!$ dispositions. Mais à l'intérieur du bloc, les $3$ voyelles peuvent encore être permutées de $3!$ façons, et ces permutations internes donnent des mots différents. Le total est donc $6!\times 3!=720\times 6=4\,320$ anagrammes, soit environ $10{,}7\ \%$ du total.

Un groupe de travail n'a pas de hiérarchie : l'ordre à l'intérieur du groupe ne compte PAS, et l'on utilise donc une combinaison. $\binom{30}{4}=\frac{30\times 29\times 28\times 27}{4!}=\frac{657\,720}{24}=27\,405$ groupes. La technique de calcul à la main mérite d'être notée : on écrit au numérateur $k$ facteurs descendants depuis $n$, et au dénominateur $k!$, ce qui évite de manipuler $30!$, un nombre à trente-trois chiffres.

Ici l'ordre COMPTE, car les trois rôles ne sont pas interchangeables : être président n'est pas être trésorier. On dénombre donc une liste sans répétition : $30\times 29\times 28=24\,360$ bureaux. Comparaison éclairante avec $\binom{30}{3}=4\,060$ : le rapport vaut exactement $\frac{24\,360}{4\,060}=6=3!$, qui est le nombre de façons de distribuer trois rôles distincts à un trio donné.

Une poignée de main est une PAIRE non ordonnée, puisque A serrant la main de B est le même événement que B serrant la main de A : $\binom{10}{2}=\frac{10\times 9}{2}=45$ poignées de main. La division par $2$ corrige précisément le double comptage qu'aurait produit le raisonnement naïf « chacune des $10$ personnes serre $9$ mains ».

Choisir les $26$ élèves qui font partie de la délégation revient EXACTEMENT à choisir les $4$ qui n'en font pas partie : les deux comptages décrivent la même situation vue des deux côtés, et à chaque choix de $26$ correspond un unique choix de $4$, et réciproquement. D'où la symétrie $\binom{n}{k}=\binom{n}{n-k}$, ici $\binom{30}{26}=\binom{30}{4}=27\,405$.

Construire une partie de $E$, c'est prendre chaque élément l'un après l'autre et décider s'il y appartient OU NON : deux choix indépendants, répétés $5$ fois. Le principe multiplicatif donne $2^{5}=32$ parties. Ce raisonnement, qui remplace une énumération fastidieuse par une suite de décisions binaires, est le prototype du dénombrement par choix. L'ensemble vide, obtenu en refusant tous les éléments, et $E$ lui-même, obtenu en les acceptant tous, sont bien comptés parmi les $32$.

On classe les parties par cardinal : $\binom{5}{0}=1$ pour la partie vide, $\binom{5}{1}=5$, $\binom{5}{2}=10$, $\binom{5}{3}=10$, $\binom{5}{4}=5$ et $\binom{5}{5}=1$. La somme vaut $1+5+10+10+5+1=32$, en accord avec a) ✓. On vient d'illustrer l'identité $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$, et surtout de la DÉMONTRER : les deux questions comptent le même ensemble de deux manières, globalement puis par tranches, et l'égalité des résultats est automatique.

Un cardinal pair correspond à $k\in\{0\,;\,2\,;\,4\}$, d'où $1+10+5=16$ parties. On obtient exactement la moitié du total, et ce n'est pas une coïncidence : $16=2^{4}=2^{5-1}$. Les parties de cardinal impair sont elles aussi au nombre de $5+10+1=16$ ✓, et l'égalité vaut pour tout ensemble NON VIDE, ce que l'exercice 8 démontrera par le binôme.

On cherche $n$ tel que $2^{n}=1\,024$. Comme $2^{10}=1\,024$, l'ensemble possède $10$ éléments. On peut aussi le lire comme une équation logarithmique, $n=\frac{\ln 1\,024}{\ln 2}=10$, mais la reconnaissance directe des puissances de $2$ est plus rapide et il vaut la peine de les connaître jusqu'à $2^{10}$.

On tire avec REMISE et l'on note l'ordre de sortie : l'ordre compte, la répétition est possible. C'est une liste de $3$ éléments parmi $10$ avec répétition, soit $10^{3}=1\,000$ résultats. La remise est ce qui rend la répétition possible ; c'est le seul détail de l'énoncé à surveiller.

On tire SANS remise en notant l'ordre : l'ordre compte, la répétition est impossible. C'est une liste sans répétition, soit $10\times 9\times 8=720$ résultats, ce qui s'écrit aussi $\frac{10!}{7!}$.

On retire les trois boules d'un seul coup : il n'y a plus d'ordre de sortie, et une boule ne peut évidemment pas être prise deux fois. L'ordre ne compte pas, la répétition est impossible : c'est une combinaison, $\binom{10}{3}=\frac{10\times 9\times 8}{3!}=\frac{720}{6}=120$ résultats.

On constate que $720=120\times 6=120\times 3!$. L'explication est directe : à chaque poignée de $3$ boules correspondent $3!=6$ ordres de sortie possibles, de sorte que le tirage successif sans remise compte SIX FOIS chaque poignée. C'est la relation générale $\frac{n!}{(n-k)!}=\binom{n}{k}\times k!$, et c'est elle qui justifie le $k!$ au dénominateur de la combinaison : la combinaison n'est rien d'autre que la liste ordonnée dont on a effacé l'ordre.

Le comité n'a pas de rôles distincts, donc l'ordre ne compte pas : $\binom{13}{5}=1\,287$ comités.

On décompose en deux choix indépendants, puis on multiplie : $3$ femmes parmi $7$, soit $\binom{7}{3}=35$, et $2$ hommes parmi $6$, soit $\binom{6}{2}=15$. Le principe multiplicatif donne $35\times 15=525$ comités. La règle de rédaction à respecter est de traiter séparément chaque catégorie et de MULTIPLIER les comptages ; additionner reviendrait à compter des comités qui n'auraient que des femmes ou que des hommes.

« Au moins une » appelle presque toujours le passage par l'événement CONTRAIRE, qui est ici « aucune femme », c'est-à-dire un comité entièrement masculin : $\binom{6}{5}=6$ comités. Il reste $1\,287-6=1\,281$ comités comptant au moins une femme. Le comptage direct aurait exigé la somme des cinq cas, avec $1$, $2$, $3$, $4$ puis $5$ femmes, soit cinq produits de combinaisons au lieu d'une soustraction.

Ici le contraire n'est pas plus court, car il compte trois cas lui aussi. On somme donc directement les trois cas DISJOINTS. Trois femmes : $\binom{7}{3}\binom{6}{2}=35\times 15=525$. Quatre femmes : $\binom{7}{4}\binom{6}{1}=35\times 6=210$. Cinq femmes : $\binom{7}{5}\binom{6}{0}=21\times 1=21$, le facteur $\binom{6}{0}=1$ correspondant à l'unique façon de ne choisir aucun homme. Total : $525+210+21=756$ comités.

Première façon : on choisit le comité, $\binom{13}{5}=1\,287$ possibilités, puis son président parmi ses $5$ membres et son secrétaire parmi les $4$ restants.

Le principe multiplicatif donne $1\,287\times 5\times 4=25\,740$ bureaux. Les deux rôles sont distincts : ici l'ordre compte, c'est un arrangement de $2$ parmi $5$.

Seconde façon : président et secrétaire parmi les $13$ membres, $13\times 12=156$ possibilités, puis les $3$ autres membres du comité parmi les $11$ restants, $\binom{11}{3}=165$.

On retrouve $156\times 165=25\,740$ : les deux comptages décrivent le même ensemble de bureaux.

Piège : écrire $\binom{13}{2}$ pour le président et le secrétaire. Cela compterait des paires sans rôle, et diviserait le résultat par $2$.

Un comité contenant Alice est formé d'Alice et de $4$ membres parmi les $12$ autres : $\binom{12}{4}=495$ comités, donc $P(A)=\frac{495}{1\,287}=\frac{5}{13}\approx 0{,}3846$.

Par symétrie, $P(B)=\frac{5}{13}$ : chaque membre a $5$ chances sur $13$ d'être élu, puisque $5$ places sont à pourvoir pour $13$ membres.

Un comité contenant Alice et Bruno est complété par $3$ membres parmi les $11$ autres : $\binom{11}{3}=165$, donc $P(A\cap B)=\frac{165}{1\,287}=\frac{5}{39}\approx 0{,}1282$.

Or $P(A)\times P(B)=\frac{25}{169}\approx 0{,}1479\ne\frac{5}{39}$ : $A$ et $B$ ne sont pas indépendants.

Lecture : $P_{A}(B)=\frac{P(A\cap B)}{P(A)}=\frac{4}{12}=\frac{1}{3}<\frac{5}{13}$. Si Alice occupe une place, il en reste $4$ pour $12$ candidats : sa présence réduit les chances de Bruno.

Piège : conclure à l'indépendance parce qu'Alice et Bruno « ne s'influencent pas ». L'indépendance se démontre par le calcul, et les places limitées créent ici une dépendance.

$F+H=5$, donc $F-H=2F-5$ est impair : $T=|2F-5|$ vaut $5$ pour $F=0$ ou $F=5$, $3$ pour $F=1$ ou $F=4$, $1$ pour $F=2$ ou $F=3$.

Nombre de comités selon $F$, comme en b) : $\binom{7}{F}\binom{6}{5-F}$, soit $6$, $105$, $420$, $525$, $210$ et $21$ pour $F$ allant de $0$ à $5$.

$P(T=1)=\frac{420+525}{1\,287}=\frac{945}{1\,287}=\frac{105}{143}\approx 0{,}7343$.

$P(T=3)=\frac{105+210}{1\,287}=\frac{315}{1\,287}=\frac{35}{143}\approx 0{,}2448$.

$P(T=5)=\frac{6+21}{1\,287}=\frac{27}{1\,287}=\frac{3}{143}\approx 0{,}0210$.

Contrôle : $945+315+27=1\,287$. Les cas $F=k$ et $F=5-k$ ont des effectifs différents ($525$ et $420$ par exemple), parce que le club compte plus de femmes que d'hommes : on additionne, on ne double pas.

$E(T)=1\times\frac{945}{1\,287}+3\times\frac{315}{1\,287}+5\times\frac{27}{1\,287}=\frac{945+945+135}{1\,287}=\frac{2\,025}{1\,287}=\frac{225}{143}\approx 1{,}5734$.

En moyenne, sur un grand nombre de tirages, l'écart à la parité vaut un peu plus de $1{,}5$ : la plupart des comités sont à $3$ contre $2$, et un sur quatre environ est à $4$ contre $1$.

Sachant $T=1$, le comité compte $3$ femmes et $2$ hommes, ou $2$ femmes et $3$ hommes. Les femmes sont majoritaires dans le premier cas.

$P_{T=1}(F=3)=\frac{P(F=3)}{P(T=1)}=\frac{525}{945}=\frac{5}{9}\approx 0{,}5556$.

Le résultat dépasse $\frac{1}{2}$ : les deux répartitions sont aussi équilibrées l'une que l'autre, mais le club compte $7$ femmes pour $6$ hommes, et $\binom{7}{3}\binom{6}{2}=525$ dépasse $\binom{7}{2}\binom{6}{3}=420$.

Piège : répondre $\frac{1}{2}$ par symétrie. La symétrie entre femmes et hommes n'existe pas dans ce club.

$\binom{6}{2}=15$ et $\binom{6}{3}=20$, donc la somme vaut $35$. Et $\binom{7}{3}=35$ ✓. La formule est vérifiée sur ce cas, ce qui ne la démontre évidemment pas, mais rassure sur son énoncé.

Soit $E$ un ensemble à $n$ éléments et $a$ l'un d'eux, fixé une fois pour toutes. Les parties de $E$ à $k$ éléments se répartissent en deux familles DISJOINTES selon qu'elles contiennent $a$ ou non. Celles qui contiennent $a$ : il reste à choisir les $k-1$ autres éléments parmi les $n-1$ restants, il y en a donc $\binom{n-1}{k-1}$. Celles qui ne contiennent pas $a$ : les $k$ éléments sont tous pris parmi les $n-1$ autres, il y en a $\binom{n-1}{k}$. Comme toute partie à $k$ éléments appartient à exactement une des deux familles, la partition est complète et le principe additif donne $\binom{n-1}{k-1}+\binom{n-1}{k}=\binom{n}{k}$.

$(x+2)^{5}=\sum_{k=0}^{5}\binom{5}{k}x^{k}2^{5-k}=x^{5}+10x^{4}+40x^{3}+80x^{2}+80x+32$. Le détail du coefficient de $x^{2}$, souvent raté : il vaut $\binom{5}{2}\times 2^{5-2}=10\times 8=80$. Deux contrôles rapides valident le développement : la somme des coefficients doit valoir $(1+2)^{5}=243$, et l'on a bien $1+10+40+80+80+32=243$ ✓ ; le terme constant doit valoir $2^{5}=32$ ✓.

En prenant $a=b=1$ dans $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$, il vient $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$, ce qui redonne par une tout autre voie le nombre de parties d'un ensemble à $n$ éléments établi à l'exercice 5. En prenant $a=-1$ et $b=1$, on obtient $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=(1-1)^{n}=0^{n}=0$ pour $n\geq 1$.

Faux. Sans distribution de rôles, l'ordre ne compte pas et la réponse est $\binom{20}{3}=1\,140$. Le produit $20\times 19\times 18=6\,840$ correspond au comptage des trios ORDONNÉS, et il compte donc chaque trio $3!=6$ fois, une fois par ordre d'énumération : on vérifie que $6\,840=6\times 1\,140$ ✓. La question à se poser est toujours la même : deux réponses contenant les mêmes personnes rangées autrement décrivent-elles la même situation ? Ici oui, donc combinaison.

Faux. Les coefficients binomiaux ne croissent pas indéfiniment : la ligne $n$ du triangle de Pascal croît jusqu'à son MILIEU puis décroît, par la symétrie $\binom{n}{k}=\binom{n}{n-k}$ établie à l'exercice 4. Ici $\binom{10}{6}=210$ et $\binom{10}{7}=120$, l'inégalité annoncée est donc inversée. Le maximum de la ligne est atteint en $k=5$, avec $\binom{10}{5}=252$. On aurait d'ailleurs pu conclure sans calcul par la symétrie : $\binom{10}{7}=\binom{10}{3}$ et $\binom{10}{6}=\binom{10}{4}$, et il est clair que choisir $4$ objets offre plus de possibilités que d'en choisir $3$ dans cette zone de la ligne.

Faux, la base et l'exposant ont été intervertis. Il y a $4$ POSITIONS, chacune offrant $10$ VALEURS, donc $10^{4}=10\,000$ codes. La valeur annoncée, $4^{10}=1\,048\,576$, est plus de cent fois trop grande et ne compte rien qui figure dans l'énoncé. Le contrôle mental qui évite cette erreur est de tester sur un cas minuscule : avec un code à $2$ chiffres, on sait qu'il y a $100$ possibilités, de $00$ à $99$, ce qui vaut $10^{2}$ et non $2^{10}$.

Faux, et c'est le DOUBLE COMPTAGE classique. Le raisonnement « on choisit l'as, puis les quatre autres cartes » compte deux fois une main contenant deux as, selon lequel des deux joue le rôle de l'as désigné, et trois fois une main en contenant trois. Le bon comptage passe par l'événement contraire, comme à l'exercice 7 : $\binom{52}{5}-\binom{48}{5}=2\,598\,960-1\,712\,304=886\,656$ mains contiennent au moins un as. La formule fausse donne $4\times\binom{51}{4}=4\times 249\,900=999\,600$, soit $112\,944$ mains en trop.

Une main est une partie à $5$ éléments d'un ensemble à $52$ éléments, l'ordre de distribution ne comptant pas puisque le joueur range ses cartes comme il veut : $\binom{52}{5}=2\,598\,960$ mains.

On choisit $2$ as parmi les $4$ et $3$ cartes parmi les $48$ qui ne sont pas des as, puis on multiplie : $\binom{4}{2}\times\binom{48}{3}=6\times 17\,296=103\,776$ mains. La probabilité vaut $\frac{103\,776}{2\,598\,960}\approx 0{,}0399$, soit environ $4\ \%$. Le point à surveiller est de bien prendre les trois autres cartes parmi $48$ et non parmi $50$ : sinon on autoriserait un troisième as et l'on compterait plusieurs fois les mêmes mains, exactement comme au piège de l'exercice 9.

On construit le full en quatre étapes. Hauteur du brelan : $13$ possibilités. Ses $3$ cartes parmi les $4$ de cette hauteur : $\binom{4}{3}=4$. Hauteur de la paire, choisie parmi les $12$ hauteurs restantes : $12$ possibilités. Ses $2$ cartes parmi $4$ : $\binom{4}{2}=6$. Total : $13\times 4\times 12\times 6=3\,744$ fulls, de probabilité $\frac{3\,744}{2\,598\,960}\approx 0{,}00144$, soit environ une main sur $694$. Attention à ne pas écrire $\binom{13}{2}$ pour le choix des deux hauteurs : le brelan et la paire ne sont PAS interchangeables, un full de rois par les dames n'étant pas un full de dames par les rois, et l'ordre des deux hauteurs compte donc bel et bien ici.