- #1
dystplan
- 13
- 0
Homework Statement
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 [itex]4^n[/itex] 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
[itex]X1 = 4[/itex]
[itex]X2 = (4)(4) -1 = 15[/itex]
[itex]X3 = 4^3 - 7 = 57[/itex]
[itex]X4 = 4^4 - 34 = 222[/itex]
[itex]X5 = 4^5 - 145 = 879[/itex]
[itex]X6 = 4^6 - 589 = 3507[/itex]
I'm fairly sure those are correct, but I can't see any recursive function
Thank-you in advance!
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 [itex]4^n[/itex] 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
[itex]X1 = 4[/itex]
[itex]X2 = (4)(4) -1 = 15[/itex]
[itex]X3 = 4^3 - 7 = 57[/itex]
[itex]X4 = 4^4 - 34 = 222[/itex]
[itex]X5 = 4^5 - 145 = 879[/itex]
[itex]X6 = 4^6 - 589 = 3507[/itex]
I'm fairly sure those are correct, but I can't see any recursive function
Thank-you in advance!
Last edited: