Math/CS question for you guys...

[FrogDog]

I've been working on this for a couple hours and can't figure it out.

Say you have a 2D grid (one that looks like excel) and it is NxN. The number of columns = the number of rows. What I have to do is count the number of unique paths that you could trace out to go from the bottom left cell, (1, 1), to the top right cell (N, N). You can only move up and to the right.

There must be a way of calculating this but I can't get it. Doing them by hand is a huge pain and very confusing. For a 2x2 grid the answer is obviously just 2. For a 3x3 it's 6 and for a 4x4 I'm pretty sure it's 20. Is there a pattern here...?

Thanks

 

[upsciLLion]

I'm going to assume you meant, "go from the bottom top cell, (1, 1), to the bottom right cell (N, N)." Secondly, the definition looks recursive to me. There isn't much to go off of with only 3 values given, but the pattern seems to be something like 2^n + (n-2)^2. I could easily be wrong, though. 🙂 I hope that helps.

ups

 

[FrogDog]

Originally posted by: upsciLLion
I'm going to assume you meant, "go from the bottom top cell, (1, 1), to the bottom right cell (N, N)." Secondly, the definition looks recursive to me. There isn't much to go off of with only 3 values given, but the pattern seems to be something like 2^n + (n-2)^2. I could easily be wrong, though. 🙂 I hope that helps.

ups

No, I did mean bottom left to top right. It's weird how it's labeled, but the bottom left cell is (1, 1) and the top right is (n, n). Sorry for any confusion.

 

[upsciLLion]

I suppose it doesn't really matter. Orientation doesn't AFAIK affect equations like that.

<edit> Congrats on 4000 posts. 🙂 </edit>

ups

 

[TuxDave]

TuxDave to the rescue once again....

Here's an easy way to calculate it. For an N by N grid, you need to get to the top by moving N-1 rights and N-1 ups, and you can do that in any order. So for your 3x3 grid, you can go RRUU, or RURU or even URUR. Get it now? It's a combinational problem. So use your <blank> pick <blank> knowledge to fill in the rest.

 

[upsciLLion]

You're right. He has to have N-1 rights and N-1 ups, but order matters so it'd be a permutational calculation instead of a combinational one, right? I've only had one probability class, and it was taught by a Chinese guy that can't speak English very well. 😕

ups

 

[TuxDave]

I actually liked my probability professor. He was a goofy man that talked about his kids instead of about probability. And he had this policy that if he made a mistake and someone pointed it out to him, he would have to give him a quarter. Easy way to make laundry money.

Oh... as for your question, I never understood what was called what, combination/permutation. I just know which formula is appropriate in each situation.

 

[FrogDog]

Thanks a lot, TuxDave.

And I think it is combinations instead of permutations..

 

[upsciLLion]

Originally posted by: TuxDave
I actually liked my probability professor. He was a goofy man that talked about his kids instead of about probability. And he had this policy that if he made a mistake and someone pointed it out to him, he would have to give him a quarter. Easy way to make laundry money.

Oh... as for your question, I never understood what was called what, combination/permutation. I just know which formula is appropriate in each situation.

RRUU = RURU = UURR is an example of combinations. It's just 2 rights and 2 ups.

RRUU != RURU != UURR is an example of permutations (where != means does not equal, for those not in the know 😉). Permutations mean that the order of the selected objects is significant.

ups