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