Suppose that poker chips come in four colors red white gree

Suppose that poker chips come in four colors - red, white, green, and blue. Write a recurrence relation and initial conditions for the number of ways to stack n of these poker chips so that there are no consecutive blue chips.

Solution

Here we have to obtain the recurrence relation for the number of ways to stack n poker chips of 4 colors - red, white, green and blue..

That is, there are n pokers chips which includes chips of 4 colors - red, white, green and blue and we have to find the recurrence relation to stack these n chips.

Thus, let a_n be the number of ways of stacking n pokers chips.

That is, if we want to stack just one chip then the number of ways to do so is a₁, if we want to stack 2 chips then the number of ways is a₂ and so on.

Here we can set the initial condition as:

a₁ = 4 .

This is because, we are given chips of four colors so stack of one chip can consist of either of one chip from red, white, green or blue chip.

And obviously, a₀ = 1, because the only way to stack no chip is not to stack any of the chip, hence we have only on choice for it.

Now to start with stacking of n chips, if the top chip of stack is any non- blue chip (i.e. either red, white or green) then the number of stacking of the rest ( n - 1) chips will be a_n-1.

And with 3 color chips remaining, there are total of 3a_n-1 ways to stack n chips this manner.

Now if the first chip is blue then to avoid the two consecutive blue chips, next chip should be red, green or white. Thus, fixing blue chip at top and fixing either of one non-blue chip at next to top, there are ( n - 2 ) chips still left to be stacked.

Similarly as above, the stacking of 3 possible colors can be done in 3a_n-2 in this case.

Thus, the total number of ways in which the stacking of n chips in 3 colors can be done, is

a_n = 3 a_n-1 + 3 a_n-2

The above equation serves as the recurrence relation for the given problem with initial conditions, a₀ = 1 and a₁ = 4.