Dénombrement de SUP

[Nowotny]

Bonsoir,
Voici l'énoncé qui me pose problème :"Soit E de cardinal n. Calculer le cardinal de S={(A,B) appartenant à (P(E))^2 / }
Je commence d'abord par construire A:
Pour construire A on choisit k éléments, k appartenant à {0,1,...1n} de E parmi les n éléments que compte E. Donc pour un k donné le nombre de parties vaut , donc le nombre de parties A possibles est ce qui donne 2ⁿ d'après le binôme de Newton.
Ensuite je construit B à partir de A: il faut nécessairement que B contienne les n-k éléments de l'ensemble E-A donc B est déjà en partie déterminée par cette obligation, il n'existe qu'une seule possibilité. Ensuite le cardinal de B peut varier de n-k à n d'où le nombre de parties B possibles dans le cas où A dispose de k éléments est .
C'est là que se pose pour moi un souci majeur, le cardinal de S serait-il tout simplement , c'est-à-dire ? (Je peux détailler le calcul mais c'est très pénible surtout en LaTex ) Je ne vois pas trop comment rédiger la fin s'il s'avère que le résultat soit confirmé.
Merci d'avance pour vos précieux conseils.
Cordialement, Arthur.
-----

[Snowey]

Bonsoir (:P),
Tu ne tiens pas compte de la dépendance des événements: construis d'abord A, puis B et enfin il faut faire varier le k (cardinal de À) pour recouvrir tous les cas
Pars donc en posant k un naturel, A de cardinal k (tu connais le nbre de parties à k éléments), ensuite on peut construire B (qui dépends bien sur de ce k !!). Par exemple, tu peux remarquer qu'il faut choisir le complémentaire de À dans E, et de lui ajouter (par union) n'importe qu'elle partie de A (tu traduits la propriété de l'ensemble par "le complémentaire de À est inclus dans B").
Bon mais en fait tu as bien fais ça (désolé la fatigue ... :/)
Tu te trompes uniquement dans le calcul de B: ce n'est pas necessairement une partie à n-k éléments, donc ...

En espérant t'avoir au moins aiguillé,

Snowey

[Médiat]

Bonjour,

Il y a un moyen plus simple de faire ce calcul :à chaque élément de E on associe :
0 s'il est dans A-B
1 s'il est dans B-A
2 s'il est dans A et B

Je vous laisse démontrer que ceci établit une bijection entre votre ensemble et un certain ensembles d'applications facile à dénombrer.

[Nowotny]

Merci beaucoup, toutefois j'ai encore besoin d'éclaircissement
Pour répondre à Snowey, le cardinal serait donc ? (le calcul de ce bazar à l'air subtil)

Par contre Médiat, je ne vois pas la bijection peux-tu m'en dire plus?

[A voir en vidéo sur Futura]

[Médiat]

Par contre Médiat, je ne vois pas la bijection peux-tu m'en dire plus?

Je l'ai entièrement décrite, sous la forme , où f est l'application que j'ai décrite, à vous de montrer que est bien une bijection

[Nowotny]

Soit qui associe au couple de parties de E (A,B) l'application .
Je montre assez facilement l'injectivité, avec les complémentaires par rapport à E.
Par contre en ce qui concerne la surjectivité, je pêche un peu:
Soit . Supposons qu'il existe tels que , mais après je n'arrive pas à définir le couple (A,B) pour en déduire la surjectivité. Merci beaucoup en tous cas.

[Médiat]

[Nowotny]

Exprimer A et B suffit donc à prouver la surjectivité, n'est-ce pas? donc est bijective, d'où card(S)= card(F(E,{0,1,2})= 3ⁿ.
Encore Merci

[Snowey]

Non, j'ai du mal m'exprimer ! (désolé, il était tard ^^)
On va "construire" par des arguments de dénombrement (sans bijections entre ensembles) l'espace S dont le cardinal est recherché.
Soit A une partie de E de cardinal k. On en a exactement . Maintenant, construisons B tel que . Il faut et il suffit que , autrement dit, B s'écrit (de manière unique) où . Il y a donc autant de façons de choisir B que de parties de A (qui est de cardinal k): .
Finalement, on trouve que , soit par binôme de Newton

[Nowotny]

Finalement, on trouve que , soit par binôme de Newton

Merci beaucoup bon, j'vais chipoter mais y une toute petite erreur: c'est 0 à la place de 1 dans
Vraiment merci en tout cas pour ces deux méthodes