The general path in the grid 3 * 3

Question

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

Answer 1

You take 4 steps. Choose exactly 2 of these steps east.

Answer 2

Depends on how you define your problem. Here are the first three ways that appear in my head.

Vector space task

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

To find out what the possible paths are: 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 their length: Length[Permutations[{"south", "south", "east", "east"}]]

 6 

Algebraic Problem

2) Reduce the problem to an algebraic form. This is a combinatorial problem when the binomial coefficient 4 choose 2 will give an answer, because you can do 2 different actions just 4 times.

To calculate: Binomial [4, 2]

 6 

Graphics problem

3) make a schedule:

Then complete, there are only 6 ways to do this.

Answer 3

Explanation: We can encode the path simply by saving steps in a downward direction. That is, we only encode the columns that we select to go one step down:

eg. 0 1 1 3 means that we do the following:

  0123 = columns vv = down >V > = right v>v X 

So, we have lines n (thus, n-1 steps down), and at each step we can choose among the possibilities m (while these possibilities are monotonously increasing).

Thus, we can "a priori" select columns n-1 column-columns from columns m , sort them and take them as our path through the grid.

Thus, this experiment corresponds to a picture of n-1 elements from a set with m separate elements, and the order of the drawn elements does not matter (because we just look at them in ascending order). Thus, the total number of possibilities for this:

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

I realized that my first post contains incorrect data, but the idea was the same. Check out the stars and bars to see how this idea works.

Answer 4

We have to go 2 times east and 2 times south. No counter in what order. Let east be designated as 1 and south as 0. Then the question is how many ways we can write a string of length 4, which has two 1st and two 0-s (for example, 1100 or 1001, etc.).

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

Evidence. Assuming south = 0 and east = 1 here are all 6 ways:

1100

1010

One thousand and one

0110

0101

0011