nombre de chemin de longueur donnée dans une grille

[sobriquet]

Bonjour,

Dans une grille à deux dimensions, je cherche à trouver le nombre de chemins de longueur n joignant O(0, 0) à un point M(x, y) donné.

Les déplacements possibles sont des déplacements d'une unité vers le Haut, le Bas, la Droite et la Gauche. Tous les rebroussements et les boucles sont autorisés.

Dans le cas où n = x + y, j'ai trouvé la valeur C_n^x

Dans le cas général, je n'arrive pas à trouver de réponse. Le problème revient à trouver le nombre de séquences de longueur n à partir des lettres H, B, G, D (chacune correspond à une direction) telles que :
#D - #G = x et
#H - #B = y.
(Je note # le nombre d’occurrences d'une lettre)

A partir de là, j'arrive à trouver la solution C_n^(x+n)/2 dans le cas à une dimension. Mais en deux dimensions, je sèche !

Merci d'avance
-----

[Médiat]

Bonjour,

Il y a des conditions de parité, mais en gros il faut choisir les mouvements dans le bon sens et ceux en marche arrière, dans la formule ci-dessous (à vérifier absolument, je suis allé vite) x et y sont positifs, si ce n'est pas le cas, il faut mettre des valeurs absolues

[sobriquet]

Oh, super ! Par quel raisonnement es-tu arrivé à ce résultat ?

[Médiat]

Soit la position à atteindre à partir de , avec
Soit le nombre de mouvements
Pour qu'il existe une solution, il faut :

Sinon, on ne peut atteindre la destination
Tout mouvement au delà de la destination doit être compensé par un mouvement en arrière

Posons

Les mouvements "inutiles" peuvent se répartir entre les et les


Si on impose qu'il y a mouvements "inutiles" pour (et donc mouvements pour les compenser), il y aura mouvements inutiles pour (et donc mouvements pour les compenser)


Il faut choisir les mouvements dans le bon sens pour parmi les mouvements possibles
Ensuite il faut choisir les mouvements qui compensent les mouvements inutiles précédents parmi les mouvements restants
Enfin il faut choisir les mouvements qi compense les mouvements inutiles pour parmi les mouvements possibles
(Pour les mouvements restant il n'y a plus le choix)

Soit

Et comme peut varier de à :


Soit


Une autre façon de raisonner :

On choisit les mouvements compensateurs dans les deux sens parmi les mouvements
Ensuite on choisit les mouvements compensateurs parmi les possibles qui seront dans le sens de
Enfin on choisit les mouvements dans le bon sens pour parmi les mouvements restants

Soit

[A voir en vidéo sur Futura]

[sobriquet]

ok, je comprends maintenant ! Merci de t'être penché sur le sujet !

[Médiat]

Bonjour,

En fait, on peut simplifier le résultat et ne plus avoir de somme :

On choisit x + k positions parmi les n possibles représentant les mouvements nécessaires à x et k mouvements "inutiles" (sans préciser si ces mouvements sont dans le sens des x ou des y), puis on choisit les k mouvements inutiles parmi n (donc on peut reprendre certain des mouvements précédents)
une case choisie la première fois mais pas choisie dans le deuxième, correspond à un mouvement (+x)
une case choisie dans le premier cas et dans le deuxième, correspond à un mouvement (-y),
une case choisie dans le deuxième cas, mais pas dans le premier, correspond à un mouvement (-x),
une case jamais choisie correspond à un mouvement (+y)



[EDIT] On peut d'ailleurs remarquer que en appliquant la formule de Vandermonde