total path in 3*3 grid

If a person can mo开发者_开发技巧ve 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

---

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

---

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

---

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.

---

We must go 2 times east and 2 times south. No meter in which order. Let's define east as 1 and south as 0. Then question is equal to how many ways we can write string with length 4, which has two 1-s and two 0-s (for example 1100 or 1001 etc...).

It is equal to Binomial(4,2)=6.

Proof: Assuming, that south=0 and east=1 here are all 6 ways:

1100

1010

1001

0110

0101

0011