Dénombrement

Exercice 6083. Un mot $M$ long de $n$ lettres est constitué de $r$ lettres différentes.\\ La $j$-ème lettre apparaît $p_j$ fois dans le mot $M$, avec \[ p_1+\dots+p_r=n. \] Combien d'anagrammes du mot $M$ peut-on constituer ?
Exercice 6084. \\
  1. Quel est le coefficient de $a^2b^5c^3$ dans le développement de $(a+b+c)^{10}$ ?\\
  2. Même question avec $a_1^{k_1}a_2^{k_2}\dots a_p^{k_p}$ dans $(a_1+a_2+\dots+a_p)^n$.
Exercice 6085. Cinq cartes d'un jeu de $52$ cartes sont servies à un joueur de poker.\\
  1. Combien y a-t-il de mains possibles ?\\
  2. Combien de ces mains comportent exactement un As ?\\
  3. Combien de ces mains ne comportent aucun As ?\\
  4. Combien comportent au moins un As ?
Exercice 6086. Calculer le nombre de lois internes abéliennes sur un ensemble de cardinal $n$.
Exercice 6087. Sur une étagère d'une bibliothèque sont disposés 20 libres deux à deux distincts. \\
  1. Combien y a-t-il de rangements possibles ? \\
  2. Deux de ces 20 livres sont signés par monsieur F. Combien y-a-t-il de rangements possibles tels que ces deux livres soient côte à côte ? \\
  3. On range les livres completement au hasard. QUelle est la probabilité que les deux livres de monsieur F. ne soient pas côte à côte ?
Exercice 6088. 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$ ?
Exercice 6089. On trace dans un plan $n$ droites en position générale, c'est-à-dire que deux d'entre elles ne sont jamais parallèles et que trois d'entre elles ne sont jamais concourantes.\\ Combien forme-t-on ainsi de triangles ?
Exercice 6090. Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $n$ et $p$.\\ Combien y a-t-il d'injections de $E$ dans $F$ ?
Exercice 6091. Combien existe-t-il de relations d'ordre total sur un ensemble $E$ à $n$ éléments ?
Exercice 6092. Soit un club anglophile constitué de $35$ membres.\\ Sur ces $35$ membres, $31$ ont traversé la Tamise sur le Tower Bridge, $5$ ont gravi le Ben Nevis et $3$ ont fait les deux.\\
  1. Combien ont traversé la Tamise ou gravi le Ben Nevis ?\\
  2. Combien n’ont fait ni l’un, ni l’autre ?
Exercice 6093. On sert une main de $5$ cartes à un joueur de poker d'un jeu de $52$ cartes. \\
  1. Quelle est la probabilité que celle-ci comporte exactement une paire d'as ? \\
  2. Même question sachant que le jeu distribué comporte au moins un As.
Exercice 6094. Soient $n,p\in\mathbb{N}^*$.\\ Quel est le nombre de suites strictement croissantes constituées de $p$ nombres de l’intervalle $[1,n]$ ?
Exercice 6095. Soient $(a, b, n) \in \mathbb{N}^3$. Montrer que : \[ \sum_{k=0}^{n} \binom{a}{k}\binom{b}{n-k} = \binom{a+b}{n}. \]
Exercice 6096. Un club anglophile est constitué de $35$ membres.\\ Sur ces $35$ membres, $31$ ont traversé la Tamise sur le Tower Bridge, et $5$ ont gravi le Ben Nevis.\\ $3$ ont fait les deux.\\ Combien ont traversé la Tamise sur le Tower Bridge ou gravi le Ben Nevis ?\\ Combien n’ont fait ni l’un, ni l’autre ?
Exercice 6097. Retrouver la formule donnant le cardinal de la réunion de trois parties $A$, $B$, $C$ d’un ensemble $E$.\\ Dans une classe de $36$ élèves, tous les élèves étudient au moins une langue étrangère parmi l’allemand, l’espagnol et l’anglais.\\ $22$ étudient l’anglais, $22$ l’allemand, et $18$ l’espagnol.\\ $10$ étudient à la fois l’anglais et l’allemand, $9$ étudient à la fois l’allemand et l’espagnol, et $11$ étudient à la fois l’anglais et l’espagnol.\\ Combien d’élèves étudient les trois langues ?
Exercice 6098. Un club anglophile est constitué de $35$ membres. Sur ces $35$ membres, $31$ ont traversé la Tamise sur le Tower Bridge, et $5$ ont gravi le Ben Nevis. $3$ ont fait les deux. Combien ont traversé la Tamise sur le Tower Bridge ou gravi le Ben Nevis ? Combien n’ont fait ni l’un, ni l’autre ?
Exercice 6099.
  1. Retrouver la formule donnant le cardinal de la réunion de trois parties $A$, $B$, $C$ d’un ensemble $E$.\\
  2. Dans une classe de $36$ élèves, tous les élèves étudient au moins une langue étrangère parmi l’allemand, l’espagnol et l’anglais. $22$ étudient l’anglais, $22$ l’allemand, et $18$ l’espagnol. $10$ étudient à la fois l’anglais et l’allemand, $9$ étudient à la fois l’allemand et l’espagnol, et $11$ étudient à la fois l’anglais et l’espagnol. Combien d’élèves étudient les trois langues ?
Exercice 6100.
  1. Huit coureurs sont au départ d’une course. Combien de classements et de podiums sont-ils possibles ?\\
  2. Combien y a-t-il de parties à $3$ éléments dans un ensemble à $9$ éléments ?\\
  3. Sur une grille de $16$ cases, on souhaite placer $6$ points indiscernables. Combien y a-t-il de possibilités ?\\
  4. Combien de nombres à $6$ chiffres choisis parmi $1$, $2$ et $3$ existe-t-il ?\\
  5. À partir de combien d’élèves est-on sûr de trouver deux élèves portant les mêmes initiales dans un lycée ?\\
  6. Dans une soirée, il y a $7$ hommes et $8$ femmes. Les femmes font la bise à tout le monde, une fois seulement, les hommes se serrent la main et font la bise aux femmes. Combien y a-t-il de poignées de main échangées ? Combien y a-t-il de bises échangées ?\\
  7. Trois cubes rouges, identiques, doivent être rangés dans une boîte à cinq compartiments numérotés $1$, $2$, $3$, $4$, $5$. Dénombrer les rangements possibles. Même question si les cubes sont l’un rouge, l’autre bleu et le dernier blanc.\\
  8. $10$ tee-shirts différents doivent être rangés en une pile sur une étagère. Combien de rangements sont possibles ? Même question si on doit faire deux piles de $5$ tee-shirts.\\
  9. Dans un jeu de $52$ cartes, on tire deux cartes simultanément. Combien de tirages sont tels qu’une carte est rouge et l’autre noire ?\\
  10. Dans un jeu de $52$ cartes, on tire trois cartes simultanément. Combien de tirages comportent au moins un roi ?\\
  11. Combien y a-t-il d’anagrammes du mot AVIRON ? du mot TRIATHLON ? du mot NATATION ?\\
  12. Soit $n \in \N^*$. Quel est le nombre de termes dans les sommes suivantes ?
    • $\Sum_{1 \leqslant i < j \leqslant n} a_{i,j}$.
    • $\Sum_{1 \leqslant i \leqslant j \leqslant n} a_{i,j}$.
  13. On veut former des $3$-listes de chiffres qui forment une suite strictement croissante. Combien de suites strictement croissantes de $3$ chiffres existe-t-il ?
Exercice 6101. Combien le mot ABRACADABRA possède-t-il d’anagrammes ? Et le mot LIPSCHITZIENNE ?
Exercice 6102. Combien y a-t-il de couples $(x,y)$ dans $\{1,\ldots,n\}^2$ tels que :
  1. $x < y$ ?\\
  2. $y=x+1$ ?\\
  3. $|x-y| \leqslant 1$ ?
Exercice 6103. On appelle diagonale d’un polygone convexe tout segment joignant deux de ses sommets non consécutifs. Si un polygone possède autant de diagonales que de côtés, combien possède-t-il de côtés ?
Exercice 6104.
  1. De combien de façons peut-on ranger $10$ chemises différentes dans $7$ tiroirs de taille infinie ?\\
  2. De combien de façons peut-on garer $3$ voitures identiques sur $5$ places de parking numérotées ?\\
  3. De combien de façons peut-on distribuer $10$ places de théâtre à $10$ personnes ?\\
  4. Combien peut-on former de nombres différents de $8$ chiffres avec cinq $1$ et trois $2$ ?
Exercice 6105. Soient $n \in \mathbb{N}^*$ et $E$ un ensemble fini à $n$ éléments. Dénombrer dans $E$ :\\
  1. les relations,\\
  2. les relations réflexives,\\
  3. les relations symétriques,\\
  4. les relations antisymétriques,\\
  5. les relations réflexives et symétriques,\\
  6. les relations réflexives et antisymétriques.
Exercice 6106. Soient $p,q\in\mathbb{N}$ et $n\in\llbracket 0,p+q\rrbracket$.\\ 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}. \]
Exercice 6107. Soit $(a_n)_{n\in\mathbb{N}}$ une suite réelle fixée. Construisons une suite $(b_n)_{n\in\mathbb{N}}$ par \[ \forall n\in\mathbb{N},\qquad b_n=\sum_{k=0}^{n}\binom{n}{k}a_k. \] Considérons $\varphi\in\mathcal{L}(\mathbb{R}[X],\mathbb{R})$ définie par \[ \varphi(X^k)=a_k \] pour tout $k$.\\
    1. Soit $Y=X+1$. Pour tout $n\in\mathbb{N}$, calculer $\varphi(Y^n)$ en fonction des $a_k$.\\
    2. Démontrer que \[ \forall n\in\mathbb{N},\qquad a_n=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}b_k. \]
    1. Soit $S_{q,n}$ le nombre de surjections d’un ensemble à $q$ éléments dans un ensemble à $n$ éléments. Pour $k\in\llbracket 1,n\rrbracket$, déterminer en fonction de $S_{q,k}$ le nombre de fonctions d’un ensemble à $q$ éléments dans un ensemble à $n$ éléments telles que le cardinal de l’image soit égal à $k$.\\
    2. En déduire que \[ n^q=\sum_{k=1}^{n}\binom{n}{k}S_{q,k}. \]
Exercice 6108. Combien de mains de $13$ cartes peut-on constituer dans un jeu de $52$ cartes telles que :\\
  1. Elles contiennent exactement un roi ?\\
  2. Elles contiennent au plus un roi ?\\
  3. Elles contiennent le roi de trèfle et au moins $2$ piques ?\\
  4. Elles contiennent $5$ cartes d’une couleur, $4$ cartes d’une autre, et $4$ cartes d’une troisième ?
Exercice 6109. Pour le $14$ juillet, un artificier s’occupe d’un feu d’artifice composé de $8$ blocs comportant chacun quatre fusées.\\ Le pupitre de mise à feu possède $32$ boutons, correspondant chacun à une fusée. L’artificier appuie simultanément et au hasard sur $5$ boutons.\\
  1. Dénombrer tous les cas possibles.\\
  2. Dénombrer tous les cas où les $5$ fusées partent de $5$ blocs différents.\\
  3. Dénombrer tous les cas où $3$ fusées partent d’un même bloc, et les deux autres d’un même bloc, différent du précédent.\\
  4. Dénombrer tous les cas où $2$ fusées partent d’un même bloc, $1$ d’un autre bloc et $2$ d’un autre encore.
Exercice 6110. Soit $A$ une partie d'un ensemble $E$ à $n$ éléments.\\ On pose $p=\Card(A)$.\\
  1. Combien y a-t-il de parties $X$ de $E$ contenant $A$ ?\\
  2. Combien y a-t-il de parties $X$ de $E$ à $m\in\llbracket p,n\rrbracket$ éléments contenant $A$ ?\\
  3. Combien y a-t-il de couples $(X,Y)$ de parties de $E$ tels que $X \cap Y=A$ ?
Exercice 6111. Combien y a-t-il de $p$-cycles dans le groupe $(\mathfrak{S}_n,\circ)$ ?
Exercice 6112. Soient $E=\{1,\dots,n\}$ et $F=\{1,\dots,p\}$ avec $n \leqslant p$.\\ Combien y a-t-il d'applications strictement croissantes de $E$ vers $F$ ?
Exercice 6113. Soient $A,B,C$ trois parties d’un ensemble $E$.\\
  1. Retrouver la formule donnant le cardinal de $A \cup B \cup C$.\\
  2. Dans une classe de $36$ élèves, tous étudient au moins une langue parmi anglais, allemand, espagnol.\\ On a : $22$ anglais, $22$ allemand, $18$ espagnol, $10$ anglais-allemand, $9$ allemand-espagnol, $11$ anglais-espagnol.\\ Combien étudient les trois langues ?
Exercice 6114. Soit $E$ un ensemble à $n$ éléments.\\ Calculer $\Sum_{X \subset E}\Card(X)$ et $\Sum_{X,Y \subset E}\Card(X \cap Y)$.
Exercice 6115.
  1. Combien existe-t-il de suites strictement croissantes de $p$ entiers choisis dans $\{1,\dots,n\}$ ?\\
  2. En déduire le nombre de suites $(x_1,\dots,x_p)$ vérifiant \[ x_1+\dots+x_p \leqslant n \quad \text{et} \quad x_1,\dots,x_p\in\mathbb{N}^*. \]
  3. Même question avec \[ x_1+\dots+x_p=n \quad \text{et} \quad x_1,\dots,x_p\in\mathbb{N}^*. \]
Exercice 6116. Soit $a$ et $b$ deux entiers positifs ou nuls.\\ On appelle chemin monotone de $(0,0)$ vers $(a,b)$ une succession de pas de longueur $1$ vers la droite ou vers le haut, de point de départ $(0,0)$ et de point d’arrivée $(a,b)$.\\ On dispose de $x$ couleurs pour colorier les pas vers le haut, et de $y$ couleurs pour les pas vers la droite.\\ En comptant de deux manières différentes les chemins colorés de longueur $n$, retrouver la formule du binôme pour $(x+y)^n$, dans le cas où $x$ et $y$ sont entiers positifs.
Exercice 6117. Soit $n \in \mathbb{N}^*$. Déterminer le nombre de surjections de $\{1, \ldots, n+1\}$ sur $\{1, \ldots, n\}$.
Exercice 6118. Déterminer $\mathrm{Card}(\mathrm{O}_n(\mathbb{R}) \cap M_n(\mathbb{Z}))$.
Exercice 6119. Soit $n$ et $k$ deux entiers naturels tels que $k \leqslant n$.\\
  1. Montrer que pour tout entier $p$ compris entre $0$ et $k$, on a \[ \binom{n}{p}\binom{n-p}{k-p}=\binom{n}{k}\binom{k}{p}. \]
  2. En déduire que \[ \Sum_{p=0}^{k}\binom{n}{p}\binom{n-p}{k-p}=2^k\binom{n}{k}. \]
Exercice 6120.
  1. Calculer les sommes suivantes pour $n$ entier positif : \[ A_n=\Sum_{k=0}^{n}k\binom{n}{k}, \quad B_n=\Sum_{k=0}^{n}k(k-1)\binom{n}{k}, \quad C_n=\Sum_{k=0}^{n}k^2\binom{n}{k}. \]
  2. Montrer par récurrence que, pour tout entier naturel $n$, et pour tout entier naturel $p \leqslant n$, \[ \Sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1}. \] Redémontrer ce résultat en utilisant le fait que \[ \binom{k}{p}=\binom{k+1}{p+1}-\binom{k}{p+1}. \]
Exercice 6121. On aligne $n$ boîtes et un nombre suffisamment grand de boules. On dispose les boules dans les boîtes de la manière suivante :
  • Il y a au plus une boule par boîte.
  • Il n’y a jamais deux boîtes consécutives vides.
On note $F_n$ le nombre de manières de placer des boules dans les $n$ premières boîtes. Montrer que \[ F_{n+2}=F_{n+1}+F_n. \]
Exercice 6122. Soit $n \in \N^*$ et $E$ un ensemble possédant $n$ éléments.\\ On désigne par $\mathcal{P}(E)$ l’ensemble des parties de $E$.\\
  1. Déterminer le nombre $a$ de couples $(A,B) \in \mathcal{P}(E)^2$ tels que $A \subset B$.\\
  2. Déterminer le nombre $b$ de couples $(A,B) \in \mathcal{P}(E)^2$ tels que $A \cap B=\emptyset$.\\
  3. Déterminer le nombre $c$ de triplets $(A,B,C) \in \mathcal{P}(E)^3$ tels que $A$, $B$, $C$ soient deux à deux disjoints et vérifient \[ A \cup B \cup C=E. \]
Exercice 6123.
  1. Combien y a-t-il d’anagrammes du mot DENOMBREMENT ?\\
  2. Soit $n,p \in \N^*$.
    1. Combien existe-t-il de matrices de $\mathcal{M}_{n,p}(\R)$ dont les coefficients sont $0$ ou $1$ ?\\
    2. Combien en existe-t-il dont chaque ligne contient exactement un coefficient $1$ ?\\
    3. Combien en existe-t-il dont chaque colonne contient exactement deux coefficients $1$ ?\\
    4. Si $n=p$, combien en existe-t-il dont chaque ligne et chaque colonne contient exactement un coefficient $1$ ?
Exercice 6124. On considère $n$ personnes, avec $n < 365$. Combien existe-t-il de cas possibles où au moins deux personnes ont la même date d’anniversaire ?\\ Trouver le nombre d’applications surjectives de $E$ vers $F$ si $\mathrm{Card}(E)=n+1$ et $\mathrm{Card}(F)=n$.
Exercice 6125. Soit $E$ un ensemble de cardinal $n$, avec $n$ un entier impair.\\ Soit $\mathcal{P}_i(E)$ l’ensemble des parties de $E$ de cardinal impair et $\mathcal{P}_p(E)$ l’ensemble des parties de $E$ de cardinal pair.\\ Soit $\varphi$ l’application de $\mathcal{P}_i(E)$ vers $\mathcal{P}_p(E)$ qui à $A$ associe $E \setminus A$.\\
  1. Montrer que $\varphi$ est bien définie, puis que $\varphi$ est bijective.\\
  2. En déduire proprement que \[ \mathrm{Card}(\mathcal{P}_i(E))=2^{n-1}. \]
  3. On pose $n=2p+1$. En déduire que \[ \Sum_{k=0}^{p}\binom{n}{2k+1}=2^{n-1}. \]
Exercice 6126. Dénombrer les applications $f : \{1, \ldots, n\} \to \{1, \ldots, n\}$ telles que $f \circ f = f$.
Exercice 6127. Fournir une preuve combinatoire de l’identité de Vandermonde :\\ \[ \forall n,N,M\in\mathbb{N},\quad \Sum_{k=0}^n\binom{N}{k}\binom{M}{n-k}=\binom{N+M}{n} \] en convenant que $\binom{a}{b}$ est nul dès que $\neg(0\leqslant b\leqslant a)$.\\ Formaliser cette preuve en une preuve rigoureuse si ce n’est déjà fait.\\ En déduire une formule plus générale.
Exercice 6128. Soit $E$ un ensemble de cardinal $n\geqslant 1$.\\
  1. Calculer $\Sum_{X\subset E}\mathrm{Card}(X)$.\\
    1. Déterminer le nombre de couples $(A,B)$ de parties disjointes de $E$.\\
    2. Calculer $\Sum_{X,Y\in\mathcal{P}(E)}\mathrm{Card}(X\cap Y)$.
Exercice 6129. On note $d_n$ le nombre de permutations $\sigma$ de $\llbracket 1,n\rrbracket$ vérifiant \[ \forall k\in\llbracket 1,n\rrbracket,\; \sigma(k)\neq k. \] On convient que $d_0=1$.\\
  1. Établir \[ \forall n\in\mathbb{N}^*,\quad n!=\Sum_{k=0}^{n}\binom{n}{k}d_{n-k}. \]
  2. En déduire \[ \forall n\in\mathbb{N},\quad d_n=\Sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k!. \]
Exercice 6130. On note $\mathfrak{S}_n$ l'ensemble des permutations de $\llbracket 1,n\rrbracket$ et $\mathfrak{S}_n(k)$ le sous-ensemble des permutations possédant exactement $k$ points fixes.\\ On pose \[ s_n(k)=\Card(\mathfrak{S}_n(k)). \]
  1. Calculer $\Sum_{k=0}^{n}s_n(k)$.\\
  2. Soient $n,k \geqslant 1$. En calculant de deux façons le nombre de couples $(\sigma,x)$ constitués de $\sigma\in\mathfrak{S}_n(k)$ et de $x$ point fixe de $\sigma$, établir \[ ks_n(k)=ns_{n-1}(k-1). \]
  3. En déduire \[ s_n(k)=\binom{n}{k}s_{n-k}(0). \]
  4. Retrouver directement le résultat précédent.
Exercice 6131. Pour tout $n \in \mathbb{N}^*$, combien y a-t-il de nombres entiers naturels dont l'écriture en base dix comporte exactement $n$ chiffres dont un chiffre $1$ et un seul ?
Exercice 6132. On tire successivement sans remise $n$ boules dans une urne contenant initialement $b$ boules blanches et $r$ boules rouges, où $n \leqslant b+r$.\\
  1. On suppose les boules blanches discernables entre elles (par exemple par une numérotation) ainsi que les boules rouges.\\
    1. Dénombrer le nombre de tirages possibles amenant un total de exactement $k$ boules rouges ($k \leqslant \min(n,r)$).\\
    2. Déterminer le nombre de tirages telles que la $m$-ième boule rouge tirée le soit lors du $k$-ième tirage ($m \leqslant r$, $k-m \leqslant b$).\\
  2. Mêmes questions en supposant les boules blanches discernables et les boules rouges indiscernables.\\
  3. Mêmes questions en supposant les boules blanches indiscernables et les boules rouges discernables.\\
  4. Mêmes questions en supposant les boules blanches indiscernables entre elles, ainsi que les boules rouges.
Exercice 6133. (Formule de Vandermonde généralisée)\\ Soit $p \geqslant 2$, $q \geqslant 0$, et $(a_1,\ldots,a_p) \in \N^p$.\\ Montrer que\\ \[ \Sum_{\substack{j_1+\cdots+j_p=q}} \binom{a_1}{j_1}\cdots\binom{a_p}{j_p} =\binom{a_1+\cdots+a_p}{q} \]
Exercice 6134. Soit $n \geqslant 2$.\\ Quel est le nombre de surjections de $\llbracket 1,n+2 \rrbracket$ dans $\llbracket 1,n \rrbracket $ ?
Exercice 6135. On appelle dérangement de $\llbracket 1,n\rrbracket$ une permutation $\sigma \in \mathfrak{S}_n$ n’ayant aucun point fixe.\\ On note $D_n$ le nombre de dérangements de $\llbracket 1,n\rrbracket$.\\ Par convention, $D_0=1$.\\ Montrer que pour tout $n \in \N^*$, $D_{n+1}=n(D_n+D_{n-1})$.\\ Indication : on pourra admettre que toute permutation de $\llbracket 1,n\rrbracket$ s’écrit comme produit de permutations cycliques à supports formant une partition de $\llbracket 1,n\rrbracket$.
Exercice 6136. Combien existe-t-il de mots de $9$ lettres contenant le mot MERCI ? Le mot OSLO ?
Exercice 6137.
  1. Combien existe-t-il de $p$-listes d’entiers de $\{1,\ldots,n\}$ strictement croissantes ?\\
  2. On note $E$ l’ensemble des $(x_1,\ldots,x_p) \in (\N^*)^p$ tels que \[ x_1+\cdots+x_p \leqslant n. \] Montrer que $E$ est en bijection avec l’ensemble $F$ des $p$-listes d’entiers de $[[1,n]]$ strictement croissantes.\\ En déduire combien il existe de suites $(x_1,\ldots,x_p) \in (\N^*)^p$ telles que \[ x_1+\cdots+x_p \leqslant n. \]
  3. En déduire combien il existe de suites $(x_1,\ldots,x_p) \in (\N^*)^p$ telles que \[ x_1+\cdots+x_p=n. \]
Exercice 6138. Le but de cet exercice est d’établir la formule dite du crible.\\ Soit $n \in \N^*$. Soient $A_1,\ldots,A_n$ des ensembles finis. Montrer que \[ \mathrm{Card}\left(\bigcup_{i=1}^{n}A_i\right) = \Sum_{k=1}^{n}(-1)^{k+1} \Sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} \mathrm{Card}\left(\bigcap_{j=1}^{k}A_{i_j}\right). \] On pose \[ E=\bigcup_{i=1}^{n}A_i. \] Pour $A \subset E$, on introduit la fonction caractéristique $\mathbf{1}_A$ de $A$ définie sur $E$ par \[ \mathbf{1}_A(x)= \begin{cases} 1 & \mathrm{si}\ x \in A\\ 0 & \mathrm{si}\ x \notin A. \end{cases} \]
  1. Montrer que pour toute partie $A$ de $E$, on a \[ \mathrm{Card}(A)=\Sum_{x \in E}\mathbf{1}_A(x). \]
  2. Montrer que \[ 1-\mathbf{1}_{\bigcup_{i=1}^{n}A_i} = \Prod_{i=1}^{n}(1-\mathbf{1}_{A_i}). \]
  3. Montrer que \[ \Prod_{i=1}^{n}(1-\mathbf{1}_{A_i}) = 1+\Sum_{k=1}^{n}(-1)^k \Sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} \mathbf{1}_{A_{i_1}}\cdots \mathbf{1}_{A_{i_k}}. \]
  4. En évaluant l’égalité établie à la question $2$ en tout $x \in E$, puis en sommant, terminer la preuve.
Exercice 6139. Formule du crible :\\
  1. Si $E_1,\ldots,E_n$ sont $n$ ensembles finis, montrer que :\\ \[ \mathrm{Card}\left(\bigcup_{i=1}^n E_i\right) =\Sum_{i=1}^n\mathrm{Card}(E_i) -\Sum_{1 \leqslant i < j \leqslant n}\mathrm{Card}(E_i\cap E_j)+\cdots +(-1)^{k+1}\Sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n}\mathrm{Card}\left(\bigcap_{j=1}^k E_{i_j}\right) +\cdots+(-1)^{n+1}\mathrm{Card}\left(\bigcap_{i=1}^n E_i\right). \]
  2. Une soirée dansante réunit $n$ couples mariés hétérosexuels. Chaque homme invite au hasard une femme masquée. Quelle est la probabilité qu’aucun mari ne danse avec sa femme ?
Exercice 6140. Soit $n\in\mathbb{N}^*$.\\ On note $X$ l'ensemble des suites $(x_1,\dots,x_n)$ avec \[ \forall k\in\llbracket 1,n\rrbracket,\quad x_k=1 \; \text{ou} \; -1. \] À une suite $x=(x_1,\dots,x_n)$, on associe la suite $(s_0,s_1,\dots,s_n)$ définie par \[ s_k=s_{k-1}+x_k. \]
  1. On note $p$ le nombre de $1$ dans la suite $x$. Exprimer $s_n$ en fonction de $n$, $p$ et $s_0$.\\
  2. Étant donné $m\in\mathbb{N}$, combien existe-t-il de chemins tels que $s_n=m$ ?\\
  3. On suppose $s_0\in\mathbb{N}$. Expliquer pourquoi il y a autant de chemins joignant $(0,-s_0)$ à $(n,m)$ que de chemins joignant $(0,s_0)$ à $(n,m)$ et coupant l'axe des abscisses.\\
  4. En déduire le nombre de chemins joignant $(0,1)$ à $(n,m)$ dont tous les points sont d'ordonnée strictement positive.
Exercice 6141. On considère une matrice $3\times 3$ composée des $9$ jetons numérotés de $1$ à $9$.\\ On cherche à déterminer la probabilité $p$ pour que le déterminant de la matrice soit un entier impair.\\
  1. Soit $A=(a_{i,j})\in M_n(\mathbb{Z})$. Montrer que la classe de congruence du déterminant de $A$ modulo $2$ est égale à celle du déterminant de la matrice obtenue en remplaçant chaque coefficient par son reste modulo $2$.\\
  2. On note $M$ l'ensemble des matrices carrées d'ordre $3$ composées des $9$ jetons. Déterminer $\Card(M)$.\\ On définit \[ \Omega=\{M\in M \mid \det(M) \; \text{impair}\} \] et $\Delta$ l'ensemble des matrices carrées d'ordre $3$ dont cinq coefficients valent $1$, quatre valent $0$, et de déterminant impair.\\
  3. Donner une relation entre $\Card(\Omega)$ et $\Card(\Delta)$.\\
  4. On considère une matrice de $\Delta$ dont une colonne possède trois coefficients égaux à $1$. Donner le nombre $K_1$ de telles matrices.\\ On considère une matrice de $\Delta$ dont deux colonnes possèdent exactement un coefficient nul. Déterminer le nombre $K_2$ de telles matrices.\\
  5. Calculer $\Card(\Delta)$ puis $\Card(\Omega)$.\\
  6. Déterminer la probabilité $p$.
Exercice 6142. Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $m$ et $n$ tels que $m \leqslant n$. On note $i_{m,n}$ le nombre d’injections de $E$ dans $F$ et $s_{n,m}$ le nombre de surjections de $F$ sur $E$. On pose \[ \mathcal{C}=\{(f,g)\in F^E \times E^F \mid g\circ f=\mathrm{id}_E\} \]
  1. Rappeler une expression de $i_{m,n}$.
  2. Rappeler des propriétés de $f$ et $g$ si $(f,g)\in\mathcal{C}$.
  3. Justifier que \[ |\mathcal{C}|=i_{m,n}m^{n-m} \]
  4. Montrer que \[ |\mathcal{C}| \leqslant s_{n,m}\left(\Frac{n}{m}\right)^m \]
  5. En déduire qu’une application \[ f:E\to F \] prise au hasard a moins de chance d’être injective qu’une application \[ g:F\to E \] n’a de chance d’être surjective.
Exercice 6143. Pour tout $n \in \N^*$, on note $p_n$ le $n$-ième nombre premier.\\
  1. Montrer que pour tout $n \in \N^*$, \[ p_n \geqslant 2n-1. \] On fixe à présent un entier $n \geqslant 3$, et on pose pour tout $k \in [[1,p_n]]$ : \[ m_k=kp_1\cdots p_{n-1}-1. \]
  2. Montrer que les entiers $m_1,\ldots,m_{p_n}$ sont premiers entre eux deux à deux.\\
  3. En déduire que l’un des entiers $m_1,\ldots,m_{p_n}$ n’est divisible par aucun des nombres $p_n,\ldots,p_{3n-3}$.\\
  4. En déduire que \[ p_{3n-2} < p_1\cdots p_n. \]
Exercice 6144. On rappelle que les permutations sont les bijections de $[[1,n]]$ vers $[[1,n]]$. On note $d_n$ le nombre de permutations $\sigma$ vérifiant \[ \forall k \in [[1,n]],\quad \sigma(k) \neq k. \] On dit que $\sigma$ est un dérangement de $[[1,n]]$. On convient que $d_0=1$.\\
  1. Soit $A \subset [[1,n]]$. On note \[ S_A=\{\sigma \in S_n,\ \forall x \in A,\ \sigma(x)=x\ \mathrm{et}\ \forall x \notin A,\ \sigma(x) \neq x\}. \]
    1. Discuter du cardinal de $S_A$.\\
    2. Faire le lien entre les $S_A$ et $S_n$.
  2. Montrer que \[ n!=\Sum_{k=0}^{n}\binom{n}{k}d_{n-k}. \]
  3. Montrer par récurrence que \[ \forall n \in \N,\quad d_n=\Sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k!. \]
Exercice 6145. Soit $n \in \N^*$. On note $X$ l’ensemble des suites $(x_1,\ldots,x_n)$ avec \[ \forall k \in [[1,n]],\quad x_k=1\ \mathrm{ou}\ x_k=-1. \] À chaque suite $x=(x_1,\ldots,x_n)$ élément de $X$, on associe la suite $(s_0,\ldots,s_n)$ avec $s_0 \in \Z$ et, pour tout $k \in [[1,n]]$, \[ s_k=s_{k-1}+x_k. \] Ainsi on forme une ligne brisée déterminée par les points de coordonnées $(k,s_k)$.\\
  1. Faire un dessin pour $x=(-1,1,1,-1,1)$.\\
  2. On note $p$ le nombre de $1$ dans la suite $x=(x_1,\ldots,x_n) \in X$. Exprimer $s_n$ en fonction de $n$, $p$ et $s_0$.\\
  3. Soit $m \in \N$. Combien existe-t-il de chemins tels que $s_n=m$ ?\\
  4. Soit $s_0 \in \N$. Expliquer pourquoi il y a autant de chemins joignant $(0,-s_0)$ à $(n,m)$ que de chemins joignant $(0,s_0)$ à $(n,m)$ et coupant l’axe des abscisses.\\
  5. En déduire le nombre de chemins joignant $(0,1)$ à $(n,m)$ sans couper l’axe des abscisses.
Exercice 6146. Pour tout $n,p \in \N^*$, on note $S_{n,p}$ le nombre de surjections de $[[1,n]]$ sur $[[1,p]]$.\\
  1. Déterminer $S_{n,1}$, $S_{n,2}$, $S_{n,n}$ et $S_{n+1,n}$ pour tout $n \in \N^*$, ainsi que $S_{n,p}$ pour $n < p$.\\
    1. Montrer que pour tout $n,p \in \N^*$, \[ S_{n+1,p+1}=(p+1)(S_{n,p+1}+S_{n,p}). \]
    2. Dresser un tableau des entiers $S_{n,p}$ où $n$ et $p$ décrivent $[[1,4]]$.
  3. Montrer que pour tout $n,p \in \N^*$, \[ p^n=\Sum_{k=1}^{p}\binom{p}{k}S_{n,k}. \]
    1. Montrer par dénombrement que pour tout $p,k,i \in \N$ tels que $i \leqslant k \leqslant p$, \[ \binom{p}{k}\binom{k}{i}=\binom{p}{i}\binom{p-i}{k-i}. \]
    2. En déduire que pour tout $n,p \geqslant 1$, \[ S_{n,p}=\Sum_{k=1}^{p}(-1)^{p-k}\binom{p}{k}k^n. \]
Exercice 6147. Soit $n,p,q \in \N$ et soit $A$ l’ensemble des mots de $p+q+1$ lettres composés à l’aide des lettres E et C.\\
  1. Déterminer $\mathrm{Card}(A')$ sous forme d’une somme, où $A'$ est l’ensemble des éléments de $A$ contenant au moins $p+1$ fois la lettre E.\\
  2. Déterminer $\mathrm{Card}(A'')$ sous forme d’une somme, où $A''$ est l’ensemble des éléments de $A$ contenant au moins $q+1$ fois la lettre C.\\
  3. En déduire que \[ \Sum_{k=0}^{q}\binom{p+k}{p}2^{q-k} + \Sum_{k=0}^{p}\binom{q+k}{q}2^{p-k} = 2^{p+q+1}. \] Puis que \[ \Sum_{k=p}^{2p}\binom{k}{p}2^{2p-k}=2^{2p}. \]
Exercice 6148. On note $N_n=\{1,\ldots,n\}$ où $n$ est un entier naturel fixé non nul.\\ Pour tout $k\in\mathbb{N}$, on note $A_{n,k}=\left\{f:N_n\to\mathbb{N}\;/\;\Sum_{1 \leqslant x \leqslant n}f(x)\leqslant k\right\}$ et $B_{n,k}=\left\{f:N_n\to\mathbb{N}\;/\;\Sum_{1 \leqslant x \leqslant n}f(x)=k\right\}$.\\ Pour tout $(n,k)\in\mathbb{N}^2$, on pose $a_{n,k}=\mathrm{Card}(A_{n,k})$ et $b_{n,k}=\mathrm{Card}(B_{n,k})$.\\
  1. Montrer que pour tout $(n,k)\in\mathbb{N}^2$,\\ \[ b_{n,k}=a_{n-1,k}\quad\mathrm{et}\quad a_{n,k}=b_{n,k}+a_{n,k-1}. \]
  2. En déduire que pour tout $(n,k)\in\mathbb{N}^*\times\mathbb{N}$ :\\ \[ a_{n,k}=\binom{n+k}{k}\quad\mathrm{et}\quad b_{n,k}=\binom{n+k-1}{k}. \]
  3. Donner une preuve combinatoire de ces formules.
Exercice 6149. On considère dans $\N^2$ des chemins partant de l’origine $(0,0)$, et constitués de pas montants $(x,y)\mapsto(x+1,y+1)$ et de pas descendants $(x,y)\mapsto(x+1,y-1)$.\\ Pour un $n \in \N^*$, on note $\mathcal{D}_n$ l’ensemble des chemins de $n$ pas montants et $n$ pas descendants restant toujours au-dessus de l’axe des abscisses (au sens large).\\ Ainsi, au bout de $2n$ pas, ces chemins se terminent sur l’axe des abscisses. Ces chemins sont appelés chemins de Dyck.\\ On appelle rampe descendante de longueur $k$ une succession d’un pas montant, et de $k$ pas descendants terminant sur l’axe des abscisses.\\ On note $\mathcal{C}_n$ l’ensemble des chemins de $\mathcal{D}_n$ n’ayant aucune rampe descendante de longueur paire.\\ Établir une bijection entre $\mathcal{D}_n$ et $\mathcal{C}_{n+1}$.
Exercice 6150. Soient $p$ et $q$ deux réels strictement positifs. On introduit les ensembles \[ A_p=\{\lfloor np \rfloor,\ n \in \N^*\} \quad \mathrm{et} \quad A_q=\{\lfloor nq \rfloor,\ n \in \N^*\}. \] Justifier le théorème suivant : les ensembles $A_p$ et $A_q$ forment une partition de $\N^*$ si et seulement si $p$ et $q$ sont irrationnels et vérifient \[ \frac{1}{p}+\frac{1}{q}=1. \] Soit $A$ une partie de $\N^*$. On définit sa densité $\mathrm{Den}(A)$, si elle existe, par \[ \mathrm{Den}(A)=\limn \frac{\mathrm{Card}(A \cap [[1,n]])}{n}. \]
  1. Calculer la densité d’un ensemble fini.\\
  2. Donner un exemple d’un ensemble infini ayant une densité nulle.\\
  3. Montrer que si $A$ et $B$ sont des parties disjointes de $\N^*$ ayant chacune une densité, alors $A \cup B$ a une densité et donner sa densité.\\
  4. Soit $\alpha > 1$. Calculer la densité de $\{\lfloor m\alpha \rfloor,\ m \in \N^*\}$.\\
  5. On suppose que $A_p$ et $A_q$ forment une partition de $\N^*$.
    1. Montrer que \[ \frac{1}{p}+\frac{1}{q}=1. \]
    2. Montrer que $p$ ou $q$ est irrationnel, puis en déduire que $p$ et $q$ sont irrationnels.
  6. On suppose maintenant que \[ \frac{1}{p}+\frac{1}{q}=1 \] et que $p$ et $q$ sont irrationnels.
    1. Montrer que \[ A_p \cap A_q=\emptyset. \]
    2. Montrer que \[ A_p \cup A_q=\N^*. \]
Exercice 6151. On se donne $(G,+)$ un groupe abélien.\\ Soit $A$ et $B$ deux parties de $G$, on définit $A+B$ par \[ A+B=\{a+b,\ (a,b) \in A \times B\}. \] Soit $A$ une partie de $G$. Si $n \in \N^*$, on définit $1A=A$ et $(n+1)A=nA+A$.\\ Soit $b \in G$ et $A$ une partie de $G$. On note $b+A$ la partie $\{b\}+A$.\\
  1. Soient $t \in \N^*$ et $N \in \N$.
    1. Soient $n$ et $p$ deux entiers naturels tels que $n \geqslant p$. Montrer que \[ \Sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1}. \]
    2. Montrer que l’ensemble des $t$-uplets $(a_1,\ldots,a_t) \in \N^t$ tels que $a_1+\cdots+a_t=N$ a pour cardinal \[ \binom{N+t-1}{N}. \]
  2. On suppose dans cette question que $G$ est fini. Soient $A$ et $B$ deux parties non vides de $G$ telles que \[ \mathrm{Card}(A)+\mathrm{Card}(B) > \mathrm{Card}(G). \]
    1. Montrer que $G=A+B$.\\
    2. Donner un exemple où $\mathrm{Card}(A)+\mathrm{Card}(B)=\mathrm{Card}(G)$ et $A+B \neq G$.
  3. Soient $A$ et $B$ des parties finies et non vides de $G$. Montrer que \[ \max(\mathrm{Card}(A),\mathrm{Card}(B)) \leqslant \mathrm{Card}(A+B) \leqslant \mathrm{Card}(A)\mathrm{Card}(B). \]
  4. Soit $A$ une partie finie non vide de $G$. Montrer que la suite $(\mathrm{Card}(nA))_{n \in \N^*}$ est croissante et que \[ \forall n \in \N^*,\quad \mathrm{Card}(nA) \leqslant \binom{\mathrm{Card}(A)+n-1}{n}. \]
  5. Soient $A$ et $B$ deux parties non vides de $\Z$.
    1. Montrer que \[ \mathrm{Card}(A+B) \geqslant \mathrm{Card}(A)+\mathrm{Card}(B)-1. \]
    2. On suppose que $A$ et $B$ ne sont pas des singletons et que \[ \mathrm{Card}(A+B)=\mathrm{Card}(A)+\mathrm{Card}(B)-1. \] Montrer qu’il existe des entiers relatifs $a$, $b$, $c$, $d$ tels que \[ A=\{a+kc,\ k \in [[0,\mathrm{Card}(A)-1]]\} \] et \[ B=\{b+kd,\ k \in [[0,\mathrm{Card}(B)-1]]\}. \]
  6. Soient $A$ et $B$ deux parties finies non vides de $G$.
    1. Soit $H$ l’ensemble des éléments $g \in G$ tels que $A=g+A$. Montrer que $H$ est un sous-groupe fini de $G$.\\
    2. Montrer que $\mathrm{Card}(A+B)=\mathrm{Card}(A)$ si et seulement s’il existe $b \in G$ tel que $B \subset b+H$.
Exercice 6152. Pour tout $x \in \R$ et pour tout entier naturel $k$, on définit \[ \binom{x}{k}=\frac{x(x-1)(x-2)\cdots(x-k+1)}{k!} \] avec la convention $\binom{x}{0}=1$.\\
    1. Donner la valeur de $\binom{1/2}{k}$ pour $k \in \{1,2,3\}$.\\
    2. Montrer que pour tout entier $k \geqslant 1$, \[ \binom{1/2}{k}=\frac{2(-1)^{k-1}(2k-2)!}{4^k k!(k-1)!}. \]
  2. On s’intéresse dans cette partie à la fonction $f$ définie par \[ f(x)=\frac{1-\sqrt{1-4x}}{2x}. \]
    1. Donner le domaine de définition de $f$.\\
    2. Montrer que $f$ est prolongeable par continuité en $0$, on notera encore $f$ ce prolongement.\\
    3. Soit $n \in \N$. Donner le développement limité à l’ordre $n+1$ en $0$ de $\sqrt{1-4x}$ en fonction des $\binom{1/2}{k}$. En déduire un développement limité à l’ordre $n$ en $0$, puis le développement limité à l’ordre $4$ en $0$ de $f$.\\
    4. En déduire l’existence d’une tangente en $0$ pour $\mathcal{C}_f$. Donner son équation et étudier sa position par rapport à $\mathcal{C}_f$.\\
    5. Étudier les variations de la fonction $f$, puis dresser son tableau de variations.\\
    6. Donner une allure de $\mathcal{C}_f$, en faisant figurer la tangente calculée précédemment.
  3. On s’intéresse dans cette partie à des suites de symboles constituées de parenthèses ouvrantes et fermantes qui sont bien parenthésées.\\ Pour tout entier naturel $n$, on note $c_n$ le nombre de suites de parenthèses de taille $2n$ qui sont bien parenthésées.\\
    1. Pourquoi n’avoir considéré que des suites dont la longueur est paire pour la définition des $c_n$ ?\\
    2. Donner la valeur de $c_0$, $c_1$, $c_2$ et $c_3$.\\
    3. Combien existe-t-il au total de suites de parenthèses de longueur $6$ contenant trois parenthèses ouvrantes et trois parenthèses fermantes ?\\
    4. Démontrer que pour tout $n \geqslant 1$, \[ c_n=\Sum_{k=0}^{n-1}c_kc_{n-1-k}. \]
    5. Montrer que la fonction $f$ étudiée ci-dessus vérifie l’équation \[ f(x)=1+xf(x)^2. \]
    6. En déduire que les coefficients de son développement limité d’ordre $n$ en $0$ sont les nombres $c_n$.\\
    7. En déduire une expression explicite de $c_n$ en fonction de $n$.