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 (;-)) ?

  • 2
    $\begingroup$ For $n=2$ you should get $7$ possibilities. $\endgroup$ – Thomas Andrews May 14 '13 at 16:33
  • $\begingroup$ Hint: Try to find a recursion. $\endgroup$ – vadim123 May 14 '13 at 16:34
  • $\begingroup$ When you say "possibilities", can you be more specific? Are you talking about the different possible combinations of colors? Does order matter? $\endgroup$ – rurouniwallace May 14 '13 at 16:34
  • $\begingroup$ Order doesn't matter $\endgroup$ – khernik May 14 '13 at 16:35
  • 1
    $\begingroup$ The bigger blocks can be one of six colors. If the colors don't matter, why have them in the problem? @khernik $\endgroup$ – Thomas Andrews May 14 '13 at 16:39

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.


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.


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} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.