2 Colored blocks and towers If a tower is to be constructed with blue and red blocks, and red blocks cannot touch each other, what would the formula be to find all possible combinations for every set of blue and red blocks? Order does not matter. I've tried combinations for about 2 hours and still cannot find out how this works.
 A: There are say $r$ red and $b$ blue, and we want to make a legal tower of height $r+b$. Lay out the $b$ blue blocks in a line on the ground like this:
$$B\qquad B\qquad B\qquad  B\qquad B\qquad B\qquad B\qquad B\qquad B\qquad B\qquad B\qquad B$$
with a little space between them.
There are $b-1$ gaps between blue blocks, and two "endgaps," a total of $b+1$. We must choose $r$ of these to put a red into. That can be done in $\binom{b+1}{r}$ ways. (Of course we need $r\le b+1$.)
Now build the tower, using the blocks on the ground, from left to right.
A: Assume that we have $r$ red blocks and $b$ blue blocks. The general principle is this: stack all red blocks in a tower, and put one blue block between each pair of red blocks, i.e. the tower is $RBRBR\cdots RBR$. This is the minimal arrangement we need so that no red blocks touch teach other. We have $b-r+1$ blue blocks left to place. Note that this implies that we must have $b-r+1\geq 0$, that is $b\geq r-1$ in order to build such a tower.
Now, to fill in the blue blocks, for each block we select one of the $r+1$ spots in the tower -- either at the bottom, on top, or between any two red bricks. This means there are $(r+1)^{b-r+1}$ possibilities.
A: I'm assuming the "tower" is a string of red/blue bricks.
Let $r_n$ be the number of towers of height $n$ ending in a red brick, $b_n$ the number of towers not ending in a red brick (i.e., blue or height 0). You can set up the recurrences (a tower ending in red can only be made from a blue-ending one and a red brick; a tower ending in blue is made from a red-ending one or a blue-ending one):
$$
r_{n + 1} = b_n \\
b_{n + 1} = b_n + r_n
$$
Also $b_0 = 1$, $r_0 = 0$. we are interested in the total number of $n$-towers, i.e., $r_n + b_n$.
Define generating functions $R(z) = \sum_{n \ge 0} r_n z^n$, $B(z) = \sum_{n \ge 0} b_n z^n$. Multiply the recurrences by $z^n$ and add them up for $n \ge 0$, express in terms of $A(z)$ and $B(z)$:
$$
\frac{R(z) - r_0}{z} = B(z) \\
\frac{B(z) - b_0}{z} = B(z) + R(z)
$$
This is just a linear system:
$$
R(z) = \frac{z}{1 - z - z^2} \\
B(z) = \frac{1}{1 - z - z^2}
$$
I happen to know that those are the generating function of the Fibonacci numbers:
$$
b_n = F_{n + 1} \\
r_n = F_n
$$
The final result, the number of towers of height $n$ is:
$$
t_n = r_n + b_n = F_n + F_{n + 1} = F_{n + 2}
$$
