Répondre à la discussion
Affichage des résultats 1 à 19 sur 19

Nombre de surjections



  1. #1
    Aylward

    Nombre de surjections

    Bonjour à tous !

    Voila j'ai un problème d'ensemble et j'ai DU mal à le résoudre :

    Nous avons 2 ensembles E et F ayant chacun respectivement n et p elts. p>n

    et il faut calculer le nombre d'applications surjectives de E sur F.

    J'ai dit que :

    Il y a plus elt a l'arrivé qu'au départ ( p>n ) : il a forcement 2 elts de E qui auront 2 imgs ce qui est impossible. Il n'y a donc aucune applications surjective dans le cas où p>n. Je pense que c'est bon.

    Mais apres, on nous demande de calculer le nombre de surjections de E ( p+1 elts ) et F ( p elts ). On nous donne une aide : on peut utiliser l'elts "r" de F qui a 2 antécédants apres avoir justifier son existence.

    Et je bloque à ce niveau.

    Merci d'avance pour votre aide !!

    -----


  2. Publicité
  3. #2
    Aylward

    Re : Nombre de surjections

    En fait j'ai trouvé la solution,

    mais je suis bloqué à la question d'après :


    Il faut démontrer que :

    Quelque soit k € {0,...,p-1},

    Sigma de [ q=k à p ] [ (-1)^q * ( q parmi p ) * (k parmi q ) ] = 0


    merci d'avance

    Aylward

  4. #3
    Aylward

    Re : Nombre de surjections

    je pense qu'en séparant la somme en 2 on peut arriver à qqch mais j'ai du mal :


    si on met d'un côté les q pairs le (-1)^q = 1

    et de l'autre côté

    les q impair : (-1)^q = -1 que l'on peut retirer sur sigma.
    Je vois bien que les 2 membres vont finir par s'annuler mais neanmoins je n'arrive pas à bien comprendre comment fonctionne le sigma pour résoudre l'exo

    Help !!

    Aylward

  5. #4
    watashi wa

    Re : Nombre de surjections

    salut tu devrais essayer encore en transformant les coeff du binome : ( q parmi p ) * (k parmi q ) = (k parmi p) * (k-q parmi k-p). De sorte que le facteur (k parmi p) peut etre factorise dans le sigma puis chgt d'indice puis formule du binome (1-1)=0 ... cela devrait le faire !

  6. #5
    Aylward

    Re : Nombre de surjections

    merci bcp je vais essayer ça tout de suite !

  7. A voir en vidéo sur Futura
  8. #6
    Aylward

    Re : Nombre de surjections

    Merci bcp watashi wa j'ai reussi !!!


    mais j'ai juste dit :


    q parmi p ) * (k parmi q ) = (k parmi p) * (q-k parmi p-k)

    et non

    q parmi p ) * (k parmi q ) = (k parmi p) * (k-q parmi k-p)



    MERCIIIIIIIIIIIIIIIIIIIIIII

  9. Publicité
  10. #7
    watashi wa

    Re : Nombre de surjections

    bravo ! et la suite de l'exo ???

  11. #8
    Aylward

    Angry Re : Nombre de surjections

    Dans la suite de l'exo,

    Soit Sn,p le nombre d'applications surjectives de En ( à n éléments ) dans Ep ( à p élements ).


    Il faut établir que

    p^n = sigma (de k=0 à p) (q parmi p) * Sn,p


    Le nombre d'application de En dans Ep est card(Ep)^card(En) = p^n
    d'où le résultat.

    Il faut donc calculer toutes les applications de En dans Ep.

    Je sais que Sn,p est le nombre de surjection de n,p.
    Supposons que Sn,p a q élements. On a donc le choix entre (q parmi p ) surjections.

    Mais je ne sais pas comment prouver qu'en les sommants, on a bien toutes les applications.


    2/ E n déduire la formule :

    Sn,p = (-1)^p * sigma (de k=0 à p) (-1)^k * ( k parmi p ) k^n



    et là je n'ai vraiment pas d'idée ! je ne vois pas d'où viennent les élements



    Merci watashi wa ! ( et les autres )

  12. #9
    watashi wa

    Re : Nombre de surjections

    salut
    dans le 1. il ya une erreur dans ce que tu écris : la formule a demontrer est fausse!! En effet :
    p^n = sigma (de k=0 à p) (k parmi p) * Sn,k
    tu as vu que p^n est le nb d'applc de En dans Ep. Ensuite tu recalcules le nb d'applic de En dans Ep en discutant suivant l'ensemble des images. Choisis une partie a k elements de Ep (il y a dc (k parmi p) possibltes) le nombre d'applications surjectives de En vers cette partie est Sn,k. En sommant pour k variant de 0 a p tu obtiens toutes les applications de En dans Ep.
    Pour le 2. c'est un calcul de somme qui utilise les propriétés des coefficients du binôme. C'est dans ce calcul que tu dois te servir de ce que tu as prouvé hier : la première question de la discussion.

    Bon courage !

  13. #10
    Aylward

    Re : Nombre de surjections

    effetivement dans le 1/ c'est plutot :


    p^n = sigma (de q=0 à p) (q parmi p) * Sn,p


    merci bien je vais essayer cela !!

  14. #11
    Aylward

    Re : Nombre de surjections

    merci bcp watashi wa tu m'a bcp aidé pour ce DM !!

    j'ai bien compris les questions et réussi la 2 ( en utilisant la question du début de la discution )


    puis-je encore te poser une derniere question ?

    nous avons toujours :

    En : l'ensemble des entier naturel strictement positifs et inférieur ou égaux à n.

    Sn,p : le nombre d'application surjective de En dans Ep

    An,p : le nombre de partition de En en p parties non vides


    Il faut trouver la relation entre An,p et Sn,p

    je ne vois pas vraiment comment je pourrais commencer. Et comme c'est la 1ère question au problème ....
    mais apres bcp d'exemples, je pense que la relation pourrait être :

    An,p =Sn,p/p!


    En te remerciant encore de toute ton aide !!!!!

  15. #12
    watashi wa

    Re : Nombre de surjections

    Voici le lien entre Sn,p et An,p : Considère une application surjective f de En vers {1,..,p}. Alors pour tout considère l'ensemble des antécédents de k par f : les (Fk) forment une partition de E_n. Ainsi, a chaque application surjective f correspondent p! partitions de E_n. Tu peux alors conclure en utilisant le théorème des Bergers que



    A bientot !

  16. Publicité
  17. #13
    watashi wa

    Re : Nombre de surjections

    Desole ! ce message annule le precedent!


    Voici le lien entre Sn,p et An,p : Considère une application surjective f de En vers {1,..,p}. Alors pour tout considère l'ensemble des antécédents de k par f : les (Fk) forment une partition ORDONNEE de E_n. C'est-a-dire une liste (F1,..,Fp) de parties non vides de En telles que :



    Il y a donc autant de partitions ordonnées que d'applications surjectives. Ainsi, a chaque partition non ordonnée correspondent p! applications surjectives de de E_n sur {1..p}. Tu peux alors conclure en utilisant le théorème des Bergers que



    L'enonce - ou ton cours- doit preciser si l'on entend par partition une liste (l'ordre compte) ou simplement la donnée de p parties disjointes de reunion E_n (partition non ordonnée). D'après ce que tu dis, il semble qu'il faille considérer des partitions non ordonnées, auquel cas le resultat que tu donnes est juste !!


    A bientot!

  18. #14
    Aylward

    Re : Nombre de surjections

    je te remercie bcp de toute l'aide que tu m'a apporté !

    et je te souhaite un très bon réveillon et une bonne année !!!


    A bientôt !



  19. #15
    watashi wa

    Re : Nombre de surjections

    pareillement !! Aylward ! Je te souhaite la sante et le succes dans tes etudes !!

    Bonne année !

  20. #16
    Aylward

    Re : Nombre de surjections

    Citation Envoyé par watashi wa
    ( q parmi p ) * (k parmi q ) = (k parmi p) * (k-q parmi k-p).

    une petite question me turlupine lol !

    As-tu fais exprès de mettre (k-q parmi k-p) au lieu de (q-k parmi p-k) dans le but de me forcer à bien comprendre la question et à trouver la réponse ou bien cela fonctionne aussi de cette maniere ?

  21. #17
    watashi wa

    Re : Nombre de surjections

    Ni l'un ni l'autre, je me suis gauffré !!

  22. #18
    anne-c

    Re : Nombre de surjections

    bonjour ,je traite le même exercice que vous sur le nombre de surjections mais je suis bloqué a la question calculer Sp+1,p en utilisant et justufiant l'existence de l'élément r de Ep ayant 2 antécédents pourriez vous m'aider?

  23. Publicité
  24. #19
    Nailuree

    Re : Nombre de surjections

    Et bien on est trois sur ce dm. 831?

    Moi je ne suis pas du tout d'accord avec la formule du Sn,p=p!*An,p car si l'on fait la "table" des arrangements et celle des surjections on remarque aisement que la formule n'est pas valable par exemple S(4,3)=36 et A(4,3)=24.

Sur le même thème :

Discussions similaires

  1. nombre premier et nombre impair
    Par nélli dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 08/01/2016, 17h49
  2. Démonstration - nombre de surjections ?
    Par g_h dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 11/07/2012, 18h03
  3. nombre de diviseurs premiers positifs d un nombre
    Par ludovic BOURGOIN dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 23/09/2007, 17h08
  4. Injections - Surjections -Bijections
    Par Kate901 dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 29/03/2007, 19h09
  5. Injections, Surjections !
    Par Elo23 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 03/10/2006, 14h41