# Recursive definition construction

1. Jul 15, 2011

### dystplan

The problem statement, all variables and given/known data
Construct a recursive definition for the following:

The number of ways to stack n red, white, green, and blue poker chips so that there are no two consecutive blue poker chips.

The attempt at a solution
The number of possible combinations is $4^n$ minus the number of combinations that involve at least two blue poker next to each other.
The number of combinations with blue poker chips next to each other for the first 6 steps is:
3 chips: BBB + BB* (x3 other chips) + *BB (x3 other chips) = 7
4 chips: BBBB + BBB* (x2 x3) + BB** (x3 x3 x3) = 34
5 chips: BBBBB + BBBB* (x2 x3) + BBB** (x3 x3 x3) + BB*** (x4 x3 x3 x3) + BB*BB (x3) = 145
6 chips: BBBBBB + BBBBB* (x2x3) + BBBB** (x3x3x3) + BBB*** (x4x3x3x3) + BB**** (x5x3x3x3x3) + BB**BB (x4x3x3) + BB*BBB (x2x3) = 1+6+27+108+405+36+6 = 589

$X1 = 4$
$X2 = (4)(4) -1 = 15$
$X3 = 4^3 - 7 = 57$
$X4 = 4^4 - 34 = 222$
$X5 = 4^5 - 145 = 879$
$X6 = 4^6 - 589 = 3507$

I'm fairly sure those are correct, but I can't see any recursive function

Last edited: Jul 15, 2011
2. Jul 15, 2011

### Dick

That's not really very 'inductive'. Why don't you try to split the number of ways to stack into ways that end in blue and ways that don't end in blue and write an inductive step for each separately?

3. Jul 15, 2011

### dystplan

You mean something like:
X1 = 4
X2 = 12 + 4 = 16;
x3 = 48 + 4*4 = 64
x4 = 192 + 4*4*4 = 256

X1 = 4
Xn = X(n-1)*4 + 4^(n-1)

The problem is that I don't see any correlation with the rate at which exclusions occur due to consecutive blue poker chips. 0, 1, 7, 34, 145 (unless I'm doing something wrong to get to that, but I don't think I am).

4. Jul 15, 2011

### Dick

No, I mean let B(n) be the number of ways to legally stack n chips ending in blue. Let N(n) be the number of ways that don't end in blue. Can you write B(n+1) and N(n+1) in terms of B(n) and N(n)? That would be recursive.

5. Jul 15, 2011

### dystplan

I get
B(1) = 1
B(2) = 3
B(3) = 12
B(4) = 36
B(5) = 171
B(6) = 648

I still don't see any way that's recursive =[ This problem has been driving me nuts all day.

Where X represents any chip but B:
5 stack:
XXXXB x 81 possibilities
BXBXB x 9 possibilities
BXXXB x 27
XBXXB x 27
XXBXB x 27

6 stack:
XXXXXB x 243
XBXBXB x 27
BXXXXB x 81
XBXXXB x 81
XXBXXB x 81
XXXBXB x 81
BXBXXB x 27
BXXBXB x 27

6. Jul 15, 2011

### Dick

The problem isn't asking you to count them. Suppose you KNOW B(n) and N(n). Can you write B(n+1) and N(n+1) in terms of those. That's all.

7. Jul 15, 2011

### dystplan

The only way I know to discover B(n+1) is to have a starting place and identify a pattern to progression. I understand that the question isn't asking me to count them, but how can I calculate the recursion without a base set that indicates a recursive relationship?

Last edited: Jul 15, 2011
8. Jul 18, 2011

### Dick

Start with a chip pile in B(n) so it ends in blue. How many ways can you add another chip? Are the resulting piles in B(n+1) or N(n+1)? Now repeat the exercise for a chip pile in N(n).