Nombre de fonctions

Endomorphisme
Endomorphisme
Modifié (December 2021) dans Combinatoire et Graphes
Soient E et F deux ensembles finis de cardinaux respectifs n et p (n et p étant des entiers naturels).
$-$ Le nombre de relations de E vers F est égal à $2^{np}$.
$-$ Le nombre d'applications de E vers F est égal à $p^{n}$.
$-$ Mais quel est le nombre de fonctions de E vers F ? 
Bien sûr, je distingue la notion de fonction à celle d'application pour cette question.

Réponses

  • Maxtimax
    Maxtimax
    Quelle est la distinction que tu fais ? (le nombre de distinctions est à peu près égal au nombre de personnes la faisant)
  • Endomorphisme
    Endomorphisme
    Modifié (December 2021)
    De manière formelle, f étant une relation de E vers F, une fonction de E vers F est définie ainsi : pour tout triplet (x,y,y') de E x F x F, ( x f y) et (x f y') implique y = y'.
    Pour une application, f étant une fonction de E vers F : pour tout x de E, il existe y dans F tel que x f y (ou y = f(x) par unicité de l'image).

  • JLapin
    JLapin
    Endomorphisme a dit :
    Soient E et F deux ensembles finis de cardinaux respectifs n et p (n et p étant des entiers naturels).
    Bien sûr, je distingue la notion de fonction à celle d'application pour cette question.

    Pour chaque élément de E, tu peux choisir de l'envoyer sur un élément de F ou de ne pas lui attribuer d'image...
  • i.zitoussi
    i.zitoussi
    En comptant les sous-ensembles de $E$ à $i$ éléments ($0\leq i\leq n$), puis le nombre de fonctions définies sur exactement $i$ éléments, et en sommant tout ça, on arrive au même résultat que JLapin, mais c'est plus long...

    Après je bloque.
  • Endomorphisme
    Endomorphisme
    Ca doit être vraiment tout bête mais je ne vois pas comment dénombrer tout ça.
    Pour un élément de l'ensemble de départ, il y a deux possibilités. 
    Soit on lui attribue une image : p possibilités.
    Soit on ne lui attribue pas d'image.
  • zeitnot
    zeitnot
    Je ne suis pas sûr, mais tu as tout dit non ?
    Pour un élément de l'ensemble de départ, tu as donc $p+1$ possibilités. Il y a $n$ éléments, donc ...
    Karl Tremblay 1976-2023, je t'appréciais tellement.
  • Endomorphisme
    Endomorphisme
    $(p+1)^{n}$

    Oui zeitnot  ;)
  • Poirot
    Poirot
    A noter que l'on obtient le même résultat avec un autre argument faisant naturellement apparaître la somme $\sum_{k=0}^n \binom{n}{k} p^k$.
  • zeitnot
    zeitnot
    On compte les fonctions dont aucun élément n'a d'image, puis les fonctions dont 1 seul élément a une image, ....... et on finit par compter les applications.
    Karl Tremblay 1976-2023, je t'appréciais tellement.
  • Foys
    Foys
    Modifié (December 2021)
    Etant donnés $E,F$ des ensembles et $error$ un objet n'appartenant pas à $F$, il y a une bijection évidente entre l'ensemble des applications partielles ("fonctions") de $E$ dans $F$ et l'ensemble des applications de $E$ dans $F \cup \{error\}$.

    NB : étant donné un ensemble $x$, il existe toujours un ensemble n'appartenant pas à $x$, par exemple $\{y \in x \mid y \notin y\}$.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 37

CidrolinGeorges AbitbolJLTgai requinstfjzeste +31 Invités