I am trying to determine the number of paths between two points.
I am representing the paths as a list of steps "ruru" = right -> up -> right -> up
For my purposes, we can assume that there will never be "backwards" steps (lrlr), and we will only be working with diagonal cases (equal number of steps in each direction, ie: ulul, NOT luu)
Example: Between points (0,0) and (2,2) there are 6 different paths (uurr, urur, urru, ruur, ruru, rruu)
How would I find this value mathematically?
If it is of any help, I found this by exhaustion: 20 paths between (0,0) and (3,3), 6 paths between (0,0) and (2,2), and 2 paths between (0,0) and (1,1).
Note: I will need to be able to do this for both 2 and 3 dimensional cases. The same assumptions are true for the 3D case, I just have a 3rd variable (f and b for forward and back) a valid 3D path might look something like: furrfu. My ideal answer would be in the form "f(dimensions,numSteps) = numPaths"
Best Answer
To get from $\langle 0,0\rangle$ to $\langle m,n\rangle$ you must take $m$ steps to the right and $n$ steps up. These $m+n$ steps may be taken in any order. As soon as you know which $m$ of them are to the right, you know the whole path. There are $\binom{m+n}m$ ways to select $m$ of the $m+n$ steps to be the rightward steps, so there are $$\binom{m+n}m=\binom{m+n}n=\frac{(m+n)!}{m!\,n!}$$ possible paths.
The three-dimensional problem is similar: to get from the origin to $\langle k,m,n\rangle$ you must choose which $k$ of the steps are to the right and which $m$ are up; the remaining $n$ must be in the third direction. There are
$$\binom{k+m+n}k\binom{m+n}m$$
to make these choices, so that is the number of paths. This can be expressed more compactly as the multinomial coefficient
$$\binom{k+m+n}{k,m,n}=\frac{(k+m+n)!}{k!\,m!\,n!}\;.$$