I cannot give you a recursive solution. But can give a counting solution.
If we have chips then maximum number of blue chips is .
Then the count is .
(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.
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 be the number of acceptable arrangements with n poker chips. We know
[1] and
[2] .
Now suppose we have a stack of n+1 chips, where . 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 . 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 ways.
Hence
.
Together with [1] and [2], this is enough to find for any n.