1. ## 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 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)!!

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

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

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

but thanks for the detailed reponse. really appriciate it!

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

5. 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?

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