Nombre d'applications d'un ensemble fini

totem

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 pⁿ et non pas n^p ?

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 3⁴ et non pas 4³...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 ! :-)

Math Coss

Tu as $4$ choix pour l'image de $a$, $4$ choix pour l'image de $b$, $4$ choix pour l'image de $c$. Chacun de ces choix est indépendant, le nombre de choix total est le produit, ça en fait $4^3$.

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$.

totem

Ah oui zut ! Désolé.
C'et le même raisonnement pour montrer que le nombres d'applications injectives est un arrangement (A₃² en l'occurrence ) ?

Math Coss

Avec $3$ éléments au départ et $4$ à l'arrivée, le nombre d'injections est plutôt $\mathsf{A}_4^3=4\times3\times2$, non ?

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.

totem

OK j'ai compris merci Math Coss.

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 ?

Math Coss

On peut mais c'est plus cher.

Shah d'Ock

Trois applications cutanées devraient suffire. Si le bobo persiste, il faudra envisager une injection.