Results 1 to 6 of 6

Math Help - Monomers and p-mers

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    Monomers and p-mers

    Hi I need help with this question.

    A monomer is a square. A -mer is a rectangle (ie. adjacent squares). Let be the set of tilings of the -board by monomers and -mers.

    First consider monomers and trimers. Thus, representing the tilings by words there are six tilings of the -board by monomers and trimers. ie. , and .

    where represents a monomer and a trimer.

    a) if is a word in , let and . Write down an equation relating , and .
    I know how to do this one.
    &


    where represents the length of the word, and represents the length of the tilings.

    rearrange and let .
    Sub it into , and we get
    therefore,

    b) Use the equation in a) to conjecture (but do not prove) a binomial summation form for . Give a brief justification for the form of the binomial coefficients.

    I'm not quite sure about this one. But here it goes.


    I don't know how to justify it. Can I say the word representing a tiling of a n-board has k "t"s and length is n-2k. It is the number of ways of chossing k position from the length for the letter "t" in the word. For e.g. if n=6, k=2, there is only one way of rearranging the word.

    c) Generalise a) and b) to the tilings of the n-board by monomers and p-mers.
    Going by what I have above (assuming its correct):
    &





    where represents the word of the -mer, , represents the length of the p-mer. i.e if (trimer, in a)) we can produce the same equation from c) as well.



    d) Write down a recurrence relation for with initial values,. Gice a brief justification (ie. the idea of a proof not the whole proof) for your recurrence.

    I'm really stuck on this question. Does it have somethings to do with Fibonacci numbers? I'm not sure, because there are so many unknown variables.

    Thanks for your help. Really need help with d)!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    Hi I need help with this question.

    A monomer is a square. A -mer is a rectangle (ie. adjacent squares). Let be the set of tilings of the -board by monomers and -mers.

    First consider monomers and trimers. Thus, representing the tilings by words there are six tilings of the -board by monomers and trimers. ie. , and .

    where represents a monomer and a trimer.

    a) if is a word in , let and . Write down an equation relating , and .
    I know how to do this one.
    &


    where represents the length of the word, and represents the length of the tilings.

    rearrange and let .
    Sub it into , and we get
    therefore,

    b) Use the equation in a) to conjecture (but do not prove) a binomial summation form for . Give a brief justification for the form of the binomial coefficients.

    I'm not quite sure about this one. But here it goes.


    I don't know how to justify it. Can I say the word representing a tiling of a n-board has k "t"s and length is n-2k. It is the number of ways of chossing k position from the length for the letter "t" in the word. For e.g. if n=6, k=2, there is only one way of rearranging the word.

    c) Generalise a) and b) to the tilings of the n-board by monomers and p-mers.
    Going by what I have above (assuming its correct):
    &





    where represents the word of the -mer, , represents the length of the p-mer. i.e if (trimer, in a)) we can produce the same equation from c) as well.



    d) Write down a recurrence relation for with initial values,. Gice a brief justification (ie. the idea of a proof not the whole proof) for your recurrence.

    I'm really stuck on this question. Does it have somethings to do with Fibonacci numbers? I'm not sure, because there are so many unknown variables.

    Thanks for your help. Really need help with d)!!
    It's clear from context but they should still tell you an n-board is a 1xn-board. Also I think the question inventor should say that |w| means the length of a word and |w|_t means the number of t's in the word, even though it's guessable from context.

    Your (a) looks good.

    I'll use uppercase L since lowercase looks like 1.

    For (b), the number k ranges from 0 to floor(n/3). When k = 0 there is only one way to order the letters. When k = 1 there are L ways to arrange the letters. When k = 2 there are C(L,2) ways to arrange the letters. Etc. So I get

    \displaystyle |T_{n,3}| = \sum_{k=0}^{\lfloor\frac{n}{3}\rfloor}\binom{n-2k}{k}

    which is the same as you got not counting the stray "=" sign.

    Part (c) your letters get a bit mixed up. No need to call x the length of the polymer because that's already specified as p in T_{n,p}; and I would just use the letter k as before to reduce confusion. And I think you switched the minus sign to plus, I get

    \displaystyle |T_{n,p}| = \sum_{k=0}^{\lfloor\frac{n}{p}\rfloor}\binom{n-(p-1)k}{k}

    Part (d). I have another issue with this problem. Are they interested in going from |T_{n,p}| to |T_{n+1,p}| or to |T_{n,p+1}|? I'll assume the first.

    Seems there should be a straightforward way, but since they don't place any restrictions on your recurrence, you could just write

    |T_{1,p}|=1

    \forall n>1:|T_{n,p}| = |T_{n-1,p}| + (|T_{n,p}|-|T_{n-1,p}|)

    \displaystyle = |T_{n-1,p}|+ \sum_{k=0}^{\lfloor\frac{n}{p}\rfloor}\binom{n-(p-1)k}{k} - \sum_{k=0}^{\lfloor\frac{n-1}{p}\rfloor}\binom{n-1-(p-1)k}{k}

    Obviously it is justified by part (c). This satisfies what the question asks and in my opinion should be marked as correct. (Assuming I haven't made any mistakes leading up to it.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    for part d), is there any difference in between the recurrence of n and p?

    but thanks for the detailed reponse. really appriciate it!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    for part d), is there any difference in between the recurrence of n and p?

    but thanks for the detailed reponse. really appriciate it!
    The main difference would be that the initial condition would not be 1, but rather would be based on n according to part (c). (It simplifies to 2^n.) Otherwise we can proceed as above, just replacing p with p-1 instead of replacing n with n-1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    Oh, I see. I think the question is asking me to find a recurrence relative for n in respect to the set.

    I'm still having trouble to writing out the "idea" of a proof for part d). I can see how |T_{n-1}| cancels out. But why is that the case?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    Oh, I see. I think the question is asking me to find a recurrence relative for n in respect to the set.

    I'm still having trouble to writing out the "idea" of a proof for part d). I can see how |T_{n-1}| cancels out. But why is that the case?
    Q: What do you need to add to |T_{n-1}| in order to get |T_n|?

    A: |T_n| - |T_{n-1}|
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum