Ways to give 3 different coloured hats to 5 people in a circle , such that no two adjacent people have same color

Question

So I have this question,

Five persons A, B, C, D and E are seated in a circular arrangement. If each of them is given a hat of one of the three colours red, blue and green, then the number of ways of distributing the hats such that the persons seated in adjacent seats get different coloured hats is _________.

What I did was , make cases. A has 3 options (RGB)

Say A gets Red

Case 1

B,E get both blue or green (2 options) leaving 2 options for C,D

Case 2

B gets Blue and E green or vice versa(2 options ) leaving 3 options for C,D

The answer comes out to be 3*2*(2+3) = 30

Is there any shorter more elegant method than manual counting

Eg:if there were more people , manual counting may become tedious , and prone to error

Answer 1

No color can be used $\geq3$ times; hence one color is used once, and the other colors are used twice. You can choose the single color in three ways and the person to obtain it in five ways. The remaining hats then can be allocated in two ways, makes $3\cdot5\cdot2=30$ in total.

Answer 2

Consider strings on the characters $A,B,C$.

For $n>1$, let $a_n$ be the number of such strings that contain no matching consecutive letters and which do not start and end with the same letter. The answer we want is $a_5$.

Method I: Consider a string of type $a_n$. The second to last character either matches the first or it doesn't. If it doesn't, then deleting the final character gives you a string of type $a_{n-1}$. If it does then deleting the final two characters gives you a string of type $a_{n-2}$. Clearly there is a unique way to extend a string of type $a_{n-1}$ to one of type $a_n$ and there are two ways to extend a string of type $a_{n-2}$ to type $a_n$ such that the second to last character matches the first. Thus $$a_n=a_{n-1}+2a_{n-2}\implies \boxed {a_n=2^n+2\times (-1)^n}$$

Method II: Let $b_n$ be the number of strings which contain no matching consecutive letters. $b_n$ is easy to count...the first character has three possibilities, thereafter there are two choices at each stage. Thus $$b_n=3\times 2^{n-1}$$

Let $c_n$ be the number of such strings that contain no matching consecutive letters and which do start and end with the same letter. Clearly we have $$b_n=a_n+c_n$$

Note that if we have a string of type $c_n$ then deleting the final letter must produce a string of type $a_{n-1}$. Conversely, given a string of type $a_{n-1}$ we can always append the first character to the end to obtain a string of type $c_n$. Thus $$c_n=a_{n-1}\implies 3\times 2^{n-1}=a_n+a_{n-1}\implies a_n=3\times 2^{n-1}-a_{n-1}$$

Starting with $a_2=6$ we quickly get $a_5=30$ as desired.

Answer 3

Do it by induction. $a_n$ are the points and $s_n$ are the number of ways.

Consider $a_n$ between $a_1$ and $a_{n-1}$. If $a_1$ and $a_{n-1}$ are different color then there is only one choice for $a_n$. So in this case we get $s_{n-1}$ number of ways.

If $n\ge 4$, and $a_1$ and $a_{n-1}$ are the same then consider $a_{n-1}$ and $a_2$. Given the color of $a_2,...a_{n-1}$ there are $2$ ways to choose $a_1$ and $a_n$, hence there are $2\cdot s_{n-1}$ ways.

So the number of ways satisfy the relation $x^2=x+2$

Now solve the eigenvalue equation and using $s_4=18$, $s_5=30$ we get $\boxed{s_n=2^n+2\cdot(-1)^n}$