We have given $n$ and $k$ we want to count all sequences of length $n$, each element in the range $[1, k]$ such that no two adjacent elements are equal, plus the first and the last elements should be different, in other words the sequence is circle.
For example $n=4, k=2$, there are two possible orderings: $\{1,2,1,2\}$, $\{2,1,2,1\}$.
My try: Let's say $f(x)$ is the number of such sequences of length $x$ with fixed $k$.
We can see that $f(x) = k \cdot (k-1)^{x-1}$, but on this way there might be cases where the first and the last elements are equal, so we should subtract those cases from $f(x)$, now I cannot come up with formula how many such sequences exist.
Let $l$ be the first element of a sequence. Let's denote by $a_n$ the number of such sequences that also end with $l$, while $b_n$ shall be the number of such sequences that do not end in $l$. (I'm only ever talking about sequences that fullfill the 'no adjacent elements are equal' rule). We get
$$ f(n) = k \times b_n $$
as there are $k$ possible values for $l$ and the sequences counted by $a_n$ are exactly those that have the same first and last element, which we don't want. Also, it is easily seen that $a_1=1$ and $b_1=0$.
Further, we have for $n \ge 1$ $$a_{n+1}=b_n,$$ as there is a 1-1 correspondence between a sequence ending in $l$ of length $n+1$ and a sequence not ending in $l$ of length $n$: Just remove the last element of the former.
If we remove the last element of a sequence of length $n+1$ not ending in $l$, there are two possibilites: The (new) last element can be $l$ or something else.
Any given sequence of length $n$ ending in $l$ will be obtained this way in exactly $k-1$ ways (any of the $k-1$ non-$l$ values could have been removed).
Any given sequence of length $n$ not ending in $l$ will be obtained this way in exactly $k-2$ ways (the last element of the $n+1$-length sequence could have been anything except $l$ and the last element of the $n$-length series).
This leads to
$$ b_{n+1} = (k-1)a_n + (k-2)b_n$$
Using the above, we get $$ b_1=0, b_2=k-1,$$ $$ b_{n+2} = (k-2)b_{n+1} + (k-1)b_n$$.
This is a recurrence relation with constant coefficients, the usual methods lead to the following formula:
$$ b_n = \frac{k-1}k\left((k-1)^{n-1} - (-1)^{n-1}\right)$$
(if you don't know about those methods, you can just prove the formula using mathematical induction).
To get the final answer, we multiplay with $k$ and get
$$ f(n) = (k-1)\left((k-1)^{n-1} - (-1)^{n-1}\right) = (k-1)^n +(k-1)(-1)^n$$