1
$\begingroup$

Suppose I have a an ixj grid (i rows, j columns)

From the bottom left, to the top right, you may only move UP or RIGHT, how many paths are there from A to Z.

In this case, you must go up twice, right thrice, so my options are ^^>>> which gives $\frac{5!}{(3!2!)}$ arrangements. or in the general case, $\frac{(i+j-2)!}{((i-1)!(j-1)!)}$ arrangements.

In the 3x4 case, that gives us 10 paths.

However, when I tried to look at the choices per node, and add them up, I got a different answer. Meaning, The first node has 2 choices, the moment you reach the top or right side, you have no more choices.

So if I add up the total choices, that would be 6? Similar discrepancies arise when I try larger grids.. however I always reach the correct answer with the combination method of ^^^^>>>> (which is a more mathematically sound one to me anyway) but I just wanted to get some insight on what is wrong in this situation.

Thank you.

$\endgroup$
0
$\begingroup$

It might be helpful to think of a coordinate system to stay on top of things.

2x3 grid:

02 12 22 32

01 11 21 31

00 10 20 30

The possible paths are:

10 20 30 31 32

10 20 21 31 32

10 20 21 22 32

10 11 21 31 32

10 11 21 22 32

10 11 12 22 32

01 11 21 31 32

01 11 21 22 32

01 11 12 22 32

01 02 12 22 32

10 paths in total.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.