Dénombrement du nombre de couples de parties (X,Y) d'un ensemble

Posté par charmuzelle charmuzelle

Bonjour

J'ai un problème de dénombrement à résoudre, mais comme je n'ai pas l'habitude, j'ai peur de me tromper. Je vais vous le soumettre ainsi que ma résolution pour que vous me disiez si je fais erreur ou si vous avez une autre solution.

Il s'inscrit dans le cours sur les nombres entiers. On vient d'introduire factorielle n, ainsi que les A_n^p et les C_n^p

Enoncé : E est un ensemble fini de cardinal n.
On veut dénombrer les couples (X,Y) de parties de E tels que XY

Ma proposition de résolution :

Y peut avoir un cardinal k compris entre 0 et n inclus.

Si k = 0, il n'y a qu'une possibilité. Idem si k = n.
Si k = 1 ou n-1, il y a n possibilités.
Si k = 2 ou n-2 il y a C_n² possibilités (manière de choisir 2 éléments parmi n sans obligation d'ordre.

...Pour tout k, on peut donc choisir C_n^k possibilités (de sous-ensembles Y de E de cardinal k)

Maintenant, pour chacun des C_n^k sous-ensembles Y de cardinal k, il existe 2^k sous-ensembles X de Y possibles. (C'est dans le cours)

C'est pourquoi le nombre total de couples (X,Y) de parties de E tels que XY serait

Faut-il ensuite donner une autre expression de cette somme ?

Merci beaucoup et bonne journée.

Posté par PIL PIL

Bonjour,

C'est parfait !  Tu peux juste simplifier ta réponse en utilisant la formule du binôme (1+...)^....

Posté par charmuzelle charmuzelle

3ⁿ ? C'était ma première conjecture mais je croyais que ça ne marchait pas après quelques vérifications... J'avais essayé sans succès de le prouver par récurrence. C'est moins compliqué en effet. Merci beaucoup.

J'ai travaillé aujourd'hui sur un nouveau problème de dénombrement que je vais vous soumettre aussi car je n'arrive pas à prouver ma formule...