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.
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$.
Can you find the generating functions now?
P.S. There is a more direct approach to find these generating functions based on "unbreakable" tiles. See the chapter "Generating functions" in Concrete Mathematics by Graham, Knuth, and Patashnik. Another useful reference for g.f. is the wonderful book Generatingfunctionology by Herbert Wilf.