Soit $n\in\mathbb N^*$, $E=\llbracket1,n\rrbracket$ et $F=\{a,b,c\}$ un ensemble à trois éléments.
- Démontrer, à partir de la formule $|A\cup B|=|A|+|B|-|A\cap B|$, que pour trois ensembles finis $A$, $B$, $C$ : $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.$$
- Pour $t\in F$, on note $N_t$ l'ensemble des applications de $E$ dans $F$ qui ne prennent pas la valeur $t$. Calculer $\operatorname{Card}N_a$, $\operatorname{Card}(N_a\cap N_b)$ et $\operatorname{Card}(N_a\cap N_b\cap N_c)$.
- En déduire le nombre $s_n$ de surjections de $E$ sur $F$.
- Calculer $s_3$, $s_4$ et $s_5$. Interpréter la valeur de $s_3$ et vérifier que $s_1=s_2=0$.
Appliquer la formule à $A\cup B$ et $C$, puis utiliser $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$.
$N_a$ s'identifie à l'ensemble des applications de $E$ dans $\{b,c\}$.
Une application n'est pas surjective lorsqu'au moins une valeur de $F$ n'est pas atteinte.
-
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.
-
$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.
-
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.$$
-
$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$.
$s_n=3^n-3\cdot2^n+3$ ; $s_3=6$, $s_4=36$, $s_5=150$