23 *. There are $k$ colors. In how many ways can the sides of a given regular $n$-gon be painted so that adjacent sides are painted in different colors (the polygon cannot be rotated)?

## $10-11$ grades
66.23. Let's denote this number of ways by $x_{n}$. Then, as we can see, $x_{1}=0, x_{2}=k(k-1)$ and for any $n$ the relation $x_{n}=(k-2) x_{n-1}+(k-1) x_{n-2}$ holds. Indeed, let's paint the sides from the first to the $(n-2)$-th. The number of such colorings, in which the color of the $(n-2)$-th side does not match the color of the first side - $x_{n-1}$, and the $(n-1)$-th side can then be painted in one of $k-2$ colors. The number of colorings in which the color of the $(n-2)$-th side matches the color of the first side is $x_{n-2}$, and the $(n-1)$-th side can then be painted in $k-1$ colors. From the proven relation, by induction, it follows that

$$
x_{n}=(k-1)^{n}+(k-1)(-1)^{n}
$$