Dénombrement

Exercice 4285. 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 4286. 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 4287. 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 4288. 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 4289. 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 4290. 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 4291. \\
  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 4292. 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 4293. 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 4294. 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 4295. 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 4296. 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 4297. 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 4298. Calculer le nombre de lois internes abéliennes sur un ensemble de cardinal $n$.
Exercice 4299. 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 4300. 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 4301. 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 4302. 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 4303. 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 4304. 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 4305. Combien y a-t-il de $p$-cycles dans le groupe $(\mathfrak{S}_n,\circ)$ ?
Exercice 4306. 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 4307. 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 4308. Combien existe-t-il de relations d'ordre total sur un ensemble $E$ à $n$ éléments ?
Exercice 4309. 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 4310. 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 4311.
  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 4312. 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 4313. 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 4314. 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 4315. 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 4316. 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 4317. 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 4318. (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 4319. Soit $n \geqslant 2$.\\ Quel est le nombre de surjections de $\llbracket 1,n+2 \rrbracket$ dans $\llbracket 1,n \rrbracket $ ?
Exercice 4320. 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 4321. 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 4322. 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 4323. 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.