1. ## Random walk problem

Hi there,

I'm currently studying diffusion theory and I'm hung up on a basic principle. Imagine a line that extends infinitely in either direction and in the middle is the origin. Where I'm hung up is here: say you had n moves and you wanted to know the number of paths to get to a point m units to the right of the origin and you could go left a times and right b times in one unit steps. My text gives this formula:

n!/(a!b!)
My problem is not that I don't know how to use this formula; instead, I don't understand how they arrived at this formula. Why do they use n! and why do they divide it by a!b!? Any insight into this would be appreciated.

jjmclell

2. Let's cast your problem into a 8x8 chessboard.
How many shortest paths can you take from one diagonal corner to the next?

We know the length of the shortest path is 16. (no of moves is 16)
Let the path of going up 1 square be a, and the path of going right one square be b.
So to get to the other corner, we can take a path of:
aaaaaaaabbbbbbbb
or
abababababababab
...

The number of ways you can order this is:
${16!\over {8!8!}}$

Maybe this helps.

3. So basically we're talking permutations?...it's been so long since my highschool finite math class but I think I understand what you're getting at. However I still don't understand the WHY part of the formula. From your example, I can understand n!...it's like having having 16 moves in a hat and the order in which you can draw them is 16x15x14....or 16!. I also see that because we only have two different moves, there would be paths that are replicates of each other and we want to take them out of the total number of paths. I assume that is why we divide n! by a!b! but I cannot understand why that does the trick of eliminating replicated paths. Does this make sense?...I'm probably talking like a crazy person right now but it's hard to describe my mental frustration with this problem.

jjmclell

4. Let's create another simplier analogy.
There are 3 boys and 2 girls. How many ways can you order them in a row?

BBBGG
BBGGB
BGGBB
GGBBB
GBBBG
GBBGB
GBGBB
BGBGB
BBGBG
BGBBG

There are 10 ways. Instead of listing them out, you can use the formula:
${5!}\over{3!2!}$

And the reason for dividing by 3! is to remove all instances of the case when:
B1 B2 B3 GG = B2 B1 B3 GG = B3 B1 B2 GG = ....(there are 6 such arrangements. We are interested in only 1).
Same goes for the girls.

Is this what you want? Forgive me if I am out of point.

5. Thanks a lot. I think I now understand why the formula is the way it is. Much appreciated.