Finding the number of possible ways to 'paint' a geometry Problem:

Find the number of possible ways to paint $n$ sectors of a disk with $n$ color brushes to differentiate all $n$ sectors. (i.e., you cannot paint an adjoining sector with the same color)
  

It's simple labor when n is small, but I can't find a general way of solving this for any $n$
... Thanks in advance
 A: We shall solve a (slightly) general problem: We find the number of circular sequences or necklaces (identical up to rotation) with $n$ elements and $k$ colors such that no two neighboring elements are equal (In a circular sequence, we consider first and last terms to be neighbors of each other).

Lemma Let $f(k,m)$ be the number of circular sequences (rotations are considered different) of length $m$ with entries from $\{1,2,\dots , k\}$ such that no two neighboring terms are equal is given by the recurrence relation, $$f(k,m)=(k-1)f(k,m-2)+(k-2)f(k,m-1)$$ and the initial conditions,
$f(k,1)=k, f(k,2)=k(k-1), f(k,3)=k(k-1)(k-2)$


*

*If $m-1$ th entry is same as the first entry: we can fill the last
entry in $k-1$ ways and the initial part of the sequence of length
$m-2$ in $f(k,m-2)$ ways as the $m-2$ th entry cannot be same as the
first entry.

*If the $m-1$ th entry is not the first entry: we can fill the last
entry in $k-2$ ways. The initial part of length $m-1$ can be filled
in $f(k,m-1)$ ways.


Solving the recursion yields, $$f(k,m)=(-1)^{m+1}+(k-1)^m+k(-1)^m$$
when $m>3$ and $k>2$.

We shall consider the action of the group $\mathbb{Z}_n$ over the set of necklaces (as in the lemma). We shall use Burnside lemma to count the number of distinct (identical up to rotation) circular sequences. Let $|C(R_m)|$ be the number of necklaces fixed (that look identical to the start position) after $m$ rotations (say clockwise). For $m=1$, $|C(R_1)|=0$ as neighbors are distinct. For $m=2$ and $n$ is even, $|C(R_2)|=k(k-1)$ as the circular sequence is $2$-periodic (A circular sequence is said to be $p$-periodic if $a_i=a_{(i+p)\mod n} \quad \forall \, 0\le i\le n$ and $1\le p\le n-1$ is the smallest number with the property). If $n$ is odd, $|C(R_2)|=0$ as the sequence is $1$-periodic ($a_0=a_{n-1}$ and so on).
To compute $|C(R_m)|$: Let $n=qm+r$. The sequence has to repeat after $m$ rotations. The patch that repeats should have property stated in the lemma. If $r=0$, we get the simplest case. Here, $|C(R_m)|=f(k,m)$.
If $r\ne 0$, we have a cascading set of possibilities. Let $a_0,a_1,\dots a_{n-1}$ be the circular sequence 'read' clockwise from some arbitrary start point. We have $a_i=a_{(i+r)\mod n}\quad \forall \, 0\le i\le n-1$. (I might sound terse here. Please construct an example alongside as you read this). Hence, the sequence repeats after $r$ rotations if $r|n$.
We define a new function,
$$g(k,m,n):=
\begin{cases}
f(k,m) \quad \text{ if } m|n  \\
g(k,r,n) \quad \text{ if }m\nmid n
\end{cases}
$$
where $r$ is the remainder left when $m$ divides $n$ and $g(k,1,n)=0$
The required sum,
$$\frac{1}{|\mathbb{Z}_n|}\sum_{i=1}^{n}|C(R_i)|=\frac{1}{n}\left(\sum_{c=2}^{n} g(k,c,n) \right)$$
edit: except when $n=1$, there are $k$ different colorings.
The OEIS sequence is here. The sequence for $k=n$ (one corresponding to the question above) is here.
