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... Maths spé ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau maths spé
Partager :

Dénombrement Coefficient Binomial : problème compréhension

Posté par
NicoNien 10-03-10 à 19:14

Bonsoir à tous.

J'ai un gros problème pour comprendre le corrigé d'un de mes exercices.

Voici l'énoncé :

Soit E un ensemble à n éléments avec n*
On va dénombrer des parties de E, à savoir (X ; Y ; Z), sur lesquelles on posera certaines contraintes.

1) Le nombre de de couples (X ; Y) tels que XY = est-il égal à 3n ?

2) Le nombre de de couples (X ; Y) tels que XY = E est-il égal à 3n ?

3) Le nombre de de couples (X ; Y) tels que (X ; Y) forme une partition de E est-il égal à 3n ?

4) Le nombre de couple (X ; Y ; Z) tels que XY = Z est-il égal à 3n ?




Voici la correction pour la question 1 :


card(E) = n   =>   card(P(E)) = 2n

Soit X une partie de E telle que  card(X) = k

Les parties Y telles que  XY =   sont les parties de  \bar{X}  telles que  card(\bar{X}) = n - k

Il y a donc  2n-k choix de Y différents

De plus, on sait qu'il y a  C_n^k  choix de X différents

Il y a donc  \sum \limits_{k=0}^n C_n^k.2n-k  =  3n  couples possibles




Mes questions :

On relisant le cours, il est écrit que  card(E) = n  =>  card(P(E)) = 2n
Aurait-on alors  card(X) = k  =>  card(P(X)) = 2k  et  card(\bar{X}) = n - k  =>  card(P(\bar{X})) = 2n - k ?

Eux disent qu'on n'a pas  card(P(X)) = 2k  mais  card(P(X)) = C_n^k.
Pourriez-vous m'expliquer pourquoi ?

Ensuite, pour trouver le nombre de couples, pourquoi fait-on la somme du produits des deux nombres de possibilités pour X et \bar{X} ?




Je suis vraiment perdu, j'ai cherché dans mes cours, sur Internet, mais impossible de comprendre pourquoi on fait ainsi :-s

Pourriez-vous m'éclairer ?

En vous remerciant.

Bonne soirée

Posté par
veledare : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 20:08

bonsoir,
C_n^kc'est le nombre de parties de E de cardinal k c'est à dire le nombre de sous ensembles X de E à k éléments

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 20:30

Bonsoir.

Tout d'abord, merci de porter attention à mon problème.

Donc si j'ai bien compris votre explication, on peut écrire :

card(P(X)) = C_n^k

Or on peut aussi écrire  card(P(X)) = 2k  (en me référant à la définition du cours, enfin il me semble ).

Le problème, c'est que  C_n^k 2k

C'est là mon problème, je ne comprends pas de tout ce point.

Pourriez-vous m'éclairer là-dessus ?

En vous remerciant.

Bonne soirée

Posté par
veledare : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 21:24

*si X est une partie de E à k éléments le nombre de sous- ensembles de X c'est bien 2^k
**dans un ensemble E de cardinal n il y a C_n^ksous-ensemble X de E de cardinal n
ce n'est pas la même chose
pour un X donné de cardinal k il y a 2^{n-k}Ytels queX\cap Y=
-pour k donné il y a doncC_n^k2^{n-k}(X,Y]répondant à la question
mais k varie de 0 à n donc le nombre de couples (X,Y)solutions=\bigsum_{k=0}^nC_n^k2^{n-k}

Posté par
verdurinre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 21:34

Bonsoir.

Citation :
Donc si j'ai bien compris votre explication, on peut écrire :
card(P(X)) = C_n^k

Tu as mal compris ce que t'as dit veleda.
\ - Il y a {\large \text{C}}_n^k parties à k éléments dans E.
\ - Chacune d'elles à 2^k parties, mais ce n'est pas la question.

On commence par choisir une partie X à k éléments.
Une fois choisie la partie X (il y a {\large \text{C}}_n^k possibilités) on recherche les parties Y telles que XY=.
Il est évident que Y est dans le complémentaire de X. Or le complémentaire de X à n-k éléments, et donc on a 2^{n-k} choix possibles. En effet Y est un sous ensemble de \overline{X}

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 21:54

Rebonsoir.

Merci encore pour votre intérêt, mais au risque de vous paraître pas très bon en maths, je n'arrive toujours pas à comprendre.

Si j'ai bien compris ce que vous m'avez expliqué, on a :


X est une partie de E
                                            =>              ALORS  il y a {n \choose k} sous ensemble X dans E   ;   ET  il y a 2k sous-ensembles P(X) dans X
X est à k éléments


\bar{X} est une partie de E
                                            =>              ALORS  il y a {n \choose n-k} sous ensemble \bar{X} dans E   ;   ET  il y a 2n-k sous-ensembles P(\bar{X}) dans \bar{X}
\bar{X} est à n - k éléments


Si c'est bien ça (corrigez-moi si je me trompe ), pourquoi multiplie t-on  {n \choose k}  avec  2n-k  ;  plutôt que de multiplier  2k  avec  2n-k  ?


Veuillez encore m'excuser pour mon manque de compréhension, mais je ne désespère pas, je vais y arriver

En vous remerciant.

Bonne soirée

Posté par
lafol Moderateurre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 22:02

Bonsoir

ton problème, c'est la notation P(X) !

P(X), c'est l'ENSEMBLE de TOUTES les parties de X.
Si X a k éléments, on peut faire 2^k parties avec ces k éléments de X, donc Card(P(X)) = 2^k

ça n'a rien à voir avec le nombre de parties X contenant k éléments qu'on peut faire avec les n éléments de l'ensemble E : là, il faut choisir parmi ces n éléments les k qui vont constituer la partie X, il y a donc \(n\\k\) possibilités.

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 22:29

Bonsoir.

Verdurin et Lafol, je n'avais pas vu vos réponses avant de poster, merci de porter attention à mon problème.


Donc je pense commencer à comprendre :


Je prends X qui contient k éléments.
Mais combien de X (contenant k éléments) différents puis-je créer à partir des n éléments de E ?
Il faut que je choisisse k éléments parmi les n éléments à ma disposition pour créer chacun des X.
Et comme je ne choisi pas toujours les mêmes k éléments (j'en prends des différents à chaque fois), j'obtiens donc {n \choose k} X différents.

Maintenant, combien de P(X) différents puis-je créer à partir de mes X ?
Je peux en créer card(P(X)) = 2k différents.


Ai-je bien compris ?


Mais dans ce cas là, et c'est là que je ne vois pas pourquoi, si on dit qu'il y a  {n \choose k} X différents ; en faisant le même raisonnement, on devrait trouver  {n \choose n-k} \bar{X} différents, non ? Pourquoi trouve-t-on 2n-k \bar{X} différents, et non pas {n \choose n-k} ?


Voilà, j'espère que déjà, j'ai bien compris la première partie

Merci de votre aide

Bonne soirée

Posté par
lafol Moderateurre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 23:04

Une fois que X est choisi, il n'y a qu'un complémentaire de X ! (= l'ensemble qui contient tous les éléments de E qui ne sont pas dans X)

Ce que tu veux, c'est que Y ne contienne aucun élément de X, pour que l'intersection de X et de Y soit vide. Tu dois donc fabriquer ton Y en choisissant ses éléments (on ne sait pas combien) parmi les (n-k) qui ne sont pas dans X : tu dois choisir pour Y une partie du complémentaire de X, tu as le choix entre les 2^(n-k) parties de ce complémentaire

Posté par
verdurinre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 23:06

Je dirais que tu n'as pas compris la méthode de base.

On doit chercher les couples (X,Y)E2 tels que XY=.

Pour ceci on commence par chercher les possibilités pour X, note bien que l'on aurait pu commencer par chercher les possibilités pour Y.

\ - On choisit le nombre d'éléments de X : c'est un entier k entre 0 et n.
\ - On choisit les k éléments de X : il y a n \choose k possibilités différentes.
\ - On choisit les éléments de Y parmi les n-k éléments restants.
\qquad \bullet On pourrait bien sur recommencer le même raisonnement et calculer \displaystyle \sum_{i=0}^{n-k}{n-k \choose i}, mais on sait que le résultat est 2^{n-k}.
\ - Il y a donc {n \choose k} 2^{n-k} choix possible pour le couple (X,Y) si X à k éléments.
\ - On additionne les résultats pour les différentes valeurs de k : on a le nombres total de possibilités.

Le résultats final est :
3$ \sum_{k=0}^{n}{n \choose k}2^{n-k}=\sum_{k=0}^{n}{n \choose k}1^k 2^{n-k}=(1+2)^n

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 10-03-10 à 23:39



Rebonsoir.

Merci à nouveau de consacrer du temps à essayer de me faire comprendre.

Je ne vais pas vous le cacher, j'ai très bien compris le déroulement de votre raisonnement, mais en fait, je bloque toujours sur le même point (je suis confus, je n'ai pas envie que vous croyiez que j'abuse de votre patience ).

Donc je comprends bien le déroulement, mais c'est pile au milieu que j'ai mon problème.

Je choisi les k éléments de X parmi les n éléments de E : j'ai {n \choose k} possibilités   =>   OK

Et c'est là que je n'arrive pas à comprendre (je sais que j'ai faux, mais je ne comprends pas pourquoi).
Je crois comprendre que maintenant, il ne nous reste plus que n-k éléments, donc je vais choisir i éléments de Y parmi ces n-k éléments. Et c'est à ce moment là que tout devient flou. Pour moi, si je choisi i éléments de Y parmi n-k éléments, j'ai {n-k \choose i} possibilités. Mais je n'arrive pas à comprendre pourquoi c'est faux (car en fait, j'ai \sum \limits_{i=0}^{n-k} {n-k \choose i} possibilités).

Voilà exactement le seul endroit où j'ai un réel problème : pourquoi  \sum \limits_{i=0}^{n-k} {n-k \choose i} possibilités  et non pas  juste  {n-k \choose i} possibilités ?


Ahlala, plus que ce petit problème à résoudre, et grâce à vous, j'aurai enfin compris ce problème

En vous remerciant.

Bonne soirée

Posté par
verdurinre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 00:36

On en est au moment de choisir Y. On doit prendre ses éléments parmi les n-k qui ne sont pas dans X.
\ - On choisit le nombre d'éléments de Y : les possibilités sont 0;1...; n-k
\ - Soit i le nombre d'éléments de Y : il y a n-k \choose i façons de les prendre.
\ - On fait le total des façons de choisir Y : \displaystyle \sum_{i=0}^{n-k}{n-k \choose i}=2^{n-k}

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 01:13

Bonsoir.

Tout d'abord, merci de m'aider à une heure si tardive.

En fait, mon problème est là : pourquoi pour Y, on fait la somme des possibilités \sum \limits_{i=0}^{n-k} {n-k \choose i}, alors que pour le X, on ne fait pas la somme, on n'en reste qu'à l'étape des {n \choose k}.

C'est ça le truc, c'est la somme qui me dérange, je ne comprends pas pourquoi on la fait intervenir pour Y, mais pas pour X.

En gros, dans ma tête, et en numérotant les 3 étapes de votre dernier message, c'est comme si pour X, on faisait l'étape 1 puis l'étape 2 ; et que pour Y, on faisait l'étape 1 puis l'étape 2 puis l'étape 3 (voyez-vous ce que je veux dire ?)

En gros, j'aurais tendance à faire exactement le même raisonnement pour X que pour Y :


-  il y a k éléments dans X
-  {n \choose k} est une façon de choisir ces k éléments
-  on fait le total des façons de choisir les k éléments : \sum \limits_{k=0}^{n} {n \choose k}


-  il y a i éléments dans Y
-  {n-k \choose i} est une façon de choisir ces i éléments
-  on fait le total des façons de choisir les i éléments : \sum \limits_{i=0}^{n-k} {n-k \choose i}



Dans ma tête, il manque soit une étape à X, soit il y a une étape en trop à Y.

C'est exactement là et seulement là où je bloque.

Je sais très bien que c'est faux, car si je faisais la troisième étape pour X, je me retrouverai avec \sum \limits_{k=0}^{n} {n \choose k} = 2n = card(P(E)).

Mais je ne comprends pas pourquoi il n'y a que deux étapes pour X (ie on ne fait pas la somme à la fin), alors que pour Y, il y a bien les trois étapes (ie on fait la somme à la fin).

J'espère que vous comprenez ce qu'est mon problème

Donc pourquoi y'a fait-on la somme pour Y, mais pas pour X ?

Ah oui, et merci pour votre rédaction bien détaillées point par point, je comprends beaucoup mieux quand tout est séparé ainsi

Bonne soirée

Posté par
verdurinre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 01:46

On fait le total pour les X aussi :

Citation :
Le résultats final est :
3$ \sum_{k=0}^{n}{n \choose k}2^{n-k}=\sum_{k=0}^{n}{n \choose k}1^k 2^{n-k}=(1+2)^n

à la fin de mon message de 23h06.

Ton problème vient sans doute de l'introduction d'une dissymétrie entre X et Y. Elle est finalement assez artificielle, mais très utile : tu n'as sans doute pas envie de calculer
3$ \sum_{\stack{k\in \{0,\cdots,n\}}{i+j=k}}{n\choose k}{k \choose i}
et je me rend compte que l'expression n'est toujours pas symétrique, mais il est clair que {k \choose i}={k \choose j} car k=i+j (j'espère que je ne me suis pas tromper en écrivant ça).

Donc l'idée est la suivante :
On fixe le nombre d'éléments de X soit k.
On calcule le nombre de possibilité dans ce cas : {n \choose k}2^{n-k}
On ajoute tous les résultats obtenus : \displaystyle\sum_{k=0}^{n}{n \choose k}2^{n-k}

Il est a noté que l'on aurait pu faire :
On fixe le nombre d'éléments de Y soit n-k.
On calcule le nombre de possibilité dans ce cas : {n \choose n-k}2^{k}
On ajoute tous les résultats obtenus : \displaystyle\sum_{k=0}^{n}{n \choose n-k}2^{k}

Dans les deux calculs on trouve le même résultat.

Posté par
verdurinre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 01:48


Excuse mon orthographe : il est tard

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 14:27

Bonjour.

Comme toujours, la nuit porte conseil.
En fait, essayant de m'endormir hier, j'ai eu LA révélation dans mon lit (c'est fou à quel point ça arrive souvent, cf mes autres topics ^^). Ce lit est une véritable source d'inspirations ... pour les maths j'entends hein ? Le reste, ça ne vous regarde pas nah

Et puis, votre dernière réponse vient visiblement confirmer ce dont je me suis rendu compte hier soir


Donc, pour résumer, je dirais :


-  On choisi X à k éléments, k éléments que l'on fixe dans un premier temps (c'est ça l'étape qui me dérangeait), et qu'on fera varier plus tard (à la toute fin).
-  {n \choose k} est UNE façon de choisir ces k éléments.
-  Pas de troisième étape dans l'immédiat, puisque l'on a fixé k (car si on faisait varier k maintenant, ce serait le bordel pour choisir comment construire nos Y, effectivement, il est plus simple de fabriquer tous nos Y à partir d'un X fixé, ie il est plus facile de recenser toutes les possibilités de combinaisons d'éléments formant les différents Y à partir d'éléments fixés de X, ie à partir de toujours les mêmes éléments). Je ne sais pas si je m'exprime bien mais en gros, on fabrique X à partir de E à n éléments fixes, bah c'est la même chose pour construire Y, il faut le faire à partir de X à k éléments fixes.

-  Maintenant qu'on a construit UN X (qui nous sert à construire TOUS les Y), on peut construire nos Y.
-  On sait que Y est inclus dans \bar{X}, et \bar{X} est à n - k éléments.
-  On va donc choisir i éléments parmi ces n -k  éléments pour construire nos Y.
-  On va dans un premier temps construire UN SEUL Y.
-  {n-k \choose i} est une façon de choisir ces i éléments => on a construit UN Y.
-  Pour avoir TOUS nos Y, il suffit de sommer chacune des différentes possibilités de construire UN Y en faisant varier i de 0 à n - k.
-  Donc \sum \limits_{i=0}^{n-k} {n-k \choose i} sont toutes les façons de choisir ces i éléments, ie de construire TOUS les Y.

-  Ainsi, à partir d'UN X à k éléments choisis tels que {n \choose k}, on a construit TOUS les Y à i éléments choisis tels que {n-k \choose i}, soit \sum \limits_{i=0}^{n-k} {n-k \choose i}
-  On a donc {n \choose k}.\sum \limits_{i=0}^{n-k} {n-k \choose i} possibilités de couples (X ; Y) à partir d'UN seul X.
-  On a donc TOUS nos Y, mais UN seul X. Pour avoir TOUS nos X, on va maintenant (et seulement maintenant) faire varier k de 0 à n.
-  On a donc \sum \limits_{k=0}^{n}{n \choose k}.\sum \limits_{i=0}^{n-k} {n-k \choose i} possibilités de couples (X ; Y), comprenant cette fois-ci TOUS nos X (et toujours TOUS nos Y, bien-sûr)
-  D'où le résultat.


Pfiuuu, dites-moi que ce raisonnement est bon, sinon je vais devenir fou

Plus sérieusement, je pense que ce raisonnement est bon, il colle bien et en plus, je trouve le bon résultat ; de surcroît, on peut effectivement commencer par créer UN Y pour en déduire TOUS les X, ça fonctionne dans l'autre sens

Je sollicite quand même vos remarques sur ce raisonnement, car je suis loin d'être fiable

Ah, et au fait, pas grave pour vos (éventuelles) fautes d'orthographe (je n'ai même pas fait gaffe), car bien que je sois très pointilleux là-dessus, je ne suis pas du genre à ennuyer les gens dès qu'il y a la moindre petite faute (ça m'arrive aussi d'en faire ). Je retiendrais surtout le fait que vous (et vos autres collègues) avez consacré du temps à m'expliquer ce problème, et c'est ça qui compte

Bon, j'attends votre confirmation pour valider mon raisonnement
En attendant, je retourne dans le "bossage" de ces fichus concours

Bonne journée

Posté par
verdurinre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 19:14

C'est ça

Posté par
lafol Moderateurre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 22:08

Bonsoir
ce n'est pas tout à fait ça, mais ça en approche :

quand tu dis :

Citation :
\(n\\k\) est UNE façon de choisir ces k éléments.


en fait, c'est plutôt : il y a \(n\\k\) façons de choisir ces k éléments

et plus loin :
Citation :
- On va donc choisir i éléments parmi ces n -k éléments pour construire nos Y.
- On va dans un premier temps construire UN SEUL Y.
- {n-k \choose i} est une façon de choisir ces i éléments => on a construit UN Y.
- Pour avoir TOUS nos Y, il suffit de sommer chacune des différentes possibilités de construire UN Y en faisant varier i de 0 à n - k.


pas exactement : on commence par se demander combien de Y ayant i éléments on peut construire : on peut en construire {n-k \choose i}

mais on peut construire des Y avec 0 éléments, un seul élément, deux éléments ,... n-k éléments. c'est pour ça que pour avoir le nombre total de Y, on somme en faisant varier i de 0 à n - k.

et ainsi on a toutes les manières de choisir X avec k éléments puis Y, reste à dire qu'on peut choisir k = 0 ou 1 ou 2 ou ... ou n, et c'est pour ça qu'on fait la dernière somme.

Posté par
NicoNienre : Dénombrement Coefficient Binomial : problème compréhension 11-03-10 à 23:27

Bonsoir.

OK, j'ai bien compris l'erreur que j'ai faite. Effectivement, on peut choisir un Y avec 0 élément, un Y avec 1 élément, etc ...

Donc au final, et non sans peine, j'ai ENFIN réussi à comprendre

Merci encore pour votre aide qui m'a été très précieuse, et merci pour votre patience

Bonne soirée

Posté par
lafol Moderateurre : Dénombrement Coefficient Binomial : problème compréhension 12-03-10 à 18:40

avec plaisir


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