Exo 9
Commencez par chercher à résoudre l'exercice par vous-même.
Si vous manquez d'idée pour débuter, consultez l'indice fourni et recommencez à chercher.
Une solution détaillée vous est ensuite proposée.
Soient
et
deux ensembles finis non vides tels que
et
.
On note
le nombre de surjections de
dans
et l'on pose
.
Question
Calculer
lorsque
et lorsque
.
Si
est une application de
dans
, alors
, donc
.
Or
est une surjection de
dans
si
, ce qui n'est pas possible si
.
Conclusion : Si
, alors
.
Si
, toute surjection de
dans
est une bijection et réciproquement. En effet, pour que
, il faut que les
éléments de
aient des images distinctes, donc que l'application soit injective.
Conclusion :
.
Question
Calculer
et
.
Pour calculer
, utilisez le complémentaire.
Si
,
n'a qu'un seul élément
, donc il n'y a qu'une seule application de
dans
: tous les éléments de
ont pour image
. Et elle est surjective.
Conclusion :
.
Si
,
a deux éléments
et
. Il y a
applications de
dans
.
Une application
n'est pas surjective de
dans
si et seulement si
ou
. Il n'y a donc que
applications non surjectives.
Conclusion :
.
Question
Démontrer que :
.
Définissez une partition de l'ensemble des applications
de
dans
suivant le cardinal de
.
Si
est une application de
dans
, alors
, donc
est une partie à
éléments de
où
.
Soit
l'ensemble de toutes les applications de
dans
telles que
où
.
Cette famille d'ensembles constitue une partition de l'ensemble
de toutes les applications de
dans
.
Donc :
.
Toute application
est une surjection de
dans
. Donc pour toute partie
à
éléments de
, il existe
applications de
dans
telles que
. Et il y a
parties
possibles.
Donc
.
Donc :
. De plus,
.
Conclusion :
.
Question
Démontrer que :
si
.
Définissez une partition de l'ensemble des surjections d'un ensemble
à
éléments dans un ensemble
à
éléments.
Si
est une surjection de
dans
, tout élément
de
a un antécédent, mais il y a deux cas : soit cet antécédent est unique, soit
possède plusieurs antécédents.
Soit
un ensemble à
éléments et
un ensemble à
éléments.
Si
est une surjection de
dans
, tout élément de
possède un antécédent (unique ou pas).
Pour tout élément
de
, on peut définir :
l'ensemble
des surjections
de
dans
telles que
ait un unique antécédent
. La restriction de
à
est alors une surjection de
dans
. Donc :
.l'ensemble
des surjections
de
dans
telles que
ait plusieurs antécédents. Soit
l'un de ses antécédents.La restriction de
à
est alors une surjection de
dans
. Donc :
.
Donc, pour tout élément
de
, on obtient
surjections.
Conclusion :
si
.
Question
Démontrer que :
.
Définissez l'ensemble
des applications telles que le
éme élément de
n'ait pas d'antécédent et utilisez la formule du crible.
Soient
, ...,
les
éléments de
et soit
l'ensemble des applications telles que
n'ait pas d'antécédent dans
.
Une application est surjective de
dans
si tout élément de
possède un antécédent dans
.
Donc l'ensemble
de toutes les surjections de
dans
est :
.
Donc :
.
Or, d'après la formule du crible :
.
est l'ensemble des applications de
dans
telles que
, ...,
n'aient pas d'antécédents, donc des applications de
dans
. Donc :
.
Donc :
.
Le nombre de manières de choisir
dans
est égal au nombre de manières de choisir simultanément
nombres parmi
car il y aura une seule manière de les ordonner.
Donc :
.
On transforme la somme en posant
:
. Or
.
Conclusion :
.
