Building a tower using colorful blocks

Question

How many possibilities are there to build a tower of n height, using colorful blocks, where:

white block is of 1 height
black, red, blue, green, yellow, pink blocks are equal to 2 heights

I need to find the generating function formula for this.

So, for n = 1 I get 1 possibility,
for n = 2 I get 2 possibilities,
for n = 3 I get 3 possibilities
for n = 4 I get > 4 possibilities etc.

The generating function at this moment would be $1 + 2x + 3x^{2} + ...$. But I have no idea how can I find the general formula calculating this.

Could you give me any suggestions, or solutions (;-)) ?

When you say "possibilities", can you be more specific? Are you talking about the different possible combinations of colors? Does order matter? — rurouniwallace, May 14 '13 at 16:34
If n = 2, there are two empty fields. I can fill them with two white blocks, or one bigger block. So I can do this in two different manners. That's what it is about. — khernik, May 14 '13 at 16:36
The bigger blocks can be one of six colors. If the colors don't matter, why have them in the problem? @khernik — Thomas Andrews, May 14 '13 at 16:39
Well, I didn't even think about it this way...they of course are not needed :P — khernik, May 14 '13 at 16:43
For 3, if order and color don't matter, there are only two: 1+2 and 1+1+1 — Ross Millikan, May 14 '13 at 16:48

Ross Millikan · Answer 1 · 2013-05-14T16:54:50.630

It looks to me like for $n=2$ you have $7$ possibilities, either two white or one of any of the $6$ colors. Similarly for $n=3$ you can have three white, or a white and a color, or a color and a white, for $13$ possibilities.

To make the recurrence, if there are $T(n)$ ways to make a tower $n$ high, we can either put a white block on a tower one shorter or put a colored block (6 ways) on a tower two shorter, so $$T(n)=T(n-1)+6T(n-2), T(1)=1, T(0)=1$$

This can be solved by the usual techniques-find the characteristic polynomial, factor, etc.

Added: if color doesn't matter but order does, change the $6$ to $1$ above. If color and order don't matter, the only choice to make is how many $2$ size blocks to use, which can range from $0$ to $\lfloor \frac n2 \rfloor$, for a total of $1+\lfloor \frac n2 \rfloor$ ways.

Thomas Andrews · Answer 2 · 2013-05-14T17:03:25.770

An alternative approach is to note that the generating function for the number towers made out of exactly $k$ blocks of any size can be written as $$(x+6x^2)^k$$ So the total generating function must be:

$$\sum_{k=0}^\infty (x+6x^2)^k$$

which is just a geometric sequence for which a closed form can easily be found.

If you want to ignore the colors of the bigger blocks, then the generating function for exactly $k$ blocks is $$(x+x^2)^k$$ and the total generating function is $$\sum_{k=0}^\infty (x+x^2)^k$$

It turns out in this case the sequence will look familiar.

score 0 · Answer 3 · answered May 14 '13 at 23:20

Let the number of towers of height $n$ be $a_n$. To build a tower of height $n$, you start with a tower of height $n - 1$ and add a white block ($a_{n - 1}$ ways) or with a tower of height $n - 2$ and add one of 6 height-2 blocks. In all, you can write: $$ a_{n + 2} = a_{n + 1} + 6 a_n $$ Clearly $a_0 = a_1 = 1$.

Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = \frac{A(z) - a_0}{z} + 6 A(z) $$ You get: $$ A(z) = \frac{1}{1 - z - 6 z^2} = \frac{3}{5} \cdot \frac{1}{1 - 3 z} + \frac{2}{5} \cdot \frac{1}{1 + 2 z} $$ This is just geometric series: $$ a_n = \frac{3}{5} \cdot 3^n + \frac{2}{3} \cdot (-2)^n = \frac{3^{n + 1} - (-2)^{n + 1}}{5} $$

Building a tower using colorful blocks

3 Answers3