# Combinatorics Problem - Tiling to cover length $n$

Suppose you have $$4$$ types of tiles: blue dominoes, blue monominoes, red dominoes and red monominoes. Find the generating function for the number of ways of lining up tiles to cover length n such that:

a) no further restriction

b) all blue tiles, if any are before all red tiles.

My work. For part a), when I worked it out by actually sketching the possible combinations, I cancelled out the ones that would essentially be the same. For example, if $$n=3$$ there are three ways in which the board will be all blue which is $$3x$$ monominoes, and 2 tilings where theres $$1x$$ monomino and $$1x$$ domino, however since they all make the board all blue, wouldn't it simplify to being 1 combination? If I do this indefinitely, wouldn't this give me the generating function for the Fibonacci sequence?

For part b), I'm not too sure how to start this.

• We have the generating function of the Fibonacci sequence for one color tiles and no restriction. See my answer below. – Robert Z Oct 26 '18 at 5:57
• An expanded version of this question, with at least one answer, can be found here: math.stackexchange.com/questions/2974255/… – awkward Oct 31 '18 at 12:31

Hint. In a strip $$1\times n$$ we can arrange $$0\leq k\leq n/2$$ dominoes. Let $$x_i\geq 0$$ be the number of monominoes, to be put between the $$i$$-th domino and the next one, for $$i=0,\dots,k$$. Then $$x_0+x_1+\dots+x_k=n-2k$$ and, by Stars and Bars, the number of the non-negative integer solutions of the above equation is $$\binom{n-k}{k}$$. The total number of tiles is $$k+(n-2k)=n-k$$.
a) It follows that the number of ways of lining up these blue or red colored tiles and to cover the strip $$1\times n$$ is $$a_n=\sum_{k=0}^{n/2}\binom{n-k}{k}2^{n-k}.$$ The first terms are $$1,2,6,16,44,120,328$$. Note that here we obtain the Fibonacci numbers if we replace $$2$$ (the number of colors) with $$1$$.
b) Similarly to a), the number of ways of lining up these colored tiles where all blue tiles, if any, are before all red tiles is $$b_n=\sum_{k=0}^{n/2}\binom{n-k}{k}\cdot ?.$$ where $$?$$ is a factor to be found. The first terms are $$1,2,5,10,20,38,71$$.