Exercices corrigés : Dénombrement (Prépa, 1re année)

1. Pour $a\le b$, $\operatorname{Card}\llbracket a,b\rrbracket=b-a+1$. Ici $215-37+1=179$.

2. L'application $k\mapsto 4k$ est une bijection de $\llbracket 1,250\rrbracket$ sur $A$, car $1\le 4k\le 1000\iff 1\le k\le 250$. Donc $\operatorname{Card}A=250$.

De même, $1\le 6k\le 1000\iff 1\le k\le 166$, puisque $6\times166=996\le1000<1002=6\times167$. Donc $\operatorname{Card}B=166$.

Un entier est multiple de $4$ et de $6$ si et seulement s'il est multiple de $\operatorname{ppcm}(4,6)=12$. Comme $12\times83=996\le1000<1008=12\times84$, on obtient $\operatorname{Card}(A\cap B)=83$.

3. Par la formule de la réunion : $$\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B)=250+166-83=333.$$ Les entiers divisibles ni par $4$ ni par $6$ forment $E\setminus(A\cup B)$, de cardinal $1000-333=667$.

1. Le nombre d'applications de $E$ dans $F$ est $(\operatorname{Card}F)^{\operatorname{Card}E}=6^4=1296$. Dans l'autre sens : $4^6=4096$.

2. En numérotant $E=\{x_1,x_2,x_3,x_4\}$, l'application $f\mapsto(f(x_1),\dots,f(x_4))$ envoie les injections exactement sur les $4$-listes d'éléments distincts de $F$ : il y en a $6\times5\times4\times3=\frac{6!}{2!}=360$. Les applications non injectives forment le complémentaire des injections dans $F^E$ : $1296-360=936$.

3. Comme $\operatorname{Card}F=6>4=\operatorname{Card}E$, aucune application de $F$ dans $E$ n'est injective (principe des tiroirs). Si $f:E\to F$ était surjective, on aurait $\operatorname{Card}F\le\operatorname{Card}E$, soit $6\le4$, ce qui est faux : il n'existe aucune surjection de $E$ sur $F$.

4. Les bijections de $E$ sur $E$ sont au nombre de $4!=24$. $F$ possède $2^6=64$ parties, dont $\binom{6}{4}=\binom{6}{2}=15$ à $4$ éléments.

1. Une anagramme est déterminée par l'ensemble des positions des A (partie à $3$ éléments de $\llbracket1,7\rrbracket$), puis par l'ensemble des positions des B parmi les $4$ positions restantes ; les R occupent les $2$ dernières. Le nombre de choix pour les B ne dépend pas des positions des A, d'où $$\binom{7}{3}\binom{4}{2}=35\times6=210.$$ Contrôle par le lemme des bergers : $\frac{7!}{3!\,2!\,2!}=\frac{5040}{24}=210$.

2. Si les trois A sont consécutifs, ils occupent les positions $i,i+1,i+2$ pour un unique $i\in\llbracket1,5\rrbracket$. En remplaçant ce bloc par un symbole $\square$, on obtient une bijection vers les mots de $5$ symboles formés de $\square$, de deux B et de deux R (l'opération inverse remplace $\square$ par AAA). Ces mots sont déterminés par la position de $\square$ ($5$ choix) puis par celles des B parmi les $4$ restantes ($\binom42=6$ choix) : il y en a $5\times6=30$.

3. On écrit d'abord le mot formé des $4$ lettres autres que A (deux B, deux R) : $\binom42=6$ possibilités. Ce mot délimite $5$ emplacements : avant la première lettre, entre deux lettres consécutives ($3$ emplacements), après la dernière. Une anagramme sans deux A adjacents s'obtient en mettant les trois A dans $3$ emplacements distincts, un A par emplacement. Réciproquement, une telle anagramme détermine le mot en B et R (on efface les A) et les $3$ emplacements utilisés, puisque deux A ne sont jamais voisins. C'est une bijection, d'où $6\times\binom53=6\times10=60$ anagrammes.

1. Un chemin de $(0,0)$ à $(a,b)$ compte $a+b$ pas dont $a$ vers la droite ; il est déterminé par l'ensemble des rangs des pas vers la droite, partie à $a$ éléments de $\llbracket1,a+b\rrbracket$. Il y a donc $\binom{a+b}{a}$ tels chemins, et ce nombre ne dépend que du déplacement $(a,b)$, pas du point de départ. De $O$ à $M$ : $\binom{10}{6}=\binom{10}{4}=210$.

2. Un chemin passant par $P$ se coupe de façon unique en un chemin de $O$ à $P$ suivi d'un chemin de $P$ à $M$, et tout tel couple donne un chemin passant par $P$ : c'est une bijection avec un produit cartésien. De $O$ à $P$ : $\binom42=6$ ; de $P$ à $M$ (déplacement $(4,2)$) : $\binom64=15$. Il y a donc $6\times15=90$ chemins par $P$.

De même, de $O$ à $Q$ : $\binom74=35$ ; de $Q$ à $M$ (déplacement $(2,1)$) : $\binom32=3$. Il y a $35\times3=105$ chemins par $Q$.

Les coordonnées croissent le long d'un chemin et $P$ a des coordonnées inférieures à celles de $Q$ : un chemin passant par $P$ et $Q$ passe d'abord par $P$. Il se découpe en trois morceaux : $O\to P$ ($6$), $P\to Q$ (déplacement $(2,1)$, $3$ chemins), $Q\to M$ ($3$). Il y en a $6\times3\times3=54$.

3. En notant $\mathcal C_P$ et $\mathcal C_Q$ les ensembles de chemins passant par $P$ et par $Q$ : $$\operatorname{Card}(\mathcal C_P\cup\mathcal C_Q)=90+105-54=141.$$ Les chemins ne passant ni par $P$ ni par $Q$ sont au nombre de $210-141=69$.

1. Premier comptage : on choisit d'abord $A\in\mathcal P_k(E)$ ($\binom nk$ choix), puis $B\in\mathcal P_j(A)$ ($\binom kj$ choix, puisque $\operatorname{Card}A=k$). Le nombre de choix de $B$ ne dépend pas de $A$, donc $\operatorname{Card}X=\binom nk\binom kj$.

Second comptage : on choisit d'abord $B\in\mathcal P_j(E)$ ($\binom nj$ choix). Une partie $A$ à $k$ éléments contenant $B$ s'écrit de façon unique $A=B\cup C$ avec $C=A\setminus B\in\mathcal P_{k-j}(E\setminus B)$. Réciproquement, toute telle partie $C$ fournit une partie $A=B\cup C$ convenable (réunion disjointe de cardinal $j+(k-j)=k$). Comme $\operatorname{Card}(E\setminus B)=n-j$, il y a $\binom{n-j}{k-j}$ choix de $C$. Donc $\operatorname{Card}X=\binom nj\binom{n-j}{k-j}$.

Les deux expressions valent $\operatorname{Card}X$ : elles sont égales.

2. On a $$\binom nk\binom kj=\frac{n!}{k!\,(n-k)!}\cdot\frac{k!}{j!\,(k-j)!}=\frac{n!}{j!\,(k-j)!\,(n-k)!}$$ et, comme $(n-j)-(k-j)=n-k$, $$\binom nj\binom{n-j}{k-j}=\frac{n!}{j!\,(n-j)!}\cdot\frac{(n-j)!}{(k-j)!\,(n-k)!}=\frac{n!}{j!\,(k-j)!\,(n-k)!}.$$

3. On somme l'égalité de la question 1 pour $k\in\llbracket j,n\rrbracket$, puis on pose $i=k-j$ : $$\sum_{k=j}^n\binom nk\binom kj=\binom nj\sum_{k=j}^n\binom{n-j}{k-j}=\binom nj\sum_{i=0}^{n-j}\binom{n-j}{i}=\binom nj2^{n-j},$$ en utilisant $\sum_{i=0}^m\binom mi=2^m$.

Interprétation : on compte les couples $(B,A)$ avec $B\subset A\subset E$ et $\operatorname{Card}B=j$, sans contrainte sur le cardinal de $A$ ; une fois $B$ choisi, $A\setminus B$ est une partie quelconque de $E\setminus B$.

4. Pour $n=4$, $j=2$ : $\binom42\binom22+\binom43\binom32+\binom44\binom42=6+12+6=24$, et $\binom42\times2^2=24$.

1. On applique la formule à $A\cup B$ et $C$ : $$|A\cup B\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|.$$ Par distributivité, $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$, et $(A\cap C)\cap(B\cap C)=A\cap B\cap C$, donc $$|(A\cup B)\cap C|=|A\cap C|+|B\cap C|-|A\cap B\cap C|.$$ En remplaçant aussi $|A\cup B|=|A|+|B|-|A\cap B|$, on obtient la formule annoncée.

2. $N_a$ est l'ensemble des applications de $E$ dans $\{b,c\}$ : $\operatorname{Card}N_a=2^n$. L'ensemble $N_a\cap N_b$ est celui des applications de $E$ dans $\{c\}$, réduit à l'application constante égale à $c$ : il a $1$ élément. Une application de $N_a\cap N_b\cap N_c$ ne prendrait aucune valeur, ce qui est impossible car $E\ne\varnothing$ : cet ensemble est vide. Par symétrie des rôles, chacun des trois $N_t$ a $2^n$ éléments et chacune des trois intersections deux à deux a $1$ élément.

3. Une application $f:E\to F$ n'est pas surjective si et seulement s'il existe $t\in F$ non atteint, c'est-à-dire si et seulement si $f\in N_a\cup N_b\cup N_c$. Par la question 1 : $$\operatorname{Card}(N_a\cup N_b\cup N_c)=3\times2^n-3\times1+0=3\cdot2^n-3.$$ Par passage au complémentaire dans $F^E$, qui a $3^n$ éléments : $$s_n=3^n-3\cdot2^n+3.$$

4. $s_3=27-24+3=6$, $s_4=81-48+3=36$, $s_5=243-96+3=150$.

Pour $n=3$, $E$ et $F$ sont finis de même cardinal : les surjections sont exactement les bijections, au nombre de $3!=6$, ce qui est cohérent. Enfin $s_1=3-6+3=0$ et $s_2=9-12+3=0$, conformément au fait qu'une surjection de $E$ sur $F$ impose $\operatorname{Card}F\le\operatorname{Card}E$.

1. Notons $\mathcal S$ l'ensemble des applications strictement croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ et $\Psi:\mathcal S\to\mathcal P_p(\llbracket1,n\rrbracket)$, $f\mapsto f(\llbracket1,p\rrbracket)$. Une application strictement croissante est injective, donc son image a $p$ éléments : $\Psi$ est bien définie.

• Surjectivité : si $A=\{a_1<\dots<a_p\}$, l'application $i\mapsto a_i$ est strictement croissante d'image $A$.
• Injectivité : si $f\in\mathcal S$ a pour image $A=\{a_1<\dots<a_p\}$, les nombres $f(1)<\dots<f(p)$ sont les éléments de $A$ rangés dans l'ordre croissant, donc $f(i)=a_i$ pour tout $i$ : $f$ est déterminée par son image. Donc $\operatorname{Card}\mathcal S=\binom np$ (ce nombre est nul si $p>n$).

2. Soit $f$ croissante de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ et $g(i)=f(i)+i-1$. Pour $1\le i<p$, $g(i+1)-g(i)=f(i+1)-f(i)+1\ge1$ : $g$ est strictement croissante. De plus $g(1)=f(1)\ge1$ et $g(p)=f(p)+p-1\le n+p-1$ ; par croissance, $g$ est à valeurs dans $\llbracket1,n+p-1\rrbracket$.

Réciproquement, soit $g$ strictement croissante de $\llbracket1,p\rrbracket$ dans $\llbracket1,n+p-1\rrbracket$ et $f(i)=g(i)-i+1$. Les valeurs de $g$ étant entières, $g(i+1)\ge g(i)+1$, d'où $f(i+1)-f(i)=g(i+1)-g(i)-1\ge0$ : $f$ est croissante. De plus $f(1)=g(1)\ge1$ et $f(p)=g(p)-p+1\le n$, donc, par croissance, $f$ est à valeurs dans $\llbracket1,n\rrbracket$.

Les applications $f\mapsto g$ et $g\mapsto f$ sont réciproques l'une de l'autre : c'est une bijection.

3. Par invariance du cardinal par bijection et par la question 1 appliquée avec $n+p-1$ à la place de $n$, le nombre d'applications croissantes de $\llbracket1,p\rrbracket$ dans $\llbracket1,n\rrbracket$ vaut $\binom{n+p-1}{p}$.

Contrôle pour $n=p=2$ : les applications croissantes sont $(1,1)$, $(1,2)$, $(2,2)$ (en notant $(f(1),f(2))$), soit $3=\binom32$.

4. Un résultat se code de façon unique par ses trois valeurs rangées dans l'ordre croissant, $f(1)\le f(2)\le f(3)$ : c'est une application croissante de $\llbracket1,3\rrbracket$ dans $\llbracket1,6\rrbracket$, et réciproquement toute telle application code un résultat. Il y a donc $\binom{6+3-1}{3}=\binom83=56$ résultats. Ceux à trois valeurs distinctes correspondent aux applications strictement croissantes : $\binom63=20$.

1. $\operatorname{Card}\big(\mathcal P(E)^2\big)=(2^n)^2=4^n$.

2. Soit $(A,B)\in\mathcal I$ et $x\in E$. Comme $A\subset B$ : si $x\in A$, $\varphi_{A,B}(x)=2$ ; si $x\in B\setminus A$, $\varphi_{A,B}(x)=1$ ; si $x\notin B$, $\varphi_{A,B}(x)=0$. Donc $\varphi_{A,B}\in\{0,1,2\}^E$ et $$A=\varphi_{A,B}^{-1}(\{2\}),\qquad B=\varphi_{A,B}^{-1}(\{1,2\}).$$ Injectivité : ces formules montrent que $(A,B)$ est déterminé par $\varphi_{A,B}$.

Surjectivité : pour $h\in\{0,1,2\}^E$, on pose $A=h^{-1}(\{2\})$ et $B=h^{-1}(\{1,2\})$. Alors $A\subset B$, et pour tout $x$, $\mathbf 1_A(x)+\mathbf 1_B(x)$ vaut $2$ si $h(x)=2$, $1$ si $h(x)=1$, $0$ si $h(x)=0$ : c'est $h(x)$. Donc $\varphi_{A,B}=h$.

Ainsi $\operatorname{Card}\mathcal I=\operatorname{Card}\{0,1,2\}^E=3^n$.

3. On découpe $\mathcal I$ selon $k=\operatorname{Card}B\in\llbracket0,n\rrbracket$ (cas disjoints et exhaustifs). Il y a $\binom nk$ parties $B$ à $k$ éléments, et pour chacune, $A$ est une partie quelconque de $B$ : $2^k$ choix. D'où $$\operatorname{Card}\mathcal I=\sum_{k=0}^n\binom nk2^k.$$ La formule du binôme donne $\sum_{k=0}^n\binom nk2^k1^{n-k}=(2+1)^n=3^n$ : les deux comptages concordent.

4. Pour $A,B\subset E$ : $A\cap B=\varnothing\iff A\subset E\setminus B$. L'application $(A,B)\mapsto(A,E\setminus B)$ est une bijection de $\mathcal P(E)^2$ sur lui-même (elle est sa propre réciproque), qui envoie l'ensemble des couples de parties disjointes exactement sur $\mathcal I$. Il y a donc $3^n$ couples $(A,B)$ avec $A\cap B=\varnothing$.

De même, $A\cup B=E\iff(E\setminus A)\cap(E\setminus B)=\varnothing$, et $(A,B)\mapsto(E\setminus A,E\setminus B)$ est une bijection involutive de $\mathcal P(E)^2$ qui envoie les couples vérifiant $A\cup B=E$ exactement sur les couples de parties disjointes : il y en a $3^n$.

5. On intervertit les sommes finies : $$S=\sum_{(A,B)}\sum_{x\in E}\mathbf 1_A(x)\mathbf 1_B(x)=\sum_{x\in E}\operatorname{Card}\{(A,B)\in\mathcal P(E)^2\mid x\in A\text{ et }x\in B\}.$$ Pour $x$ fixé, une partie contenant $x$ s'écrit de façon unique $\{x\}\cup A'$ avec $A'\subset E\setminus\{x\}$ : il y en a $2^{n-1}$. Le nombre de couples $(A,B)$ avec $x\in A\cap B$ vaut donc $2^{n-1}\times2^{n-1}=4^{n-1}$, et $S=n4^{n-1}$.

6. Avec $\operatorname{Card}(A\cup B)=\operatorname{Card}A+\operatorname{Card}B-\operatorname{Card}(A\cap B)$ : $$T=\sum_{(A,B)}\operatorname{Card}A+\sum_{(A,B)}\operatorname{Card}B-S.$$ Or, $B$ décrivant librement $\mathcal P(E)$, $\sum_{(A,B)}\operatorname{Card}A=2^n\sum_{A\subset E}\operatorname{Card}A=2^n\sum_{k=0}^nk\binom nk=2^n\cdot n2^{n-1}=2n4^{n-1}$ ; de même pour la somme des $\operatorname{Card}B$. Donc $$T=2n4^{n-1}+2n4^{n-1}-n4^{n-1}=3n4^{n-1}.$$ Pour $n=1$, $E=\{x\}$, les $4$ couples sont $(\varnothing,\varnothing)$, $(\varnothing,E)$, $(E,\varnothing)$, $(E,E)$. Les cardinaux des intersections valent $0,0,0,1$ : $S=1=1\times4^0$. Ceux des réunions valent $0,1,1,1$ : $T=3=3\times1\times4^0$.

1. $\llbracket1,0\rrbracket=\varnothing$ n'a que la partie $\varnothing$, qui est creuse : $u_0=1$. Pour $n=1$ : $\varnothing$ et $\{1\}$, donc $u_1=2$. Pour $n=2$ : $\varnothing$, $\{1\}$, $\{2\}$ (la partie $\{1,2\}$ est exclue), donc $u_2=3$. Pour $n=3$ : $\varnothing$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,3\}$, donc $u_3=5$.

2. Soit $n\in\mathbb N$ et $\mathcal C_m$ l'ensemble des parties creuses de $\llbracket1,m\rrbracket$. On partage $\mathcal C_{n+2}$ en deux parties disjointes.

• Les parties creuses ne contenant pas $n+2$ sont exactement les parties creuses de $\llbracket1,n+1\rrbracket$ : il y en a $u_{n+1}$.
• Si $A\in\mathcal C_{n+2}$ contient $n+2$, elle ne contient pas $n+1$, donc $A\setminus\{n+2\}$ est une partie creuse de $\llbracket1,n\rrbracket$. Réciproquement, si $B\in\mathcal C_n$, alors $B\cup\{n+2\}$ est creuse, car les éléments de $B$ sont au plus égaux à $n$, donc aucun ne vaut $n+1$. Les applications $A\mapsto A\setminus\{n+2\}$ et $B\mapsto B\cup\{n+2\}$ sont réciproques l'une de l'autre : il y a $u_n$ telles parties.

Le principe additif donne $u_{n+2}=u_{n+1}+u_n$.

3. On montre par récurrence double que $u_n=F_{n+2}$. Initialisation : $F_2=1=u_0$ et $F_3=2=u_1$. Hérédité : si $u_n=F_{n+2}$ et $u_{n+1}=F_{n+3}$, alors $u_{n+2}=F_{n+3}+F_{n+2}=F_{n+4}$.

Les termes $F_0,\dots,F_{12}$ sont $0,1,1,2,3,5,8,13,21,34,55,89,144$, d'où $u_{10}=F_{12}=144$.

4. Une partie $A=\{a_1<\dots<a_k\}$ de $\llbracket1,n\rrbracket$ est creuse si et seulement si $a_{i+1}-a_i\ge2$ pour $1\le i<k$. Posons $b_i=a_i-(i-1)$.

• On a $b_{i+1}-b_i=a_{i+1}-a_i-1\ge1$, donc $b_1<\dots<b_k$ et $\psi(A)$ a $k$ éléments. De plus $b_1=a_1\ge1$ et $b_k=a_k-k+1\le n-k+1$. Ainsi $\psi(A)\in\mathcal P_k(\llbracket1,n-k+1\rrbracket)$.
• Réciproquement, si $B=\{b_1<\dots<b_k\}\subset\llbracket1,n-k+1\rrbracket$, on pose $a_i=b_i+i-1$. Alors $a_{i+1}-a_i=b_{i+1}-b_i+1\ge2$, $a_1=b_1\ge1$ et $a_k=b_k+k-1\le n$ : $\{a_1<\dots<a_k\}$ est une partie creuse à $k$ éléments de $\llbracket1,n\rrbracket$, et son image par $\psi$ est $B$.

Les deux constructions sont réciproques l'une de l'autre : $\psi$ est une bijection et $c_{n,k}=\binom{n-k+1}{k}$ (ce nombre est nul si $k>n-k+1$). Pour $k=0$, seule $\varnothing$ convient : $c_{n,0}=1=\binom{n+1}{0}$.

5. Les parties creuses de $\llbracket1,n\rrbracket$ se répartissent selon leur cardinal $k\in\llbracket0,n\rrbracket$ (cas disjoints et exhaustifs), d'où $$F_{n+2}=u_n=\sum_{k=0}^nc_{n,k}=\sum_{k=0}^n\binom{n-k+1}{k}.$$ Contrôle pour $n=4$ : $\binom50+\binom41+\binom32+\binom23+\binom14=1+4+3+0+0=8=F_6$.

6. En numérotant les jours de $1$ à $10$, un choix convenable est une partie creuse à $3$ éléments de $\llbracket1,10\rrbracket$ : il y en a $c_{10,3}=\binom{8}{3}=56$.