Dénombrement

Exercice 4356. 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 4357. 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 4358. 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 4359. 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 4360. 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 4361. 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 4362. \\
  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 4363. 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 4364. 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 4365. 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 4366. 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 4367. 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 4368. 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 4369. Calculer le nombre de lois internes abéliennes sur un ensemble de cardinal $n$.
Exercice 4370. 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 4371. 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 4372. 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 4373. 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 4374. 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 4375. 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 4376. Combien y a-t-il de $p$-cycles dans le groupe $(\mathfrak{S}_n,\circ)$ ?
Exercice 4377. 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 4378. 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 4379. Combien existe-t-il de relations d'ordre total sur un ensemble $E$ à $n$ éléments ?
Exercice 4380. 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 4381. 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 4382.
  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 4383. 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 4384. 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 4385. 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 4386. 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 4387. 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 4388. 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 4389. (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 4390. Soit $n \geqslant 2$.\\ Quel est le nombre de surjections de $\llbracket 1,n+2 \rrbracket$ dans $\llbracket 1,n \rrbracket $ ?
Exercice 4391. 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 4392. 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 4393. 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 4394. 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.