Monomers and p-mers

**lpd** · September 4th 2010, 06:29 AM

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)!!

**undefined** · September 4th 2010, 07:43 AM

Originally Posted by lpd

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.)

**lpd** · September 4th 2010, 07:53 AM

for part d), is there any difference in between the recurrence of n and p?

but thanks for the detailed reponse. really appriciate it!

**undefined** · September 4th 2010, 07:57 AM

Originally Posted by lpd

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.

**lpd** · September 5th 2010, 02:18 AM

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?

**undefined** · September 5th 2010, 05:41 AM

Originally Posted by lpd

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}|

Thread: Monomers and p-mers

LinkBack

Thread Tools

Display

Monomers and p-mers

Search Tags