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

Démonstration - nombre de surjections ?



  1. #1
    g_h

    Démonstration - nombre de surjections ?


    ------

    Hello,

    J'ai vu en cours une formule récurrente pour le calcul du nombre de surjections d'un ensemble E dans un ensemble F.
    Je viens de tomber sur le net sur un autre formule, non récurrente, que j'aimerais bien comprendre :

    Soit e le cardinal de E, et f le cardinal de F



    Si vous avez une démonstration, un début de démonstration ou même rien qu'une piste, ça m'intéresse !

    Merci !

    -----

  2. Publicité
  3. #2
    Romain-des-Bois

    Re : Démonstration - nombre de surjections ?

    Citation Envoyé par g_h

    Soit e le cardinal de E, et f le cardinal de F

    Salut g_h,

    j'ai vu cette formule et sa démo en cours - et j'ai du la démontrer en khôlle (mais avant de l'avoir vue.......)


    la démo fait trois pages chez moi ...

    d'abord il faut connaitre une formule d'inversion qui est indispensable, et sa démo est plutôt longue...

    cette formule te dit :

    b_n= la somme de k=0 à n, de (k parmi n) des a_k

    <=>

    a_n = la somme de k=0 à n de (-1)^(n-k) x (k parmi n) x b_k


    je te fais pas la démo, c'est horrible : mon khôlleur ne la connaissait même pas ...


    Tu considères A,
    A = les applications de E vers F
    A_k = {f € A / card(f(E) = k}
    A= union disjointe de k=1 à n des A_k

    Clairement (ruse triviale dirait mon prof),

    card(A_k)=la somme de k=0 à n de (k parmie q) x S_p,k

    avec S_p,k, les surjections de E_p vers E_k

    (ah oui, p est le card de E, et q est le card de F)


    donc quelque soit n € IN, b_n=la somme de k=0 à n de (k parmi n) x a_k,

    tu utilises la formule d'inversion et c'est fini...

    il faut faire un dessin pour comprendre clairement.

    précision : k, c'est le cardinal d'un ensemble de F qui ne reçoit pas de surjection de E. F ne reçoit pas tout entier les surjections de E, il n'y en a qu'une partie (de cardinal q).

    j'espère avoir été clair

    si tu as un problème...

    Romain

  4. #3
    g_h

    Re : Démonstration - nombre de surjections ?

    Merci pour ta réponse !
    Seulement je ne comprends pas... c'est quoi E_p et E_k ?

    Citation Envoyé par Romain29
    avec S_p,k, les surjections de E_p vers E_k

  5. #4
    Romain-des-Bois

    Re : Démonstration - nombre de surjections ?

    en fait, j'ai mélangé les notations

    E_p, c'est l'ensemble E de card p, et idem pour E_k (resp card k).

    Voilà voilà !

    PS : ça fait plaisir de pouvoir aider quelqu'un,

    Romain

  6. A voir en vidéo sur Futura
  7. #5
    g_h

    Re : Démonstration - nombre de surjections ?

    Citation Envoyé par Romain29
    en fait, j'ai mélangé les notations

    E_p, c'est l'ensemble E de card p, et idem pour E_k (resp card k).

    Voilà voilà !

    PS : ça fait plaisir de pouvoir aider quelqu'un,

    Romain
    Il y a plusieurs ensembles E ou quelque chose m'a échappé ?
    E est de cardinal p, il n'est pas de cardinal k... ? (oui il y a sûrement quelque chose qui m'échappe )

    (et ça fait plaisir de se faire aider aussi !)

    EDIT : tentative : E_k est peut-être l'ensemble des parties de E à k éléments ?

  8. #6
    Romain-des-Bois

    Re : Démonstration - nombre de surjections ?

    Non non non,

    toi tu as appelé tes deux ensembles E et F

    moi je les appelle tous les deux E, mais en indice je mets leur cardinal pour les différencier : je sais c'est pas très clair, surtout que j'ai pas respecté tes notations.

    j'espère que tu vas t'en sortir...

    je te démontre pas la formule d'inversion : j'en ai pas le courage

    mais il parait que c'est une formule extraordinaire.


    HS : je sais pas vous, mais nous - en khôlle - on nous demande de démontrer les formules comme si on ne les savait pas. c'est à dire que tu n'as pas droit à la récurrence et tu n'as pas le droit de partir de la formule à démontrer. Il faut partir de quelque chose de basique et remonter jusqu'à la formule (vive les khôlles !)

  9. Publicité
  10. #7
    g_h

    Re : Démonstration - nombre de surjections ?

    Citation Envoyé par Romain29
    Non non non,

    toi tu as appelé tes deux ensembles E et F

    moi je les appelle tous les deux E, mais en indice je mets leur cardinal pour les différencier : je sais c'est pas très clair, surtout que j'ai pas respecté tes notations.

    j'espère que tu vas t'en sortir...

    je te démontre pas la formule d'inversion : j'en ai pas le courage

    mais il parait que c'est une formule extraordinaire.


    HS : je sais pas vous, mais nous - en khôlle - on nous demande de démontrer les formules comme si on ne les savait pas. c'est à dire que tu n'as pas droit à la récurrence et tu n'as pas le droit de partir de la formule à démontrer. Il faut partir de quelque chose de basique et remonter jusqu'à la formule (vive les khôlles !)
    Arf ok, donc mon F c'est ton E_k
    Mais tu écris que F est de cardinal ... q et non pas k !
    Tu voudrais bien me la refaire avec tes notations ? Je pense que ça serait mieux

    Sinon j'ai pas encore éprouvé le besoin de faire une récurrence en colle, mais en tous cas ça ne doit pas être interdit (faudra que j'essaye ) !

    D'ailleurs si tu as une démo de la formule de Taylor (avec reste intégral) qui ne passe pas par la récurrence, ça m'intéresse ! (mais je doute que ça existe, enfin qui sait !)

    PS : est-ce que la formule d'inversion en question à un nom particulier ? Je ne la trouve nulle part !

  11. #8
    g_h

    Re : Démonstration - nombre de surjections ?

    Je me permets de faire remonter ce fil... c'est mon programme de colle de la semaine prochaine et je n'aurai plus le net !

    Donc si quelqu'un pouvait me filer un coup de pouce ( Romain29 si tu passes par là ... )

    Et si quelqu'un a un lien concernant la "formule d'inversion" qui est utilisée ici, ça m'intéresse plus que fortement aussi !

    Merci encore

  12. #9
    Romain-des-Bois

    Re : Démonstration - nombre de surjections ?

    Argh ! excuse moi !

    ...


    la formule d'inversion (que je te démontre pas : mais pas de soucis à ce niveau là : je ne crois pas que ce soit au programme : en tous cas, nous, ça ne l'était pas)


    b_n= la somme de k=0 à n, de (k parmi n) des a_k

    <=>

    a_n = la somme de k=0 à n de (-1)^(n-k) x (k parmi n) x b_k


    on cherche le nombre de surj de E vers F avec e le card de E et f le card de F.

    Tu considères A,
    A = les applications de E vers F
    A_k = {f € A / card(f(E) = k}
    A= union disjointe de k=1 à n des A_k

    Clairement : avec un dessin

    card(A_k) = la somme de k=0 à n de (k parmie f) x S_e,f



    quelque soit n appartient à IN,

    b_n=la somme de k=0 à n de (k parmi n) x a_k,

    tu utilises la formule d'inversion et c'est fini...


    J'ai repris exactement ce que j'avais écrit hier en changeant les notations.
    Pour être vraiment clair, il faut le faire sur un dessin.

    Je ne vois pas comment je pourrais t'aider...

    bon courage

    PS : pour nous, les khôlleurs n'ont pas été méchants à ce sujet.

  13. #10
    g_h

    Re : Démonstration - nombre de surjections ?

    Ok, merci beaucoup pour ton aide !!
    J'espère pouvoir m'en tirer

  14. #11
    indian58

    Re : Démonstration - nombre de surjections ?

    Mon prof a donné l'année dernière un DM dont une partie traitait le nombre de surjection d'un ensemble E dans un ensemble F. Il est disponible sur internet, je vais essayer de retrouver l'adresse.

  15. #12
    g_h

    Re : Démonstration - nombre de surjections ?

    Citation Envoyé par Romain29
    Clairement : avec un dessin

    card(A_k) = la somme de k=0 à n de (k parmie f) x S_e,f
    Plutôt la somme de k=0 à f de (k parmie f) x S_e,k
    Non ?

    Sinon, ça m'intéresse aussi indian58

  16. Publicité
  17. #13
    LaFolleaLunettes

    Re : Démonstration - nombre de surjections ?

    Dans l'exercice que je suis en train de faire, on parle d'une inversion de matrice pour la formule d'inversion ; mais j'avoue avoir du mal à voir ce que vient faire une matrice là-dedans... Peut-être une histoire de déterminant ?

Discussions similaires

  1. Nombre de surjections
    Par Aylward dans le forum Mathématiques du supérieur
    Réponses: 18
    Dernier message: 06/01/2008, 12h19
  2. Injections, Surjections !
    Par Elo23 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 03/10/2006, 14h41
  3. Démonstration de l'inégalité triangulaire (nombre complexes)
    Par ccslt dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 06/09/2006, 21h48
  4. démonstration concernant le nombre d'or
    Par pseunanou dans le forum Mathématiques du supérieur
    Réponses: 18
    Dernier message: 25/01/2006, 16h13
  5. démonstration du nombre de Reynolds
    Par douzy dans le forum Physique
    Réponses: 0
    Dernier message: 06/07/2004, 15h43