There are $n$ students around the table. They all have an empty paper.
Let a set $S$ be $S=\left\lbrace 1,\omega,\omega^2 \right\rbrace$.
Each students take only one element in $S$.
But the product of two arbitrary consecutive students is not $1$.
Count all possible cases.
I tried to use relation between $n$-th term and $(n+1)$-th term, but failed.
I counted directly $n = 1, 2, 3, 4, 5$. Then the number of cases are
$3, 6, 8, 18, 32$.
But, I want to solve the problem generally.
Please help me. Thank you.
($\omega$ is a root of $x^2 + x + 1 = 0$)
The answer is $2^n+1+(-1)^n$. Given the simplicity of this answer, there's probably a simple way to get to it, but I had to take a lengthy route.
Consider students in a line (not a circle – we'll get to that), starting with a 1. Let $r_n$ be the number of lists of length $n$ ending in 1, $s_n$ the number ending in $\omega$, $t_n$ the number ending in $\omega^2$. We get the system $r_n=s_{n-1}+t_{n-1}$, $s_n=r_{n-1}+s_{n-1}$, $t_n=r_{n-1}+t_{n-1}$. So $$\pmatrix{r_n\cr s_n\cr t_n\cr}=\pmatrix{0&1&1\cr1&1&0\cr1&0&1\cr}\pmatrix{r_{n-1}\cr s_{n-1}\cr t_{n-1}\cr}$$ That matrix has eigenvalues $2,1,-1$, so $r_n=A(2)^n+B+C(-1)^n$ for some real constants $A,B,C$. The initial values are $r_2=0$, $r_3=2$, $r_4=2$ (e.g., the two sequences of length 4 beginning and ending with 1 are $1\omega\omega1$ and $1\omega^2\omega^21$), so we get $A=1/6$, $B=0$, $C=-2/3$. We get similar formulas for $s_n$ and $t_n$, as they satisfy the same recurrence, but with different initial values ($s_2=1$, $s_3=1$, $s_4=3$, likewise for $t_n$).
Then you do the same thing for sequences starting with $\omega$, and then for sequences starting with $\omega^2$. Then, you add them all up, leaving out the sequences starting and ending with 1, the sequences starting with $\omega$ and ending with $\omega^2$, and the sequences starting with $\omega^2$ and ending with $\omega$ (thus leaving out the lines that can't be closed up to a circle), and what comes out is the formula at the top of this answer.