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

a) Trois étapes indépendantes : $4\times 6\times 3=72$ menus.

b) Les deux formules sont exclusives, on additionne les deux comptages : $4\times 6+6\times 3=24+18=42$ formules. Le principe multiplicatif s'applique à l'intérieur de chaque cas, le principe additif entre les cas.

c) Chaque lettre offre 26 choix et chaque chiffre 10 choix, avec répétition autorisée : $26^{3}\times 10^{3}=17\,576\times 1\,000=17\,576\,000$ plaques.

d) Les lettres forment maintenant une liste sans répétition : $26\times 25\times 24=15\,600$, puis $15\,600\times 1\,000=15\,600\,000$ plaques. On en perd donc $1\,976\,000$, soit environ 11 % du total.

a) Trois choix libres parmi 8 : $8^{3}=512$ listes.

b) $8\times 7\times 6=336$, c'est-à-dire $\frac{8!}{5!}=\frac{40\,320}{120}=336$.

c) Un podium est exactement une liste de 3 coureurs distincts pris parmi 8, car l'ordre des médailles compte : $8\times 7\times 6=336$ podiums. C'est le même calcul qu'en b), sur un autre habillage.

d) Il y a $10^{4}=10\,000$ codes au total et $10\times 9\times 8\times 7=5\,040$ codes à chiffres distincts. La probabilité vaut $\frac{5\,040}{10\,000}=0{,}504$. Un code au hasard a donc à peine plus d'une chance sur deux d'avoir tous ses chiffres différents.

a) Il s'agit d'une permutation de 7 objets : $7!=5\,040$ rangements.

b) $8!=40\,320$ anagrammes.

c) Les voyelles sont O, E et A. 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. C'est bien $\frac{3}{8}$ du total, ce qui est cohérent puisque chaque lettre a la même chance d'occuper la première place.

d) On traite le groupe des 3 voyelles comme un seul bloc. Il reste alors 6 objets à permuter (le bloc et les 5 consonnes M, N, T, R, L), soit $6!$ dispositions, et à l'intérieur du bloc les 3 voyelles peuvent être permutées de $3!$ façons. Total : $6!\times 3!=720\times 6=4\,320$ anagrammes, soit environ 10,7 % du total.

a) L'ordre à l'intérieur du groupe ne compte pas : $\binom{30}{4}=\frac{30\times 29\times 28\times 27}{4!}=\frac{657\,720}{24}=27\,405$ groupes.

b) Ici l'ordre compte, car les trois rôles ne sont pas interchangeables : $30\times 29\times 28=24\,360$ bureaux. Comparez avec $\binom{30}{3}=4\,060$ : le rapport est exactement $3!=6$, le nombre de façons de distribuer les rôles à un trio donné.

c) Une poignée de main est une paire non ordonnée : $\binom{10}{2}=\frac{10\times 9}{2}=45$ poignées de main.

d) 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. D'où la symétrie $\binom{n}{k}=\binom{n}{n-k}$, ici $\binom{30}{26}=\binom{30}{4}=27\,405$.

a) Construire une partie de $E$, c'est décider pour chacun des 5 éléments s'il y appartient ou non : 2 choix indépendants répétés 5 fois, donc $2^{5}=32$ parties. L'ensemble vide et $E$ lui-même sont comptés.

b) $\binom{5}{0}=1$, $\binom{5}{1}=5$, $\binom{5}{2}=10$, $\binom{5}{3}=10$, $\binom{5}{4}=5$, $\binom{5}{5}=1$. Somme : $1+5+10+10+5+1=32$, ce qui illustre $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$.

c) Cardinal pair signifie $k\in\{0\ ;\ 2\ ;\ 4\}$ : $1+10+5=16$ parties. On obtient exactement la moitié du total, et ce n'est pas un hasard : $16=2^{4}$, et le résultat vaut pour tout ensemble non vide.

d) On cherche $n$ tel que $2^{n}=1\,024$. Comme $2^{10}=1\,024$, l'ensemble a 10 éléments.

a) L'ordre compte et 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.

b) L'ordre compte, sans répétition : $10\times 9\times 8=720$ résultats, c'est-à-dire $\frac{10!}{7!}$.

c) L'ordre ne compte pas et il n'y a pas de répétition : $\binom{10}{3}=\frac{10\times 9\times 8}{3!}=\frac{720}{6}=120$ résultats.

d) $720=120\times 6=120\times 3!$. À chaque tirage simultané de 3 boules correspondent $3!=6$ ordres de sortie possibles : le tirage successif sans remise compte donc 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 explique le $k!$ au dénominateur de la combinaison.

a) $\binom{13}{5}=1\,287$ comités.

b) On choisit 3 femmes parmi 7 et 2 hommes parmi 6, puis on applique le principe multiplicatif : $\binom{7}{3}\times\binom{6}{2}=35\times 15=525$ comités.

c) L'événement contraire est « aucune femme », c'est-à-dire un comité entièrement masculin : $\binom{6}{5}=6$. Il reste $1\,287-6=1\,281$ comités. Compter directement aurait exigé la somme des cas 1, 2, 3, 4 et 5 femmes.

d) Trois cas disjoints : 3 femmes, $\binom{7}{3}\binom{6}{2}=525$ ; 4 femmes, $\binom{7}{4}\binom{6}{1}=35\times 6=210$ ; 5 femmes, $\binom{7}{5}\binom{6}{0}=21\times 1=21$. Total $525+210+21=756$ comités. On vérifie que la somme sur les six valeurs possibles du nombre de femmes redonne bien 1 287.

a) $\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.

b) Soit $E$ un ensemble à $n$ éléments et $a$ l'un d'eux. Les parties de $E$ à $k$ éléments se répartissent en deux familles disjointes. Celles qui contiennent $a$ : il reste à choisir $k-1$ éléments parmi les $n-1$ autres, il y en a $\binom{n-1}{k-1}$. Celles qui ne contiennent pas $a$ : les $k$ éléments sont pris parmi les $n-1$ autres, il y en a $\binom{n-1}{k}$. Comme toute partie à $k$ éléments est dans exactement une des deux familles, la somme des deux comptages vaut $\binom{n}{k}$.

c) $(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 coefficient de $x^{2}$ est bien $\binom{5}{2}\times 2^{3}=10\times 8=80$.

d) En prenant $a=b=1$ dans $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$, on obtient $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$, ce qui redonne le nombre de parties d'un ensemble à $n$ éléments. En prenant $a=-1$ et $b=1$, on obtient $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}=(1-1)^{n}=0$ pour $n\geq 1$ : autrement dit, un ensemble non vide a autant de parties de cardinal pair que de cardinal impair.

a) Faux. Sans rôles, l'ordre ne compte pas : la réponse est $\binom{20}{3}=1\,140$. Le produit $20\times 19\times 18=6\,840$ compte chaque trio $3!=6$ fois, une fois par ordre d'énumération, et $6\,840=6\times 1\,140$.

b) Faux. La suite des $\binom{n}{k}$ croît jusqu'au milieu de la ligne puis décroît, par symétrie. Ici $\binom{10}{6}=210$ et $\binom{10}{7}=120$, donc l'inégalité est inversée. Le maximum est atteint en $k=5$ avec $\binom{10}{5}=252$.

c) Faux, la base et l'exposant sont 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 cent fois trop grande et ne correspond à rien dans l'énoncé.

d) Faux : c'est le double comptage classique. Une main contenant deux as est comptée deux fois, selon lequel des deux as joue le rôle de « l'as choisi ». Le bon comptage passe par l'événement contraire : $\binom{52}{5}-\binom{48}{5}=2\,598\,960-1\,712\,304=886\,656$ mains. La formule fausse donne $4\times\binom{51}{4}=4\times 249\,900=999\,600$, soit $112\,944$ mains de trop.

a) Une main est une partie à 5 éléments d'un ensemble à 52 éléments, l'ordre de distribution ne comptant pas : $\binom{52}{5}=2\,598\,960$ mains.

b) On choisit 2 as parmi 4 et 3 cartes parmi les 48 qui ne sont pas des as : $\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 %.

c) On choisit la hauteur du brelan (13 possibilités), puis ses 3 cartes parmi 4, soit $\binom{4}{3}=4$ ; puis la hauteur de la paire parmi les 12 restantes, et ses 2 cartes parmi 4, soit $\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 une main sur 694 environ. Attention à ne pas écrire $\binom{13}{2}$ pour les deux hauteurs : le brelan et la paire ne sont pas interchangeables, l'ordre des deux hauteurs compte ici.

d) Il faut prendre les 4 as, puis une carte quelconque parmi les 48 autres : $\binom{4}{4}\times\binom{48}{1}=48$ mains, de probabilité $\frac{48}{2\,598\,960}\approx 1{,}85\times 10^{-5}$, soit environ une main sur 54 145. Passer de 2 as à 4 as divise la probabilité par plus de 2 000 : chaque as supplémentaire est bien plus coûteux que le précédent, car il faut le prendre dans un vivier de 4 cartes seulement alors que les cartes ordinaires sont 48.