Four colors, no back-to-backs (recursive)

**jflurrie** · May 21st 2010, 03:46 AM

(I posted already that for-loop question from our exam, sorry if this comes out as flooding)

So the question was short and clear, but I can't figure out the answer.

We have four colors (blue and three others) of poker chips in a stack of n chips. In how many ways can the stack be formed so that blue chips are not directly on top of each other?

What I understood by myself:
For example with three chips the options are
1) b o b (o = other, b = blue)
2) o b o
3) o o b
4) b o o
5) o o o

Which gives us 3+9+9+9+27=57 ways.

With two chips the options are
1) b o
2) o b
3) o o

Which gives us 3+3+9 = 15 ways.

But I can't figure out any kind of formula for this.

If someone posted already similar question, a link to that thread would be nice.

**Plato** · May 21st 2010, 06:55 AM

I cannot give you a recursive solution. But can give a counting solution.
If we have $N$ chips then maximum number of blue chips is $\max = \left\lceil {\frac{N}{2}} \right\rceil$ .
Then the count is $\sum\limits_{k = 0}^{\max } {\binom{N-k+1}{k}3^{N - k} }$ .

**jflurrie** · May 21st 2010, 07:27 AM

Originally Posted by Plato

I cannot give you a recursive solution. But can give a counting solution.
If we have $N$ chips then maximum number of blue chips is $\max = \left\lceil {\frac{N}{2}} \right\rceil$ .
Then the count is $\sum\limits_{k = 0}^{\max } {\binom{N-k+1}{k}3^{N - k} }$ .

The max part is clear - if you have more than half of stack blue chips, there has to be blue chips on top of each other. On count, that 3 is the number of other colors, right?

**Plato** · May 21st 2010, 07:56 AM

Originally Posted by jflurrie

The max part is clear - if you have more than half of stack blue chips, there has to be blue chips on top of each other. On count, that 3 is the number of other colors, right?

Correct about the 3.

**awkward** · May 22nd 2010, 02:11 PM

Hi jlflurrie,

Plato has given you an excellent solution, but if I understand you correctly, you may be interested in a recursive solution, is that right?

If so let's say an arrangement is "acceptable" if no blue chips are adjacent, and let $a_n$ be the number of acceptable arrangements with n poker chips. We know

[1] $a_1 = 4$ and
[2] $a_2 = 15$ .

Now suppose we have a stack of n+1 chips, where $n \geq 2$ . The chip on top is either blue or one of the other colors. If it is blue, then the chip under it must be one of the other 3 colors, and the remaining n-1 chips can be any acceptable arrangement; so the number of arrangements with a blue chip on top is $3 a_{n-1}$ . If the chip on top is one of the other 3 colors, then the remaining n chips can be any acceptable arrangement; so this can be done in $3 a_n$ ways.

Hence
$a_{n+1} = 3 a_n + 3 a_{n-1}$ .

Together with [1] and [2], this is enough to find $a_n$ for any n.

Thread: Four colors, no back-to-backs (recursive)

LinkBack

Thread Tools

Display

Four colors, no back-to-backs (recursive)

Similar Math Help Forum Discussions

[SOLVED] Car colors

Colors

Back to back stemplot

colors

Do you know your colors?

Search Tags