$$\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 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 $E$?
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 3 - 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 4 - 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 5 - 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 6 - 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é
Exercice 7 - 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é
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 9 - 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é