Dénombrement
Feuille d'exercices
I) Dénombrement en tout genre
On tire simultanément 5 cartes d'un jeu de 32 cartes. Combien de tirages différents peut-on obtenir :
- sans imposer de contraintes sur les cartes.
- contenant 5 carreaux ou 5 piques.
- contenant 2 carreaux et 3 piques.
- contenant au plus un roi.
- contenant au moins un roi.
- contenant exactement 2 rois et exactement 3 piques.
Dénombrer les anagrammes des mots suivants : « MATHS », « RIRE », « ANANAS ».
Combien existe-t-il de mots de 9 lettres contenant le mot :
- « COLLE » ?
- « MATH » ?
- « TEST » ?
Soient $p \in \N^*$ et $m, n \geq p$. À l'issue d'un concours, $m$ filles et $n$ garçons sont admis. Combien de classements des $2p$ premiers admis contenant autant de filles que de garçons peut-on former ?
Combien y a-t-il d'applications de $\Intn{1}{n}$ vers $\Intn{1}{p}$ :
- constantes ?
- strictement croissantes ?
- strictement monotones ?
- ★★ croissantes ?
- monotones ?
Question 4) : trois méthodes possibles, à essayer chacune.
- Méthode 1. À $f$ croissante, associer $g \colon k \mapsto f(k) + k - 1$. Montrer que $g$ est strictement croissante, préciser l'ensemble d'arrivée, puis utiliser la question 2).
- Méthode 2. Représenter $f$ par un chemin de $\pa{0, 1}$ à $\pa{n, p}$ formé de pas de longueur $1$ vers la droite ou vers le haut, le $k$-ième pas vers la droite étant fait à la hauteur $f(k)$. Compter ensuite ces chemins.
- Méthode 3. Classer les applications croissantes selon le cardinal $k$ de leur image. Pour $k$ fixé, choisir l'image, puis les endroits où $f$ change de valeur. Conclure avec la formule de Vandermonde (exo:vandermonde).
- Corrigé : commande LaTeX inconnue : \fill, \y (absente des macros reconnues — coquille probable ou macro légitime à ajouter à la liste)
On s'intéresse à des tableaux de $n$ lignes et $p$ colonnes dont chaque case contient $0$ ou $1$. Combien en existe-t-il :
- qui contiennent $n$ coefficients $1$ en tout ?
- dont chaque ligne contient exactement un coefficient $1$ ?
- dont chaque ligne contient exactement deux coefficients $1$ ?
- (ici $n = p$) dont chaque ligne et chaque colonne contiennent exactement un coefficient $1$ ?
Combien y a-t-il de couples $\pa{x, y}$ :
- dans $\Intn{1}{n}^2$ pour lesquels $x + y = n$ ?
- dans $\Intn{1}{n}^2$ pour lesquels $x < y$ ?
- dans $\Intn{1}{n} \times \Intn{1}{2n}$ pour lesquels $x < y$ ?
- dans $\Intn{1}{n}^2$ pour lesquels $\abs{x - y} \leq 1$ ?
Dénombrer les triplets $\pa{i, j, k}$ tels que $i + j + k = 151$ et $i, j, k \in \Intn{1}{75}$.
Étant donnée sa décomposition en facteurs premiers, combien un entier naturel non nul possède-t-il de diviseurs positifs ?
Combien d'entiers naturels inférieurs ou égaux à $1000$ ne sont divisibles ni par $5$ ni par $7$ ?
Soit $E$ un ensemble fini non vide de cardinal $n$.
- Combien existe-t-il de relations binaires sur $E$ ?
- Combien de relations binaires réflexives ?
- Combien de relations binaires réflexives et symétriques ?
Soient $n, p \in \N$ avec $p \leq n$. Combien existe-t-il de parties de $\Intn{1}{n}$ qui contiennent :
- un et un seul élément de $\Intn{1}{p}$ ?
- au moins un élément de $\Intn{1}{p}$ ?
Soit $E$ un ensemble fini de cardinal $n$. Combien existe-t-il de couples $\pa{A, B}$ de parties de $E$ pour lesquels :
- $A \cap B = \emptyset$ et $A \cup B = E$ ?
- $A \cap B = \emptyset$ ? (Donner deux méthodes)
- $A \cup B = E$ ?
Combien y a-t-il d'applications $f : \Intn{1}{n} \to \Intn{1}{n}$ telles que ${f \circ f = f}$ ? On donnera le résultat sous la forme d'une somme.
Soit $f$ une involution de $E = \Intn{1}{2n + 1}$, c'est-à-dire que $f : E \to E$ est telle que $f \circ f = \text{Id}_E$. Montrer que $f$ possède un point fixe.
Soient $E$ un ensemble et $A_1, \dots, A_p$ des parties de $E$.
- Montrer que : $ \one_{A_1 \cup \dots \cup A_p} = 1 - \Prod{i=1}{p} \pa{1 - \one_{A_i}}. $
- En déduire que, si les $A_i$ sont finies : $$ \Card{\bigcup_{i=1}^{p} A_i} = \Sum{k=1}{p} (-1)^{k+1} \Sum{1 \le i_1 < \dots < i_k \le p}{} \Card{A_{i_1} \cap \dots \cap A_{i_k}}. $$
- Énoncé : commande mathématique hors de tout $ : \Prod, \cup (probablement un $ manquant autour)
- Corrigé : commande mathématique hors de tout $ : \overline (probablement un $ manquant autour)
Soient $n, p \in \N^*$. On note $S(n,p)$ le nombre de surjections de $\Intn{1}{n}$ dans $\Intn{1}{p}$.
- Déterminer $S(n,1)$, $S(n,2)$ et $S(n,n)$.
- Pour $n \ge 2$, déterminer $S(n,n-1)$.
- Montrer que : $p^n = \Sum{k=1}{p} \binom{p}{k} S(n,k).$
- Pour $i \in \Intn{1}{p}$, on note $A_i$ l'ensemble des applications de $\Intn{1}{n}$ dans $\Intn{1}{p}$ qui ne prennent pas la valeur $i$. À l'aide de ces ensembles et de la formule du crible, montrer que $$ S(n,p) = \Sum{k=0}{p} (-1)^k \binom{p}{k} (p-k)^n. $$
Soient $n$ et $p$ deux entiers naturels non nuls.
On appelle chemin monotone, tout déplacement sur une grille de coordonnées entières obtenu en partant de la case $(0, 0)$ et en se déplaçant successivement d'une unité vers la droite ou d'une unité vers le haut.
- Combien existe-t-il de chemins monotones rejoignant la case $(n, p)$ ?
On s'intéresse désormais aux chemins monotones rejoignant la case $(n, n)$. On dit qu'un tel chemin est sous-diagonal si les cases $(x, y)$ qu'il emprunte vérifient la condition $y \le x$.
- On considère un chemin qui n'est pas sous-diagonal et on lui associe un nouveau chemin déterminé en changeant les mouvements vers la droite par des mouvements vers le haut, et inversement, dès son premier franchissement de la diagonale. Quelle nouvelle case rejoint ce chemin ?
- Combien existe-t-il de chemins sous-diagonaux rejoignant la case $(n, n)$ ?
- Corrigé : commande LaTeX inconnue : \Psi, \fill (absente des macros reconnues — coquille probable ou macro légitime à ajouter à la liste)
II) Calculs de sommes
Soit $E$ un ensemble fini de cardinal $n \in \N$. Calculer :
- $\Sum{X \subset E}{} \Card{X}$
- $\Sum{X, Y \subset E}{} \Card{X \cap Y}$
- $\Sum{X, Y \subset E}{} \Card{X \cup Y}$
- Corrigé : commande mathématique hors de tout $ : \Card, \Sum, \cap, \cup, \in, \subset (probablement un $ manquant autour)
Montrer que, pour tout $n \ge 2$, $$ \Sum{X \in \Ps(\Intn{1}{n})}{} \Sum{k \in X}{} k = n(n+1)2^{n-2}. $$
- Corrigé : commande mathématique hors de tout $ : \Sum, \in (probablement un $ manquant autour)
Soit $n \in \N^*$. On note $\Sr_n$ l'ensemble des permutations de $\Intn{1}{n}$. Calculer $ \f{1}{n!} \Sum{f \in \Sr_n}{} \Sum{k=1}{n} \abs{f(k) - k}.$
On pourra intervertir les sommes.
- Énoncé : commande mathématique hors de tout $ : \Sum, \abs, \in (probablement un $ manquant autour)
- Corrigé : commande mathématique hors de tout $ : \Card, \Sum, \abs, \in, \leq, \times (probablement un $ manquant autour)
III) Double comptage et relations de récurrence
Soient $p, q \in \N$ et $n \in \Intn{0}{p+q}$. Proposer une démonstration par dénombrement de l’égalité $$ \binom{p+q}{n} = \Sum{k=0}{n} \binom{p}{k} \binom{q}{n-k} $$
- Corrigé : commande LaTeX inconnue : \fill (absente des macros reconnues — coquille probable ou macro légitime à ajouter à la liste)
Soient $n, p \in \N$.
- Quelles sont les valeurs possibles du maximum d'une $\pa{p + 1}$-combinaison de $\Intn{1}{n + p + 1}$ ?
- Calculer de deux manières le nombre de $\pa{p + 1}$-combinaisons de $\Intn{1}{n + p + 1}$. Conclusion ?
- Corrigé : commande mathématique hors de tout $ : \Sum, \binom (probablement un $ manquant autour)
Soient $n, k \in \N^*$. Soit $u_{n, k}$ le nombre de parties de $\Intn{1}{n}$ de cardinal $k$ qui ne contiennent pas deux entiers consécutifs. Montrer que $u_{n, k} = \dbinom{n-k+1}{k}$. On pourra commencer par établir une relation de récurrence.
- Corrigé : commande LaTeX inconnue : \Concl (absente des macros reconnues — coquille probable ou macro légitime à ajouter à la liste)
IV) Principe des tiroirs
On considère un ensemble $X$ de $n+1$ entiers distincts choisis dans $\Intn{1}{2n}$. Démontrer que parmi les éléments de $X$, on peut toujours trouver $2$ entiers :
- consécutifs.
- dont la somme fait $2n+1$.
- ★★ dont l'un divise l'autre.
Soit $A$ une partie de $\Intn{1}{100}$ de cardinal $55$. Montrer qu'il existe $n \in A$ tel que $n + 9 \in A$.
- Soient $x_1, \dots, x_n \in \Z$. Montrer l'existence d'une partie non vide $I$ de $\Intn{1}{n}$ pour laquelle $\Sum{i \in I}{} x_i$ est un multiple de $n$.
Indication : On pourra faire une division euclidienne. - Soient $x_1, \dots, x_n \in \R$. Montrer l'existence d'une partie non vide $I$ de $\Intn{1}{n}$ et d'un entier $N$ pour lesquels $\abs{N - \Sum{i \in I}{} x_i} \leq \f{1}{n + 1}$.
Glissez une image, collez-la (Ctrl+V), ou parcourez un fichier — ou collez directement l'énoncé en texte.