Consider a finite grid, suppose points a and b have positive x and y components ,and a has coordination of (x1,y1) and b has coordination of (x2,y2) and we want to go from a to b, how many possible paths exist if our movement is just going up and going right?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|||||||||||
|
|
I assume you mean for this problem to deal only with integer coordinates and also $x_1 \leq x_2$ and $y_1 \leq y_2$ (otherwise, one cannot move only up and right). Let $x = x_2 - x_1$ and $y = y_2 - y_1$ (the horizontal and vertical distance between the points). We can imagine a path from the two points as a binary string of with exactly $x$ 0's and exactly $y$ 1's, where we interpret a 0 as "move right" and a 1 as "move up". Notice the string has total length $x+y$. To form such a string, we need only pick the locations for the 0's and then fill the remaining locations with 1's. That is, we choose exactly $x$ locations (without order) out of the total $x+y$ locations, which can be done in $\binom{x+y}{x}$ ways. |
|||
|
