Nombre d'applications d'un ensemble fini
Bonjour,
soit E un ensemble fini de cardinal n et F un ensemble fini de cardinal p.
Pourquoi le nombre d'applications de E dans F est-il pn et non pas np ?
Si je considère E = {a;b;c} et F= {1;2;3;4} intuitivement je dirais que le nombre d'applications de E dans F est 34 et non pas 43...d'où vient mon erreur ? C'est un problème de dénombrement ?
Merci.
PS: par contre j'ai compris pourquoi le nombre de bijections de E dans E est n ! :-)
soit E un ensemble fini de cardinal n et F un ensemble fini de cardinal p.
Pourquoi le nombre d'applications de E dans F est-il pn et non pas np ?
Si je considère E = {a;b;c} et F= {1;2;3;4} intuitivement je dirais que le nombre d'applications de E dans F est 34 et non pas 43...d'où vient mon erreur ? C'est un problème de dénombrement ?
Merci.
PS: par contre j'ai compris pourquoi le nombre de bijections de E dans E est n ! :-)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si le cardinal de $E$ vaut $1$ et que le cardinal de $F$ vaut $p$, veux-tu que le nombre d'applications soit $1^p$ ? Ce serait bien étrange, non ? Il y en a visiblement $p=p^1$.
C'et le même raisonnement pour montrer que le nombres d'applications injectives est un arrangement (A32 en l'occurrence ) ?
Cela dit, oui, c'est le même raisonnement : $4$ choix pour l'image de $a$, il en reste $3$ pour l'image de $b$ et $2$ pour l'image de $c$. Note que dans les deux cas, pour pouvoir dire qu'on a une preuve, il faudrait justifier que c'est bien un produit qu'il faut faire.
Voici un argument un zeste plus formel que « les choix sont indépendants ». On peut faire un arbre (on a $4$ branches qui partent de la racine, correspondant aux choix de l'image de $a$ ; puis on a $3$ ou $4$ branches qui partent de chacune des branches de premier niveau, une pour chaque image de $b$ ($3$ ou $4$ selon qu'on exige une fonction injective ou pas), etc. Le produit se justifie par le fait que le nombre de sous-arbres attachés à l'image de $a$ ne dépend pas de cette image. Pour un argument formel, il faudrait faire une récurrence et sans doute invoquer le lemme des bergers.
Evidemment on ne peut pas établir le nombre d'injections de F vers E :-)
Je ne connais pas le théorème des bergers, je vais regarder.
Et peut-on établir le nombre de surjections de E vers F ?