Enumeration de chemins

[sur]

Bonjour, pourriez vous m'éclairer à propos de la question 2 de ce problème concernant les coefficients binomiaux, merci bien

"On considère l'ensemble des chemins dans le plan qui partent de l'origine O et qui sont constitués de pas (1;1) et 1;-1) uniquement.

1) Calculer le nombre de tels chemins ayant n pas.
2) Calculer le nombre de tels chemins ayant n pas et qui finissent sur l'axe (Ox).
3) Calculer le nombre de tels chemins ayant n pas et qui se finissent sur l'axe (Ox), mais qui en plus ne passent jamais sous cet axe."

J'ai déjà résolu la 1), pour la 2), j'en ai seulement déduit que le nombre de chemins k, et le nombre de pas n doivent être pair....

Merci d'avance

[Ben314]

Salut,

Le 2), c'est simple : parmi les 2^n listes de n éléments choisis parmi "Haut" ou "Bas", il faut que tu ait pris autant de "Haut" que de "Bas" (donc n/2) pour revenir a la hauteur du point de départ donc la réponse, c'est le nombre de façon de disposer les n/2 "Haut" parmi les n "cases" de la liste
Et c'est pas con de généraliser en se demandant combien il y a de chemin dont le point final est (n,k) pour un k donné, en particulier vu que ça va (un peu) te servir pour la question 3.

Par contre la 3) c'est sacrément "chaud" sans indications (surtout si déjà la 2. te pose problème...)
J'ai pas trop le temps là de rentrer dans les détails, mais cherche sur le net un truc du style "principe de réflexion pour les marche aléatoires de dimension 1" (*) et regarde si tu trouve un trucs simple (le principe est extrêmement simple sauf... qu'il faut y penser...)

(*) Ça a peut-être un nom style "théorème de machin" (ou "de Untel"), mais c'est pas sûr et de toute façon, je le connais pas...

[pascal16]

vu aussi au Capes externe de math 2015 2nd épreuve Exercice 2 partie B

pour finir sur l'axe, il faut aller autant de fois vers le haut que vers le bas.
donc n pair
c'est donc une question d'arrangements de n/2 chiffres 1 parmi n chiffres

Le chemin toujours positifs sont :
ceux qui commencent par +1 et qui ne coupent pas l'axe...

[sur]

Merci pour vos réponses ! Ça m'a aidé à y voir plus clair, je vais co,tinter à travailler dessus

[nodgim]

Pour autant que j'ai pu calculer le 3) avec un tableur, ça ressemble à une suite géométrique dont la raison tend vers 4 par défaut.

[Ben314]

Normalement, c'est comme pour la 2) et sa généralisation aux nombre de chemins qui "arrivent" en (n,k), à savoir un simple coefficient binomial.
Sauf que pour comprendre pourquoi, c'est pas complètement évident.
L'astuce, c'est de dire que partant d'un chemin qui part de (1,1) (et pas de (0,0)), qui arrive en (n,0) et qui croise au moins une fois l'axe des x, tu peut en fabriquer un autre en prenant le même "début" de chemin jusqu'au premier point d'intersection avec l'axe des x (il peut y en avoir plusieurs) puis tu prend le symétrique (par rapport à Ox) de la partie restante du chemin.
Ensuite, y'a plus qu'à constater que "l'opération" en question réalise une bijection de A={l'ensemble des chemin de (1,1) à (n,0) coupant au moins une fois l'axe des x} sur ensemble B={l'ensemble des chemin . . . }
Or le cardinal de B est facile à calculer.

[nodgim]

Et donc au final, pour le 3), ça donne quelque chose comme C(2n,n) / (n+1) si je ne m'abuse.

[Ben314]

Ça dépend :
Comment tu interprète le "...ne passent jamais sous cet axe" :
(1) y>0 pour tout x sauf x=0 et x=n
ou
(2) y>=0 pour tout x ?

Je pencherais pour le (2), c'est à dire en considérant que la phrase de départ est "...ne passent jamais strictement en dessous de l'axe", mais c'est discutable.

[nodgim]

Pour moi, c'est parfaitement clair, "ne passe jamais sous l'axe" sous entend que les chemins qui passent pas l'axe conviennent. Maintenant, on peut effectivement considérer les chemins qui passent au dessus de l'axe : Dans ce cas, ce ne sera pas difficile à déduire à partir du scénario précédent.

[chan79]

Et donc au final, pour le 3), ça donne quelque chose comme C(2n,n) / (n+1) si je ne m'abuse.

J'ai ça aussi, si tous les points du chemin ont une ordonnée supérieure ou égale à 0.

[nodgim]

@Chan79: t'es sûr ? C'est presque ça, mais pas tout à fait, je crois.

Sinon, il faudra bien maintenant justifier cette formule.....

[chan79]

@Chan79: t'es sûr ? C'est presque ça, mais pas tout à fait, je crois.

Sinon, il faudra bien maintenant justifier cette formule.....

je vais y regarder de nouveau

[Ben314]

Si on cherche les chemins de (0,0) à (n,0) tels que y reste positif ou nul tout le temps, il faut un peu adapter ce que j'ai écrit au dessus :
Si un chemin C ne respecte pas pour tout x alors il existe un plus petit x tel que le chamin passe par (x,-1) et on peut considérer le chemin C' obtenu en échangeant tout les Haut<->Bas qui suivent le (x,-1), ce qui revient à faire une symétrie par rapport à la droite y=-1 sur toute la fin du chemin (tout ce qui est après (x,-1)).
Le nouveau chemin C' obtenu va de (0,0) à (n,-2) (symétrique de (0,0) par rapport à y=-1).
Réciproquement, si on part d'un chemin quelconque C' de (0,0) à (n,-2) il passe forcément par des points (x,-1) et si on peut considérer le plus petit tel x et procéder à la même symétrie qu'au dessus pour obtenir un chemin C de (0,0) à (n,0) contenant au moins un point (x,y) avec y<0.
Il est clair que ces opérations sont des des bijection réciproque l'une de l'autre ce qui montre qu'il y a autant de chemins de (0,0) à (n,0) contenant au moins un y<0 qu'il y a de chemin de (0,0) à (n,-2).
Or pour qu'il existe de tels chemins il faut bien sur que n soit pairs et il faut ensuite qu'il contienne n/2-1 fois "Haut" et n/2+1 fois "Bas" et il y a donc Binom(n,n/2-1) possibilités.
Comme il y a au total Binom(n,n/2) chemins de (0,0) à (n,0), celà signifie qu'il y en a Binom(n,n/2)-Binom(n,n/2-1) = Binom(n,n/2)/(n/2+1) chemins de (0,0) à (n,0) tels que y soit positif ou nul en permanence :
n=2 -> 1
n=4 -> 2
n=6 -> 5
n=8 -> 14
. . .

[nodgim]

J'ai une preuve plus courte, sans utiliser les symétries.

[Ben314]

J'ai une preuve plus courte, sans utiliser les symétries.

Te gène pas : donne.
Ça m'intéresse d'autant plus que cette "astuce" d'utiliser les symétries, si on ne l'a jamais vu, ben c'est... sacrément astucieux...

P.S. S'il y en a qui veulent plus de détail concernant cette histoire de symétrie (qui semble s'appeler le "principe de réflexion") il y a par exemple ça :
http://www.bibmath.net/dico/index.php?a ... rutin.html

[nodgim]

On peut modéliser un chemin de 2n déplacements par un code binaire (1: vers haut; 0: vers bas) et quand il faut arriver au bout de 2n déplacements à y = 0, il faut un code qui ait n fois 1 et n fois 0 (d'où C( 2n, n ) sans aucune contrainte).
Un chemin qui passe sous le 0 correspondant à un surnuméraire d'un 0 ( comme 11000...). Or ce qu'il reste comme bits après ce zéro surnuméraire, c'est un surnuméraire d'un 1 (il reste un nombre impair de bits). S'il reste 2k+1 bits, il y a k+1 "1" et k "0", et le nombre de combinaisons correspondant est C(2 k+1, k+1). Mais, si on remplace un "1" par un "0", ça donnera le même nombre de combinaisons. Et remplacer un "1" par un "0", c'est fabriquer un code de C (2n, n-1). Or tout code de C(2n, n-1 ) possède à son tour toujours un surnuméraire d'un "0". Il y a donc autant de codes "échec" de C(2n, n) que de code C(2n, n-1).
CQFD

[Ben314]

O.K., mais en fait c'est exactement la même chose :
Lorsque tu dit "si on remplace un 1 par un 0, ça donnera le même nombre de combinaisons" ça signifie qu'il y a autant de "chemins" 01100... avec k+1 1 et k 0 qu'il y en a avec k 1 et k+1 0 et pour le moment tu exprime uniquement le fait qu'il y en a le même nombre, mais si tu veut aller à peine plus loin et donner une bijection explicite entre les deux ensembles pour justifier ce "même nombre", ben la première qui vient à l'esprit, c'est clairement de remplacer les 1 par des 0 et vice versa ce qui correspond très exactement au "principe de réflexion" consistant à prendre la symétrie de toute la fin du chemin à partir du premier endroit où on est passé en dessous de la droite y=0.

Ca peut éventuellement être une autre façon de trouver que la bonne idée, c'est le "principe de réflexion", mais je sais pas si, fondamentalement, c'est plus facile de "trouver l'astuce" en partant de ce principe là (ça dépend surement des personnes...)

[nodgim]

Oui, j'ai bien vu la similitude des 2 preuves, l'une étant la variante de l'autre. Disons que la preuve par la symétrie est plus imagée, et que la variante est plus déductive. C'est très proche en fait.

[chan79]

Salut
J'avais fait, pour aller de (0,0) ) (2n,0) :

nombre de chemins de (1,1) à (2n,0) - nombre de chemins de (1,1) à (2n,-2), avec la méthode du "principe de réflexion" déjà expliquée.
Ce qui m'étonne, c'est l'efficacité de wolfram qui propose la bonne suite (nombres de Catalan) si on met le début , soit: 1 2 5 14 42

A noter que le nombre de Catalan Cn est le nombre de chemins monotones le long des arêtes d'une grille
à n × n carrés, qui restent sous (ou au niveau de) la diagonale. C'est le cas ici.

[sur]

Bonjour,

Merci encore pour vos réponses, j'ai continué à réfléchir à ce problème or pour la deux je ne vois toujours pas comment m'y prendre...