Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau autre
Partager :

Analyse Combinatoire, p listes

Posté par
Dedeuch 24-01-10 à 22:33

Bonjour,

Je suis en train de reprendre mes études dans le but de passer le CAPES de math, et je bloque sur une démonstration de cours.

Je dois montrer que le nombre de couple (X1, X2) de parties d'un n ensemble E telles que X1 U X2=E est égal à 3n, que le nombre de paires vaut (3n+1)/2.

Par suite, en généralisant couple par p liste, je dois montrer que le nombre de ces p liste est égale à (2p-1)n

Merci pour votre aide

Posté par
carpediemre : Analyse Combinatoire, p listes 24-01-10 à 23:35

salut

soit X une parite à p éléments de E avec 0pn

tu as Cnp parties X

pour chacune de ces parties tu la complète par une partie Y contenant au moins les n-p éléments restants pour que XY=E

mais dans Y tu peux décider de prendre ou non chaque élément de X donc tu as 2p choix pour construire Y

donc au total tu as p=0n Cnp2p = p=0n Cnp2p * 1n-p = 3n d'après la formule du binôme de Newton

Posté par
carpediemre : Analyse Combinatoire, p listes 24-01-10 à 23:36

je ne comprends pas ce que tu veux dire par paire...

Posté par
veledare : Analyse Combinatoire, p listes 24-01-10 à 23:55

bonsoir,
soit X_1un sous ensemble de E de cardinal k (0kn)
si le couple (X_1,X_2)convient
X_2 est nécessairement un sur-ensemble  de \bar X_1le complémentaire de X_1 dans E
donc pour X_1fixé de cardinal k on peut former 2^k X_2 ils sont égaux à\bar X_1\cup Yoù Y est l'un quelconque des 2^ksous ensembles de X_1
il y a (_n^k)parties de E à k éléments ,k variant de 0 à n  il y a donc\bigsum_{k=0}^n(_k^n)2^k=3^ncouples(X_1,X_2)tels queX_1\cup X_2=E

Posté par
veledare : Analyse Combinatoire, p listes 24-01-10 à 23:58

bonsoir carpediemje suis en retard

Posté par
carpediemre : Analyse Combinatoire, p listes 25-01-10 à 00:04

bonsoir veleda

le latex c'est élastique mais pas le temps pour s'en servir (pour répondre aux questions)

Posté par
veledare : Analyse Combinatoire, p listes 25-01-10 à 06:30

parmi les couples solutions l y en a :
*le couple (E,E)
et
*3^n-1couples tels que X_1 \neq X_2
(X_1,X_2)et(X_2,X_1)provenant de la même paire {{X_1,X_2}}cela fait \frac{3^n-1}{2}paires
donc en tout 1+\frac{3^n-1}{2}=\frac{3^n+1}{2}paires

Posté par
Dedeuchre : Analyse Combinatoire, p listes 25-01-10 à 21:57

Merci de ta réponse veleda, reste le pb de l'extension des paires à une p-listes...

Posté par
veledare : Analyse Combinatoire, p listes 25-01-10 à 22:55

pour une p-liste tu peux faire une récurrence
la formule est exacte pour le couple p=2 3^n=(2^2-1)^n
on va supposer qu'elle est vraie au rang p et montrer qu'elle est vraie au rang p+1
soit
(X_1\cup X_2\cup X_3..\cup X_p\cup X_{p+1})=E.(1)
en posantA=\cup_{i=1}^pX_i(1) s'écrit A\cup X_{p+1}=E<=>\bar A\subset X_{p+1}

*il y a (_k^n)choix pour A sous ensemble de E de cardinal k(0kn)
**pour A donné
il y a (2^p-1)^kp-listes  d'prés l'hypothèse de récurrence(X_1,X_2,...X_p)/\cup_{i=0}^pX_i=A
et
2^kparties Y de A donc2^kparties X_{p+1}=(\bar A\cup Y)/E=(A\cup X_{p+1})
k variant de 0 à n il y a donc
\bigsum_{k=0}^n(_k^n)(2^p-1)^k.2^k=(1+2(2^p-1))^n=(2^{p+1}-1)^n
donc la formule est valable au rang p+1
j'espère que c'est lisible car je ne suis pas trés douée en latex


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1677 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !