Dénombrement d'applications
Fondamental :
Le nombre d'applications d'un ensemble à
éléments dans un ensemble à
éléments est :
.
Exemple :
Ranger
objets dans
tiroirs revient à définir une application qui à chaque objet associe le tiroir où on le range.
Le nombre de manières de ranger
objets dans
tiroirs est donc
.
Fondamental :
Le nombre d'applications injectives d'un ensemble à
éléments dans un ensemble à
éléments est :
si
et
sinon.
Exemple :
Garer
voitures dans
places de parking revient à définir une application qui à chaque voiture associe la place où on la gare. Mais cette application est injective car on ne peut pas garer deux voitures dans la même place de parking.
Le nombre de manières de garer
voitures dans
places de parking est donc
.
Fondamental :
Le nombre d'applications bijectives d'un ensemble à
éléments dans un ensemble à
éléments est :
si
et
sinon.
Une permutation de
est une bijection de
dans
. Si
, le nombre de permutations de
est
.
C'est aussi le nombre de manières d'ordonner
objets.
Exemple :
Placer
invités autour d'une table comportant
places revient à définir une application qui à chaque invité associe la place qu'on lui attribue. Cette application est injective puisque l'on ne peut pas mettre deux invités à la même place, et surjective puisque toutes les places seront occupées.
Le nombre de manières de placer
invités autour de la table est donc
.
