Dénombrement

[Seirios]

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

[Seirios]

Sur la lancée, vous n'auriez pas une indication pour calculer ?

[Médiat]

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.

[Seirios]

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

[A voir en vidéo sur Futura]

[invitec317278e]

Prouve simplement par récurrence (sur ... ) que le résultat vaut

[Seirios]

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.

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

[invitec317278e]

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.

[invitec7c23c92]

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.

[invitebe08d051]

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.

[invitec317278e]

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

[invite57a1e779]

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

[invitebe08d051]

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

[invite986312212]

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