0

A circular disk is divided into n sectors, each shaped like a piece of pie and all meeting at the centre point of the disk. Each sector is to be painted either red, green or blue in such a way that no two adjacent sectors are painted the same colour. Let P(n) denote the number of distinct ways to paint the disk.

a) Find explicitly P(1), P(2), P(3). b) Find a recurrence relation for P(n) in terms of P(n-1) and P(n-2) for each integer n>3.

I've done part a, (3,6,6). But I'm stuck on how to approach part b. I've had trouble with finding recurrence relations in general, so a approach that I could apply in the future would also help. Thanks in advance!

Chris
  • 11

1 Answers1

1

for part $B$ look at a given coloring; select a "particular slice", there are two possibilites: the first possibility is the slices adjacent to that slice have the same color. In that case when we take away that slice and merge the other two slices into one slice we get a pie with $n-2$ slices, since there are $2$ ways to select the color of the "particular slice" there are $2P(n-2)$ valid colorings where the slice to the sides of the "particular slice" have the same color.

the other possibility is that the slices to the sides of the "particular slice" have different colors. In this case when we remove the "particular slice" we get a valid coloring of $n-1$ slices, and this coloring determines the color of the "particular slice". So there are $P(n-1)$ colorings of this type.

So the recursion is $P(n)=2P(n-2)+(Pn-1)$

Asinomás
  • 105,651
  • Ah, makes sense. Is there any particular way you approached this? How did you come up with that solution? – Chris Nov 06 '14 at 06:15
  • Well, the question hinted that it had to be a two term recurrence, so I looked at ways to split the colorings into two types which could be accounted for by using the recurrecne. – Asinomás Nov 06 '14 at 06:19
  • Right, cool. Do you have any suggestions in approaching future problems of this nature? – Chris Nov 06 '14 at 06:21
  • I guess it's just sort of a knack you get after trying lots of problems of that nature. although in general trying to seperate into different cases is good for this type of problems. – Asinomás Nov 06 '14 at 06:26