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 ______.

$5 \text{ persons in a circle, each gets one of } 3 \text{ colours}$

$\text{adjacent persons must have different coloured hats}$

$\text{To find: number of valid hat distributions}$

$1.\ \text{view the seats as a } 5\text{-cycle}$ $2.\ \text{fix } A\text{'s colour and count along the path}$ $3.\ \text{multiply by the } 3 \text{ choices for } A$ $\text{Fix the colour of } A: 3 \text{ ways; count for one, then}\times 3$ $u_n = \text{number of proper colourings with the } n\text{-th person same as } A$ $v_n = \text{number with the } n\text{-th person different from } A$ $u_1 = 1,\qquad v_1 = 0$ $u_{n+1}=v_n,\qquad v_{n+1}=2u_n+v_n$ $(u_2,v_2)=(0,2),\qquad (u_3,v_3)=(2,2)$ $(u_4,v_4)=(2,6),\qquad (u_5,v_5)=(6,10)$ $\text{Cycle closes with } E\neq A \ \Rightarrow\ v_5 = 10$ $\text{Total} = 3 \times v_5 = 3 \times 10 = 30$ $(k-1)^n + (-1)^n(k-1) = 2^5 - 2 = 30$ $\boxed{30}$