1

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.

Mike
  • 13
  • Does the tower have a finite height? Also, in what sense does order not matter? – Ian Coley Feb 09 '14 at 01:17
  • Are we told the height of the tower, where we have an unlimited number of blocks of each type available? Or are we given a certain number $r$ of red, a certain number $b$ of blue, and we want to count all towers that use all the blocks? (There are other interpretations.) – André Nicolas Feb 09 '14 at 01:20
  • They do not have a finite height. By order does not matter, I mean that you can switch the same colored blocks and they'll still be the same kind of tower. So for 7 blue blocks and 7 red blocks, you'll have only 2 combinations. I'm not sure how to prove that mathematically, however. – Mike Feb 09 '14 at 01:20
  • I'm looking for a formula to find the number of combinations when we're given any certain set of red and blue blocks. – Mike Feb 09 '14 at 01:22
  • So like @André says, we are given a fixed number of red and blue blocks and we must use them all to build a tower? – Ian Coley Feb 09 '14 at 01:24
  • Yes. To find the # of combinations for different towers with the same fixed number of blocks. – Mike Feb 09 '14 at 01:26
  • Thank you so much everyone. Ian and Andre's were able to help me out. I could not understand Von's answer, but it might have helped too if I could. – Mike Feb 09 '14 at 02:03

3 Answers3

1

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.

André Nicolas
  • 507,029
0

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.

Ian Coley
  • 6,000
0

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

vonbrand
  • 27,812