Exercices corrigés : Combinatoire et dénombrement (Terminale)
Dénombrer, c'est compter les éléments d'un ensemble fini sans les énumérer un par un, à l'aide de quelques modèles bien choisis : k-uplets, permutations, combinaisons. Ces outils servent directement en probabilités, où le calcul d'une probabilité en situation d'équiprobabilité se ramène à compter des issues.
Exercice 1 · Calculs de factorielles et de coefficients binomiaux
application●●●
FactorielleCoefficients binomiauxSymétrie des coefficients binomiaux
Calculer sans calculatrice, en simplifiant avant de multiplier :
$6!=6\times5\times4!$, donc $\dfrac{6!}{4!}=6\times5=30$.
On reconnaît $\dfrac{8!}{3!\,(8-3)!}=\binom{8}{3}$. Donc
$$\dfrac{8!}{5!\,3!}=\dfrac{8\times7\times6}{3\times2\times1}=\dfrac{336}{6}=56.$$
$\binom{9}{2}=\dfrac{9\times8}{2}=36$.
Par symétrie, $\binom{12}{10}=\binom{12}{12-10}=\binom{12}{2}=\dfrac{12\times11}{2}=66$.
Comme $0!=1$ : $\binom{7}{0}=\dfrac{7!}{0!\,7!}=1$ et $\binom{7}{7}=\dfrac{7!}{7!\,0!}=1$. On retrouve qu'un ensemble à 7 éléments a une seule partie à 0 élément ($\emptyset$) et une seule partie à 7 éléments (lui-même).
Un code est un 4-uplet d'éléments de $\{0;\ldots;9\}$ : l'ordre compte et les répétitions sont permises. Cet ensemble a 10 éléments, donc il y a $10^4=10\,000$ codes.
Il s'agit de 4-uplets d'éléments distincts d'un ensemble à 10 éléments : $10\times9\times8\times7=5040$ codes.
On passe par le complémentaire. Les codes sans aucun 0 sont les 4-uplets de $\{1;\ldots;9\}$, ensemble à 9 éléments : il y en a $9^4=6561$. Donc le nombre de codes contenant au moins un 0 est
$$10\,000-6561=3439.$$
On choisit la lettre (4 choix), puis un 3-uplet de chiffres ($10^3$ choix). Par le principe multiplicatif : $4\times10^3=4000$ digicodes.
Résultat :
10 000 ; 5040 ; 3439 ; 4000
Exercice 3 · Choisir le bon modèle dans un club
application●●●
Choix du modèle de dénombrementArrangementsCombinaisonsk-upletsPermutations
Un club compte 15 membres.
On élit un président, un secrétaire et un trésorier, trois personnes distinctes. Combien de bureaux sont possibles ?
On désigne une délégation de 3 membres, sans rôle particulier. Combien de délégations sont possibles ?
Les 3 délégués choisis s'inscrivent chacun à un atelier parmi 5 ; plusieurs délégués peuvent choisir le même atelier. On note dans l'ordre (délégué 1, délégué 2, délégué 3) l'atelier choisi par chacun. Combien de répartitions sont possibles ?
On aligne les 15 membres pour une photographie. Combien d'alignements sont possibles ?
Les rôles sont différents : l'ordre compte, et une personne ne peut pas cumuler. C'est un 3-uplet d'éléments distincts d'un ensemble à 15 éléments :
$$15\times14\times13=2730\text{ bureaux}.$$
Sans rôle, l'ordre ne compte pas : une délégation est une partie à 3 éléments de l'ensemble des 15 membres.
$$\binom{15}{3}=\frac{15\times14\times13}{6}=\frac{2730}{6}=455\text{ délégations}.$$
On retrouve $2730=455\times3!$ : chaque délégation donne $3!=6$ bureaux.
Une répartition est un 3-uplet de l'ensemble des 5 ateliers (ordre des délégués fixé, répétitions permises) : $5^3=125$ répartitions.
Un alignement est une permutation de l'ensemble des 15 membres : $15!=1\,307\,674\,368\,000$ alignements, soit environ $1{,}3\times10^{12}$.
Résultat :
2730 ; 455 ; 125 ; 15! = 1 307 674 368 000
Exercice 4 · Prolonger le triangle de Pascal
application●●●
Formule de PascalTriangle de PascalSomme d'une ligne
La ligne $n=6$ du triangle de Pascal est : $1$ ; $6$ ; $15$ ; $20$ ; $15$ ; $6$ ; $1$.
À l'aide de la formule de Pascal, écrire les lignes $n=7$ et $n=8$.
En déduire $\binom{8}{3}$, $\binom{8}{4}$ et $\binom{8}{5}$.
Vérifier la valeur de $\binom{8}{3}$ à l'aide de l'expression $\dfrac{n(n-1)\cdots(n-k+1)}{k!}$.
Calculer la somme des coefficients de la ligne 8 et comparer avec $2^8$.
La suite est réservée aux abonnés. L'abonnement arrive bientôt ; crée ton compte dès maintenant depuis Mon espace.
Exercice 6 · Entiers à trois chiffres
entrainement●●●
Principe multiplicatifDisjonction de casPrincipe additifComplémentaire
On considère les entiers naturels qui s'écrivent avec exactement trois chiffres en base dix, c'est-à-dire de $100$ à $999$. Le premier chiffre n'est donc jamais $0$.
Combien y a-t-il de tels entiers ?
Combien ont leurs trois chiffres deux à deux distincts ?
Combien sont pairs et ont leurs trois chiffres deux à deux distincts ?
Chiffre des centaines : 9 choix (de 1 à 9) ; dizaines : 10 choix ; unités : 10 choix. Par le principe multiplicatif : $9\times10\times10=900$ entiers (on retrouve $999-100+1=900$).
Centaines : 9 choix (non nul). Dizaines : 9 choix (tous les chiffres sauf celui des centaines, 0 compris). Unités : 8 choix. Donc $9\times9\times8=648$ entiers.
Un entier est pair si son chiffre des unités est $0$, $2$, $4$, $6$ ou $8$. On distingue deux cas disjoints.
Unités égales à 0. Centaines : 9 choix (de 1 à 9). Dizaines : 8 choix (ni 0, ni le chiffre des centaines). Soit $9\times8=72$ entiers.
Unités dans $\{2;4;6;8\}$. Unités : 4 choix. Centaines : 8 choix (ni 0, ni le chiffre des unités). Dizaines : 8 choix (tous sauf les deux chiffres déjà utilisés, 0 compris). Soit $4\times8\times8=256$ entiers.
Par le principe additif : $72+256=328$ entiers pairs à chiffres distincts.
« Au moins deux chiffres égaux » est le contraire de « trois chiffres distincts ». Donc $900-648=252$ entiers.
Résultat :
900 ; 648 ; 328 ; 252
Exercice 7 · Anagrammes
entrainement●●●
PermutationsPrincipe multiplicatifCombinaisonsAnagrammes avec lettres répétées
On appelle anagramme d'un mot tout mot (ayant un sens ou non) formé avec exactement les mêmes lettres, le mot lui-même compris.
Combien le mot CARTON possède-t-il d'anagrammes ?
Combien de ces anagrammes commencent par une voyelle ?
Combien commencent et finissent par une consonne ?
Combien le mot BARBARA possède-t-il d'anagrammes ?
CARTON a 6 lettres distinctes. Une anagramme est une permutation de ces 6 lettres : $6!=720$ anagrammes.
Première lettre : A ou O, soit 2 choix. Les 5 lettres restantes se rangent dans les 5 places suivantes : $5!=120$ façons. Donc $2\times120=240$ anagrammes.
Il y a 4 consonnes : C, R, T, N. Première lettre : 4 choix ; dernière lettre : 3 choix (une autre consonne). Les 4 lettres restantes occupent les 4 places du milieu : $4!=24$ façons. Donc $4\times3\times24=288$ anagrammes.
BARBARA a 7 lettres : 3 A, 2 B, 2 R. Une anagramme est déterminée par :
les positions des 3 A parmi les 7 places : $\binom{7}{3}=\dfrac{7\times6\times5}{6}=35$ choix ;
les positions des 2 B parmi les 4 places restantes : $\binom{4}{2}=6$ choix ;
les 2 R occupent les 2 dernières places.
Par le principe multiplicatif : $35\times6=210$ anagrammes. Vérification : $\dfrac{7!}{3!\times2!\times2!}=\dfrac{5040}{24}=210$.
Une délégation est une partie à 4 éléments d'un ensemble de 22 élèves :
$$\binom{22}{4}=\frac{22\times21\times20\times19}{24}=\frac{175\,560}{24}=7315.$$
On choisit 2 filles parmi 12, puis 2 garçons parmi 10 :
$$\binom{12}{2}\times\binom{10}{2}=66\times45=2970.$$
Les délégations sans fille sont formées de 4 garçons : $\binom{10}{4}=\dfrac{10\times9\times8\times7}{24}=210$. Donc $7315-210=7105$ délégations comportent au moins une fille.
Le contraire de « au moins une fille et au moins un garçon » est « uniquement des garçons ou uniquement des filles ». Ces deux cas sont disjoints.
Uniquement des garçons : $\binom{10}{4}=210$.
Uniquement des filles : $\binom{12}{4}=\dfrac{12\times11\times10\times9}{24}=495$.
Donc $7315-(210+495)=7315-705=6610$ délégations.
Résultat :
7315 ; 2970 ; 7105 ; 6610
Exercice 9 · Une urne, trois façons de tirer
entrainement●●●
Choix du modèle de dénombrementk-upletsArrangementsCombinaisonsProbabilités et équiprobabilité
Une urne contient 8 boules indiscernables au toucher : 5 rouges et 3 vertes, numérotées pour être distinguées. On tire 3 boules.
On tire successivement 3 boules avec remise. Combien y a-t-il de tirages possibles ? Combien sont formés de 3 boules rouges ? En déduire la probabilité d'obtenir 3 boules rouges.
Mêmes questions pour 3 tirages successifs sans remise.
Mêmes questions pour un tirage simultané de 3 boules.
Comparer les probabilités obtenues aux questions 2 et 3.
La suite est réservée aux abonnés. L'abonnement arrive bientôt ; crée ton compte dès maintenant depuis Mon espace.
Exercice 12 · Comité et président : une identité
approfondissement●●●
Coefficients binomiauxDouble dénombrementSomme d'une ligne du triangle de PascalManipulation de factorielles
Soit $n$ un entier naturel non nul.
Montrer par le calcul que, pour tout entier $k$ tel que $1\leqslant k\leqslant n$ :
$$k\binom{n}{k}=n\binom{n-1}{k-1}.$$
Un groupe compte $n$ personnes. On forme un comité de $k$ personnes, puis on désigne un président parmi les membres du comité. En comptant de deux façons le nombre de résultats possibles, retrouver l'égalité de la question 1.
En déduire que $\displaystyle\sum_{k=1}^{n}k\binom{n}{k}=n\,2^{n-1}$.
Vérifier ce résultat pour $n=4$.
Retrouver le résultat de la question 3 directement, en dénombrant les couples (comité non vide, président de ce comité).
Pour $1\leqslant k\leqslant n$ :
$$\begin{aligned}k\binom{n}{k}&=\frac{k\times n!}{k!\,(n-k)!}=\frac{n!}{(k-1)!\,(n-k)!}\\&=\frac{n\times(n-1)!}{(k-1)!\,\big((n-1)-(k-1)\big)!}=n\binom{n-1}{k-1}.\end{aligned}$$
Première façon. On choisit le comité, partie à $k$ éléments du groupe ($\binom{n}{k}$ choix), puis le président parmi ses $k$ membres ($k$ choix). Il y a $k\binom{n}{k}$ résultats.
Deuxième façon. On choisit d'abord le président parmi les $n$ personnes ($n$ choix), puis les $k-1$ autres membres parmi les $n-1$ personnes restantes ($\binom{n-1}{k-1}$ choix). Il y a $n\binom{n-1}{k-1}$ résultats.
On a compté le même ensemble de deux façons, donc $k\binom{n}{k}=n\binom{n-1}{k-1}$.
D'après la question 1 :
$$\sum_{k=1}^{n}k\binom{n}{k}=n\sum_{k=1}^{n}\binom{n-1}{k-1}=n\sum_{j=0}^{n-1}\binom{n-1}{j},$$
en posant $j=k-1$. La dernière somme est celle de la ligne $n-1$ du triangle de Pascal, égale à $2^{n-1}$. Donc $\sum_{k=1}^{n}k\binom{n}{k}=n\,2^{n-1}$.
Pour $n=4$ : $1\times4+2\times6+3\times4+4\times1=4+12+12+4=32$ et $4\times2^3=32$. Le résultat est vérifié.
Par le principe additif selon la taille $k$ du comité, le nombre de couples (comité non vide, président) vaut $\sum_{k=1}^{n}k\binom{n}{k}$. Autre façon : on choisit le président ($n$ choix), puis le reste du comité, qui est une partie quelconque (éventuellement vide) des $n-1$ autres personnes ($2^{n-1}$ choix). Il y a donc $n\,2^{n-1}$ couples, ce qui redonne l'égalité.
Résultat :
$\sum_{k=1}^{n}k\binom{n}{k}=n\,2^{n-1}$ ; pour $n=4$ : 32
Exercice 13 · Sommes de coefficients sur une colonne
approfondissement●●●
Formule de PascalRaisonnement par récurrenceCoefficients binomiauxSommes d'entiers
Soit $k$ un entier naturel fixé. Pour tout entier $n\geqslant k$, on pose
$$S_n=\sum_{j=k}^{n}\binom{j}{k}=\binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{n}{k}.$$
Démontrer par récurrence que, pour tout $n\geqslant k$, $S_n=\binom{n+1}{k+1}$.
En déduire la valeur de $\binom{2}{2}+\binom{3}{2}+\cdots+\binom{10}{2}$, puis la vérifier par un calcul direct.
Retrouver, à l'aide de la question 1, l'égalité $1+2+\cdots+n=\dfrac{n(n+1)}{2}$ pour $n\geqslant1$.
Vérifier que, pour tout entier $j\geqslant1$, $j^2=2\binom{j}{2}+\binom{j}{1}$, puis en déduire que, pour tout $n\geqslant 2$,
$$1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}.$$
Pour $n\geqslant k$, on note $\mathcal{P}(n)$ : « $S_n=\binom{n+1}{k+1}$ ».
Initialisation. $S_k=\binom{k}{k}=1$ et $\binom{k+1}{k+1}=1$. $\mathcal{P}(k)$ est vraie.
Hérédité. Soit $n\geqslant k$ tel que $\mathcal{P}(n)$ est vraie. Alors
$$S_{n+1}=S_n+\binom{n+1}{k}=\binom{n+1}{k+1}+\binom{n+1}{k}.$$
On applique la formule de Pascal $\binom{N}{K}=\binom{N-1}{K-1}+\binom{N-1}{K}$ avec $N=n+2$ et $K=k+1$ ; elle est valable car $1\leqslant k+1\leqslant n+1=N-1$. On obtient $S_{n+1}=\binom{n+2}{k+1}$ : $\mathcal{P}(n+1)$ est vraie.
Conclusion. Pour tout $n\geqslant k$, $S_n=\binom{n+1}{k+1}$.
Avec $k=2$ et $n=10$ : $\sum_{j=2}^{10}\binom{j}{2}=\binom{11}{3}=\dfrac{11\times10\times9}{6}=165$.
Calcul direct : $1+3+6+10+15+21+28+36+45=165$.
Avec $k=1$ : $\sum_{j=1}^{n}\binom{j}{1}=\sum_{j=1}^{n}j=\binom{n+1}{2}=\dfrac{(n+1)n}{2}$.
Pour $j\geqslant 2$ : $2\binom{j}{2}+\binom{j}{1}=j(j-1)+j=j^2$. Pour $j=1$ : $\binom{1}{2}=0$ et $2\times0+1=1=1^2$. L'égalité est vraie pour tout $j\geqslant1$.
En sommant de $j=1$ à $n$, avec $\binom{1}{2}=0$ :
$$\sum_{j=1}^{n}j^2=2\sum_{j=2}^{n}\binom{j}{2}+\sum_{j=1}^{n}\binom{j}{1}=2\binom{n+1}{3}+\binom{n+1}{2}.$$
Or $2\binom{n+1}{3}=\dfrac{(n+1)n(n-1)}{3}$ et $\binom{n+1}{2}=\dfrac{(n+1)n}{2}$. Donc
$$\sum_{j=1}^{n}j^2=n(n+1)\left(\frac{n-1}{3}+\frac12\right)=n(n+1)\times\frac{2n-2+3}{6}=\frac{n(n+1)(2n+1)}{6}.$$
Nombre de partiesk-upletsBijectionDouble dénombrementPrincipe additif
Soit $E$ un ensemble fini à $n$ éléments ($n\geqslant1$). On s'intéresse aux couples $(A;B)$ de parties de $E$ tels que $A\subset B$.
On prend $E=\{a;b\}$. Dresser la liste de ces couples et les compter.
On revient au cas général et on note $E=\{x_1;\ldots;x_n\}$. Pour chaque élément $x_i$, combien de situations sont possibles vis-à-vis de $A$ et $B$ ? En construisant une bijection avec $\{0;1;2\}^n$, montrer qu'il y a $3^n$ couples $(A;B)$ avec $A\subset B$.
Dénombrer ces couples d'une autre façon, en classant selon le nombre $k$ d'éléments de $B$. En déduire que $\displaystyle\sum_{k=0}^{n}\binom{n}{k}2^k=3^n$, et vérifier pour $n=3$.
Combien y a-t-il de couples $(A;B)$ de parties de $E$ quelconques ? Combien vérifient $A\not\subset B$ ? Donner les valeurs pour $n=3$.
La suite est réservée aux abonnés. L'abonnement arrive bientôt ; crée ton compte dès maintenant depuis Mon espace.
Exercice 15 · Une loterie hebdomadaire
examen●●●
CombinaisonsPrincipe multiplicatifProbabilités et équiprobabilitéLoi binomialeLogarithme népérien
Les parties A et B peuvent être traitées de façon liée ; les résultats numériques sont arrondis à $10^{-3}$.
Une loterie propose une grille de 20 numéros, de 1 à 20. Un joueur coche 4 numéros distincts. Chaque semaine, l'organisateur tire au sort, simultanément, 4 numéros gagnants parmi les 20. Un « bon numéro » est un numéro coché qui fait partie des numéros gagnants.
Partie A : dénombrement
Combien de grilles différentes un joueur peut-il remplir ?
Les 4 numéros gagnants étant fixés, déterminer, pour chaque entier $k$ de $0$ à $4$, le nombre de grilles comportant exactement $k$ bons numéros. Vérifier la cohérence des résultats.
Partie B : probabilités
On suppose que toutes les grilles sont équiprobables. Le joueur gagne un lot s'il a au moins 2 bons numéros.
Montrer que la probabilité $p$ qu'une grille soit gagnante vaut $\dfrac{157}{969}$, et en donner une valeur approchée.
Le joueur joue une grille par semaine pendant $n$ semaines ; les tirages sont indépendants. On note $X$ le nombre de semaines où il gagne un lot.
a. Donner la loi de $X$.
b. Pour $n=10$, calculer la probabilité que le joueur gagne au moins une fois.
c. Déterminer le plus petit entier $n$ tel que la probabilité de gagner au moins une fois dépasse $0{,}99$.
Une grille est une partie à 4 éléments d'un ensemble à 20 éléments :
$$\binom{20}{4}=\frac{20\times19\times18\times17}{24}=\frac{116\,280}{24}=4845.$$
Une grille comportant exactement $k$ bons numéros s'obtient en choisissant $k$ numéros parmi les 4 gagnants et $4-k$ numéros parmi les 16 non gagnants. Par le principe multiplicatif, il y en a $\binom{4}{k}\binom{16}{4-k}$.
$k$
0
1
2
3
4
Calcul
$1\times\binom{16}{4}$
$4\times\binom{16}{3}$
$6\times\binom{16}{2}$
$4\times16$
$1\times1$
Nombre
1820
2240
720
64
1
Avec $\binom{16}{4}=\dfrac{16\times15\times14\times13}{24}=1820$, $\binom{16}{3}=\dfrac{16\times15\times14}{6}=560$ et $\binom{16}{2}=120$.
Cohérence : les cas $k=0,\ldots,4$ sont disjoints et couvrent toutes les grilles ; $1820+2240+720+64+1=4845$.
Partie B
Les grilles gagnantes sont celles à 2, 3 ou 4 bons numéros : $720+64+1=785$. En situation d'équiprobabilité :
$$p=\frac{785}{4845}=\frac{157}{969}\approx0{,}162.$$
a. Chaque semaine est une épreuve de Bernoulli de succès « gagner un lot », de probabilité $p$. Les $n$ épreuves sont identiques et indépendantes, et $X$ compte les succès : $X$ suit la loi binomiale $\mathcal{B}\left(n;\dfrac{157}{969}\right)$.
b. $P(X\geqslant1)=1-P(X=0)=1-(1-p)^{10}=1-\left(\dfrac{812}{969}\right)^{10}\approx1-0{,}171=0{,}829$.
c. On cherche le plus petit $n$ tel que $1-\left(\dfrac{812}{969}\right)^n\geqslant0{,}99$, c'est-à-dire $\left(\dfrac{812}{969}\right)^n\leqslant0{,}01$. La fonction $\ln$ étant strictement croissante :
$$n\ln\left(\frac{812}{969}\right)\leqslant\ln(0{,}01).$$
Comme $\dfrac{812}{969}<1$, $\ln\left(\dfrac{812}{969}\right)<0$ et le sens de l'inégalité change en divisant :
$$n\geqslant\frac{\ln(0{,}01)}{\ln\left(\frac{812}{969}\right)}\approx26{,}05.$$
Le plus petit entier convenable est $n=27$. Contrôle : $\left(\frac{812}{969}\right)^{26}\approx0{,}0101>0{,}01$ et $\left(\frac{812}{969}\right)^{27}\approx0{,}0085\leqslant0{,}01$.
Exercice 16 · Triangle de Pascal, programme et commissions paritaires
examen●●●
Formule de PascalTriangle de PascalAlgorithmique en PythonDouble dénombrementCombinaisonsProbabilités et équiprobabilité
Partie A : un programme
On considère la fonction Python suivante, dont une ligne est incomplète.
def pascal(n):
L = [1]
for i in range(n):
M = [1]
for j in range(1, len(L)):
M.append(.......)
M.append(1)
L = M
return L
Elle doit renvoyer la liste des coefficients de la ligne $n$ du triangle de Pascal, c'est-à-dire $\left[\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}\right]$.
Que renvoient pascal(0) et pascal(1) ?
Compléter la ligne en pointillés et justifier à l'aide d'une formule du cours.
Que renvoie pascal(5) ?
Partie B : une identité
Soit $n\geqslant1$. Un groupe est formé de $n$ femmes et $n$ hommes. On forme une commission de $n$ personnes, sans rôle particulier.
Combien de commissions sont possibles ?
Pour $0\leqslant k\leqslant n$, montrer que le nombre de commissions comportant exactement $k$ femmes est $\binom{n}{k}^2$.
En déduire que $\displaystyle\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2$.
Vérifier cette égalité pour $n=4$, à l'aide de la liste renvoyée par pascal(4).
Partie C : tirage au sort
Dans cette partie, $n=4$ : le groupe compte 4 femmes et 4 hommes, et la commission de 4 personnes est tirée au sort, toutes les commissions étant équiprobables.
Calculer la probabilité que la commission soit paritaire (2 femmes et 2 hommes).
Calculer la probabilité que la commission comporte plus de femmes que d'hommes.
Calculer la probabilité que la commission comporte au moins une femme.