Exercices — Dénombrement

Dans les questions 1. à 4., on travaille dans $[\text{\hspace{0.17em}⁣}[1,200]\text{\hspace{0.17em}⁣}]$. La notation $d\mid n$ signifie « $d$ divise $n$ ».

1. Déterminer le cardinal de chacun des ensembles suivants.

d. $D=\{n\in [\text{\hspace{0.17em}⁣}[1,200]\text{\hspace{0.17em}⁣}];\text{le chiffre des unit}\acute{\text{e}}\text{s de }n\text{ vaut }3\}$

2. Démontrer qu'un entier naturel non nul est divisible à la fois par $6$ et par $9$ si et seulement s'il est divisible par $18$. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)$.

3. Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap D)$.

4. On pose $T=\{n\in [\text{\hspace{0.17em}⁣}[1,200]\text{\hspace{0.17em}⁣}];3\mid n\}$. Justifier que $A\subset T$, calculer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(T)$, et dire si $A=T$.

5. Soit $n$ un entier naturel non nul. Déterminer le cardinal de

$$\mathrm{\Delta }=\{(i,j)\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}{]}^2;i⩽j\},$$

puis donner sa valeur pour $n=20$.

Dans tout l'exercice, on suppose que les objets proposés dans chaque catégorie sont deux à deux distincts.

1. Un restaurant propose $4$ entrées, $6$ plats et $3$ desserts.

a. Combien peut-on composer de menus complets, formés d'une entrée, d'un plat et d'un dessert ?

b. Combien peut-on composer de menus allégés, formés soit d'une entrée et d'un plat, soit d'un plat et d'un dessert ?

2. Une armoire contient $5$ hauts, $4$ bas et $3$ paires de chaussures. Une tenue est la donnée d'un haut, d'un bas et d'une paire de chaussures.

a. Combien de tenues différentes peut-on former ?

b. On décide d'ajouter éventuellement une écharpe, à choisir parmi $4$ écharpes, étant entendu qu'on peut aussi n'en porter aucune. Combien de tenues peut-on alors former ?

3. Trois routes distinctes relient la ville $A$ à la ville $B$, et quatre routes distinctes relient la ville $B$ à la ville $C$.

a. Combien de trajets de $A$ à $C$ passant par $B$ peut-on emprunter ?

b. Combien de trajets aller-retour $A\to B\to C\to B\to A$ peut-on emprunter si l'on n'accepte jamais d'emprunter deux fois la même route ?

4. Un enfant construit une tour en empilant $4$ cubes. Les cubes sont pris dans un bac qui en contient de cinq couleurs, rouge, bleu, vert, jaune et blanc, en quantité suffisante pour qu'une même couleur puisse servir plusieurs fois. Une tour est la donnée, du bas vers le haut, des couleurs des quatre cubes empilés.

a. Combien de tours différentes peut-on construire ?

b. Combien de tours n'ont pas de cube rouge à la base ?

c. Combien de tours n'ont pas de cube rouge à la base et portent au sommet un cube jaune ou blanc ?

5. Un questionnaire comporte $12$ questions ; pour chacune, on doit cocher exactement une réponse parmi les quatre propositions $A$, $B$, $C$, $D$. Une grille de réponses est la donnée des douze réponses cochées.

a. Combien de grilles de réponses différentes peut-on remplir ?

b. Combien de grilles ne comportent aucune réponse $A$ ?

c. Combien de grilles comportent au moins une réponse $A$ ?

1. Une promotion compte $120$ étudiants. Parmi eux, $74$ sont inscrits au club de sport, $46$ au ciné-club, et $21$ sont inscrits aux deux clubs à la fois. Déterminer le nombre d'étudiants :

a. inscrits à au moins un des deux clubs ;

b. inscrits à aucun des deux clubs ;

c. inscrits au club de sport et à lui seul ;

d. inscrits à exactement un des deux clubs.

2. Soit $E$ un ensemble fini, $A$ et $B$ deux parties de $E$. En écrivant $A$ comme la réunion de deux parties disjointes, démontrer que

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\setminus B)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)\mathrm{.}$$

3. On prend $E=[\text{\hspace{0.17em}⁣}[1,100]\text{\hspace{0.17em}⁣}]$, $A=\{n\in E;3\mid n\}$ et $B=\{n\in E;5\mid n\}$. Déterminer $\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)$, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B)$, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\setminus B)$, puis le cardinal du complémentaire de $A\cup B$ dans $E$.

4. Soit $E$ un ensemble fini et $A$, $B$ deux parties de $E$, dont on note $\bar{A}$ et $\bar{B}$ les complémentaires dans $E$. Démontrer que

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\bar{A}\cap \bar{B})=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)-\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),$$

puis retrouver par cette formule le résultat de la question 1. b.

5. Soit $E$ un ensemble fini et $A$, $B$ deux parties de $E$. À quelle condition nécessaire et suffisante a-t-on $\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)$ ?

1. On pose $E=[\text{\hspace{0.17em}⁣}[1,12]\text{\hspace{0.17em}⁣}]$ et $F=\{a,b,c,d\}$. Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\times F)$, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F\times E)$, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F\times F\times F)$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E\times F\times F)$.

2. On considère le quadrillage

$$R=\{(x,y)\in {\mathbb{Z}}^2;-4⩽x⩽7\text{ et }1⩽y⩽9\}\mathrm{.}$$

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

b. Combien de points de $R$ ont leurs deux coordonnées paires ?

c. Combien de points de $R$ ont leurs deux coordonnées de même parité ?

3. On pose $A=\{n\in [\text{\hspace{0.17em}⁣}[1,50]\text{\hspace{0.17em}⁣}];7\mid n\}$ et $B=\{n\in [\text{\hspace{0.17em}⁣}[1,30]\text{\hspace{0.17em}⁣}];5\mid n\}$. Écrire $A$ et $B$ en extension, puis déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\times B)$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\times A)$.

4. Soit $n$ un entier supérieur ou égal à $2$. Déterminer le cardinal des ensembles

$$D=\{(x,y)\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}{]}^2;x\mathrm{\ne }y\}\text{et}I=\{(x,y)\in [\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}{]}^2;x<y\},$$

puis donner leurs valeurs pour $n=12$.

5. On considère les triplets $(x,y,z)$ d'éléments de $[\text{\hspace{0.17em}⁣}[1,6]\text{\hspace{0.17em}⁣}]$.

a. Combien y a-t-il de tels triplets ?

b. Combien en existe-t-il dont les trois coordonnées sont deux à deux distinctes ?

c. Combien en existe-t-il dont deux coordonnées au moins sont égales ?

1. Soit $p$ et $n$ deux entiers naturels non nuls, $E$ un ensemble de cardinal $p$ et $F$ un ensemble de cardinal $n$.

a. Rappeler la valeur de $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{F}(E,F))$ et la justifier par le principe multiplicatif.

b. On suppose $p⩽n$. Rappeler le nombre d'applications injectives de $E$ dans $F$ et l'exprimer à l'aide de factorielles.

2. Un cadenas s'ouvre avec un code de $4$ chiffres, chaque chiffre étant pris entre $0$ et $9$.

a. Expliquer pourquoi un code est exactement une application de $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[0,9]\text{\hspace{0.17em}⁣}]$, puis compter les codes possibles.

b. Combien de codes ont leurs quatre chiffres deux à deux distincts ?

c. Combien de codes comportent au moins un $0$ ?

3. Une plaque d'immatriculation est de la forme $\text{AB-123-CD}$ : deux lettres, puis trois chiffres, puis deux lettres. L'alphabet compte $26$ lettres et les chiffres vont de $0$ à $9$ ; aucune combinaison n'est interdite.

a. Combien de plaques peut-on former ?

b. Combien de plaques ont leurs quatre lettres deux à deux distinctes et leurs trois chiffres deux à deux distincts ?

4. Un mot de passe est une suite de $8$ caractères choisis parmi les $26$ lettres minuscules et les $10$ chiffres, les répétitions étant autorisées.

a. Combien de mots de passe peut-on former ?

b. Combien de mots de passe comportent au moins un chiffre ?

5. On appelle ici mot de $5$ lettres toute suite de $5$ lettres de l'alphabet, qu'elle ait un sens ou non. On convient que les voyelles sont $a$, $e$, $i$, $o$, $u$, $y$, soit six lettres.

a. Combien y a-t-il de mots de $5$ lettres deux à deux distinctes ?

b. Combien y a-t-il de mots de $5$ lettres deux à deux distinctes ne comportant aucune voyelle ?

Dans tout l'exercice, les personnes et les objets considérés sont deux à deux distincts, et l'on suppose qu'aucune course ne se termine par une égalité.

1. Une course réunit $12$ coureurs.

a. Combien de podiums différents peut-on obtenir, un podium étant la donnée du premier, du deuxième et du troisième dans cet ordre ?

b. Combien de résultats différents peut-on obtenir pour les cinq premières places, dans l'ordre ?

c. Combien de classements complets des $12$ coureurs peut-on obtenir ?

2. Toujours avec ces $12$ coureurs, l'un d'eux se nomme Léa. Combien de podiums font figurer Léa ? On donnera deux méthodes.

3. Huit personnes, parmi lesquelles Alice et Bob, s'installent côte à côte sur un banc de huit places numérotées.

a. Combien y a-t-il d'installations possibles ?

b. Combien y en a-t-il dans lesquelles Alice occupe la place numéro $1$ ?

c. Combien y en a-t-il dans lesquelles Alice occupe la place numéro $1$ et Bob la place numéro $8$ ?

4. Avec les mêmes huit personnes sur le même banc :

a. combien d'installations placent Alice et Bob sur deux places voisines ?

b. combien d'installations ne les placent pas sur deux places voisines ?

5. On range côte à côte, sur une étagère, $4$ romans et $3$ bandes dessinées.

a. Combien de rangements différents peut-on faire ?

b. Combien de rangements placent les trois bandes dessinées les unes à côté des autres, sans livre intercalé ?

1. Calculer les coefficients binomiaux suivants.

2. Énoncer la formule de symétrie des coefficients binomiaux, puis l'utiliser pour calculer $\left(\genfrac{}{}{0px}{}{20}{18}\right)$, $\left(\genfrac{}{}{0px}{}{50}{47}\right)$ et $\left(\genfrac{}{}{0px}{}{100}{99}\right)$ sans effectuer de produit de plus de trois facteurs.

3. Résoudre dans les entiers naturels les équations suivantes.

a. $\left(\genfrac{}{}{0px}{}{n}{2}\right)=45$, d'inconnue $n⩾2$.

b. $\left(\genfrac{}{}{0px}{}{n}{3}\right)=35$, d'inconnue $n⩾3$.

4. Soit $E$ un ensemble de cardinal $11$. Déterminer le nombre de parties de $E$ ayant respectivement $3$ éléments, $8$ éléments, $0$ élément, puis $11$ éléments.

5. On travaille dans $E=[\text{\hspace{0.17em}⁣}[1,10]\text{\hspace{0.17em}⁣}]$.

a. Combien $E$ possède-t-il de parties à $2$ éléments ?

b. Combien d'entre elles sont formées de deux entiers pairs ?

c. Combien d'entre elles sont formées de deux entiers consécutifs ?

Dans tout l'exercice, $E=[\text{\hspace{0.17em}⁣}[1,8]\text{\hspace{0.17em}⁣}]$.

1. Écrire en extension $\mathcal{P}(F)$ pour $F=\{a,b,c\}$, puis donner $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(G))$ lorsque $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(G)$ vaut successivement $0$, $1$, $2$ et $3$. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))$.

2. Combien $E$ possède-t-il de parties de cardinal $3$ ? de cardinal $6$ ?

3. Combien $E$ possède-t-il de parties contenant l'élément $1$ ? Parmi elles, combien sont de cardinal $3$ ?

4. À toute partie $A$ de $E$ on associe le mot de huit lettres

$$m(A)={\mathbf{1}}_A(1){\mathbf{1}}_A(2){\mathbf{1}}_A(3){\mathbf{1}}_A(4){\mathbf{1}}_A(5){\mathbf{1}}_A(6){\mathbf{1}}_A(7){\mathbf{1}}_A(8),$$

dont la $k$-ième lettre vaut $1$ si $k\in A$ et $0$ si $k\mathrm{\notin }A$.

a. Écrire $m(A)$ pour $A=\{1,4,8\}$, pour $A=\mathrm{\varnothing }$ et pour $A=E$. Déterminer la partie $A$ telle que $m(A)=10110010$.

b. Expliquer pourquoi deux parties distinctes de $E$ donnent deux mots distincts, et pourquoi tout mot de huit lettres écrit avec des $0$ et des $1$ est le mot d'une partie de $E$. Retrouver ainsi les réponses des questions 1. et 3.

5. Combien $E$ possède-t-il de parties ne contenant ni $2$ ni $3$ ? Combien de parties ne contenant pas simultanément $2$ et $3$ ?

6. Combien $E$ possède-t-il de parties non vides et distinctes de $E$ ?

Le club de robotique d'un lycée compte $16$ membres, tous discernables : $9$ élèves de première année et $7$ élèves de deuxième année. Léa est l'une des élèves de première année.

Dans les questions 1. à 5., un comité désigne un ensemble de membres du club : ni l'ordre, ni les rôles n'interviennent, et deux comités sont égaux exactement lorsqu'ils sont formés des mêmes personnes.

1. Combien peut-on former de comités de $4$ membres ?

2. Combien de comités de $4$ membres comptent exactement $2$ élèves de première année et $2$ élèves de deuxième année ?

3. Combien de comités de $4$ membres contiennent Léa ?

4. Combien de comités de $4$ membres contiennent au moins un élève de deuxième année ?

5. Combien de comités de $4$ membres contiennent au moins deux élèves de deuxième année ?

6. Le club doit maintenant élire une délégation de $4$ personnes occupant quatre rôles distincts : président, trésorier, secrétaire et responsable technique. Une même personne ne peut pas cumuler deux rôles. Combien de délégations différentes peut-on former ? Quel lien cette valeur entretient-elle avec celle de la question 1. ?

On rappelle la formule de Pascal : pour tous entiers naturels $n$ et $p$,

$$\left(\genfrac{}{}{0px}{}{n}{p}\right)+\left(\genfrac{}{}{0px}{}{n}{p+1}\right)=\left(\genfrac{}{}{0px}{}{n+1}{p+1}\right),$$

avec la convention $\left(\genfrac{}{}{0px}{}{n}{p}\right)=0$ dès que $p>n$.

1. En partant de la ligne $n=0$, construire de proche en proche les lignes $n=0$ à $n=7$ du triangle de Pascal, c'est-à-dire la liste des coefficients $\left(\genfrac{}{}{0px}{}{n}{p}\right)$ pour $p$ allant de $0$ à $n$. Préciser la règle de construction utilisée.

2. Vérifier, en recalculant chaque coefficient par la formule $\left(\genfrac{}{}{0px}{}{n}{p}\right)={\displaystyle \frac{n!}{p!(n-p)!}}$, les deux égalités

$$\left(\genfrac{}{}{0px}{}{7}{3}\right)=\left(\genfrac{}{}{0px}{}{6}{2}\right)+\left(\genfrac{}{}{0px}{}{6}{3}\right)\text{et}\left(\genfrac{}{}{0px}{}{6}{4}\right)=\left(\genfrac{}{}{0px}{}{5}{3}\right)+\left(\genfrac{}{}{0px}{}{5}{4}\right)\mathrm{.}$$

3. Développer et réduire $(1+x{)}^6$, puis $(2x-3{)}^4$, où $x$ désigne un réel quelconque.

4. Dans le développement de $(x+2y{)}^7$, déterminer le coefficient du monôme $x^3{y}^4$, puis celui du monôme $x^5{y}^2$. En déduire la somme de tous les coefficients de ce développement.

5. Soit $n$ un entier naturel. Calculer

$$\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)3^k\text{et}\sum _{k=0}^n(-1{)}^k\left(\genfrac{}{}{0px}{}{n}{k}\right)3^k\mathrm{.}$$

Donner la valeur de chacune de ces sommes pour $n=7$.

Un lycée compte $240$ élèves en classe de seconde. Chacun d'eux suit une ou plusieurs langues vivantes, choisies parmi l'espagnol, l'allemand et l'italien. Le secrétariat relève les effectifs suivants : $154$ élèves suivent l'espagnol, $118$ suivent l'allemand, et $63$ suivent à la fois l'espagnol et l'allemand.

On note $E$ l'ensemble des $240$ élèves de seconde, $A$ l'ensemble de ceux qui suivent l'espagnol et $B$ l'ensemble de ceux qui suivent l'allemand. On rappelle la formule du cours, valable pour deux parties d'un ensemble fini :

$$\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)\mathrm{.}$$

1. Combien d'élèves suivent au moins une des deux langues espagnol et allemand ?

2. Combien d'élèves n'en suivent aucune des deux ?

3. Combien d'élèves suivent l'espagnol sans suivre l'allemand ? Combien suivent l'allemand sans suivre l'espagnol ?

4. Combien d'élèves suivent exactement une des deux langues ? On répondra par deux méthodes différentes.

5. Vérifier que les effectifs obtenus aux questions 2. et 3., complétés par celui des élèves suivant les deux langues, redonnent bien l'effectif total de la classe de seconde. Expliquer pourquoi.

6. On oublie maintenant la donnée « $63$ ». En n'utilisant que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=240$, $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)=154$ et $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B)=118$, encadrer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)$ le plus finement possible, et montrer que les deux bornes obtenues peuvent effectivement être atteintes.

7. Un second lycée annonce les chiffres suivants pour sa classe de seconde : $240$ élèves, dont $154$ suivent l'espagnol, $118$ suivent l'allemand et $20$ suivent les deux. Démontrer que ces données sont impossibles.

Soit $E$ un ensemble fini et $A$, $B$, $C$ trois parties de $E$. On rappelle la formule du cours, valable pour deux parties :

$$\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)\mathrm{.}$$

La formule générale du crible est hors programme en PCSI ; c'est précisément pourquoi on l'établit ici à la main, dans le seul cas de trois ensembles, à partir de la formule à deux ensembles du cours.

1. En écrivant $A\cup B\cup C=(A\cup B)\cup C$, en appliquant la formule ci-dessus aux deux parties $A\cup B$ et $C$, puis en développant les deux cardinaux ainsi obtenus à l'aide de cette même formule et de la distributivité

$$(A\cup B)\cap C=(A\cap C)\cup (B\cap C),$$

démontrer que

$$\begin{array}{rl}{\displaystyle \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B\cup C)=}& {\displaystyle \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}(C)}\\ {\displaystyle }& {\displaystyle -\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap C)-\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(B\cap C)}\\ {\displaystyle }& {\displaystyle +\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B\cap C)\mathrm{.}}\end{array}$$

Dans les questions suivantes, $E=[\text{\hspace{0.17em}⁣}[1,300]\text{\hspace{0.17em}⁣}]$, et $A$, $B$, $C$ désignent respectivement l'ensemble des multiples de $2$, celui des multiples de $3$ et celui des multiples de $5$ appartenant à $E$.

2. Soit $d$ un diviseur de $300$. Déterminer le nombre de multiples de $d$ appartenant à $[\text{\hspace{0.17em}⁣}[1,300]\text{\hspace{0.17em}⁣}]$.

3. Démontrer que $A\cap B$ est l'ensemble des multiples de $6$ de $E$, et identifier de même $A\cap C$, $B\cap C$ et $A\cap B\cap C$. En déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cup B\cup C)$, c'est-à-dire le nombre d'entiers de $[\text{\hspace{0.17em}⁣}[1,300]\text{\hspace{0.17em}⁣}]$ divisibles par $2$, par $3$ ou par $5$.

4. Combien d'entiers de $[\text{\hspace{0.17em}⁣}[1,300]\text{\hspace{0.17em}⁣}]$ ne sont divisibles par aucun des trois nombres $2$, $3$ et $5$ ?

5. Combien d'entiers de $[\text{\hspace{0.17em}⁣}[1,300]\text{\hspace{0.17em}⁣}]$ sont divisibles par exactement un des trois nombres $2$, $3$ et $5$ ?

Pour deux ensembles finis $X$ et $Y$, on note $\mathcal{F}(X,Y)$ l'ensemble des applications de $X$ dans $Y$. Une application $f$ de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sera systématiquement représentée par la liste de ses valeurs $(f(1),f(2),\dots ,f(p))$.

1. Déterminer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{F}([\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}],[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]))$, puis $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{F}([\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}],[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]))$.

2. Combien existe-t-il d'injections de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ ? Démontrer qu'il n'existe aucune injection de $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$.

3. Démontrer qu'il n'existe aucune surjection de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$. Plus généralement, soit $p$ et $n$ deux entiers naturels non nuls : à quelle condition portant sur $p$ et $n$ existe-t-il au moins une surjection de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ ? On démontrera la condition nécessaire, et l'on exhibera une surjection lorsqu'elle est remplie.

4. Écrire la liste des huit applications de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,2]\text{\hspace{0.17em}⁣}]$, et en déduire, à la main, le nombre de surjections de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,2]\text{\hspace{0.17em}⁣}]$.

5. Déterminer, à la main, toutes les surjections de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ sur $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$. Que peut-on dire de ces applications ?

6. Combien existe-t-il d'applications $f$ de $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ telles que :

a. $f(1)=f(2)$ ;

b. $f([\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}])\subset \{1,2\}$ ;

c. $f$ prend au moins une fois la valeur $3$ ?

On considère le mot LOGARITHME, formé de dix lettres deux à deux distinctes : L, O, G, A, R, I, T, H, M et E. Parmi elles, quatre sont des voyelles, à savoir O, A, I et E, et six sont des consonnes, à savoir L, G, R, T, H et M.

On appelle anagramme de LOGARITHME tout mot de dix lettres obtenu en écrivant ces dix lettres, chacune une fois et une seule, dans un ordre quelconque ; un tel mot n'a pas nécessairement de sens, et LOGARITHME est lui-même l'une de ses anagrammes. Les positions des lettres sont numérotées de $1$ à $10$, et deux anagrammes sont égales lorsqu'elles portent les mêmes lettres aux mêmes positions.

1. Combien y a-t-il d'anagrammes de LOGARITHME ?

2. Combien d'anagrammes commencent par une voyelle ?

3. Combien d'anagrammes commencent par une voyelle et se terminent par une consonne ?

4. Dans combien d'anagrammes les lettres T et H sont-elles côte à côte, dans un ordre ou dans l'autre ?

5. Dans combien d'anagrammes les lettres T et H ne sont-elles pas côte à côte ?

6. Dans combien d'anagrammes les quatre voyelles occupent-elles exactement les positions $2$, $4$, $6$ et $8$ ?

7. Dans combien d'anagrammes les quatre voyelles occupent-elles quatre positions consécutives ?

Une urne contient $n$ jetons deux à deux discernables, numérotés de $1$ à $n$. On prélève $p$ jetons, avec $1⩽p⩽n$. Quatre protocoles de prélèvement sont possibles.

Protocole A (successivement, avec remise). On prélève un jeton, on note son numéro, on le remet dans l'urne, et on recommence, $p$ fois de suite. Le résultat est la suite ordonnée des $p$ numéros notés.

Protocole B (successivement, sans remise). On prélève un jeton, on note son numéro, on le met de côté, et on recommence, $p$ fois de suite. Le résultat est la suite ordonnée des $p$ numéros notés.

Protocole C (simultanément). On prélève d'un seul geste une poignée de $p$ jetons. Le résultat est la collection des $p$ numéros obtenus, sans ordre.

Protocole D. On dispose maintenant, pour chacun des $n$ numéros, de $p$ jetons portant ce numéro, et on constitue une poignée de $p$ jetons dans laquelle un même numéro peut figurer plusieurs fois, sans tenir compte de l'ordre.

1. Pour chacun des protocoles A, B et C, identifier précisément l'objet mathématique décrivant un résultat, puis donner le nombre de résultats possibles en fonction de $n$ et de $p$. Pour le protocole D, décrire l'objet obtenu et expliquer pourquoi aucune des trois formules précédentes ne le compte (on ne demande pas de le dénombrer ici).

2. Établir la relation $A_n^p=p!\left(\genfrac{}{}{0px}{}{n}{p}\right)$ et l'interpréter en termes de protocoles. Donner les trois valeurs numériques pour $n=10$ et $p=3$.

3. Protocole C : combien de résultats contiennent le jeton numéro $1$ ? Application numérique pour $n=10$ et $p=3$.

4. Protocole C avec $n=10$ et $p=3$ : combien de résultats ne comportent que des numéros pairs ?

5. Protocole C : soit $k$ un entier de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. Combien de résultats ont pour plus grand numéro exactement $k$ ? En déduire l'identité

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

Application numérique pour $n=10$, $p=3$ et $k=7$.

6. Protocole A : combien de résultats font apparaître le jeton numéro $1$ au moins une fois ? Application numérique pour $n=10$ et $p=3$.

On considère un jeu de $32$ cartes. Chaque carte est déterminée par sa couleur, choisie parmi les quatre couleurs pique, coeur, carreau et trèfle, et par sa hauteur, choisie parmi les huit hauteurs $7$, $8$, $9$, $10$, valet, dame, roi et as. Les $32$ cartes sont donc deux à deux distinctes.

On appelle main un ensemble de $5$ cartes du jeu : les cartes d'une main sont deux à deux distinctes et l'ordre dans lequel on les énumère n'intervient pas. Dans tout l'exercice, on précisera le modèle utilisé.

1. Combien y a-t-il de mains ?

2. Combien de mains contiennent exactement deux as ?

3. Combien de mains contiennent au moins un as ?

4. Combien de mains sont formées de cinq cartes de la même couleur ?

5. Combien de mains contiennent exactement une paire, c'est-à-dire exactement deux cartes de même hauteur, les trois autres cartes ayant trois hauteurs deux à deux distinctes et différentes de celle de la paire ?

6. Combien de mains contiennent au moins une carte de chacune des quatre couleurs ? On raisonnera par disjonction de cas sur la répartition des cinq cartes entre les couleurs.

Soit $n$ un entier avec $n⩾5$. On considère un polygone convexe de sommets $A_1,A_2,\dots ,A_n$, énumérés dans cet ordre le long du contour. Les indices sont lus de façon cyclique, autrement dit on convient que $A_0=A_n$, que $A_{n+1}=A_1$ et que $A_{n+2}=A_2$. On suppose que trois sommets ne sont jamais alignés.

Les côtés du polygone sont les $n$ segments $[A_i{A}_{i+1}]$ joignant deux sommets consécutifs. Une diagonale est un segment joignant deux sommets non consécutifs. Un triangle du polygone est un triangle dont les trois sommets sont des sommets du polygone.

1. Combien y a-t-il de segments joignant deux sommets du polygone ?

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

3. Combien y a-t-il de triangles du polygone ?

4. Combien de triangles du polygone n'ont aucun côté commun avec le polygone ? On effectuera une disjonction de cas selon le nombre de côtés du polygone portés par le triangle.

5. Donner les quatre valeurs numériques obtenues pour $n=12$.

6. Pour quelles valeurs de $n$ le polygone possède-t-il autant de diagonales que de côtés ?

Pour un entier $N⩾1$, on note $\mathcal{D}(N)$ l'ensemble des diviseurs positifs de $N$, c'est-à-dire

$$\mathcal{D}(N)=\{d\in {\mathbb{N}}^{\ast };d\mid N\},$$

et $\tau (N)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{D}(N))$ le nombre de ces diviseurs. On rappelle que tout entier $N⩾2$ s'écrit de façon unique, à l'ordre des facteurs près, sous la forme

$$N=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_r^{{\alpha }_r},$$

où $p_1<p_2<\cdots <p_r$ sont des nombres premiers et où ${\alpha }_1,\dots ,{\alpha }_r$ sont des entiers supérieurs ou égaux à $1$.

1. Décomposer $360$ puis $2520$ en produit de facteurs premiers.

2. Soit $N⩾2$ décomposé comme ci-dessus. Démontrer qu'un entier $d⩾1$ divise $N$ si et seulement s'il s'écrit $d=p_1^{a_1}{p}_2^{a_2}\cdots p_r^{a_r}$ avec $0⩽a_i⩽{\alpha }_i$ pour tout $i$ de $[\text{\hspace{0.17em}⁣}[1,r]\text{\hspace{0.17em}⁣}]$, et que cette écriture de $d$ est unique.

3. En décrivant un diviseur par la suite de ses exposants, en déduire par choix successifs la formule

$$\tau (N)=({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_r+1)=\prod _{i=1}^r({\alpha }_i+1)\mathrm{.}$$

Calculer $\tau (360)$ et $\tau (2520)$.

4. Combien $360$ possède-t-il de diviseurs pairs ? Et $2520$ ?

5. Combien $360$ possède-t-il de diviseurs qui sont des carrés parfaits ? Les expliciter. Même question pour $2520$.

6. Déterminer le plus petit entier $N⩾1$ possédant exactement $12$ diviseurs positifs.

Soit $n$ un entier avec $n⩾1$. On appelle mot binaire de longueur $n$ toute suite finie $m=x_1{x}_2\cdots x_n$ dont chaque terme $x_i$ appartient à l'alphabet $\{0,1\}$. Par exemple, $10110$ est un mot binaire de longueur $5$, comportant trois chiffres $1$. On note ${\mathcal{B}}_n$ l'ensemble des mots binaires de longueur $n$.

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

2. Soit $k\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$. Combien de mots de ${\mathcal{B}}_n$ comportent exactement $k$ chiffres $1$ ?

3. Combien de mots de ${\mathcal{B}}_n$ comportent au moins deux chiffres $1$ ?

4. On suppose $n⩾2$. Combien de mots de ${\mathcal{B}}_n$ commencent et finissent par $1$ ?

5. Combien de mots de ${\mathcal{B}}_{10}$ comportent autant de chiffres $0$ que de chiffres $1$ ? Donner également les valeurs numériques des questions 1, 3 et 4 pour $n=10$.

6. En classant les mots de ${\mathcal{B}}_n$ selon leur nombre de chiffres $1$, démontrer l'identité

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

Dans tout l'exercice, $n$ et $p$ désignent des entiers naturels et $E$ un ensemble fini de cardinal $n$. Pour $0⩽p⩽n$, on note ${\mathcal{P}}_p(E)$ l'ensemble des parties de $E$ de cardinal $p$, de sorte que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{P}}_p(E))=\left(\genfrac{}{}{0px}{}{n}{p}\right)$. Pour une partie $A$ de $E$, on note $\bar{A}=E\setminus A$ son complémentaire dans $E$.

1. Soit $0⩽p⩽n$. Démontrer, en passant au complémentaire, que $\left(\genfrac{}{}{0px}{}{n}{p}\right)=\left(\genfrac{}{}{0px}{}{n}{n-p}\right)$.

2. Soit $1⩽p⩽n$. Démontrer la formule du pivot

$$p\left(\genfrac{}{}{0px}{}{n}{p}\right)=n\left(\genfrac{}{}{0px}{}{n-1}{p-1}\right)$$

par le calcul, à l'aide des factorielles.

3. Redémontrer la formule du pivot par double comptage, en dénombrant de deux façons l'ensemble des couples $(A,x)$ où $A$ est une partie de $E$ de cardinal $p$ et où $x$ est un élément de $A$.

4. Soit $n⩾1$. Simplifier le quotient ${\displaystyle \frac{\left(\genfrac{}{}{0px}{}{2n}{n}\right)}{\left(\genfrac{}{}{0px}{}{2n-1}{n-1}\right)}}$. Vérifier le résultat pour $n=6$.

5. Soit $0⩽k⩽n-1$. Calculer le quotient ${\displaystyle \frac{\left(\genfrac{}{}{0px}{}{n}{k+1}\right)}{\left(\genfrac{}{}{0px}{}{n}{k}\right)}}$, en déduire que la suite finie $\left(\genfrac{}{}{0px}{}{n}{0}\right),\left(\genfrac{}{}{0px}{}{n}{1}\right),\dots ,\left(\genfrac{}{}{0px}{}{n}{\lfloor n\mathrm{/}2\rfloor }\right)$ est strictement croissante, puis établir que, pour $a$ et $b$ dans $[\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$,

$$\left(\genfrac{}{}{0px}{}{n}{a}\right)=\left(\genfrac{}{}{0px}{}{n}{b}\right)⟺(a=b\text{ ou }a+b=n)\mathrm{.}$$

6. Soit $n⩾3$. Résoudre l'équation $\left(\genfrac{}{}{0px}{}{n}{p}\right)=\left(\genfrac{}{}{0px}{}{n}{2p-3}\right)$, d'inconnue l'entier $p$ vérifiant $0⩽p⩽n$ et $0⩽2p-3⩽n$. Expliciter les solutions pour $n=12$.

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

Soit $n$ un entier naturel. On rappelle la formule du binôme : pour tous nombres réels $a$ et $b$,

$$(a+b{)}^n=\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)a^k{b}^{n-k}\mathrm{.}$$

Toutes les sommes de cet exercice se calculent en choisissant convenablement $a$ et $b$.

1. Calculer ${\displaystyle S_n=\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)}$ et interpréter le résultat en termes de parties d'un ensemble à $n$ éléments.

2. Calculer ${\displaystyle T_n=\sum _{k=0}^n(-1{)}^k\left(\genfrac{}{}{0px}{}{n}{k}\right)}$, en distinguant le cas $n=0$.

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

4. On suppose $n⩾1$. On note $P_n$ la somme des $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ pour les entiers $k$ de $[\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ pairs, et $I_n$ la somme des $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ pour les entiers $k$ de $[\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$ impairs :

$$P_n=\left(\genfrac{}{}{0px}{}{n}{0}\right)+\left(\genfrac{}{}{0px}{}{n}{2}\right)+\left(\genfrac{}{}{0px}{}{n}{4}\right)+\cdots ,I_n=\left(\genfrac{}{}{0px}{}{n}{1}\right)+\left(\genfrac{}{}{0px}{}{n}{3}\right)+\left(\genfrac{}{}{0px}{}{n}{5}\right)+\cdots$$

En combinant les questions 1 et 2, calculer $P_n$ et $I_n$.

5. Pour tout réel $x$, exprimer simplement ${\displaystyle f_n(x)=\sum _{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)x^k}$. En déduire les valeurs de $f_n(-2)$ et de $f_n(3)$, et retrouver les résultats des questions 1, 2 et 3.

6. Soit $E$ un ensemble de cardinal $n⩾1$. Déduire de la question 4 une comparaison entre le nombre de parties de $E$ de cardinal pair et le nombre de parties de $E$ de cardinal impair. Illustrer sur l'exemple $n=3$.

1. Le principe. Soient $E$ et $F$ deux ensembles finis non vides tels que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)>\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$. Démontrer qu'aucune application de $E$ dans $F$ n'est injective, autrement dit que pour toute application $f:E⟶F$ il existe deux éléments distincts $x$ et $y$ de $E$ tels que $f(x)=f(y)$.

Ce résultat est appelé principe des tiroirs : si l'on range plus d'objets que l'on n'a de tiroirs, un tiroir au moins contient deux objets. Dans chacune des questions qui suivent, on précisera explicitement quels sont les « objets », quels sont les « tiroirs », et quelle est l'application considérée.

2. Dans un groupe de $27$ personnes, démontrer que deux au moins ont la même initiale de prénom (on convient que chaque initiale est l'une des $26$ lettres de l'alphabet). La conclusion est-elle encore garantie avec $26$ personnes ?

3. Démontrer que dans un groupe de $13$ personnes, deux au moins sont nées le même mois.

4. Soit $n\in {\mathbb{N}}^{\ast }$. On choisit $n+1$ entiers deux à deux distincts dans $[\text{\hspace{0.17em}⁣}[1,2n]\text{\hspace{0.17em}⁣}]$. Démontrer que deux d'entre eux sont consécutifs, c'est-à-dire diffèrent de $1$. Montrer que $n$ entiers ne suffiraient pas.

5. On place cinq points dans un carré plein de côté $2$. Démontrer que deux de ces points sont à une distance inférieure ou égale à $\sqrt{2}$. Montrer que quatre points ne suffiraient pas.

6. Version quantitative. Soient $E$ et $F$ deux ensembles finis non vides et $k\in {\mathbb{N}}^{\ast }$ tels que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)>k\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$. Démontrer que pour toute application $f:E⟶F$, il existe un élément $y$ de $F$ tel que $f^{-1}(\{y\})$ contienne au moins $k+1$ éléments. En déduire que dans un groupe de $100$ personnes, neuf au moins sont nées le même mois.

On appelle anagramme d'un mot toute suite de lettres obtenue en réordonnant les lettres de ce mot, chaque lettre étant utilisée autant de fois qu'elle figure dans le mot initial. Les anagrammes n'ont pas à avoir de sens, et le mot lui-même compte parmi ses anagrammes. Deux occurrences d'une même lettre sont indiscernables : le mot ETE n'a que trois anagrammes, à savoir ETE, EET et TEE.

1. On considère le mot STATISTIQUE.

a. Donner le nombre de lettres du mot et le décompte de chacune de ses lettres.

b. Dénombrer ses anagrammes en choisissant successivement les positions occupées par chaque lettre.

2. Toujours pour le mot STATISTIQUE :

a. Combien d'anagrammes commencent par la lettre T ? par la lettre A ?

b. Vérifier la cohérence de ces résultats en classant les anagrammes selon leur première lettre.

c. Combien d'anagrammes comportent les trois T côte à côte, c'est-à-dire en trois positions consécutives ?

3. On considère maintenant le mot court ANANAS.

a. Combien a-t-il d'anagrammes ?

b. Combien de ses anagrammes ne comportent jamais deux A côte à côte ?

c. Combien de ses anagrammes ne comportent jamais deux lettres identiques côte à côte ? On donnera la liste complète de ces mots.

4. Cas général. Soit un mot de $n$ lettres écrit avec $r$ lettres deux à deux distinctes, la $j$-ième figurant $n_j$ fois, de sorte que $n_1+n_2+\cdots +n_r=n$. Démontrer, par la méthode de placement de la question 1, que le nombre d'anagrammes de ce mot vaut

$$\frac{n!}{n_1!n_2!\cdots n_r!}\mathrm{.}$$

Soient $m$ et $n$ deux entiers naturels non nuls. On appelle sommets de la grille les points du plan de coordonnées entières $(i,j)$ vérifiant $0⩽i⩽m$ et $0⩽j⩽n$. Un pas mène d'un sommet $(i,j)$ soit au sommet $(i+1,j)$, et on dit que le pas va vers la droite, soit au sommet $(i,j+1)$, et on dit que le pas va vers le haut ; dans les deux cas le pas doit rester dans la grille. Un chemin est une suite de pas partant du sommet $(0,0)$ et arrivant au sommet $(m,n)$.

1. Démontrer qu'un chemin comporte exactement $m+n$ pas, dont exactement $m$ vers la droite.

2. On code un chemin par le mot obtenu en écrivant, dans l'ordre où on les effectue, la lettre D pour un pas vers la droite et la lettre H pour un pas vers le haut. Décrire précisément ce codage et en déduire que le nombre de chemins de $(0,0)$ à $(m,n)$ vaut $\left(\genfrac{}{}{0px}{}{m+n}{n}\right)$.

Dans les questions suivantes, on prend $m=6$ et $n=4$.

3. Combien y a-t-il de chemins en tout ?

4. Combien de chemins passent par le sommet $(3,2)$ ? Donner d'abord la formule générale donnant le nombre de chemins passant par un sommet $(a,b)$ de la grille.

5. Combien de chemins évitent le sommet $(3,2)$ ?

6. Combien de chemins empruntent le pas horizontal joignant $(3,2)$ à $(4,2)$ ? Même question pour le pas vertical joignant $(3,2)$ à $(3,3)$. Contrôler la cohérence avec la question 4.

1. Le théorème. Soient $E$ et $F$ deux ensembles finis non vides de même cardinal $n$, et soit $f:E⟶F$ une application.

a. Démontrer que si $f$ est injective, alors $f$ est surjective.

b. Démontrer que si $f$ est surjective, alors $f$ est injective. On pourra considérer les ensembles $f^{-1}(\{y\})$ pour $y\in F$.

c. En déduire que les trois propriétés « $f$ est injective », « $f$ est surjective » et « $f$ est bijective » sont équivalentes.

2. Montrer, par deux contre-exemples explicites, que l'hypothèse $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(E)=\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(F)$ ne peut pas être supprimée : on construira une application injective et non surjective, puis une application surjective et non injective.

3. Montrer que l'hypothèse de finitude ne peut pas non plus être supprimée, en étudiant l'injectivité et la surjectivité des trois applications de $\mathbb{N}$ dans $\mathbb{N}$ suivantes :

$$u:k⟼k+1,v:k⟼2k,w:k⟼\{\begin{array}{ll}0& \text{si }k=0,\\ k-1& \text{si }k⩾1.\end{array}$$

4. Une application concrète. Soit $p\in {\mathbb{N}}^{\ast }$. On définit $f$ sur $[\text{\hspace{0.17em}⁣}[1,2p]\text{\hspace{0.17em}⁣}]$ par

$$f(k)=\{\begin{array}{ll}2k& \text{si }1⩽k⩽p,\\ 2(k-p)-1& \text{si }p+1⩽k⩽2p\mathrm{.}\end{array}$$

a. Vérifier que $f$ est bien une application de $[\text{\hspace{0.17em}⁣}[1,2p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,2p]\text{\hspace{0.17em}⁣}]$.

b. Démontrer que $f$ est injective, et en déduire qu'elle est bijective.

c. Écrire les images de $1,2,\dots ,10$ dans le cas $p=5$.

5. Dénombrer les permutations d'un ensemble fini de cardinal $n$, c'est-à-dire ses bijections sur lui-même. Donner les valeurs pour $n=5$ et $n=10$.

Soit $E$ un ensemble fini de cardinal $n$. On se propose de démontrer de trois façons indépendantes que

$$\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathcal{P}(E))=2^n\mathrm{.}$$

1. Première preuve, par récurrence. Démontrer le résultat par récurrence sur $n$, en séparant, dans un ensemble à $n+1$ éléments, les parties qui contiennent un élément fixé de celles qui ne le contiennent pas.

2. Deuxième preuve, par codage. On numérote les éléments de $E$ sous la forme $E=\{x_1,x_2,\dots ,x_n\}$, les $x_i$ étant deux à deux distincts. À une partie $A$ de $E$, on associe le mot de $n$ chiffres

$$m(A)=({\mathbf{1}}_A(x_1),{\mathbf{1}}_A(x_2),\dots ,{\mathbf{1}}_A(x_n)),$$

où ${\mathbf{1}}_A$ désigne la fonction indicatrice de $A$. Justifier que ce codage permet de conclure.

3. Troisième preuve, par le binôme. Classer les parties de $E$ selon leur cardinal, puis conclure à l'aide de la formule du binôme.

4. Deux corollaires.

a. On suppose $n⩾1$ et l'on fixe un élément $a$ de $E$. À une partie $A$ de $E$, on associe la partie

$$\phi (A)=\{\begin{array}{ll}A\cup \{a\}& \text{si }a\mathrm{\notin }A,\\ A\setminus \{a\}& \text{si }a\in A\mathrm{.}\end{array}$$

Démontrer que $\phi$ est une bijection de $\mathcal{P}(E)$ sur lui-même qui échange les parties de cardinal pair et celles de cardinal impair, puis en déduire que le nombre de parties de $E$ de cardinal pair vaut $2^{n-1}$. Que se passe-t-il pour $n=0$ ?

b. Déterminer le nombre de parties non vides de $E$, puis le nombre de parties de $E$ contenant un élément fixé $a$.

5. Donner toutes les valeurs numériques obtenues dans le cas $n=10$, et contrôler le résultat du 4.a. par un calcul direct.

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

1. Dénombrer les couples $(A,B)$ de parties de $E$ tels que $A\subset B$, en attribuant à chaque élément de $E$ un statut parmi trois possibilités que l'on précisera.

2. Retrouver ce résultat par un calcul : classer les couples selon le cardinal de $A$, puis reconnaître la somme obtenue comme une application de la formule du binôme.

3. Dénombrer les couples $(A,B)$ de parties de $E$ tels que $A\cap B=\mathrm{\varnothing }$, puis les couples tels que $A\cup B=E$. Commenter les résultats.

4. Dénombrer les triplets $(A,B,C)$ de parties de $E$ deux à deux disjointes et de réunion $E$. Commenter.

5. Dénombrer les couples $(A,B)$ tels que l'inclusion soit stricte, c'est-à-dire $A\subset B$ et $A\mathrm{\ne }B$.

6. Donner les valeurs numériques pour $n=5$ et $n=10$.

Soient $n$ et $p$ deux entiers naturels non nuls. Une application $f:[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]⟶[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est dite strictement croissante lorsque

$$f(1)<f(2)<\cdots <f(p),$$

et croissante (au sens large) lorsque $f(1)⩽f(2)⩽\cdots ⩽f(p)$. On adopte la convention usuelle $\left(\genfrac{}{}{0px}{}{q}{r}\right)=0$ dès que $r>q$, qui traduit qu'un ensemble à $q$ éléments n'a aucune partie à $r$ éléments lorsque $r>q$.

1. Démontrer que le nombre d'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}⁣}]$ vaut $\left(\genfrac{}{}{0px}{}{n}{p}\right)$. On expliquera précisément comment retrouver une telle application à partir de l'ensemble de ses valeurs. Que devient le résultat lorsque $p>n$ ?

2. Soit $f:[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]⟶[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ une application croissante. On pose $g(i)=f(i)+i-1$ pour tout $i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$.

a. Dé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}⁣}]$.

b. Démontrer réciproquement que toute application strictement croissante $g$ de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n+p-1]\text{\hspace{0.17em}⁣}]$ provient d'une unique application croissante $f$ de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ par cette formule.

c. En déduire que le nombre d'applications croissantes de $[\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ vaut $\left(\genfrac{}{}{0px}{}{n+p-1}{p}\right)$.

3. Contrôler les deux formules dans le cas $p=2$ et $n=3$, en écrivant toutes les applications concernées.

4. Applications numériques : combien y a-t-il d'applications strictement croissantes, puis croissantes, de $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,10]\text{\hspace{0.17em}⁣}]$ ? de $[\text{\hspace{0.17em}⁣}[1,3]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,5]\text{\hspace{0.17em}⁣}]$ ? de $[\text{\hspace{0.17em}⁣}[1,6]\text{\hspace{0.17em}⁣}]$ dans $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ ?

Soient $n\in \mathbb{N}$ et $p\in {\mathbb{N}}^{\ast }$. On s'intéresse aux $p$-uplets $(x_1,x_2,\dots ,x_p)$ d'entiers naturels vérifiant

$$x_1+x_2+\cdots +x_p=n\mathrm{.}$$

Deux $p$-uplets sont distincts dès qu'ils diffèrent par au moins une coordonnée : l'ordre des inconnues compte, et $(2,1,0)$ et $(0,1,2)$ sont deux solutions différentes. On adopte la convention usuelle $\left(\genfrac{}{}{0px}{}{q}{r}\right)=0$ dès que $r>q$, qui traduit qu'un ensemble à $q$ éléments n'a aucune partie à $r$ éléments lorsque $r>q$.

1. On aligne $n$ jetons identiques et $p-1$ séparateurs identiques. Décrire comment un tel alignement fournit une solution de l'équation, et comment toute solution s'obtient ainsi une fois et une seule. En déduire que le nombre de solutions vaut $\left(\genfrac{}{}{0px}{}{n+p-1}{p-1}\right)$.

2. Contrôler le résultat pour $n=3$ et $p=3$ en écrivant toutes les solutions.

3. Dénombrer les solutions en entiers strictement positifs, c'est-à-dire vérifiant $x_i⩾1$ pour tout $i$.

4. Dénombrer les solutions en entiers naturels vérifiant la contrainte supplémentaire $x_1⩾2$.

5. Dénombrer les $p$-uplets d'entiers naturels vérifiant l'inéquation $x_1+x_2+\cdots +x_p⩽n$.

6. Donner les valeurs numériques des questions 1, 3, 4 et 5 pour $n=10$ et $p=4$.

7. Expliquer le lien avec les tirages avec répétitions rencontrés à l'exercice 15 : de combien de façons peut-on choisir $10$ viennoiseries parmi $4$ sortes disponibles, sans tenir compte de l'ordre, chaque sorte pouvant être prise plusieurs fois ou pas du tout ?

Soit $n$ un entier naturel non nul et soit $F=\{a,b\}$ un ensemble à deux éléments (donc $a\mathrm{\ne }b$). On note $S_n$ le nombre de surjections de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $F$.

1. a. Combien y a-t-il d'applications de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ dans $F$ ?

b. Décrire complètement les applications de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ dans $F$ qui ne sont pas surjectives, puis en déduire $S_n$ par passage au complémentaire.

c. Donner les valeurs de $S_1$, $S_2$, $S_3$ et $S_{10}$.

2. On appelle partition de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ en deux parties non vides toute paire $\{A,B\}$ formée de deux parties de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ telles que $A\mathrm{\ne }\mathrm{\varnothing }$, $B\mathrm{\ne }\mathrm{\varnothing }$, $A\cap B=\mathrm{\varnothing }$ et $A\cup B=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$. On note $P_n$ le nombre de telles partitions.

a. À une surjection $f$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $F$, on associe le couple $(f^{-1}(\{a\}),f^{-1}(\{b\}))$. Montrer que la paire $\{f^{-1}(\{a\}),f^{-1}(\{b\})\}$ est une partition de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ en deux parties non vides.

b. Montrer que chaque partition en deux parties non vides provient d'exactement deux surjections, et en déduire $P_n$.

c. Calculer $P_4$ et $P_{10}$.

3. Combien y a-t-il de surjections $f$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $F$ vérifiant $f(1)=a$ ? Commenter le résultat obtenu en le comparant à celui de la question 2.

4. On suppose ici $n⩾2$. Combien y a-t-il de surjections $f$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ sur $F$ vérifiant $f(1)=f(n)$ ?

Soit $E$ un ensemble fini de cardinal $n⩾1$. On s'intéresse à la somme des cardinaux de toutes les parties de $E$ :

$${\mathrm{\Sigma }}_n=\sum _{A\in \mathcal{P}(E)}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A)\mathrm{.}$$

1. Calculer ${\mathrm{\Sigma }}_3$ à la main, en listant les huit parties de $E=\{1,2,3\}$.

2. On note $\mathrm{\Delta }$ l'ensemble des couples $(x,A)$ où $A$ est une partie de $E$ et $x$ un élément de $A$ :

$$\mathrm{\Delta }=\{(x,A)\in E\times \mathcal{P}(E);x\in A\}\mathrm{.}$$

a. En regroupant les couples de $\mathrm{\Delta }$ selon leur seconde composante $A$, montrer que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathrm{\Delta })={\mathrm{\Sigma }}_n$.

b. Soit $x\in E$. Combien y a-t-il de parties de $E$ contenant $x$ ? En regroupant les couples de $\mathrm{\Delta }$ selon leur première composante, en déduire $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(\mathrm{\Delta })$.

c. Conclure, et vérifier la cohérence avec la question 1.

3. Retrouver le résultat en regroupant les parties de $E$ selon leur cardinal : montrer que ${\mathrm{\Sigma }}_n={\displaystyle \sum _{k=0}^{n}k\left(\genfrac{}{}{0px}{}{n}{k}\right)}$, puis calculer cette somme à l'aide de la formule du pivot $k\left(\genfrac{}{}{0px}{}{n}{k}\right)=n\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)$.

4. Combien y a-t-il de couples $(x,A)\in E\times \mathcal{P}(E)$ tels que $x\mathrm{\notin }A$ ? En déduire la valeur de ${\displaystyle \sum _{A\in \mathcal{P}(E)}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}\left(\bar{A}\right)}$, où $\bar{A}$ désigne le complémentaire de $A$ dans $E$, et commenter.

5. Soit $B$ une partie fixée de $E$, de cardinal $b$. Par la même méthode, calculer

$$\sum _{A\in \mathcal{P}(E)}\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap B)\mathrm{.}$$

Vérifier la formule obtenue dans les deux cas particuliers $B=E$ et $B=\mathrm{\varnothing }$.

6. En déduire la moyenne des cardinaux des $2^n$ parties de $E$, puis retrouver ce résultat en regroupant les parties deux par deux.

Dans tout l'exercice, $m$, $n$ et $p$ désignent des entiers naturels, et l'on adopte la convention usuelle $\left(\genfrac{}{}{0px}{}{q}{r}\right)=0$ dès que $r>q$ ou $r<0$. On se donne un ensemble fini $E$ réunion de deux parties disjointes $M$ et $N$, avec

$$E=M\cup N,M\cap N=\mathrm{\varnothing },\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(M)=m,\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(N)=n\mathrm{.}$$

1. Mise en train. En classant les parties à deux éléments de $E$ selon le nombre d'éléments qu'elles prennent dans $M$, démontrer que

$$\left(\genfrac{}{}{0px}{}{m+n}{2}\right)=\left(\genfrac{}{}{0px}{}{m}{2}\right)+mn+\left(\genfrac{}{}{0px}{}{n}{2}\right)\mathrm{.}$$

2. Cas général. Soit $p\in \mathbb{N}$. Pour $k\in [\text{\hspace{0.17em}⁣}[0,p]\text{\hspace{0.17em}⁣}]$, on note ${\mathcal{A}}_k$ l'ensemble des parties $A$ de $E$ à $p$ éléments telles que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap M)=k$.

a. Justifier que la famille $({\mathcal{A}}_k{)}_{0⩽k⩽p}$ est une partition de l'ensemble des parties de $E$ à $p$ éléments.

b. Calculer $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}({\mathcal{A}}_k)$.

c. En déduire la formule de Vandermonde :

$$\sum _{k=0}^p\left(\genfrac{}{}{0px}{}{m}{k}\right)\left(\genfrac{}{}{0px}{}{n}{p-k}\right)=\left(\genfrac{}{}{0px}{}{m+n}{p}\right)\mathrm{.}$$

3. Donner une seconde démonstration de cette formule en identifiant les coefficients de $x^p$ dans les deux membres de l'égalité polynomiale $(1+x{)}^m(1+x{)}^n=(1+x{)}^{m+n}$.

4. Applications.

a. Calculer ${\displaystyle \sum _{k=0}^3\left(\genfrac{}{}{0px}{}{5}{k}\right)\left(\genfrac{}{}{0px}{}{7}{3-k}\right)}$ en détaillant les quatre termes, puis en appliquant la formule.

b. Un concours est jugé par un jury de $4$ personnes, choisies parmi $7$ femmes et $5$ hommes. Combien de jurys différents peut-on constituer ? Combien en comptent exactement deux femmes ? Vérifier que la répartition des jurys selon leur nombre de femmes redonne le total.

c. Écrire ce que devient la formule de Vandermonde lorsque $m=n=p$. (Ce cas particulier remarquable fait l'objet de l'exercice 33 ; on ne demande pas ici de le démontrer.)

On adopte la convention $\left(\genfrac{}{}{0px}{}{q}{r}\right)=0$ dès que $r>q$ ou $r<0$.

1. Vérifier à la main, pour $n=3$ puis pour $n=4$, l'identité

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

2. Première démonstration, par double comptage. Soit $n\in {\mathbb{N}}^{\ast }$. On pose $E=[\text{\hspace{0.17em}⁣}[1,2n]\text{\hspace{0.17em}⁣}]$, $M=[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ et $N=[\text{\hspace{0.17em}⁣}[n+1,2n]\text{\hspace{0.17em}⁣}]$, de sorte que $E$ est la réunion disjointe de $M$ et de $N$.

a. Combien $E$ possède-t-il de parties à $n$ éléments ?

b. Pour $k\in [\text{\hspace{0.17em}⁣}[0,n]\text{\hspace{0.17em}⁣}]$, combien y a-t-il de parties $A$ de $E$ à $n$ éléments telles que $\mathrm{C}\mathrm{a}\mathrm{r}\mathrm{d}(A\cap M)=k$ ? On exprimera le résultat à l'aide de la symétrie $\left(\genfrac{}{}{0px}{}{n}{n-k}\right)=\left(\genfrac{}{}{0px}{}{n}{k}\right)$.

c. Conclure.

3. Seconde démonstration. Retrouver l'identité en identifiant les coefficients de $x^n$ dans les deux membres de $((1+x{)}^n{)}^2=(1+x{)}^{2n}$.

4. La somme d'une « colonne » du triangle de Pascal. Soient $p$ et $n$ deux entiers naturels avec $p⩽n$. On veut établir

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

a. Déduire de la formule de Pascal que ${\displaystyle \left(\genfrac{}{}{0px}{}{k}{p}\right)=\left(\genfrac{}{}{0px}{}{k+1}{p+1}\right)-\left(\genfrac{}{}{0px}{}{k}{p+1}\right)}$, puis conclure par télescopage.

b. En donner une seconde démonstration en classant les parties à $p+1$ éléments de $[\text{\hspace{0.17em}⁣}[1,n+1]\text{\hspace{0.17em}⁣}]$ selon leur plus grand élément.

5. Applications.

a. Calculer ${\displaystyle \sum _{k=3}^8\left(\genfrac{}{}{0px}{}{k}{3}\right)}$ en détaillant les six termes, puis à l'aide de la formule.

b. En remarquant que $k^2=2\left(\genfrac{}{}{0px}{}{k}{2}\right)+k$ pour tout entier $k⩾0$, retrouver la formule

$$\sum _{k=1}^n{k}^2=\frac{n(n+1)(2n+1)}{6}\mathrm{.}$$

Soit $n$ un entier naturel. On dit qu'une partie $A$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ est écartée lorsqu'elle ne contient jamais deux entiers consécutifs, c'est-à-dire lorsque

$$\mathrm{\forall }x\in A,x+1\mathrm{\notin }A\mathrm{.}$$

L'ensemble vide et les singletons sont écartés. On note $u_n$ le nombre de parties écartées de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$, avec la convention $[\text{\hspace{0.17em}⁣}[1,0]\text{\hspace{0.17em}⁣}]=\mathrm{\varnothing }$, et l'on adopte la convention $\left(\genfrac{}{}{0px}{}{q}{r}\right)=0$ dès que $r>q$.

1. Écrire la liste des parties écartées de $[\text{\hspace{0.17em}⁣}[1,4]\text{\hspace{0.17em}⁣}]$ et en déduire $u_4$. Combien d'entre elles ont exactement deux éléments ?

2. Comptage à nombre d'éléments fixé. Soient $n⩾1$ et $p⩾1$. On considère une partie écartée $A=\{x_1,x_2,\dots ,x_p\}$ de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ à $p$ éléments, écrite dans l'ordre croissant $x_1<x_2<\cdots <x_p$, et l'on pose

$$y_i=x_i-(i-1)\text{pour }i\in [\text{\hspace{0.17em}⁣}[1,p]\text{\hspace{0.17em}⁣}]\mathrm{.}$$

a. Montrer que $y_1<y_2<\cdots <y_p$ et que $\{y_1,\dots ,y_p\}$ est une partie de $[\text{\hspace{0.17em}⁣}[1,n-p+1]\text{\hspace{0.17em}⁣}]$ à $p$ éléments.

b. Décrire le procédé qui, à partir d'une partie quelconque à $p$ éléments de $[\text{\hspace{0.17em}⁣}[1,n-p+1]\text{\hspace{0.17em}⁣}]$, reconstruit une partie écartée de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ à $p$ éléments, et vérifier que les deux procédés se défont l'un l'autre.

c. En déduire que le nombre de parties écartées de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ à $p$ éléments vaut $\left(\genfrac{}{}{0px}{}{n-p+1}{p}\right)$. Pour quelles valeurs de $p$ ce nombre est-il non nul ?

d. Application : combien y a-t-il de parties écartées de $[\text{\hspace{0.17em}⁣}[1,10]\text{\hspace{0.17em}⁣}]$ à $4$ éléments ?

3. Comptage global par récurrence. Soit $n⩾2$. En séparant les parties écartées de $[\text{\hspace{0.17em}⁣}[1,n]\text{\hspace{0.17em}⁣}]$ selon qu'elles contiennent ou non l'entier $n$, démontrer que

$$u_n=u_{n-1}+u_{n-2}\mathrm{.}$$

Préciser $u_0$ et $u_1$, puis dresser la liste des valeurs de $u_0$ à $u_{10}$.

4. Vérifier, pour $n=10$, l'identité ${\displaystyle \sum _{p=0}^n\left(\genfrac{}{}{0px}{}{n-p+1}{p}\right)=u_n}$ en détaillant les termes. (Seuls les premiers sont non nuls, d'après la question 2.c.)

5. Application. Un professeur dispose de dix journées consécutives, numérotées de $1$ à $10$, pour placer des séances de soutien, sans jamais programmer deux séances deux jours de suite. Combien de plannings comportant exactement quatre séances peut-il constituer ? Et combien de plannings comportant au moins une séance ?