1
$\begingroup$

Find a recurrence relation for the number of ways to make a pile of $n$ poker chips using red, white, and blue chips and such that no two red chips are together (consecutive).

My workings:

Consider the color of the top chip, if it is red, then he one below cannot be red and the remaining $n-2$ chips give $a_{n-2}$ different ways.

If it is not red, then the remaining $n-1$ chips give $a_{n-1}$ different ways. Then I believe my recurrence relation is

$$a_n = 2a_{n-1}+2a_{n-2}$$

My questions are the following:
1) are my workings correct?
2) should this be for n>2
3) is $a_1=3, a_2=8$ and why?

$\endgroup$

1 Answer 1

1
$\begingroup$

1) and 2) seem correct.

is $a_1=3, a_2=8$ and why?

  • If you have two poker chips you have 8 ways to make a pile without two consecutive red chips: $wb,bw,rw,wr,rb,br,ww, bb$. Or you calculate all possible ways and substract the $rr$ combination: $a_2=3^2-1=8$
  • Similar for $a_1$: The are 3 ways without two consecutive red chips: $r,b,w\Rightarrow a_1=3$
$\endgroup$
5
  • $\begingroup$ thanks for your detailed answer! $\endgroup$
    – user104
    Mar 4, 2018 at 17:07
  • $\begingroup$ @user104 You´re welcome. $\endgroup$ Mar 4, 2018 at 17:07
  • $\begingroup$ is there a $a_0$ term? $\endgroup$
    – user104
    Mar 4, 2018 at 18:32
  • $\begingroup$ @user104 No.You cannot make a pile of $0$ poker chips. $\endgroup$ Mar 4, 2018 at 18:34
  • $\begingroup$ good point haha was hoping since now I am trying to solve this recurrence relation $\endgroup$
    – user104
    Mar 4, 2018 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.