I need help with this problem!

[Sneky-Bear]

Find out how many shortest routes it takes to get from one corner to the other in
a nxn square. For a 1x1 square, there are two paths. For a 2x2 there are 6 paths. For a 3x3
will it be? For a 4x4?


I found: n!*n+2 is working for n=2 and n=3 but not for and possibly not for 5 and so on

 

[R.M.]

How many "right" moves do you need? How many "up" moves do you need? Start there, and see if you can find a pattern.

 

[pka]

Consider a [imath]5\times 3[/imath]. How many ways can the string [imath]uuuuurrr[/imath] be rearranged?

 

[Sneky-Bear]

Consider a [imath]5\times 3[/imath]. How many ways can the string [imath]uuuuurrr[/imath] be rearranged?

Im sorry but im unsure on how to answer this. I know I can just count the possible paths but that would take a really long time. I know the 3x3 has 20 paths and I belive the 4x4 has 70 but further than that im unsure. I realised that n!*n+2 works for n=2 and n=3 but not for n=4. Anything else you could share that could help me? Much obliged!

How many "right" moves do you need? How many "up" moves do you need? Start there, and see if you can find a pattern.

Correct me if im wrong but for each possible path I need n right and n ups. Resulting in an nxn, but that didn't help me. But again, correct me if im missing something!

 

[Dr.Peterson]

Im sorry but im unsure on how to answer this. I know I can just count the possible paths but that would take a really long time. I know the 3x3 has 20 paths and I belive the 4x4 has 70 but further than that im unsure. I realised that n!*n+2 works for n=2 and n=3 but not for n=4. Anything else you could share that could help me? Much obliged!


Correct me if im wrong but for each possible path I need n right and n ups. Resulting in an nxn, but that didn't help me. But again, correct me if im missing something!

In order to help most effectively, we need to know something about what you have learned, and what ideas you are able to apply. If this is for school, what topics have you recently covered?

Have you learned anything about combinations and permutations? That's the direction we've been going, but it sounds like you may not be familiar with that. Yet you do know about factorials, it seems.

Can you see that any path from lower left to upper right in an nxn square can be described by a set of 2n letters consisting of n U's and n R's? So the problem is equivalent to counting ways to rearrange UUURRR (for a 3x3 square) and the like.

Have you learned a way to count those? If not, do you know a way to count ways to choose 3 places to put U's in _ _ _ _ _ _?

If none of this works for you, then there are other ways. Let us know what you can do, and we can work with that.

 

[pka]

Im sorry but im unsure on how to answer this. I know I can just count the possible paths but that would take a really long time. I know the 3x3 has 20 paths and I belive the 4x4 has 70 but further than that im unsure. I realised that n!*n+2 works for n=2 and n=3 but not for n=4. Anything else you could share that could help me? Much obliged!

There is an often used in counting theory courses. The word [imath]TENNESSEE[/imath] can be rearranged in [imath]\dfrac{9!}{(4!)(2!)(2!)}[/imath] ways.
Why divide by anything? Well if it were [imath]T_1E_1N_1N_2E_2S_1S_2E_3E_4[/imath] the subscripts make all nine letters distinct so we can rearrange them in [imath]9![/imath] ways. But no there are several identical letters: four e's, two each of s' & n's. So we divide.
Using the same idea the [imath]UUURRRRR[/imath] can be rearranged in [imath]\dfrac{8!}{(3!)(5!)}=56[/imath] ways.
The tells us that in a [imath]3\times 5[/imath] grid there are fifty-six paths moving five to the Right and three Up.

 

[Sneky-Bear]

In order to help most effectively, we need to know something about what you have learned, and what ideas you are able to apply. If this is for school, what topics have you recently covered?

Have you learned anything about combinations and permutations? That's the direction we've been going, but it sounds like you may not be familiar with that. Yet you do know about factorials, it seems.

Can you see that any path from lower left to upper right in an nxn square can be described by a set of 2n letters consisting of n U's and n R's? So the problem is equivalent to counting ways to rearrange UUURRR (for a 3x3 square) and the like.

Have you learned a way to count those? If not, do you know a way to count ways to choose 3 places to put U's in _ _ _ _ _ _?

If none of this works for you, then there are other ways. Let us know what you can do, and we can work with that.

Hey, thanks for the reply! I am very new to this area of math, I am familiar with a little bit but im mainly trying to learn more, I have picked up the faculty yea. This is as mentioned before, over my skill level. The problem itself comes from my math teacher whom I asked for a really hard problem during Easter break but I have been unable to solve it during this time. Sadly I can not expect you guys to help me understand something that is way above my level as that may require alot of prior knowledge etc. This post was more of a hail marry to see if I missed something of simpler origin.

 

[Dr.Peterson]

Hey, thanks for the reply! I am very new to this area of math, I am familiar with a little bit but im mainly trying to learn more, I have picked up the faculty yea. This is as mentioned before, over my skill level. The problem itself comes from my math teacher whom I asked for a really hard problem during Easter break but I have been unable to solve it during this time. Sadly I can not expect you guys to help me understand something that is way above my level as that may require alot of prior knowledge etc. This post was more of a hail marry to see if I missed something of simpler origin.

Thanks for giving at least a little insight into where you are (though I still don't know your grade level or what details you have learned).

As I said, this can be handled in different ways, at various levels of difficulty. Here is a collection of problems like yours (starting very simple, and getting considerably harder), with different explanations and methods. Don't expect to understand nearly all of it, but take any ideas you find useful. One of the methods there (labeling points with counts) takes little math; making a formula for the general case of a square requires more, and may not be part of what your teacher is asking for.

 

[Sneky-Bear]

There is an often used in counting theory courses. The word [imath]TENNESSEE[/imath] can be rearranged in [imath]\dfrac{9!}{(4!)(2!)(2!)}[/imath] ways.
Why divide by anything? Well if it were [imath]T_1E_1N_1N_2E_2S_1S_2E_3E_4[/imath] the subscripts make all nine letters distinct so we can rearrange them in [imath]9![/imath] ways. But no there are several identical letters: four e's, two each of s' & n's. So we divide.
Using the same idea the [imath]UUURRRRR[/imath] can be rearranged in [imath]\dfrac{8!}{(3!)(5!)}=56[/imath] ways.
The tells us that in a [imath]3\times 5[/imath] grid there are fifty-six paths moving five to the Right and three Up.

Thank you very much- this helped alot! My answer to my problem is now: (2n)!/(n!^2) which works for all n's I have tried. I cant claim to fully understand it- for example im unsure as to why you add the n's togheter for the top but I do think I understand why you devide as you do: to remove solutions that are identical, most obvious in word form. I cubical form its a little less unclear but I understand it as you remove the sulotions where you break the rules of the problem i.e go the wrong way (backwards or down). Please correct me if im wrong! Best regards,

 

[pka]

Take the word [imath]MISSISSIPPI[/imath] there are eleven letters in that string.
The number of rearrangements is [imath]\dfrac{11!}{(4!)(4!)(2!)}[/imath] .
Because there are only four distinct, we divide by those that repeat.
The consider [imath]PPQQQRRRRSSSSSTTTTTT[/imath] there are twenty letters in that string.
The number of rearrangements is [imath]\dfrac{20!}{(2!)(3!)(4!)(5!)(6!)}[/imath]
The idea works for any string, say [imath]|||XXXXXX[/imath] can rearranged in [imath]\dfrac{9!}{(3!)(6!)}[/imath] ways.
That happens to be the number of ways to put six identical objects into four distinct cells.
[imath][/imath][imath][/imath]