Une question de denombrement

[Anonyme]

Bonsoir
j'ai une autre petite question.
on considere un repere orthonormale.
on considere le point A (n,0) et B(0,p) et C(n,p).
combien y a-t-il de chemins allant de O à C (on se déplace uniquement vers la
Droite ou vers le Haut) ?
le repere est sous forme de quadrillage!
la reponse est C(n,n+p) mais je ne comprends pas d'ou ça vient!
pouviez vous m'aider???
MERCI

[Zebulon]

Bonsoir,
tout d'abord, soyons d'accord sur un point:il faudra faire n+p déplacements (n vers la droite et p vers le haut).
Il y a bijection entre l'ensemble des chemins joignant O à C de cette sorte et l'ensemble des familles composées de n flèches vers la droites et p flèches vers le haut. Choisir les n flèches vers la droites et les p flèches vers le haut, "c'est" choisir les n flèches vers la droites et remplir les trous de la famille par des flèches vers le haut, et il y a n parmi n+p manières de les choisir. On peut faire le même raisonnement avec le choix des flèches vers le haut, et on trouve p parmi n+p. Heureusement, on sait que c'est deux résultats sont égaux! Donc le nombre de chemins joignant O et C de la sorte est n parmi n+p.
Si vous vous intéressez à ce genre de dénombrements (que notre prof appelait "chemins nord-est"), je peux vous proposer plein d'exercices!!!
Par exemple, combien y a-t-il de chemins joignant 0 à C=(n,n) en restant (au sens large) sous la diagonale? Remarquez qu'on peut voir ce problème autrement:une urne contient n boules bleues et n boules rouges;combien existe-t-il de manière de vider l'urne de telle sorte qu'on tire chaque fois une boule et qu'après chaque tirage (d'une boule), le nombre de boules bleues est supérieur au nombre de boules rouges.
Bonne soirée et à bientôt,
Zeb.

[Anonyme]

Salut Mathman,


Comme l'as dit Zebulon le plus simple c'est de voir qu'il faut n+p déplacements et que les déplacements verticaux determinent les déplacement horizontaux (et heureusement C(n+p,n) = (n+p,p) ;))

Tu peux aussi le faire par récurrence si tu préféres (tu ajoutes une ligne et tu regardes le nombre de chemin possible et tu as une "belle" somme binomiale).

[Anonyme]

merci bien zeb pour votre explication
je suis d'accord avec toi sur le fait qu'il faut n+p déplacement pour passer de O à C.mais quand meme je n'ai pas compris pourquoi le nobre de chemin possible est C(n,p+n)?
car je n'ai pas compris cette histoire de l'ensemble de familles composeé de n fleches...
est ce que vous pouvez m'envoyé le corrigé des exercices que vous m'avez proposés seulement pour le comparer à ce que j'ai trouvé.
MERCI ZEB

[Zebulon]

Bonjour,
en aidant un élève de prépa, j'ai vu qu'il avait eu un devoir sur les nombres de Catalan, et il y a aussi le corrigé en ligne:
http://mpsi.pirandello.free.fr/
C'est le DL6. C'est en gros un concentré de pas mal de choses que j'avais à vous proposer.
Amusez-vous bien!
Zeb.

[Zebulon]

je suis d'accord avec toi sur le fait qu'il faut n+p déplacement pour passer de O à C.mais quand meme je n'ai pas compris pourquoi le nobre de chemin possible est C(n,p+n)?
car je n'ai pas compris cette histoire de l'ensemble de familles composeé de n fleches...

Bonsoir,
OK, oublions un instant cette histoire de familles de flèches!

Ce qu'il faut comprendre, c'est qu'un chemin joignant O à C est entièrement déterminé par les n fois où l'on va à droite. On doit choisir n déplacements vers la droite parmi n+p déplacements au total, on a donc n parmi n+p choix.
Je ne sais pas si c'est plus compréhensible.

Je reviens à mon histoire de familles (en changeant un peu la version!):
soit l'ensemble des chemins allant de O à C par des déplacements horizontaux et verticaux comme on a déjà défini,
et soit l'ensemble des familles composées de n lettres d et de p lettres h. Je dis que et sont en bijection par l'application suivante:
je ne vais faire que donner un exemple:
prenons n=5, p=3,
soit un premier chemin: on va vers la droite, puis vers le haut, puis trois fois vers la droite, puis vers le haut, puis vers la droite, puis vers le haut,
alors on lui associerait la famille (d,h,d,d,d,h,d,h).
Un deuxième exemple: on prend le chemin:on va deux fois vers le haut, puis deux fois vers la droite, puis vers le haut, puis trois fois vers la droite, on lui associe alors (h,h,d,d,h,d,d,d). Vous comprenez le principe?

C'est clair que cette application est une bijection.
Et maintenant on se place dans l'ensemble . Quel est son cardinal? Un élément de est, par définition de cet ensemble, une famille composée de n lettres d et de p lettres h. Choisir n lettres d et p lettres h pour remplir ce truc ( , , , ,..., ) ayant n+p "trous" par n lettres d et p lettres h, c'est encore choisir l'emplacement des n lettres d, et combler les p "trous" restant par des h. Autrement dit, une fois choisis les emplacements des n lettres d, il n'y a plus de choix à faire sur les emplacements des lettres h, et la famille est entièrement déterminée! Il y a donc n parmi n+p éléments dans l'ensemble .

Comme est en bijection avec , a également n parmi n+p éléments,
donc il y a n parmi n+p chemins joignant O à C!
Youpii!

J'espère que cette fois, j'ai été plus claire. N'hésitez pas à me dire que je ne le suis pas du tout, je ne serai pas vexée. Non, non, pas du tout vexée... ...non, je ne me vexerai pas! Allez-y, tapez-moi dessus si c'était nul!
Zeb.:lol4:.