total path in 3*3 grid

Question

If a person can move only in east and south direction. What are the total number of paths from initial point (0,0) to final point (2,2) in a 3*3 grid

Answer 1

You take 4 steps total. Choose exactly 2 of those steps to be eastward.

Answer 2

Depends on how you define your problem. Here are 3 first ways, that pop into my head.

Vector space problem

1) From point A(0, 0) to point B(2, 2) create a vector AB(B_x-A_x, B_y-B_y). This vector exists in affine space and we will introduce custom coordinate axis of "south" and "east" to it. So we get the vector to be `AB = 2 "south" + 2 "east".

To find what are the possible paths: Permutations[{"south", "south", "east", "east"}]

{{"south", "south", "east", "east"}, {"south", "east", "south", "east"}, {"south", "east", "east", "south"}, {"east", "south", "south", "east"}, {"east", "south", "east", "south"}, {"east", "east", "south", "south"}}

To find the length of them: Length[Permutations[{"south", "south", "east", "east"}]]

6

Algebraic problem

2) Reduce the problem to algebraic form. That is a combinatorial problem, where binomial coefficient 4 choose 2 will give the answer, because you can do 2 different actions total of 4 times.

To calculate: Binomial[4, 2]

6

Graphing problem

3) make a graph:

Then conclude, there are only 6 ways to do it

Answer 3

Explanation: We can encode the way by just storing the steps in the downwards-direction. That, is, we encode just the columns we choose to go one step down:

E.g. 0 1 1 3 means, we go as follows:

 0123      = columns 

 v         v = down
 >V        > = right
  v>v
    X

So, we have n lines (thus n-1 steps downwards) and in each step we can choose among m possibilities (as long as these possibilities are monotonly increasing).

Thus, we can "a priori" choose n-1 column-numbers from the m columns in total, sort them and take them as our way through the grid.

Thus, this experiment corresponds to drawing n-1 elements from a set with m distinct elements, and the order of the elements drawn does not matter (because we just consider them in increasing order). Thus, the total number of possibilities to do this is:

/ n-1+m-1 \
|         |
\   n-1   /

I realized that my first post contained the wrong details but the idea was the same. Have a look at stars and bars too see how the idea works.