- #1
Townsend
- 232
- 0
There are a few areas I wanted to make sure I understand what is going on in with discrete math. I have a test tomorrow over these topics and so this is not exactly homework unless you count studying for a test as homework. In any case I will do my best to explain what I know or don't know and of course any help is appreciated.
I guess any place is a good place to start so let's start with catalan numbers. Here is an example test question
How many paths lead from the lower left hand corner to the upper right hand corner of an n x n grid with the following restrictions.
1) Only moves to the right or up are allowed.
I guess 2n choose n the total.
2) Same as 1 but in addition you must cross the diagonal running from the lower left hand corner to the upper right hand corner.
2n choose n-1 ways, I guess.
3) Same as 1 but you are allowed to touch but not cross the diagonal running from the lower left hand corner to the upper right hand corner.
This would be the total from #1 minus the bad from number 2 or
2n choose n minus sn choose n-1.
4) (a) Given a bad path in a 5 by 5 grid what is the corresponding path in a 4 by 6 gird?
This is where I get a little bit sketchy. I know that we need to reverse the direction of the path at the first place we go bad, i.e. the first place where we have crossed the diagonal line. I guess that is all I need to answer this question but I am not completely sure why this works.
(b) Given a path in a 4 by 6 grid find the corresponding bad path in a 5 by 5 grid.
To do this I guess I could just follow the path from the 4 by 6 until I find the first place I go bad and then just switch the order.
...
There are many more but something just came up so I have to leave for about an hour. I will post the remaining questions when I can get back.
Thanks
Jeremy
I guess any place is a good place to start so let's start with catalan numbers. Here is an example test question
How many paths lead from the lower left hand corner to the upper right hand corner of an n x n grid with the following restrictions.
1) Only moves to the right or up are allowed.
I guess 2n choose n the total.
2) Same as 1 but in addition you must cross the diagonal running from the lower left hand corner to the upper right hand corner.
2n choose n-1 ways, I guess.
3) Same as 1 but you are allowed to touch but not cross the diagonal running from the lower left hand corner to the upper right hand corner.
This would be the total from #1 minus the bad from number 2 or
2n choose n minus sn choose n-1.
4) (a) Given a bad path in a 5 by 5 grid what is the corresponding path in a 4 by 6 gird?
This is where I get a little bit sketchy. I know that we need to reverse the direction of the path at the first place we go bad, i.e. the first place where we have crossed the diagonal line. I guess that is all I need to answer this question but I am not completely sure why this works.
(b) Given a path in a 4 by 6 grid find the corresponding bad path in a 5 by 5 grid.
To do this I guess I could just follow the path from the 4 by 6 until I find the first place I go bad and then just switch the order.
...
There are many more but something just came up so I have to leave for about an hour. I will post the remaining questions when I can get back.
Thanks
Jeremy