Un problème de dénombrement plutôt compliqué!

par **Diaz** » 14 Avr 2006, 15:33

Bonjour à tous!

Avant de commencer,j'aimerais dire un grand merci à tous ceux qui m'ont aidé pour mon concours;il est fini mercredi dernier et,grâce à vous,j'ai bon espoir qu'il sera bon:Merci beaucoup à tous!
A présent,voici un problème de dénombrement qui m'empêche de dormir:
On dispose de n cases,numérotées de 1 à n.
Dans chaque case,se trouve une boule,sur laquelle est marqué un chiffre,qui est soit +1,soit -1.
On convient de noter chif(i),le chiffre porté sur la boule de la case numéro i.
m de ces n boules portent le chiffre -1,et k d'entre elles(k étant strictement supérieur à m) portent le chiffre +1;on a donc:m+k=n.
On demande le nombre de façons dont on peut ranger ces n boules telles que:
-Pour tout i=1,...,n,la somme des chif(j),j allant de 1 à i,soit strictement positive?
-La somme des chif(j),j allant de 1 à n-1,soit strictement positive et,dans le même temps,la somme des chif(j),j allant de 1 à n,soit nulle?(ici,k=m)
Merci!

par **Zebulon** » 14 Avr 2006, 15:44

Diaz a écrit:La somme des chif(j),j allant de 1 à n-1,soit strictement positive et,dans le même temps,la somme des chif(j),j allant de 1 à n,soit nulle?

Bonjour,
n'est-ce pas la somme des chif(2j) qu'on veut nulle, pour j allant de 1 à partie entière de n?
Je suppose

Pour la première, cherche une relation de récurrence:soit i l'indice où la somme est nulle pour la première fois, combien y a-t-il de possiblités? Puis tu sommes sur i.
Bon courage,
Zeb.

par **Zebulon** » 14 Avr 2006, 15:49

Quel est ton niveau?
Zeb.

par **Diaz** » 14 Avr 2006, 15:53

Licence de Maths
Je rappelle que mon énoncé n'a pas d'erreur

par **Zebulon** » 14 Avr 2006, 16:00

Ben pour i=1, tu as forcément

!

par **Diaz** » 14 Avr 2006, 16:02

En outre,j'ai essayé cette récurrence,mais je n'ai pas pu caractériser le nombre de cas favorables,en fonction de i.

par **Zebulon** » 14 Avr 2006, 16:12

Soit

le nombre de possibilités. Soit i le premier indice tel que

, alors il y a

possibilités donc

.
Ces nombres s'appellent les nombres de Catalan. En as-tu déjà entendu parler?
Zeb.

par **Zebulon** » 14 Avr 2006, 16:36

Pour en savoir plus sur les nombres de Catalan, voici une conversation interressante :++: :
http://maths-forum.com/showthread.php?t=8702&highlight=catalan
Zeb.

PS: Quelqu'un se souvient-il de la forme explicite des nombres de Catalan? Je l'ai chez moi, mais n'étant pas chez moi, je ne la connaît pas par coeur...

par **Zebulon** » 14 Avr 2006, 16:54

C'est bon, j'ai trouvé sur internet:

.
A bientôt,
Zeb.

par **Diaz** » 14 Avr 2006, 17:00

Merci Zeb!Mais,ne pars pas encore!

par **Diaz** » 14 Avr 2006, 17:03

L'expression entre parenthèses dans ta formule donnant Cn,est-ce la notation anglo-saxonne de la combinaison de n dans 2n?

par **Zebulon** » 14 Avr 2006, 17:07

Oui, c'est ça. Tu as tout compris ou veux-tu que je détaille davantage?
Zeb.

par **Diaz** » 14 Avr 2006, 18:34

Je veux que tu détailles davantage,d'autant que j'ai l'impression que tu as mal lu la question:Peux-tu la relire?

par **Zebulon** » 14 Avr 2006, 18:39

C'est vrai, j'ai mal lu! Mince! Je croyais que c'était que pour tout j allant de 1 à n,

.

par **Diaz** » 14 Avr 2006, 18:39

Je rappelle qu'à la 1ère question,on demande le nombre de façons dont on peut ranger ces n boules de sorte que pour tout i allant de 1 à n,la somme des chif(j),j allant de 1 à i,soit STRICTEMENT POSITIVE!

par **Diaz** » 14 Avr 2006, 18:42

Je suis heureux que tu t'en rendes compte;mais,je crois que c'est de ma faute,car je ne sais pas insérer les symboles mathématiques dans mes posts;peux-tu me dire comment tu fais?

par **Zebulon** » 14 Avr 2006, 19:40

Oui, j'utilise ça:
http://fr.wikipedia.org/wiki/Aide:Formules_TeX

par **Diaz** » 15 Avr 2006, 12:55

Zebulon,on dirait que tu es le seul à t'être intéressé à mon problème de dénombrement:Merci!
Maintenant que tu t'es rendu compte de ton erreur,n'as-tu pas d'autre solution à me proposer?

par **Zebulon** » 20 Avr 2006, 05:31

En fait, ce que j'ai fait répond à cette question mais avec

pour tout i allant de 1 à n.
On fait le même raisonnement en fixant i le premier indice tel que

. Pour ranger les i premières boîtes on a alors

choix. i-3 et pas i car les deux premières doivent contenir +1 et la i-ème doit contenir -1.
Ensuite, pour ranger les m-i autres, on a

choix car la (i+1)-ième boîte doit contenir +1, donc pour i fixé comme tel, on a

choix.
Comme i peut aller de 3 à m,

soit

J'ai peut-être fait une erreur de comptage...
Si quelqu'un pouvait proposer une autre méthode...???
Voilà en tout cas ce que j'aurais fait.
Zeb.

Un problème de dénombrement plutôt compliqué!

Un problème de dénombrement plutôt compliqué!

Nombres de Catalan

Qui est en ligne