- #1
Sprooth
- 15
- 0
Hi,
I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid. For example, for the paths from (0,0) to (a,b), you can consider it to be a rearrangement of a word with a x's and b y's, so the number of paths is (a+b)! / a!b!.
The variation I would like to figure out would allow a specified number of reverse movements in addition to the movements in the proper direction. I am representing a movement to the right by "x", a movement to the left by "w", a movement upward by "y", and a movement downward by "z". If I am finding a path from (0,0) to (a,b) with c reverse horizontal movements and d reverse vertical movements, then the number of paths I have so far would be:
(a + b + 2c + 2d)! / (a+c)!(b+d)!c!d!
since the paths could be considered as a rearrangement of a word made of a+c x's, b+d y's, c w's and d z's. (a+c x's since there must be an additional movement to the right for every allowed movement to the left.
I believe this is correct so far, but now I want to prevent paths where for example it goes right, then left, then right with a net result of just going right. To do this I want to find rearrangements of the word where there are no adjacent x's and w's and no adjacent y's and z's. I began by simplifying the problem to one where only reverse horizontal movements were allowed and I would then attempt to generalize to the case with reverse movements in both dimensions. However, I got stuck even in the simpler case.
Would someone be able to help me through the simpler case (where there would be x's for going right, y's for going up, and w's for going left)? Then I will try to generalize to the other case.
Thanks for your help.
I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid. For example, for the paths from (0,0) to (a,b), you can consider it to be a rearrangement of a word with a x's and b y's, so the number of paths is (a+b)! / a!b!.
The variation I would like to figure out would allow a specified number of reverse movements in addition to the movements in the proper direction. I am representing a movement to the right by "x", a movement to the left by "w", a movement upward by "y", and a movement downward by "z". If I am finding a path from (0,0) to (a,b) with c reverse horizontal movements and d reverse vertical movements, then the number of paths I have so far would be:
(a + b + 2c + 2d)! / (a+c)!(b+d)!c!d!
since the paths could be considered as a rearrangement of a word made of a+c x's, b+d y's, c w's and d z's. (a+c x's since there must be an additional movement to the right for every allowed movement to the left.
I believe this is correct so far, but now I want to prevent paths where for example it goes right, then left, then right with a net result of just going right. To do this I want to find rearrangements of the word where there are no adjacent x's and w's and no adjacent y's and z's. I began by simplifying the problem to one where only reverse horizontal movements were allowed and I would then attempt to generalize to the case with reverse movements in both dimensions. However, I got stuck even in the simpler case.
Would someone be able to help me through the simpler case (where there would be x's for going right, y's for going up, and w's for going left)? Then I will try to generalize to the other case.
Thanks for your help.