Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Some discrete math questions

  1. Apr 21, 2005 #1
    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 lets 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.


  2. jcsd
  3. Apr 21, 2005 #2

    Next I need to know how to find a formula for the sequence [tex]a_n[/tex] given the recurrence relation [tex]a_n=3(n+1)a_{n-1}[/tex] and [tex]a_0=5[/tex].

    I guess [tex]a_n=5*3^{n+1}[/tex]. Can someone confirm this answer?

    One more

    Find a formula for the sequence [tex]a_n[/tex] given by the recurrence relation
    and the initial condition [tex]a_0=3[/tex].

    I tried to work this problem out but I cannot seem to find an explict formula. :confused:

    I think that is about it...I think I can handle everything else with high confidence.


  4. Apr 21, 2005 #3


    User Avatar
    Science Advisor
    Homework Helper

    Do you know about Pascal's triangle? If so, can you find it in this grid? Each number in the grid is the number of paths into that location for #1


    The elements in Pascal's triangle are the binomial coefficients, or the number of combinations of n things taken r at a time nCr
  5. Apr 21, 2005 #4
    I see it...cool...basically if you write out the triangle the row corresponds to the diagonal of the triangle starting with the left most diagonal of 1's then to the 1,2,3,4,5,6 and I so on. But what is cool is how this somehow relates the catalan numbers to the binomial coefficients. However I cannot quite make the connection yet. The catalan sequence is 1,1,2,5,14,42,132,... it really amazes me how much mileage you can get from a simple set of numbers like the fibonacci sequence.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook