$$\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 math sup : 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é
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 hebdomadaire à chaque boulangerie.
  2. Déterminer le nombre de façons d'attribuer un jour de fermeture hebdomadaire à chaque boulangerie si plusieurs boulangeries ne peuvent fermer le même jour.
  3. Déterminer le nombre de façons d'attribuer un jour de fermeture hebdomadaire à chaque boulangerie si chaque jour, il doit y avoir au moins une boulangerie ouverte.
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é
Dénombrer les anagrammes des mots suivants : MATHS, RIRE, ANANAS.
Indication
Corrigé
Enoncé
Dans cet exercice, on attend des réponses qui ne sont pas des valeurs numériques, mais des expressions en termes de factorielles, sous la forme la plus simple possible.
  1. Combien y-a-t-il de façons de répartir les 52 cartes d'un jeu entre 4 joueurs N, S, E, O, chacun possédant 13 cartes.
  2. Parmi ces façons, combien y-en-a-t-il qui sont telles que chaque joueur n'a qu'une seule couleur (par exemple, N a les 13 piques, S a les 13 coeurs,...)?
  3. Combien y-a-t-il de façons que deux joueurs quelconques aient chacun une seule couleur?
  4. Combien y-a-t-il de façons que deux partenaires, c'est-à-dire (N,S) ou (E,O), aient chacun une seule couleur, les deux autres partenaires ayant des cartes quelconques.
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 (Attention! la suite as, 2, 3, 4 et 5 est une quinte flush).
  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 8 - 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. contenant 2 carreaux et 3 piques.
  4. contenant au moins un roi.
  5. contenant au plus un roi.
  6. contenant exactement 2 rois et exactement 3 piques.
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é
Exercice 10 - $n+1$ entiers parmi $2n$ [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On considère un ensemble $X$ de $n+1$ entiers (distincts) choisis dans $\{1,\dots,2n\}$. Démontrer que parmi les éléments de $X$, on peut toujours trouver $2$ entiers dont la somme fait $2n+1$.
Indication
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é
Coefficients binomiaux
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é
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é
Dénombrements théoriques
Enoncé
Soit $n\geq 2$ un entier. Combien y-a-t-il de couples $(x,y)$ dans $\{1,\dots,n\}^2$ tels que
  1. $x+y=n$;
  2. $x<y$;
  3. $|x-y|\leq 1$;
Indication
Corrigé
Exercice 17 - Partitions d'un entier [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On appelle partition d'un entier naturel $n$ toute suite finie $(\alpha_1,\dots,\alpha_k)\in (\mathbb N^*)^k$ telle que $\alpha_1\geq \cdots\geq\alpha_k$ et $\alpha_1+\cdots+\alpha_k=n$. On note $\Gamma_n$ l'ensemble des partitions de l'entier $n$.
  1. Déterminer $\Gamma_1,\Gamma_2,\Gamma_3,\Gamma_4$.
  2. Pour $j,n\in\mathbb N$, on note $Y_{n,j}$ l'ensemble des partitions de $n$ dont le premier terme est inférieur ou égal à $j$, et on note $y_{n,j}$ le cardinal de $Y_{n,j}$. On convient que $y_{0,0}=1$.
    1. Calculer $y_{n,1}$.
    2. On se propose de démontrer que, si $2\leq j\leq n$, alors $y_{n,j}=y_{n,j-1}+y_{n-j,\min(j,n-j)}$. Démontrer cette relation pour $j=n$.
    3. Pour $2\leq j<n$, vérifier que $y_{n,j}=y_{n,j-1}+y_{n-j,j}$ puis conclure.
  3. Écrire une fonction Python qui prend en argument un entier $n\geq 1$ et qui renvoie le cardinal de $\Gamma_n$.
Indication
Corrigé
Exercice 18 - Contenant un et un seul élément d'une partie donnée [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n$ un entier naturel non nul et soit $E$ un ensemble à $n$ éléments. Soit $p$ un entier naturel tel que $1\leq p\leq n$ et soit $A$ une partie de $E$ à $p$ éléments. Quel est le nombre de parties de $E$ qui contiennent exactement un et un seul élément de $A$?
Indication
Corrigé
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 $E$?
Indication
Corrigé
Exercice 20 - Nombre de partitions d'un ensemble à $n$ éléments [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n$ et $k$ deux entiers strictement positifs.
  1. Montrer qu’il n’existe qu’un nombre fini de partitions de l’ensemble $\{1,\dots,n\}$ en $k$ parties. Dans la suite, on notera $S(n,k)$ le nombre de ces partitions. On pose de plus $S(0,0)=1$ et $S(n,0)=S(0,k)=0$.
  2. Que vaut $S(n,k)$ pour $k>n$?
  3. Que vaut $S(n,1)$?
  4. Démontrer que $S(n,k)=S(n-1,k-1)+kS(n-1,k)$.
  5. Rédiger une fonction récursive Python permettant de calculer $S(n,k)$.
Indication
Corrigé
Enoncé
Pour $n\in\mathbb N$, on note $B_n$ le nombre de partitions d'un ensemble $E$ de cardinal $n$. On pose $B_0=1$.
  1. Calculer $B_1$, $B_2$ et $B_3$.
  2. Établir la formule de récurrence $$B_{n+1}=\sum_{k=0}^n \binom nk B_k.$$
Indication
Corrigé
Exercice 22 - Nombre de fonctions (strictement) croissantes [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $n,p\geq 1$ deux entiers.
  1. Combien y-a-t-il de fonctions strictement croissantes de $\{1,\dots,p\}$ dans $\{1,\dots,n\}$?
    1. Soit $f:\{1,\dots,p\}\to\{1,\dots,n\}$ une fonction croissante. On pose $\phi(f)$ la fonction définie sur $\{1,\dots,p\}$, à valeurs dans $\{1,\dots,n+p-1\}$, par $\phi(f)(k)=f(k)+k-1$. Démontrer que $\phi(f)$ est strictement croissante.
    2. Soit $g:\{1,\dots,p\}\to\{1,\dots,n+p-1\}$ une fonction strictement croissante. On pose $\psi(g)$ la fonction définie sur $\{1,\dots,p\}$, à valeurs dans $\{1,\dots,n\}$, par $\psi(g)(k)=g(k)-k+1$. Démontrer que $\psi(g)$ est croissante.
    3. Combien y-a-t-il de fonctions croissantes de $\{1,\dots,p\}$ dans $\{1,\dots,n\}$?
Indication
Corrigé
Exercice 23 - 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 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$, avec la convention $D_0=1$.
  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é
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é