Exo dénombrement (je crois !)

[xie]

salut !

pourriez-vous m'expliquer ce qu'il faut faire dans cet exo :
on forme les mots de longueur , en utilisant les lettres abc . (par ex : bbb,aab,abc sont des mots de longueur 3 )
soit le nombre de mots de longueur contenant un nombre pair de lettres a .
calculer en fonction de .

merci !

[Zebulon]

Bonsoir,
vous préférez avoir le résultat et trouver la démonstration seul ou avoir une idée de la démonstration et trouver le résultat seul ?! :happy3:

[xie]

je préfère avoir une idée de la démonstration :we:

merci

[Zebulon]

OK ! Regardons le cas où n est pair : n=2n'.
Pour des petites valeurs de n :

1). n=2 :
soit 0 a et alors on a bb, bc, cb, cc --> 4 choix
soit 2 a et alors on a aa --> 1 choix
donc .

2). n=4 :
soit 0 a et alors soit 4 b --> 1 choix, soit 3 b --> choix, soit 2 b --> choix, soit 1 b --> combien de choix ?, soit 0 b (et à partir de maintenant, je ne donne plus le nombre de choix !)
soit 2 a (il y a façons de choisir les places des a) et alors soit 2 b, soit 1 b, soit 0 b
soit 4 a et alors 1 seul choix.

3). Cas général : n=2n' :
soit 0 a, ...
soit 2 a, il y a façons de choisir les places des a, puis ...
soit 4 a, il y a façons de choisir les places des a, puis...

soit n' a, ...

A vous de jouer ! :we:

[BQss]

salut !

pourriez-vous m'expliquer ce qu'il faut faire dans cet exo :
on forme les mots de longueur , en utilisant les lettres abc . (par ex : bbb,aab,abc sont des mots de longueur 3 )
soit le nombre de mots de longueur contenant un nombre pair de lettres a .
calculer en fonction de .

merci !

Voila le resultat:
Ne le lis pas si tu ne veux pas la reponse, mais je pense qui si tu cherches a savoir d'ou il vient tu comprendras plus de chose que si tu es guidé.

somme de k=0 a E(n/2)* de [C(2k,n) multiplié par (somme de i=0 a i=n-2k de(C(i,n-2k)) ] --> ( c'est la somme de quelquechose fois une somme, c'est en fait une double somme):
sigma(k=0-->E(n/2)) [ sigma(i=0-->n-2k) [ C(2k,n)*C(i,n-2k) ] ]

*E est la fonction partie entiere.


Maintenant ca c'est les indications sur la formule(ne le lis pas si tu veux voir d'ou elle vient tout seul):

1erement on compte le nombre de fois que l'on a de placer un nombre pair de quelquechose parmis n choix-->C(2k,n)

Puis on somme cela pour tout les nombre 2k de lettre a possible --->somme des C(2k,n) de k=0 jusqu'a partie entiere de n sur 2, la partie entiere de n/2 te permet d'obtenir quoi qu'il arrive une somme jusqu'a soit si n est pair jusqu'a n si non jusqu'a n-1 car 2*E(n/2)=n si n est pair et n-1 si n est impaire.

Maintenant il ne faut pas oublier de multiplier a l'interieur meme de cette somme chaque C(2k,n) par le nombre i de b que l'on a( C(i,n-2k) et comme il peut y en avoir n'importe quel nombre entre 0 et les n-2k restant on fait la somme de toute ces combinaisons sur i.

Le nombre de c restant ainsi que leur place est alors completement determiné car on choisit la place des a et des b pour chaque terme de la double somme et on a donc pas besoin de rajouté des elements.

[BQss]

OK ! Regardons le cas où n est pair : n=2n'.
Pour des petites valeurs de n :

1). n=2 :
soit 0 a et alors on a bb, bc, cb, cc --> 4 choix
soit 2 a et alors on a aa --> 1 choix
donc .

2). n=4 :
soit 0 a et alors soit 4 b --> 1 choix, soit 3 b --> choix, soit 2 b --> choix, soit 1 b --> combien de choix ?, soit 0 b (et à partir de maintenant, je ne donne plus le nombre de choix !)
soit 2 a (il y a façons de choisir les places des a) et alors soit 2 b, soit 1 b, soit 0 b
soit 4 a et alors 1 seul choix.

3). Cas général : n=2n' :
soit 0 a, ...
soit 2 a, il y a façons de choisir les places des a, puis ...
soit 4 a, il y a façons de choisir les places des a, puis...

soit n' a, ...

A vous de jouer ! :we:

Zebulon n'oublie pas qu'apres il faut aussi compter le nombre de manieres que l'on a de placer les b et les c restant pour les places de a. Sachant que parmi les n-2k places restantes, on peut choisir de 0 a n-2k b ou c...

[xie]

ok merci à vous deux , mais je vais essayer d'abord de comprendre avec les indications de Zebulon .

Zebulon --- je dois étudier aprés le cas de n impair ?

[Zebulon]

Sous une forme simplifiée, je trouve aussi ce résultat :

[xie]

Zebulon n'oublie pas qu'apres il faut aussi compter le nombre de manieres que l'on a de placer les b et les c restant pour les places de a.

je crois en choisissant les places des a on a implicitement choisi celles de b et c sans ordre , donc il suffit aprés de placer soit b soit c non ?

[BQss]

ok merci à vous deux , mais je vais essayer d'abord de comprendre avec les indications de Zebulon .

Zebulon --- je dois étudier aprés le cas de n impair ?

Xie le cas n impaire ou paire n'ont pas reellement d'importance. C'est juste que si tu as n paire ou impaire quand tu vas sommer tu ne vas pas sommer jusqu'a n mais jusqu'a n-1 si n est impaire.
Ce n'est qu'un detail qui apparaitras dans ton resultat finale.

Pour eviter d'ecrire deux sommes differentes.

Il suffit de dire que tu sommes des parametres 2k jusqu'a partie entiere de n/2, comme ca tu sommes jusqu'a n si n est paire et jusqu'a n-1 si n est impaire

[Zebulon]

Zebulon --- je dois étudier aprés le cas de n impair ?

Disons que si on étudie les deux cas séparément, par exemple d'abord le cas pair, le cas impair se traite de manière anlogue. C'est même immédiat une fois dès qu'on a compris la seule nuance. L'avantage de cette méthode est qu'on ne s'embrouille pas avec des parties entières.
Mais on peut le faire directement pour n quelconque. Comme vous voulez !

[Zebulon]

Zebulon n'oublie pas qu'apres il faut aussi compter le nombre de manieres que l'on a de placer les b et les c restant pour les places de a. Sachant que parmi les n-2k places restantes, on peut choisir de 0 a n-2k b ou c...

Je ne les ai pas oubliés ! On trouve d'ailleurs la même formule !

[BQss]

Je ne les ai pas oubliés ! On trouve d'ailleurs la même formule !

Oui je sais mais je veux dire quand tu les enumeres apres, je sais pas si il avait saisi que tu faisais en fait deux sommes.

[xie]

ok , merci beaucoup je vais vraiment essayer de comprendre tt ça , j'ai fait du dénombrement en première S , et je crois que je dois revenir sur qq notions pour bien comprendre ...
merci encore ..

[Zebulon]

1). n=2 :
soit 0 a et alors on a bb, bc, cb, cc --> 4 choix
soit 2 a et alors on a aa --> 1 choix
donc ..

Je l'ai fait de manière naïve pour n=2,

2). n=4 :
soit 0 a et alors soit 4 b --> 1 choix, soit 3 b --> choix, soit 2 b --> choix, soit 1 b --> combien de choix ?, soit 0 b (et à partir de maintenant, je ne donne plus le nombre de choix !)
soit 2 a (il y a façons de choisir les places des a) et alors soit 2 b, soit 1 b, soit 0 b
soit 4 a et alors 1 seul choix

j'ai expliqué quels cas regarder pour n=4 (la somme sur les i se traduit par "soit 0 b, soit 1 b, soit 2 b"),

3). Cas général : n=2n' :
soit 0 a, ...
soit 2 a, il y a façons de choisir les places des a, puis ...
soit 4 a, il y a façons de choisir les places des a, puis...

soit n' a, ...

et je laisse Xie trouver dans le cas général ! :we:

[BQss]

Sous une forme simplifiée, je trouve aussi ce résultat :

Moi j'ai ca t'es sur que c'est la meme chose?

Si oui t'as simplifié comment la somme sur les i?
Autrement dit comment tu trouves ca?
=

Je me souvenais plus que :
=

[Zebulon]

D'une manière générale, .
Vous ne connaissiez pas ce truc ?
Ici, p=n-2k.

[BQss]

D'une manière générale, .
Vous ne connaissiez pas ce truc ?
Ici, p=n-2k.

(Oui j'ai remplacé apres pour n=n-2k, c'etait deja plus clair.)
Ah oui le binome pour 1 , si si, ok.

Je pensais a un truc plus con comme un lien direct entre somme des combinaisons et cardinal de l'ensemble des parties d'un ensemble vu que card(P(E))=2^n.

C'est surtout sur la combinatoire que ca m'interesse, que en fait la somme des combinaisons vaut le nombre de partie differentes d'un ensemble. Ce qui est logique finalement en y pensant, je cherchais un lien sans passer par la formule.

i.e:
Soit A un sensemble de cardinal n.

le nombre de maniere d'en prendre 0
+
le nombre de maniere d'en prendre 1
+
.
.
.
+
le nombre de maniere d'en prendre n

vaut effectivement le nombre de maniere de prendre des parties d'un ensemble de cardinal n:

2^n qui en fait represente: 2 qui est le choix de prendre ou de ne pas prendre l'element n fois.

C'est deux manieres differentes de compter le nombre de partie de A...


en posant 1+1 dans le binome de Newton on retombe sur ce resultat...

Merci pour la simplification, ca permet de retrouver des trucs.

[Zebulon]

Je pensais a un truc plus con comme un lien direct entre somme des combinaisons et cardinal de l'ensemble des parties d'un ensemble vu que card(P(E))=2^n.

La formule vient justement du fait que puisque décrit exactement comment prendre de façon simple et systématique toutes les parties de E : .

C'est surtout sur la combinatoire que ca m'interesse, que en fait la somme des combinaison vaut le nombre de partie differente d'un ensemble.

Moi aussi, j'aime beaucoup ça. Hier, j'aidais un élève de Terminale à montrer que . Elle se montre très facilement par récurrence, mais je cherchais une interprétation combinatoire. Soit , alors , car c'est le nombre de permutations d'un ensemble à n+1 éléments privées de l'identité. Je cherche à interpréter , je veux dire par là que je cherche une façon de dénombrer qui se reflète dans la somme. Bien sûr, j'ai pensé qu'on prenait k éléments et on regardait les permutations de ces k éléments. Mais je ne vois pas pourquoi ça dénombre ...
Vous avez une idée ?

P.S. : , c'est l'ensemble des bijections des ensembles à n+1 éléments, mais je n'arrive pas à faire le S gothique...

[BQss]

La formule vient justement du fait que puisque décrit exactement comment prendre de façon simple et systématique toutes les parties de E : .


Moi aussi, j'aime beaucoup ça. Hier, j'aidais un élève de Terminale à montrer que . Elle se montre très facilement par récurrence, mais je cherchais une interprétation combinatoire. Soit , alors , car c'est le nombre de permutations d'un ensemble à n+1 éléments privées de l'identité. Je cherche à interpréter , je veux dire par là que je cherche une façon de dénombrer qui se reflète dans la somme. Bien sûr, j'ai pensé qu'on prenait k éléments et on regardait les permutations de ces k éléments. Mais je ne vois pas pourquoi ça dénombre ...
Vous avez une idée ?

P.S. : , c'est l'ensemble des bijections des ensembles à n+1 éléments, mais je n'arrive pas à faire le S gothique...

Je regarde, j'essaie de te dire si j'ai des pistes d'ici 1heure si t'es pas couché.

décrit exactement comment prendre de façon simple et systématique toutes les parties de E :

Oui tout a fait et comme ces ensembles sont evidemment disjoints on a bien:
card(P(E))= card (union_sur_k des sous ensembles de P(E) de cardinal k)=somme_sur_ k [card( du sous ensemble de P(E) qui contient tout les ensembles de cardinal k)] = somme_sur_k des C(k,n)

PS: désolé je te tutoies tu me vouvoies, si tu veux tu me tutoyer ou moi te vovoyer lol, on a pas trente ans tout les deux, et aucun de nous n'est encore au cnrs alors ...