$$\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

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é
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é
Exercice 4 - 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 7 - 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é
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é
Dénombrement et coefficients binomiaux
Exercice 9 - 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é
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é
Exercice 13 - 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 14 - 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 15 - 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 16 - 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é