relationship between pascal's triangle and number of combinations? I was able to solve a classic algorithm question, robot paths by using pascal's triangle (PT). This is where a robot starts in the upper left corner and can only go down or right.  I kind of reverse engineered the solution - I knew that the answer for a 4 by 4 grid is 20, which is the middle element on line 7 of PT.  I checked for a 5 by 5 grid and saw that it is on line 9 of PT. Is there an established proof/equation between getting the possible paths for a 4x4 grid and line 7(middle element) of Pascal's triangle? Math is not my strong suit so the more detailed you can explain the better...
 A: The number of paths for a $4 \times 4$ grid is the sum of the numbers of paths for a $3 \times 4$ grid and for a $4 \times 3$ grid, and similarly in other cases where the number of paths is the sum of the numbers for grids one smaller in each dimension.
Pascal's triangle can be constructed the same way, by summing two numbers from the row above.
A: Assume you are going from $(0,0)$ to $(m,n)$
The path length must be $m+n$ according to your settings
the number of ways is $m+n \choose m$
For example, if you go from $(0,0)$ to $(5,3)$, you must move 8 steps and 5 of them moving down and the remaining 3 moving to the right.
Such a path can be encoded by DDDRRRDD
(or any possible codes with 5D's and 3R's)
In this case, the number of ways is $8 \choose 5$ or  $8 \choose 3$.
i.e. Out of the 8 steps, you fill 5 of them to be D, then the remaining must be R.
So, you can check in the Pascal triangle for the corresponding value.
In your setting, the upper left corner is (1,1)
so, subtract the number of $m$ and $n$ above by 1
