Exercices — Dénombrement

1. Déterminer, en justifiant, le cardinal de chacun des ensembles suivants :

   a. $A=\{k\in [\text{\hspace{0.17em}⁣}[1,100]\text{\hspace{0.17em}⁣}]\mid k\text{ est multiple de }7\}$

   b. $B=\{k\in [\text{\hspace{0.17em}⁣}[1,100]\text{\hspace{0.17em}⁣}]\mid k\text{ est multiple de }5\}$

   c. $A\cap B$

   d. $A\cup B$

2. Soit $D$ l'ensemble des diviseurs positifs de $360$. Décomposer $360$ en produit de facteurs premiers, exhiber une bijection entre $D$ et un produit cartésien d'intervalles d'entiers, puis en déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(D)$.

3. Soit $n\in {\mathbb{N}}^{\ast }$. Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(T)$, où $T=\{(i,j)\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}{]}^2\mid i<j\}$.

4. Soit $E$ un ensemble fini avec $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=6$. Donner $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))$, puis le nombre de parties de $E$ distinctes de $\mathrm{\varnothing }$ et de $E$.

Dans chaque question, on décrira précisément l'ensemble compté et on justifiera le modèle utilisé (produit cartésien, bijection, réunion disjointe) avant de donner le résultat numérique.

1. Un restaurant propose $4$ entrées, $5$ plats et $3$ desserts. Un menu est la donnée d'une entrée, d'un plat et d'un dessert. Écrire l'ensemble $M$ des menus comme un produit cartésien, puis donner $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(M)$.

2. Pour aller de la ville $A$ à la ville $D$, on passe obligatoirement par $B$, puis par $C$. Il existe $3$ routes de $A$ à $B$, $4$ routes de $B$ à $C$ et $2$ routes de $C$ à $D$. Combien de trajets de $A$ à $D$ peut-on emprunter ?

3. Soient $E$ et $F$ deux ensembles finis avec $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=7$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=5$. Combien y a-t-il de couples $(a,b)$ avec $a\in E$ et $b\in F$ ? Énoncer le résultat général.

4. Soit $E$ un ensemble fini de cardinal $n⩾1$. Déterminer de deux façons différentes le cardinal de l'ensemble $\mathcal{D}=\{(a,b)\in E^2\mid a\mathrm{\ne }b\}$, puis donner la valeur obtenue pour $n=7$.

On pose $E=[\text{\hspace{0.17em}⁣}[1,200]\text{\hspace{0.17em}⁣}]$ et, pour $d\in {\mathbb{N}}^{\ast }$, $M_d=\{k\in E\mid d\text{ divise }k\}$.

1. Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(M_3)$.

2. En déduire le nombre d'entiers de $E$ qui ne sont pas multiples de $3$.

3. Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(M_3\cup M_5)$.

4. Déterminer le nombre d'entiers de $E$ qui sont multiples de $3$ mais pas de $5$.

5. On appelle mot de trois lettres toute suite de trois lettres de l'alphabet français, qui en compte $26$ (un tel mot n'a pas besoin d'avoir un sens, et les répétitions de lettres sont autorisées). Les voyelles sont $a$, $e$, $i$, $o$, $u$, $y$. Combien de ces mots contiennent au moins une voyelle ? On traitera la question par passage au complémentaire, et on expliquera pourquoi le comptage direct serait maladroit.

1. Une plaque d'immatriculation est constituée de deux lettres, puis de trois chiffres, puis de deux lettres. L'alphabet compte $26$ lettres, les chiffres vont de $0$ à $9$, et les répétitions sont autorisées. Combien de plaques peut-on former ?

2. Un mot de passe est une suite de $8$ caractères choisis dans un alphabet de $62$ caractères. Donner le nombre de mots de passe sous forme d'une puissance, puis en donner un ordre de grandeur justifié, sans calculatrice.

3. Déterminer les cardinaux suivants :

   a. le nombre d'applications de $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$

   b. le nombre de parties de $[\text{\hspace{0.17em}⁣}[1,10]\text{\hspace{0.17em}⁣}]$

4. Soient $k\in {\mathbb{N}}^{\ast }$ et $n⩾2$. Sur un alphabet $L$ à $k$ lettres, un mot de longueur $n$ est une $n$-liste d'éléments de $L$. Combien de mots de longueur $n$ commencent et finissent par la même lettre ? Contrôler la formule pour $n=2$.

Dans tout l'exercice, aucun ex aequo n'est possible.

1. Une course réunit $12$ concurrents. Un podium est la donnée, dans l'ordre, des trois premiers arrivés. Combien de podiums peut-on former ?

2. Une course réunit $18$ chevaux. Combien y a-t-il de tiercés dans l'ordre, c'est-à-dire de listes des trois premiers arrivés dans l'ordre d'arrivée ? Combien y a-t-il de tiercés dans le désordre, c'est-à-dire de choix des trois chevaux arrivés en tête, sans tenir compte de leur ordre ?

3. Déterminer les nombres suivants :

   a. le nombre de $5$-listes d'éléments deux à deux distincts de $[\text{\hspace{0.17em}⁣}[1,9]\text{\hspace{0.17em}⁣}]$

   b. le nombre d'injections de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,7]\text{\hspace{0.17em}⁣}]$

4. Comparer $A_7^3$ et $7^3$. Que compte exactement leur différence ?

On appelle anagramme du mot FLACON tout mot de six lettres obtenu en écrivant chacune des six lettres F, L, A, C, O, N une fois et une seule ; le résultat n'a pas besoin d'avoir un sens. Les voyelles sont A et O, les consonnes sont F, L, C et N.

1. Combien le mot FLACON possède-t-il d'anagrammes ?

2. Combien de ces anagrammes commencent par une consonne ?

3. Combien de ces anagrammes ont leurs deux voyelles côte à côte ? On expliquera soigneusement le modèle utilisé.

4. Combien de ces anagrammes n'ont de voyelle ni en première ni en dernière position ?

5. Soit $n\in {\mathbb{N}}^{\ast }$. De combien de façons peut-on ranger $n$ livres distincts côte à côte sur une étagère ? Et, pour $n⩾2$, si deux livres fixés à l'avance doivent rester l'un à côté de l'autre ?

1. Calculer les coefficients binomiaux suivants :

   a. ${\displaystyle \left(\genfrac{}{}{0px}{}{7}{2}\right)}$

   b. ${\displaystyle \left(\genfrac{}{}{0px}{}{10}{3}\right)}$

   c. ${\displaystyle \left(\genfrac{}{}{0px}{}{9}{9}\right)}$

   d. ${\displaystyle \left(\genfrac{}{}{0px}{}{12}{11}\right)}$

   e. ${\displaystyle \left(\genfrac{}{}{0px}{}{6}{0}\right)}$

   f. ${\displaystyle \left(\genfrac{}{}{0px}{}{20}{18}\right)}$

2. Énoncer la formule de symétrie des coefficients binomiaux et en donner la démonstration combinatoire. L'utiliser pour calculer ${\displaystyle \left(\genfrac{}{}{0px}{}{50}{48}\right)}$ et ${\displaystyle \left(\genfrac{}{}{0px}{}{100}{99}\right)}$ sans effectuer de gros calculs.

3. Résoudre dans $\mathbb{N}$ l'équation ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{2}\right)}=45$.

4. Dans un groupe de $10$ personnes, combien de comités de $4$ personnes peut-on former ? Combien de ces comités comptent une personne fixée à l'avance, appelée Alice ?

1. À l'aide de la formule de Pascal, construire les lignes $n=0$ à $n=7$ du triangle de Pascal.

2. En déduire le développement de $(a+b{)}^5$, où $a$ et $b$ sont deux réels.

3. Développer $(2x-3{)}^4$, où $x$ est un réel, et contrôler le résultat en évaluant les deux membres en $x=1$.

4. Calculer ${\sum }_{k=0}^7{\displaystyle \left(\genfrac{}{}{0px}{}{7}{k}\right)}$ de deux façons : d'abord à partir de la ligne $n=7$, puis par la formule du binôme.

5. Donner le coefficient de $x^3$ dans le développement de $(1+x{)}^{10}$, puis dans celui de $(1+2x{)}^{10}$.

Soit $E$ un ensemble fini de cardinal $n\in \mathbb{N}$. On se propose de démontrer de trois façons que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))=2^n$.

1. Pour $A\in \mathcal{P}(E)$, on note ${\mathbf{1}}_A$ la fonction indicatrice de $A$, définie sur $E$ par ${\mathbf{1}}_A(x)=1$ si $x\in A$ et ${\mathbf{1}}_A(x)=0$ sinon. Montrer que l'application $\phi :A⟼{\mathbf{1}}_A$, de $\mathcal{P}(E)$ dans $\mathcal{F}(E,\{0,1\})$, est bijective en explicitant sa réciproque, puis conclure.

2. Redémontrer le résultat par récurrence sur $n$.

3. Le redémontrer une troisième fois en partitionnant $\mathcal{P}(E)$ selon le cardinal des parties, puis en utilisant la formule du binôme.

4. Applications, dans le cas $E=[\text{\hspace{0.17em}⁣}[1,10]\text{\hspace{0.17em}⁣}]$. Combien de parties de $E$ contiennent l'élément $1$ ? Combien contiennent $1$ mais pas $2$ ? Combien sont de cardinal supérieur ou égal à $8$ ?

Un lycée compte $420$ élèves. Parmi eux, $260$ étudient l'anglais, $180$ étudient l'espagnol, et $95$ étudient les deux langues.

1. Combien d'élèves étudient au moins une des deux langues ?

2. Combien d'élèves étudient l'anglais mais pas l'espagnol ? Combien en étudient exactement une des deux ?

3. Combien d'élèves n'étudient aucune de ces deux langues ?

4. Soient $A$ et $B$ deux parties d'un ensemble fini $E$. En écrivant $A\cup B$ puis $B$ comme des réunions disjointes, démontrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)$.

5. En déduire l'encadrement $\max (\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A),\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B))⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B)⩽\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)$, et préciser dans chaque cas à quelle condition l'égalité a lieu.

Soient $E$ et $F$ deux ensembles finis non vides, de cardinaux respectifs $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=p$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)=n$.

1. Déterminer, en justifiant le modèle utilisé, le nombre d'applications de $E$ dans $F$.

2. Déterminer le nombre d'injections de $E$ dans $F$, en discutant selon $p$ et $n$.

3. En déduire le nombre de bijections de $E$ sur $F$, en discutant selon $p$ et $n$.

4. Donner les trois nombres précédents pour $(p,n)=(3,5)$, puis $(p,n)=(5,3)$, puis $(p,n)=(4,4)$.

5. Dénombrer les surjections de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,2]\text{\hspace{0.17em}⁣}]$ par passage au complémentaire, puis contrôler le résultat en les énumérant toutes.

6. Soit $n⩾1$. Combien y a-t-il d'applications de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ qui ne sont pas injectives ? Donner la valeur pour $n=3$.

Une association est composée de $12$ femmes et $8$ hommes. Un comité est un groupe de personnes choisies parmi les membres de l'association, sans ordre et sans répétition.

1. Combien peut-on former de comités de $5$ personnes ?

2. Combien de ces comités comportent exactement $2$ hommes ?

3. Combien en comportent au moins un ? On passera au complémentaire.

4. On veut maintenant former un comité de $5$ personnes et désigner parmi ses membres un président et un secrétaire, qui doivent être deux personnes distinctes. Dénombrer ces comités présidés de deux façons : en choisissant d'abord le comité puis les deux responsables, puis en choisissant d'abord les deux responsables. Vérifier que les deux méthodes coïncident.

5. Dans un jeu de $32$ cartes, combien y a-t-il de mains de $5$ cartes ? Combien d'entre elles contiennent les quatre as ?

On appelle anagramme d'un mot de $n$ lettres tout mot de $n$ lettres écrit avec exactement les mêmes lettres, chacune répétée le même nombre de fois. Le sens n'intervient pas, et le mot de départ compte parmi ses propres anagrammes.

1. On considère un mot de $n$ lettres écrit à l'aide de $r$ lettres distinctes $a_1,\dots ,a_r$, la lettre $a_i$ y figurant $n_i$ fois, de sorte que $n_1+\cdots +n_r=n$. Démontrer, à l'aide du lemme du berger, que le nombre d'anagrammes de ce mot vaut ${\displaystyle \frac{n!}{n_1!n_2!\cdots n_r!}}$.

2. Contrôler la formule sur le mot AABB en énumérant toutes ses anagrammes.

3. Appliquer la formule au mot MISSISSIPPI, puis au mot ANAGRAMME.

4. Combien d'anagrammes de MISSISSIPPI commencent par un I ? Contrôler le résultat en dénombrant, pour chacune des lettres du mot, les anagrammes qui commencent par cette lettre.

Dans les questions 2 et 3, $n$ personnes s'assoient autour d'une table ronde dont les $n$ places sont numérotées de $1$ à $n$ dans le sens des aiguilles d'une montre ; deux placements qui se déduisent l'un de l'autre par une rotation de la table donnent la même disposition.

1. Énoncer et démontrer le lemme du berger : si $f:X⟶Y$ est une application surjective entre deux ensembles finis dont toutes les fibres $f^{-1}(\{y\})$ ont le même cardinal $k$, alors $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(X)=k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(Y)$.

2. Soit $n⩾1$. Montrer qu'il y a exactement $(n-1)!$ dispositions.

3. Soit $n⩾3$. On identifie de plus une disposition et son image dans un miroir. Montrer qu'aucune disposition n'est égale à sa propre image par symétrie, puis en déduire qu'il reste $\frac{(n-1)!}{2}$ dispositions. Contrôler le résultat à la main pour $n=4$.

4. Soit $n⩾1$. Montrer que le nombre de façons de répartir $2n$ personnes en $n$ paires vaut $\frac{(2n)!}{2^{n}n!}$, puis contrôler ce résultat à la main pour $n=2$ et $n=3$.

Un pion part du point $(0,0)$ du plan et se déplace par pas successifs : un pas $D$ le mène de $(x,y)$ à $(x+1,y)$, un pas $H$ le mène de $(x,y)$ à $(x,y+1)$. Pour $m$ et $n$ entiers naturels, on appelle chemin de $(0,0)$ à $(m,n)$ toute suite finie de tels pas conduisant de $(0,0)$ à $(m,n)$, et on note $c(m,n)$ le nombre de ces chemins.

1. Montrer qu'un chemin de $(0,0)$ à $(m,n)$ comporte exactement $m+n$ pas, puis construire une bijection entre l'ensemble de ces chemins et l'ensemble des mots de longueur $m+n$ écrits avec les lettres $D$ et $H$ et comportant exactement $m$ fois la lettre $D$. En déduire $c(m,n)$.

2. Calculer $c(3,2)$, puis retrouver ce nombre en énumérant les mots correspondants. Calculer $c(7,5)$.

3. Soit $(a,b)$ un point à coordonnées entières vérifiant $0⩽a⩽m$ et $0⩽b⩽n$. Combien de chemins de $(0,0)$ à $(m,n)$ passent par $(a,b)$ ? Combien l'évitent ? Application numérique pour $(m,n)=(7,5)$ et $(a,b)=(3,2)$.

4. Soit $m⩾1$ et $n⩾1$. En classant les chemins selon leur dernier pas, démontrer la relation ${\displaystyle \left(\genfrac{}{}{0px}{}{m+n}{m}\right)}={\displaystyle \left(\genfrac{}{}{0px}{}{m+n-1}{m-1}\right)}+{\displaystyle \left(\genfrac{}{}{0px}{}{m+n-1}{m}\right)}$, puis la vérifier sur le cas $(m,n)=(3,2)$.

Soit $n⩾3$ et soit $\mathrm{\Pi }$ un polygone convexe à $n$ sommets. On note $S$ l'ensemble de ses sommets. On appelle diagonale tout segment joignant deux sommets non consécutifs, et on suppose que trois diagonales ne sont jamais concourantes.

1. Combien y a-t-il de segments joignant deux sommets distincts de $\mathrm{\Pi }$ ?

2. En déduire que le nombre de diagonales de $\mathrm{\Pi }$ vaut ${\displaystyle \frac{n(n-3)}{2}}$.

3. Combien y a-t-il de triangles dont les trois sommets sont des sommets de $\mathrm{\Pi }$ ?

4. Montrer que le nombre de points d'intersection de deux diagonales situés strictement à l'intérieur de $\mathrm{\Pi }$ vaut ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{4}\right)}$. On construira une bijection entre l'ensemble de ces points et l'ensemble des parties à quatre éléments de $S$.

5. Donner les quatre nombres précédents pour $n=8$, puis pour $n=12$.

Soit $n⩾1$ un entier.

1. Démontrer par le calcul, à l'aide des factorielles, que $p{\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}=n{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)}$ pour tout entier $p$ tel que $1⩽p⩽n$.

2. Redémontrer cette formule par double comptage, en dénombrant de deux façons l'ensemble des couples $(A,x)$ où $A$ est une partie à $p$ éléments de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et où $x$ est un élément de $A$.

3. En déduire la valeur de ${\displaystyle \sum _{k=1}^{n}k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$.

4. Montrer que pour tout $k$ tel que $0⩽k⩽n$ on a ${\displaystyle \frac{1}{k+1}}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}={\displaystyle \frac{1}{n+1}}{\displaystyle \left(\genfrac{}{}{0px}{}{n+1}{k+1}\right)}$, puis en déduire la valeur de ${\displaystyle \sum _{k=0}^n\frac{1}{k+1}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$.

5. Vérifier les résultats des questions 3 et 4 pour $n=3$, par le calcul direct des deux sommes.

Soit $n$ un entier naturel. Calculer, en justifiant chaque étape, les sommes suivantes.

1. ${\displaystyle \sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$.

2. ${\displaystyle \sum _{k=0}^n(-1{)}^k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$ (on distinguera le cas $n=0$).

3. ${\displaystyle \sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{2}^k}$.

4. ${\displaystyle \sum _{k=0}^{n}k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$, pour $n⩾1$, en utilisant la formule du pivot $k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}=n{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)}$.

5. ${\displaystyle \sum _{k=0}^n{k}^2{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$, pour $n⩾2$, en écrivant $k^2=k(k-1)+k$ et en appliquant deux fois la formule du pivot.

6. Vérifier le résultat de la question 5 pour $n=3$, puis pour $n=4$, par le calcul direct de la somme.

Soit $n⩾1$ et soit $E$ un ensemble fini de cardinal $n$. On note $\mathcal{A}$ l'ensemble des parties de $E$ de cardinal pair et $\mathcal{B}$ l'ensemble des parties de $E$ de cardinal impair.

1. Exprimer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{A})$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{B})$ à l'aide de coefficients binomiaux, et montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{A})+\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{B})=2^n$.

2. En calculant ${\displaystyle \sum _{k=0}^n(-1{)}^k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$ par la formule du binôme, montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{A})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{B})$.

3. Soit $a$ un élément fixé de $E$. Pour $A\in \mathcal{P}(E)$, on pose $\phi (A)=A\cup \{a\}$ si $a\mathrm{\notin }A$, et $\phi (A)=A\setminus \{a\}$ si $a\in A$ (autrement dit $\phi (A)=A\mathrm{△}\{a\}$, la différence symétrique de $A$ et de $\{a\}$). Montrer que $\phi \circ \phi ={\mathrm{i}\mathrm{d}}_{\mathcal{P}(E)}$, puis que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\phi (A))$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)$ n'ont jamais la même parité. En déduire une seconde démonstration de l'égalité $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{A})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{B})$.

4. En déduire la valeur commune de $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{A})$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{B})$.

5. Que se passe-t-il si $n=0$ ?

Dans les questions 2 à 5, on précisera explicitement quels sont les objets et quels sont les tiroirs.

1. Énoncer le principe des tiroirs sous la forme suivante, puis le démontrer : si $E$ et $F$ sont deux ensembles finis tels que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)>\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$, alors aucune application de $E$ dans $F$ n'est injective.

2. Montrer que parmi $13$ personnes, deux au moins sont nées le même mois.

3. Soit $n⩾1$. Montrer que si l'on choisit $n+1$ entiers deux à deux distincts dans $[\text{\hspace{0.17em}⁣}[1,2n]\text{\hspace{0.17em}⁣}]$, il en existe deux dont l'un divise l'autre. On pourra écrire tout entier $m⩾1$ sous la forme $m=2^{\alpha }q$ avec $\alpha \in \mathbb{N}$ et $q$ impair.

4. Montrer que parmi cinq points d'un carré de côté $2$, deux au moins sont à une distance inférieure ou égale à $\sqrt{2}$.

5. Soit $n⩾1$. Montrer que toute partie de $[\text{\hspace{0.17em}⁣}[1,2n]\text{\hspace{0.17em}⁣}]$ à $n+1$ éléments contient deux entiers consécutifs.

Soit $E$ et $F$ deux ensembles finis de même cardinal $n$, et soit $f:E⟶F$.

1. Montrer que si $f$ est injective, alors $f$ est surjective.

2. Montrer que si $f$ est surjective, alors $f$ est injective. Conclure : $f$ injective $⟺$ $f$ surjective $⟺$ $f$ bijective.

3. Donner un contre-exemple montrant que l'hypothèse « $E$ et $F$ ont même cardinal » est indispensable, puis un contre-exemple montrant que l'hypothèse « $E$ et $F$ sont finis » l'est aussi, en considérant l'application $k⟼k+1$ de $\mathbb{N}$ dans $\mathbb{N}$.

4. Soit $n⩾1$ et $f:[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]⟶[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ croissante au sens large et injective. Montrer que $f=\mathrm{i}\mathrm{d}$.

5. Soit $E$ un ensemble fini et $f:E⟶E$ telle que $f\circ f=f$. Montrer que $f$ est injective si et seulement si $f={\mathrm{i}\mathrm{d}}_E$. Qu'obtient-on si l'on suppose $f$ surjective ?

Soit $E$ un ensemble fini de cardinal $n$. On pose

1. En classant les couples de $\mathcal{E}$ selon la partie $B$, montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{E})={\displaystyle \sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{2}^k}$, puis calculer cette somme.

2. Retrouver le résultat en construisant une bijection explicite de $\mathcal{E}$ sur $\mathcal{F}(E,\{1,2,3\})$. On précisera l'application réciproque.

3. Construire une bijection de $\mathcal{E}$ sur $\mathcal{D}$, puis une bijection de $\mathcal{D}$ sur $\mathcal{R}$, chacune avec sa réciproque. Que valent $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{D})$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{R})$ ?

4. Vérifier ces résultats pour $E=\{1,2\}$ en énumérant les éléments de $\mathcal{E}$, de $\mathcal{D}$ et de $\mathcal{R}$.

Soient $m$, $n$ et $p$ trois entiers naturels. On adopte la convention usuelle ${\displaystyle \left(\genfrac{}{}{0px}{}{a}{b}\right)}=0$ dès que $b>a$. On veut établir la formule de Vandermonde :

1. Soit $E$ un ensemble à $m+n$ éléments, réunion disjointe de deux parties $F$ et $G$ de cardinaux respectifs $m$ et $n$. En classant les parties à $p$ éléments de $E$ selon le nombre d'éléments qu'elles prennent dans $F$, démontrer la formule. On exhibera la bijection utilisée et sa réciproque.

2. Démontrer à nouveau la formule en identifiant les coefficients de $X^p$ dans l'égalité polynomiale $(1+X{)}^m(1+X{)}^n=(1+X{)}^{m+n}$.

3. Vérifier numériquement la formule pour $m=3$, $n=4$ et $p=3$.

4. Soit $n⩾1$. Calculer ${\displaystyle \sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k+1}\right)}}$ à l'aide d'un unique coefficient binomial, puis contrôler le résultat pour $n=2$ et $n=3$.

Soit $n$ un entier naturel. On note $E=[\text{\hspace{0.17em}⁣}[1,2n]\text{\hspace{0.17em}⁣}]$, $F=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et $G=[\text{\hspace{0.17em}⁣}[n+1,2n]\text{\hspace{0.17em}⁣}]$, de sorte que $E$ est la réunion disjointe de $F$ et de $G$.

1. Soit $k\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$. Montrer que le nombre de parties $P$ de $E$ à $n$ éléments telles que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(P\cap F)=k$ vaut ${\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{n-k}\right)}$. On construira une bijection explicite et sa réciproque.

2. En déduire, par un dénombrement de ${\mathcal{P}}_n(E)$ et la formule de symétrie, que

3. Vérifier cette identité pour $n=1$, $n=2$ et $n=3$.

4. Soit $n⩾1$. À l'aide de la formule du pivot $k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}=n{\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)}$ puis de la formule de Vandermonde, calculer ${\displaystyle \sum _{k=0}^{n}k{{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}^2}$. Vérifier le résultat pour $n=3$.

Soient $p$ et $n$ deux entiers naturels tels que $p⩽n$. On veut établir l'identité

qui exprime que la somme d'une colonne du triangle de Pascal, arrêtée à la ligne $n$, se lit une ligne plus bas et une colonne plus loin.

1. Démontrer cette identité par récurrence sur $n$, à $p$ fixé, en utilisant la formule de Pascal.

2. La redémontrer en dénombrant les parties à $p+1$ éléments de $[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ classées selon leur plus grand élément. On explicitera la bijection utilisée et sa réciproque.

3. En prenant $p=1$, retrouver ${\displaystyle \sum _{k=1}^{n}k=\frac{n(n+1)}{2}}$. En prenant $p=2$, montrer que ${\displaystyle \sum _{k=1}^n\frac{k(k-1)}{2}={\displaystyle \left(\genfrac{}{}{0px}{}{n+1}{3}\right)}}$.

4. Vérifier que $k^2=2{\displaystyle \left(\genfrac{}{}{0px}{}{k}{2}\right)}+{\displaystyle \left(\genfrac{}{}{0px}{}{k}{1}\right)}$ pour tout $k⩾1$, et en déduire la valeur de ${\displaystyle \sum _{k=1}^n{k}^2}$.

5. Contrôler les trois sommes obtenues pour $n=5$.

Soient $n$ et $p$ deux entiers naturels non nuls. On note $\mathcal{S}(p,n)$ l'ensemble des applications strictement croissantes de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, et $\mathcal{C}(p,n)$ l'ensemble des applications croissantes au sens large de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$.

1. Montrer que l'application $f⟼f([\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}])$ est une bijection de $\mathcal{S}(p,n)$ sur ${\mathcal{P}}_p([\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}])$, en décrivant sa réciproque. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{S}(p,n))={\displaystyle \left(\genfrac{}{}{0px}{}{n}{p}\right)}$.

2. Soit $f\in \mathcal{C}(p,n)$. On pose $g(i)=f(i)+i-1$ pour $i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$. Montrer que $g$ est une application strictement croissante de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n+p-1]\text{\hspace{0.17em}⁣}]$.

3. Montrer que $f⟼g$ est une bijection de $\mathcal{C}(p,n)$ sur $\mathcal{S}(p,n+p-1)$ en explicitant sa réciproque, et en déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{C}(p,n))={\displaystyle \left(\genfrac{}{}{0px}{}{n+p-1}{p}\right)}$.

4. Vérifier les deux résultats pour $p=2$ et $n=3$, en énumérant complètement $\mathcal{S}(2,3)$ et $\mathcal{C}(2,3)$.

Soient $n\in \mathbb{N}$ et $p\in {\mathbb{N}}^{\ast }$. On note

On appelle mot de longueur $N$ sur l'alphabet $\{\mathrm{a},\mathrm{b}\}$ une application de $[\text{\hspace{0.17em}⁣}[1,N]\text{\hspace{0.17em}⁣}]$ dans $\{\mathrm{a},\mathrm{b}\}$, et on note $\mathcal{M}$ l'ensemble des mots de longueur $n+p-1$ comportant exactement $p-1$ lettres $\mathrm{b}$.

1. Montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{M})={\displaystyle \left(\genfrac{}{}{0px}{}{n+p-1}{p-1}\right)}$ en associant à un mot l'ensemble des positions de ses lettres $\mathrm{b}$.

2. À un $p$-uplet $(x_1,\dots ,x_p)$ de $\mathcal{X}(n,p)$, on associe le mot formé de $x_1$ lettres $\mathrm{a}$, puis d'une lettre $\mathrm{b}$, puis de $x_2$ lettres $\mathrm{a}$, puis d'une lettre $\mathrm{b}$, et ainsi de suite jusqu'à $x_p$ lettres $\mathrm{a}$. Montrer que l'on définit ainsi une bijection de $\mathcal{X}(n,p)$ sur $\mathcal{M}$, dont on explicitera la réciproque, et en déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{X}(n,p))$.

3. On suppose $n⩾p$. En posant $y_i=x_i-1$, montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{X}}^{\ast }(n,p))={\displaystyle \left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)}$.

4. En ajoutant une inconnue d'écart, montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{T}(n,p))={\displaystyle \left(\genfrac{}{}{0px}{}{n+p}{p}\right)}$.

5. Vérifier les trois résultats pour $p=3$ et $n=2$ par énumération exhaustive.

Soit $n\in {\mathbb{N}}^{\ast }$. Une partie $A$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est dite écartée lorsqu'elle ne contient jamais deux entiers consécutifs, c'est-à-dire lorsqu'il n'existe aucun $k$ tel que $k\in A$ et $k+1\in A$. Pour $p\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$, on note ${\mathcal{E}}_p(n)$ l'ensemble des parties écartées de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ à $p$ éléments, et $u_n$ le nombre total de parties écartées de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$.

1. Soit $p⩾1$ et soit $A=\{a_1<a_2<\cdots <a_p\}$ une partie écartée de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. Montrer que $a_{i+1}⩾a_i+2$ pour tout $i\in [\text{\hspace{0.17em}⁣}[1,p-1]\text{\hspace{0.17em}⁣}]$, puis que

est une partie à $p$ éléments de $[\text{\hspace{0.17em}⁣}[1,n-p+1]\text{\hspace{0.17em}⁣}]$.

2. Montrer que $\phi$ est une bijection de ${\mathcal{E}}_p(n)$ sur ${\mathcal{P}}_p([\text{\hspace{0.17em}⁣}[1,n-p+1]\text{\hspace{0.17em}⁣}])$, en explicitant sa réciproque, et en déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{E}}_p(n))={\displaystyle \left(\genfrac{}{}{0px}{}{n-p+1}{p}\right)}$.

3. Vérifier ce résultat pour $n=6$ et $p=2$, puis pour $n=6$ et $p=3$, par énumération exhaustive.

4. En déduire que $u_n={\displaystyle \sum _{p=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n-p+1}{p}\right)}}$, et calculer $u_n$ pour $n$ allant de $1$ à $6$.

5. Démontrer directement, en séparant les parties écartées selon qu'elles contiennent ou non l'entier $n$, que $u_n=u_{n-1}+u_{n-2}$ pour $n⩾3$. Contrôler sur les valeurs de la question 4.

Soit $n⩾1$ et soit $\{a,b\}$ un ensemble à deux éléments. On note ${\mathcal{S}}_n$ l'ensemble des surjections de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $\{a,b\}$, et ${\mathcal{A}}_n$ l'ensemble des parties de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ distinctes de $\mathrm{\varnothing }$ et de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$.

1. Décrire les applications de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ dans $\{a,b\}$ qui ne sont pas surjectives, puis en déduire par passage au complémentaire que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{S}}_n)=2^n-2$.

2. Montrer que l'application $\mathrm{\Phi }$ qui, à $f\in {\mathcal{S}}_n$, associe le couple $(f^{-1}(\{a\}),\overline{f^{-1}(\{a\})})$ est une bijection de ${\mathcal{S}}_n$ sur l'ensemble des couples $(A,\bar{A})$ avec $A\in {\mathcal{A}}_n$. Retrouver ainsi la valeur de $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{S}}_n)$.

3. On appelle partition de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ en deux parties non vides toute paire $\{A,B\}$ de parties non vides, disjointes, de réunion $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. En appliquant le lemme du berger à l'application $f⟼\{f^{-1}(\{a\}),f^{-1}(\{b\})\}$, montrer que le nombre de ces partitions vaut $2^{n-1}-1$.

4. Vérifier les résultats des questions 1 et 3 en énumérant tous les cas pour $n=3$.

Soit $E$ un ensemble fini de cardinal $n⩾1$. On pose

1. Calculer $S_1$ par double comptage de l'ensemble $\mathrm{\Omega }=\{(x,A)\in E\times \mathcal{P}(E):x\in A\}$.

2. Retrouver $S_1$ en regroupant les parties selon leur cardinal, c'est-à-dire en calculant ${\displaystyle \sum _{k=0}^{n}k{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}}$.

3. Retrouver $S_1$ une troisième fois à l'aide de l'involution $A⟼\bar{A}$ de $\mathcal{P}(E)$, et interpréter le résultat en termes de moyenne des cardinaux.

4. Calculer $S_2$ pour $n=3$ par énumération, puis démontrer que $S_2=n(n+1)2^{n-2}$ pour tout $n⩾2$.

5. Démontrer que $S_3=n{4}^{n-1}$, et vérifier pour $n=1$.

Un jeu de $52$ cartes est l'ensemble $J=H\times C$, où $H$ est l'ensemble des $13$ hauteurs et $C$ celui des $4$ couleurs : une carte est donc déterminée par le couple (hauteur, couleur). Une main est une partie de $J$ à $5$ éléments (les cartes ne sont ni ordonnées ni répétées).

1. Déterminer le nombre total de mains.

2. Compter les mains contenant exactement une paire : deux cartes de même hauteur, les trois autres étant de hauteurs deux à deux distinctes et différentes de celle de la paire.

3. Compter les mains contenant un brelan et rien d'autre : trois cartes de même hauteur, les deux autres étant de hauteurs distinctes entre elles et différentes de celle du brelan.

4. Compter les fulls : trois cartes d'une même hauteur et deux cartes d'une autre même hauteur.

5. Compter les couleurs : cinq cartes de la même couleur.

6. Compter, par passage au complémentaire, les mains contenant au moins un as (l'as est l'une des $13$ hauteurs).

Chaque comptage sera justifié en décrivant la construction utilisée et en vérifiant que chaque main est obtenue une fois et une seule.

Une permutation $\sigma \in {\mathfrak{S}}_n$ est un dérangement si elle n'a aucun point fixe, c'est-à-dire si $\sigma (i)\mathrm{\ne }i$ pour tout $i\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. On note $D_n$ l'ensemble des dérangements de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et $d_n=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(D_n)$, avec la convention $d_0=1$.

Plus généralement, si $X$ est un ensemble fini de cardinal $m$, un dérangement de $X$ est une permutation de $X$ sans point fixe ; en transportant par une bijection de $X$ sur $[\text{\hspace{0.17em}⁣}[1,m]\text{\hspace{0.17em}⁣}]$, leur nombre vaut $d_m$ et ne dépend donc que de $m$ (ce point est admis).

1. Déterminer $d_1$, $d_2$, $d_3$ et $d_4$ en énumérant les dérangements (on notera une permutation $\sigma$ par le mot $\sigma (1)\sigma (2)\cdots \sigma (n)$).

2. Soient $n⩾3$ et $k\in [\text{\hspace{0.17em}⁣}[2,n]\text{\hspace{0.17em}⁣}]$. On note $D_n^k=\{\sigma \in D_n:\sigma (1)=k\}$. Montrer que le nombre de $\sigma \in D_n^k$ tels que $\sigma (k)=1$ vaut $d_{n-2}$, puis construire une bijection explicite entre $\{\sigma \in D_n^k:\sigma (k)\mathrm{\ne }1\}$ et $D_{n-1}^{\mathrm{\prime }}$, l'ensemble des dérangements de $[\text{\hspace{0.17em}⁣}[2,n]\text{\hspace{0.17em}⁣}]$. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(D_n^k\right)=d_{n-1}+d_{n-2}$.

3. En déduire que $d_n=(n-1)(d_{n-1}+d_{n-2})$ pour tout $n⩾3$, puis calculer $d_5$ et $d_6$.

4. Démontrer que ${\displaystyle n!=\sum _{k=0}^n{\displaystyle \left(\genfrac{}{}{0px}{}{n}{k}\right)}{d}_{n-k}}$ en partitionnant ${\mathfrak{S}}_n$ selon l'ensemble des points fixes, et vérifier cette identité pour $n=4$.

Soient $E$ un ensemble fini de cardinal $n⩾1$ et $p⩾1$ un entier. On note

• ${\mathcal{C}}_p$ l'ensemble des $p$-uplets $(A_1,\dots ,A_p)$ de parties de $E$ tels que $A_1\subset A_2\subset \cdots \subset A_p$ ;
• ${\mathcal{R}}_p$ l'ensemble des $p$-uplets $(A_1,\dots ,A_p)$ de parties de $E$ tels que $A_1\cup A_2\cup \cdots \cup A_p=E$.

1. À $(A_1,\dots ,A_p)\in {\mathcal{C}}_p$, on associe l'application $f:E⟶[\text{\hspace{0.17em}⁣}[1,p+1]\text{\hspace{0.17em}⁣}]$ définie par : $f(x)$ est le plus petit indice $i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ tel que $x\in A_i$ s'il en existe un, et $f(x)=p+1$ sinon. Justifier que $f$ est bien définie.

2. Montrer que l'application $\mathrm{\Phi }:(A_1,\dots ,A_p)⟼f$ ainsi obtenue est une bijection de ${\mathcal{C}}_p$ sur $\mathcal{F}(E,[\text{\hspace{0.17em}⁣}[1,p+1]\text{\hspace{0.17em}⁣}])$, en explicitant sa réciproque. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left({\mathcal{C}}_p\right)=(p+1{)}^n$.

3. Contrôler le résultat pour $p=1$ et pour $p=2$, puis énumérer les éléments de ${\mathcal{C}}_2$ dans le cas $E=\{1,2\}$.

4. En associant cette fois à chaque $x\in E$ l'ensemble $g(x)=\{i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]:x\in A_i\}$, montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left({\mathcal{R}}_p\right)={(2^p-1)}^n$. Vérifier par énumération pour $n=p=2$.

Pour $n⩾1$ et $p⩾1$, on note $S(n,p)$ le nombre de surjections de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$. Plus généralement, si $X$ et $Y$ sont finis de cardinaux $n$ et $p$, le nombre de surjections de $X$ sur $Y$ vaut $S(n,p)$ : il ne dépend que des cardinaux, comme on le voit en transportant par des bijections $X⟶[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et $Y⟶[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ (ce point est admis).

1. Déterminer, en justifiant, $S(n,1)$, $S(n,n)$, $S(n,p)$ pour $p>n$, et $S(n,2)$.

2. Soient $n⩾2$ et $p⩾2$. En partitionnant les surjections $f$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ selon la valeur $f(n)$, puis selon que $n$ est ou non le seul antécédent de cette valeur, démontrer

3. Dresser le tableau des valeurs de $S(n,p)$ pour $1⩽p⩽n⩽5$. Contrôler les valeurs $S(4,2)=14$ et $S(4,3)=36$ par un autre argument.

4. Démontrer que ${\displaystyle p^n=\sum _{k=1}^p{\displaystyle \left(\genfrac{}{}{0px}{}{p}{k}\right)}S(n,k)}$ en partitionnant les applications de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ selon leur image, et vérifier pour $n=3$ et $p=3$.

Soit $n⩾1$ et soient $x_1,x_2,\dots ,x_N$ des réels deux à deux distincts, où $N=n^2+1$. On appelle sous-suite de $(x_1,\dots ,x_N)$ toute famille $(x_{i_1},\dots ,x_{i_m})$ avec $1⩽i_1<i_2<\cdots <i_m⩽N$ ; l'entier $m$ est sa longueur, et elle est dite croissante si $x_{i_1}<\cdots <x_{i_m}$, décroissante si $x_{i_1}>\cdots >x_{i_m}$, monotone si elle est croissante ou décroissante.

Pour $i\in [\text{\hspace{0.17em}⁣}[1,N]\text{\hspace{0.17em}⁣}]$, on note $c_i$ (resp. $d_i$) la longueur maximale d'une sous-suite croissante (resp. décroissante) dont le premier terme est $x_i$.

1. Justifier que $c_i$ et $d_i$ sont bien définis, et que $c_i⩾1$ et $d_i⩾1$.

2. Soient $i<j$. Montrer que si $x_i<x_j$ alors $c_i⩾c_j+1$, et que si $x_i>x_j$ alors $d_i⩾d_j+1$. En déduire que $(c_i,d_i)\mathrm{\ne }(c_j,d_j)$.

3. En déduire, par le principe des tiroirs, qu'il existe un indice $i$ tel que $c_i⩾n+1$ ou $d_i⩾n+1$, puis conclure que la suite contient une sous-suite monotone de longueur $n+1$.

4. Pour $n=2$, calculer les couples $(c_i,d_i)$ associés à la suite $2,5,3,1,4$, et exhiber une sous-suite monotone de longueur $3$.

5. Montrer que $n^2+1$ ne peut pas être remplacé par $n^2$ : construire, pour tout $n⩾1$, une suite de $n^2$ réels deux à deux distincts sans sous-suite monotone de longueur $n+1$, et l'expliciter pour $n=2$.

Soient $a$ et $b$ deux entiers naturels. Un chemin de $(0,0)$ à $(a,b)$ est un mot de $a+b$ lettres sur l'alphabet $\{\mathrm{D},\mathrm{H}\}$ comportant exactement $a$ lettres $\mathrm{D}$ (un pas vers la droite) et $b$ lettres $\mathrm{H}$ (un pas vers le haut) : lues de gauche à droite, les lettres décrivent les pas successifs d'un point parti de $(0,0)$.

Pour un mot $w$ de longueur $\mathrm{\ell }$ et $k\in [\text{\hspace{0.17em}⁣}[0,\mathrm{\ell }]\text{\hspace{0.17em}⁣}]$, on note $D_k(w)$ et $H_k(w)$ le nombre de lettres $\mathrm{D}$ et le nombre de lettres $\mathrm{H}$ parmi les $k$ premières lettres de $w$. Soit $n⩾1$. Un chemin $w$ de $(0,0)$ à $(n,n)$ est dit bon si $D_k(w)⩾H_k(w)$ pour tout $k\in [\text{\hspace{0.17em}⁣}[0,2n]\text{\hspace{0.17em}⁣}]$, et mauvais sinon.

1. Déterminer le nombre de chemins de $(0,0)$ à $(a,b)$, puis les nombres de chemins de $(0,0)$ à $(n,n)$ et de $(0,0)$ à $(n-1,n+1)$.

2. Soit $w$ un chemin mauvais. Montrer qu'il existe un plus petit indice $m$ tel que $H_m(w)>D_m(w)$, que la $m$-ième lettre de $w$ est $\mathrm{H}$, que $H_m(w)=D_m(w)+1$ et que $m$ est impair.

3. On note $\sigma (w)$ le mot obtenu en conservant les $m$ premières lettres de $w$ et en échangeant $\mathrm{D}$ et $\mathrm{H}$ dans chacune des $2n-m$ dernières. Montrer que $\sigma (w)$ est un chemin de $(0,0)$ à $(n-1,n+1)$.

4. Montrer que $\sigma$ est une bijection de l'ensemble des chemins mauvais sur l'ensemble de tous les chemins de $(0,0)$ à $(n-1,n+1)$, en construisant sa réciproque.

5. En déduire que le nombre de bons chemins vaut ${\displaystyle \left(\genfrac{}{}{0px}{}{2n}{n}\right)}-{\displaystyle \left(\genfrac{}{}{0px}{}{2n}{n+1}\right)}$, puis que ce nombre est aussi égal à ${\displaystyle \frac{1}{n+1}}{\displaystyle \left(\genfrac{}{}{0px}{}{2n}{n}\right)}$.

6. Vérifier le résultat pour $n=1$, $n=2$ et $n=3$ en énumérant les bons chemins.