Non inscrit a écrit:salut!
Que veux-tu dire par : "Mais pour l'instant, je ne trouve pas de formule de longueur fixe." ?
Ma formule n'est pas de longueur fixe, puisqu'elle contient p+1 termes et que p est variable. J'espérais trouver un truc du genre 3^(n+p)/p! (je dis n'importe quoi !) qui est une formule de longueur fixe : 1 terme quel que soit n et p... J'ignore si une telle formule existe pour ton problème.
Non inscrit a écrit:De toutes manières, en inversant les rôles de p et n, ça marche tout aussi bien.
Ah oui ? Je n'ai pas eu le temps de vérifier !
Non inscrit a écrit:Si tu pouvais m'expliquer ta démarche, ce serait merveilleux.
Bon ! J'appelle H un mouvement horizontal, V un mouvement vertical, D un mouvement diagonal.
Je compte d'abord le nombre de chemins sans mouvement diagonal. Il faut placer p mouvements verticaux et n mouvements horizontaux. On peut modéliser un chemin par une suite de p lettres V et de n lettres H. Si l'on liste toutes les façons d'arranger p lettres V et n lettres H on obtient tous les chemins sans diagonale. De plus, deux suites différentes correspondent forcément à deux chemins différents. Donc il y a exactement autant de façons de ranger p lettres V et n lettres H que de chemins sans diagonale. Pour fabriquer une de ces listes, il suffit de choisir p emplacements dans n+p pour les lettres V les n emplacements restants étant pour les lettres H. Donc leur nombre est C(n+p,p) soit (n+p)!/[p!n!].
Supposons à présent que l'on cherche à savoir le nombre de chemins avec i diagonales. Comme une diagonale "mange" un déplacement vertical et un déplacement horizontal, il ne restera que p-i déplacements verticaux et n-i déplacements horizontaux. Pour faire cette sous-configuration (sans les lettres D) de n+p-2i lettres H et V, on a (n+p-2i)!/[(p-i)!(n-i)!] façons de la faire. Ensuite il faut placer les i lettres D parmi ces n+p-2i lettres H et V. Il y a (n+p+i)!/[(n+p-2i)!(i!)] façons de le faire. Donc le nombre de configuration avec i diagonales est :
(n+p-2i)!/[(p-i)!(n-i)!] * (n+p+i)!/[(n+p-2i)!(i!)]
soit
(n+p+i)!/[(p-i)!(n-i)!(i)!]
On note que la formule devient la première formule trouvée ci-dessus si l'on choisit pour i la valeur 0.
Comme il y a 0, 1,...p-1 ou p diagonales on tombe finalement sur la formule :
Somme (pour i=0 jusqu'à i=p) de (n+p-i)!/[(n-i)!*(p-i)!*i!]
Tout bien réfléchi, je ne pense pas que l'on puisse échanger le rôle de p et n dans la formule car :
"Somme (pour i=0 jusqu'à i=n) de (n+p-i)!/[(n-i)!*(p-i)!*i!]"
n'aurait pas de sens si n>p car on aurait des factorielles négatives. Il faut donc bien choisir la formule Somme (pour i=0 jusqu'à i=p) de (n+p-i)!/[(n-i)!*(p-i)!*i!] avec n>=p !
