$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Exercices corrigés - Dénombrement

Dénombrements pratiques
Enoncé
A leur entrée en L1, les étudiants choisissent une langue (anglais ou allemand) et une option (informatique, chimie ou astronomie). Dans un groupe d'étudiants, 12 étudiants sont inscrits en astronomie, 15 en chimie, 16 étudient l'allemand. Par ailleurs, 8 inscrits en astronomie et 3 inscrits en informatique étudient l'anglais, 6 inscrits en chimie étudient l'allemand.
Indiquer la répartition des étudiants par discipline, ainsi que le nombre total d'étudiants dans le groupe.
Indication
Corrigé
Enoncé
Dans une entreprise, il y a 800 employés. 300 sont des hommes, 352 sont membres d'un syndicat, 424 sont mariés, 188 sont des hommes syndiqués, 166 sont des hommes mariés, 208 sont syndiqués et mariés, 144 sont des hommes mariés syndiqués. Combien y-a-t-il de femmes célibataires non syndiquées?
Indication
Corrigé
Enoncé
On trace dans un plan $n\geq 3$ droites en position générale (c'est-à-dire que deux droites ne sont jamais parallèles, et 3 droites ne sont jamais concourantes). Combien de triangles a-t-on ainsi tracé?
Indication
Corrigé
Enoncé
Une course oppose 20 concurrents, dont Émile.
  1. Combien y-a-t-il de podiums possibles?
  2. Combien y-a-t-il de podiums possibles où Émile est premier?
  3. Combien y-a-t-il de podiums possibles dont Émile fait partie?
  4. On souhaite récompenser les 3 premiers en leur offrant un prix identique à chacun. Combien y-a-t-il de distributions de récompenses possibles?
Corrigé
Enoncé
Dans une ville, il y a quatre boulangeries qui ferment un jour par semaine.
  1. Déterminer le nombre de façons d'attribuer un jour de fermeture hebdomaire?
  2. Reprendre la même question si plusieurs boulangeries ne peuvent fermer le même jour.
  3. Reprendre la même question si chaque jour, il doit y avoir au moins une boulangerie ouverte.
Indication
Corrigé
Enoncé
Dans une pièce, il y a deux tables. La première dispose de 3 chaises, numérotées de 1 à 3, la seconde dispose de 4 chaises, numérotées de 1 à 4. Sept personnes entrent. Combien y-a-t-il de possibilités de les distribuer autour de ces deux tables?
Indication
Corrigé
Enoncé
Un cadenas possède un code à $3$ chiffres, chacun des chiffres pouvant être un chiffre de $1$ à $9$.
    1. Combien y-a-t-il de codes possibles?
    2. Combien y-a-t-il de codes se terminant par un chiffre pair?
    3. Combien y-a-t-il de codes contenant au moins un chiffre $4$?
    4. Combien y-a-t-il de codes contenant exactement un chiffre $4$?
  1. Dans cette question on souhaite que le code comporte obligatoirement trois chiffres distincts.
    1. Combien y-a-t-il de codes possibles?
    2. Combien y-a-t-il de codes se terminant par un chiffre impair?
    3. Combien y-a-t-il de codes comprenant le chiffre $6$?
Corrigé
Enoncé
Fred et Émile font partie d'une équipe de $8$ joueurs ($6$ garçons et $2$ filles). On décide de fabriquer un comité de $3$ joueurs.
  1. Combien y-a-t-il de comités possibles?
  2. Combien y-a-t-il de comités contenant exactement $2$ garçons et $1$ fille?
  3. Combien y-a-t-il de comités contenant au moins deux garçons?
  4. On veut que Fred et Émile soient ensemble dans le comité. Combien y-a-t-il de comités possibles?
  5. On ne veut pas que Fred et Émile soient ensemble dans le comité. Combien y-a-t-il de comités possibles?
Corrigé
Exercice 9 - Les trois mousquetaires [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Les trois mousquetaires (donc quatre personnes avec d'Artagnan), ont mélangé leurs bottes dans le couloir de l'auberge. D'Artagnan se lève en premier et prend deux bottes au hasard.
  1. Combien de possibilités s'offrent à lui?
  2. Combien de choix a-t-il tels que les deux bottes forment une paire (une droite et une gauche quelconques)?
  3. Combien de choix a-t-il tels que les deux bottes appartiennent à deux personnes différentes?
Indication
Corrigé
Enoncé
Soit $A$ l'ensemble des nombres à 7 chiffres ne comportant aucun "1". Déterminer le nombre d'éléments des ensembles suivants :
  1. $A$.
  2. $A_1$, ensemble des nombres de $A$ ayant 7 chiffres différents.
  3. $A_2$, ensemble des nombres pairs de $A$.
  4. $A_3$, ensemble des nombres de $A$ dont les chiffres forment une suite strictement croissante (dans l'ordre où ils sont écrits).
Indication
Corrigé
Enoncé
Une table ronde comporte cinq places, numérotées de 1 à 5. On veut répartir Adélie, Brigitte, Chafik, Denis et Emilie autour de la table. Mais attention! Denis et Émilie ne s'entendent pas du tout, et il ne faut pas les placer côte à côte!!! Combien y-a-t-il de dispositions possibles?
Indication
Corrigé
Enoncé
Une main au poker est formée de 5 cartes extraites d'un jeu de 52 cartes. Traditionnellement,trèfle, carreau, coeur, pique sont appelées couleurs et les valeurs des cartes sont rangées dans l'ordre : as, roi, dame, valet, 10, 9, 8, 7, 6, 5, 4, 3, 2, de la plus forte à la plus faible. Dénombrer les mains suivantes :
  1. quinte flush : main formée de 5 cartes consécutives de la même couleur.
  2. carré : main contenant 4 cartes de la même valeur (4 as par exemple).
  3. full : main formée de 3 cartes de la même valeur et de deux autres cartes de même valeur (par exemple, 3 as et 2 rois).
  4. quinte : main formée de 5 cartes consécutives et qui ne sont pas toutes de la même couleur.
  5. brelan : main comprenant 3 cartes de même valeur et qui n'est ni un carré, ni un full (par exemple, 3 as, 1 valet, 1 dix).
Indication
Corrigé
Exercice 13 - Tirages dans un jeu de cartes [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On tire simultanément 5 cartes d'un jeu de 32 cartes. Combien de tirages différents peut-on obtenir :
  1. sans imposer de contraintes sur les cartes.
  2. contenant 5 carreaux ou 5 piques.
  3. 2 carreaux et 3 piques.
  4. au moins un roi.
  5. au plus un roi.
  6. 2 rois et 3 piques.
Indication
Corrigé
Enoncé
On souhaite ranger sur une étagère 4 livres de mathématiques (distincts), 6 livres de physique, et 3 de chimie. De combien de façons peut-on effectuer ce rangement :
  1. si les livres doivent être groupés par matières.
  2. si seuls les livres de mathématiques doivent être groupés.
Indication
Corrigé
Enoncé
Dénombrer les anagrammes des mots suivants : MATHS, RIRE, ANANAS.
Indication
Corrigé
Exercice 16 - Des tours sur un échiquier [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
De combien de façons différentes peut-on placer $p$ tours sur un échiquier de taille $n$ de façon à ce qu'elles ne puissent pas se prendre?
Indication
Corrigé
Enoncé
Soit $n$ un entier non nul. On désigne par $u_n$ le nombre de listes de $n$ termes, chaque terme étant $0$ ou $1$, et n'ayant pas deux termes $1$ consécutifs.
  1. Que vaut $u_1$? $u_2$?
  2. Démontrer que, pour tout $n\geq 3$, on a $u_n=u_{n-1}+u_{n-2}$.
  3. Écrire un algorithme permettant de calculer $u_{20}$.
  4. Application : un concours comporte vingt questions, numérotées de 1 à 20. On a constaté que, parmi les 17712 personnes ayant participé au concours, aucune n'a répondu juste à deux questions consécutives. Peut-on affirmer que deux candidats au moins ont répondu de la même manière au questionnaire, c'est-à-dire juste aux mêmes questions et faux aux mêmes questions?
Indication
Corrigé
Coefficients binomiaux comme nombre de parties
Exercice 18 - Une extension de la formule du triangle de Pascal [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $E$ l'ensemble à 12 éléments $\{a,b,c,d,e,f,g,h,i,j,k,l\}$.
  1. Dénombrer les parties de $E$ à 5 éléments qui contiennent
    1. $a$ et $b$;
    2. $a$ mais pas $b$;
    3. $b$ mais pas $a$;
    4. ni $a$, ni $b$.
  2. En déduire la relation $$\binom{12}5=\binom{10}3+2\binom{10}4+\binom{10}5.$$
  3. Généraliser le résultat obtenu en prouvant, par un dénombrement, que pour $2\leq p\leq n$, on a $$\binom np=\binom{n-2}{p-2}+2\binom{n-2}{p-1}+\binom{n-2}p.$$
  4. Retrouver le résultat précédent en appliquant la formule du triangle de Pascal.
Indication
Corrigé
Enoncé
Soit $1\leq p\leq n$. On considère $n$ boules et deux boîtes $A$ et $B$. Un échantillon est constitué d'une boule dans la boîte $A$ et de $p-1$ boules dans la boîte $B$. En dénombrant de deux façons différentes ces échantillons, établir la formule $$n\binom{n-1}{p-1}=p\binom np.$$ Retrouver cette formule par le calcul.
Corrigé
Enoncé
Un livre comporte 14 chapitres.
  1. Combien y-a-t-il de façons de choisir $3$ chapitres dans ce livre?
  2. Pour $k=3,\dots,14$, dénombrer les choix de 3 chapitres pour lesquels $k$ est le plus grand numéro des chapitres choisis.
  3. En déduire que $$\binom {14}3 = \binom{13}2+\binom{12}2+\cdots+\binom{3}{2}+\binom{2}2.$$
  4. Généraliser les dénombrements précédents pour démontrer que, pour $1\leq p\leq n$, on a $$\sum_{k=p}^n \binom kp=\binom{n+1}{p+1}.$$
Indication
Corrigé
Exercice 21 - Une extension de la formule du triangle de Pascal [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soient $p,q,m$ des entiers naturels, avec $q\leq p\leq m$. Démontrer par un dénombrement que $$\binom mp=\sum_{j=0}^q \binom qj\times \binom{m-q}{p-j}.$$
Indication
Corrigé
Enoncé
Démontrer par un dénombrement que, pour $n\geq 1$, on a : $$\binom{2n}{n}=\sum_{k=0}^n \binom{n}{k}^2.$$
Indication
Corrigé
Enoncé
Soit $n,p$ des entiers naturels avec $n\geq p$. Démontrer par dénombrement que $$\sum_{k=p}^n \dbinom{k}{p}=\dbinom{n+1}{p+1}.$$
Indication
Corrigé
Coefficients binomiaux comme chemins dans l'arbre
Exercice 24 - Somme des coefficients binomiaux au carré [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n$ un entier non nul. On considère l'arbre modélisant la répétition de $2n$ épreuves aléatoires identiques d'un schéma de Bernoulli.
  1. Dans cet arbre, quel est le nombre de chemins avec exactement $n$ succès?
    1. Quel est le nombre de chemins permettant d'obtenir $0$ succès lors des $n$ premières épreuves, puis $n$ succès lors des $n$ dernières épreuves?
    2. Dans cet arbre, que vaut le produit $\binom nk\times\binom n{n-k}$ pour $k$ entier naturel compris entre $0$ et $n$?
  2. Déduire des questions précédentes l'expression de la somme suivante en fonction de $n$ : $$\sum_{k=0}^n {\binom nk}^2.$$
Indication
Corrigé
Exercice 25 - Une formule sur les coefficients binomiaux [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $a,b,n$ des entiers naturels avec $a>n$ et $b>n$. On considère l'arbre d'un schéma de Bernoulli consistant en la répétition de $a+b$ épreuves identiques.
  1. Soit $0\leq k\leq n$. Que compte $\binom ak\times \binom b{n-k}$ pour cet arbre?
  2. En déduire que $\binom {a+b}n=\sum_{k=0}^n \binom a k\times \binom b{n-k}$.
Corrigé
Dénombrements théoriques
Enoncé
Soit $E$ un ensemble à $n$ éléments.
  1. Soit $X$ une partie à $p$ éléments de $E$. Combien y-a-t-il de parties $Y$ de $E$ disjointes de $X$?
  2. Combien y-a-t-il de couples $(X,Y)$ formés de parties disjointes de $X$?
Indication
Corrigé
Enoncé
Soit $E$ un ensemble à $n$ éléments; Combien y-a-t-il de couples $(X,Y)$ de parties de $E$ tels que $X\subset Y$?
Indication
Corrigé
Exercice 28 - Parties de cardinal pair [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $E$ un ensemble fini de cardinal $n\geq 1$. Démontrer que le nombre de parties de $E$ de cardinal pair vaut $2^{n-1}$.
Indication
Corrigé
Exercice 29 - Partition d'un ensemble [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Combien existe-t-il de partitions d'un ensemble de cardinal $np$ en $n$ parties de cardinal $p$?
Indication
Corrigé
Exercice 30 - Dérangement et problème des rencontres [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $E$ un ensemble à $n$ éléments. On appelle \emph{dérangement} de $E$ toute permutation de $E$ ne laissant aucun élément invariant. On notera $D_n$ le nombre de dérangements de $E$.
  1. Si $E$ comporte un seul élément, y-a-t-il des dérangements de $E$? En déduire $D_1$.
  2. Si $E$ comporte deux éléments, combien y-a-t-il de dérangements de $E$? En déduire $D_2$.
  3. On suppose $n$ quelconque, et on écrit $E=\{a_1,\dots,a_n\}$. Soit $f$ une permutation de $E$. On suppose qu'elle laisse $k$ éléments invariants. Combien y-a-t-il de telles permutations? En déduire la formule suivante : $$n!=\sum_{k=0}^n \binom{n}{k} D_k.$$
  4. En déduire $D_3,\ D_4$, $D_5$.
  5. Cinq couples de danseurs se rendent à un bal masqué. A l'arrivée, on sépare les hommes et les femmes , on numérote les femmes de 1 à 5 , et les hommes de 1 à 5. On les fait ensuite s'élancer sur une piste , chaque homme choississant au hasard une femme pour partenaire.
    1. A chaque numéro de femme, on associe le numéro de l'homme avec lequel elle danse. Combien y-a-t-il d'associations possibles?
    2. Donner la probabilité pour qu'aucun couple légitime ne soit reconstitué.
    3. Déterminer la probabilité pour qu'un seul couple légitime soit reconstitué.
    4. Déterminer la probabilité pour qu'il y ait plus de couples illégitimes sur la piste de danse que de couples légitimes.
Indication
Corrigé
Exercice 31 - Partie sans entiers consécutifs [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n\geq 1$ et $p\geq 0$ des entiers. On note $F_n^p$ l'ensemble des parties de $\{1,\dots,n\}$ à $p$ éléments ne contenant aucune paire d'entiers consécutifs. On note $K_n^p$ le cardinal de $F_n^p$.
  1. Déterminer $K_n^p$ quand $p> (n+1)/2$.
  2. Soit $\{a_1,\dots,a_p\}$ une partie de $F_n^p$ écrite de sorte que $a_i<a_{i+1}$. On pose $b_k=a_k+1-k$. Prouver que $1\leq b_1<b_2<\dots<b_p\leq n+1-p$.
  3. Soit $G_n^p$ l'ensemble des parties à $p$ éléments de $\{1,\dots,n+1-p\}$. Construire une bijection de $F_n^p$ sur $G_n^p$.
  4. En déduire la valeur de $K_n^p$.
  5. Application : au loto on tire 6 numéros dans $\{1,\dots,49\}$. Combien de tirages ne contiennent aucune paire d'entiers consécutifs?
Indication
Corrigé
Enoncé
On se propose de calculer le nombre $S(n,p)$ de surjections de $\{1,\dots,n\}$ sur $\{1,\dots,p\}$, où $(n,p)\in(\mathbb N^*)^2$.
  1. Des cas particuliers :
    1. Calculer $S(n,p)$ pour $p>n$.
    2. Calculer $S(n,n)$.
    3. Calculer $S(n,1)$.
    4. Calculer $S(n,2)$.
  2. Calculer $S(n+1,n)$.
  3. Démontrer que, pour tout $n>1$ et tout $p>1$, on a la relation $$S(n,p)=p\big(S(n-1,p)+S(n-1,p-1)\big).$$
  4. En déduire un algorithme pour calculer $S(n,p)$.
  5. Démontrer que $S(n,p)=\sum_{k=0}^p (-1)^{p-k}\binom pk k^n.$
Indication
Corrigé
Exercice 33 - Combinaisons avec répétitions [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Pour $n\in\mathbb N^*$ et $p\in\mathbb N$, on note $\Gamma_n^p$ le nombre de $n$-uplets $(x_1,\dots,x_n)\in\mathbb N^n$ tels que $x_1+\dots+x_n=p$.
  1. Déterminer $\Gamma_n^0$, $\Gamma_n^1$, $\Gamma_n^2$, $\Gamma_1^p$ et $\Gamma_2^p$.
  2. Démontrer que, pour tout $n\in\mathbb N^*$, pour tout $p\in\mathbb N$, $$\Gamma_{n+1}^p=\Gamma_n^0+\Gamma_n^1+\dots+\Gamma_n^p.$$
  3. En déduire que, pour tout $n\in\mathbb N^*$ et tout $p\in\mathbb N$, $$\Gamma_n^p=\binom{n+p-1}p.$$
Indication
Corrigé
Dénombrement et cryptographie
Exercice 34 - Le disque de l'armée mexicaine [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Le disque de l'armée mexicaine est un outil de cryptographie utilisé par l'armée mexicaine au début du XXiè siècle. Il est constitué de 5 disques de diamètres différents, empilés les uns sur les autres, et qui peuvent tourner les uns par rapport aux autres. Chaque disque est partagé en 26 parts. Sur le bord du plus grand disque, on écrit les 26 lettres, de A à Z. Sur le bord du second disque, on écrit les 26 nombres 01,02,…,26. Sur le bord du troisième disque, on écrit 27,…,52, sur le bord du quatrième disque, 53,…78, et enfin sur le bord du plus petit dique, 79,…,99, et 00 (il reste 4 secteurs sans nombre sur le plus petit disque).
On convient alors d'une clé, qui est un mot de 4 lettres, par exemple FRED. On fait alors coïncider alors le plus petit nombre du deuxième disque, à savoir 01, avec la première lettre de la clé, ici F. On fait de même tourner le troisième disque pour faire coïncider son plus petit nombre, 27, en face de la deuxième lettre de la clé, R, et ainsi de suite pour les deux autres disques.
Pour chiffrer un message, on remplace alors une lettre par l'un des 3 ou 4 nombres qui lui fait face sur le disque. Avec l'exemple précédente, on pourrait remplacer E par 26, 40, 53 ou 80.
Combien-y-a-t-il de clés possibles pour cette méthode de chiffrement?
Corrigé
Enoncé
Les grilles tournantes, mises au point par le colonel Fleissner, servirent pour une méthode de cryptographie qui fut utilisée par les allemands lors de la Première Guerre Mondiale. Une telle grille est constituée par un carré de côté 6. On divise ce carré en une grille de 36 petits carrés égaux (tous de côté 1), et on ôte 9 de ces carrés. La propriété suivante doit être vérifiée : les trous que l'on obtient avec la grille en position initiale, avec la grille tournée d'un quart de tour, d'un demi-tour ou de trois quart de tour ne se superposent jamais. Ainsi, les 36 positions peuvent être occupées par un trou après éventuellement une rotation de la grille d'un quart, d'un demi ou de trois-quart de tour.
  1. Combien peut-on fabriquer de telles grilles?
  2. Pour quelles valeurs de $n$ peut-on fabriquer une grille de Fleissner de côté $n$? Combien de telles grilles peut-on alors fabriquer?
Indication
Corrigé