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

Dénombrement



  1. #1
    Seirios

    Dénombrement

    Bonjour à tous,

    J'essaie de résoudre l'exercice suivant : Soit E un ensemble fini à n éléments ; déterminer le nombre de couple (X,Y) de , où est l'ensemble des parties de E, tels que .

    J'ai d'abord pensé à fixé le cardinal de X, puis à déterminer le nombre d'ensembles Y qui correspondraient à la restriction : soit donc ; alors . Si , alors il y a Y possibles. De manière générale, on a donc pour j fixé, Y possibles ; or il y a X possibles de cardinal j, d'où le nombre de couples (X,Y) possibles : .

    Mais je n'arrive pas à simplifier cette somme, alors je me demande si ma réponse est le bon résultat.

    Quelqu'un pourrait-il m'éclairer ?

    Merci d'avance,
    Phys2

    -----

    If your method does not solve the problem, change the problem.

  2. Publicité
  3. #2
    Seirios

    Re : Dénombrement

    Sur la lancée, vous n'auriez pas une indication pour calculer ?
    If your method does not solve the problem, change the problem.

  4. #3
    Médiat

    Re : Dénombrement

    Citation Envoyé par Phys2 Voir le message
    J'essaie de résoudre l'exercice suivant : Soit E un ensemble fini à n éléments ; déterminer le nombre de couple (X,Y) de , où est l'ensemble des parties de E, tels que .

    J'ai d'abord pensé à fixé le cardinal de X,[...]
    Marrant j'ai tout de suite penser à faire le contraire :

    Combien il y a-t-il de sous ensembles de E avec i éléments ?
    Combien un ensembles à i éléments a-t-il de sous-ensembles ?

    La somme du produit des deux éléments précédents donne un résultat très simple (grace au binome de Newton).

    Pour ta deuxième somme, le binome de Newton doit le faire aussi.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  5. #4
    Seirios

    Re : Dénombrement

    Citation Envoyé par Médiat Voir le message
    Marrant j'ai tout de suite penser à faire le contraire :

    Combien il y a-t-il de sous ensembles de E avec i éléments ?
    Combien un ensembles à i éléments a-t-il de sous-ensembles ?

    La somme du produit des deux éléments précédents donne un résultat très simple (grace au binome de Newton).
    En utilisant cette méthode, je me suis aperçu que j'avais fait une erreur dans les bornes de ma première somme, ce qui était évident puisque sinon mon résultat aurait été 0...J'ai donc repris mes calculs, et je trouve bien un résultat qui se simplifie très bien : .

    Pour ta deuxième somme, le binome de Newton doit le faire aussi.
    Là par contre, je ne vois pas comment utiliser le binôme de Newton si m<n (le cas où est effectivement évident en utilisant le binôme de Newton).
    If your method does not solve the problem, change the problem.

  6. #5
    Thorin

    Re : Dénombrement

    Prouve simplement par récurrence (sur ... ) que le résultat vaut
    École d'ingénieurs + M1 Physique Fondamentale

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

    Re : Dénombrement

    Citation Envoyé par Phys2 Voir le message
    J'ai donc repris mes calculs, et je trouve bien un résultat qui se simplifie très bien :
    Plutôt , mais cela ne change pas le résultat.

    Citation Envoyé par Thorin Voir le message
    Prouve simplement par récurrence (sur ... ) que le résultat vaut
    Mais on ne nous donne pas le résultat final, donc faire une preuve par récurrence me semble faire tomber le résultat du ciel...
    If your method does not solve the problem, change the problem.

  9. Publicité
  10. #7
    Thorin

    Re : Dénombrement

    Citation Envoyé par Phys2 Voir le message
    Mais on ne nous donne pas le résultat final, donc faire une preuve par récurrence me semble faire tomber le résultat du ciel...
    Regarde ton cours de maths : les formules, les théorèmes tombés du ciel sont légion. La formule d'intégration par partie, certes, on la démontre en une ligne, n'empêche qu'en elle même, on se demande ce que viennent foutre là des dérivées, des crochets...
    Bref, l'important est que le résultat soit vrai, et que pour le trouver, je n'ai pas eu à demander à un logiciel ou à chercher sur le net, ou à regarder dans mes cours, ce qui prouve qu'il est facilement trouvable par un élève de prépa.

    Je suis sûr que je peux te trouver des dizaines d'exos que tu as réussi où certaines idées à l'intérieur de la démonstration paraissent tombées du ciel ; pour autant, ce n'es pas "moins tombé du ciel" d'avoir une super idée pour conclure une démo, et de deviner le résultat auquel on va aboutir.
    École d'ingénieurs + M1 Physique Fondamentale

  11. #8
    telchar

    Re : Dénombrement

    Bonjour,

    On peut aussi trouver le 3^n directement.

    A un couple (X,Y) tel que X est inclus dans Y, on peut associer une application f de E dans {0,1,2} telle que :
    f(x)=0 si x n'appartient pas à X ni Y.
    f(x)=1 si x appartient à X mais pas à Y.
    f(x)=2 si x appartient à X et Y.
    Clairement ça donne une bijection entre les couples (X,Y) ayant la propriété voulue et {0,1,2}^E.

  12. #9
    mimo13

    Re : Dénombrement

    Citation Envoyé par telchar Voir le message
    A un couple (X,Y) tel que X est inclus dans Y, on peut associer une application f de E dans {0,1,2} telle que :
    f(x)=0 si x n'appartient pas à X ni Y.
    f(x)=1 si x appartient à X mais pas à Y.
    f(x)=2 si x appartient à X et Y.
    Clairement ça donne une bijection entre les couples (X,Y) ayant la propriété voulue et {0,1,2}^E.
    La fonction n'est autre que la somme des fonctions caractéristiques de et :

    Néanmoins, l'idée est très bonne.

  13. #10
    Thorin

    Re : Dénombrement

    somme de fonction caractéristique...sachant que l'on définit la fonction caractéristique à valeurs dans {0,1}, ça ne veut pas dire grand chose, puisque f est définie dans {0,1,2}...
    École d'ingénieurs + M1 Physique Fondamentale

  14. #11
    God's Breath

    Re : Dénombrement

    Citation Envoyé par Thorin Voir le message
    somme de fonction caractéristique...sachant que l'on définit la fonction caractéristique à valeurs dans {0,1}, ça ne veut pas dire grand chose, puisque f est définie dans {0,1,2}...
    J'avoue ne pas comprendre cette remarque ; f est bien la somme des fonctions caractéristiques de X et de Y (à condition d'échanger X et Y dans la définition de f).
    Et Dieu, dans sa colère, pour punir les humains, envoya sur la Terre les mathématiciens.

  15. #12
    mimo13

    Re : Dénombrement

    Citation Envoyé par Thorin Voir le message
    somme de fonction caractéristique...sachant que l'on définit la fonction caractéristique à valeurs dans {0,1}, ça ne veut pas dire grand chose, puisque f est définie dans {0,1,2}...
    Moi non plus...

  16. Publicité
  17. #13
    invite986312212
    Invité

    Re : Dénombrement

    Citation Envoyé par telchar Voir le message
    Bonjour,

    On peut aussi trouver le 3^n directement.

    A un couple (X,Y) tel que X est inclus dans Y, on peut associer une application f de E dans {0,1,2} telle que :
    f(x)=0 si x n'appartient pas à X ni Y.
    f(x)=1 si x appartient à X mais pas à Y.
    f(x)=2 si x appartient à X et Y.
    Clairement ça donne une bijection entre les couples (X,Y) ayant la propriété voulue et {0,1,2}^E.
    joli!

    ça vient bien aussi par récurrence: si on a montré le résultat pour un ensemble E à n éléments, et qu'on ajoute un élément a, les couples (X,Y) de parties de Eu{a} peuvent être classés en (X,Y), (X,Yu{a}) et (Xu{a},Yu{a}) pour X,Y parties de E, soit 3^n + 3^n + 3^n

Sur le même thème :

Discussions similaires

  1. [T°S] Dénombrement
    Par Shadowshark65 dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 22/02/2009, 11h00
  2. dénombrement
    Par doc123 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 04/01/2009, 21h58
  3. Dénombrement ....
    Par mimicaro dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 07/05/2008, 19h08
  4. Dénombrement
    Par just1 dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 19/10/2006, 21h03
  5. Dénombrement
    Par jiraiya dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 04/10/2006, 11h46