How we can proof that chromatic polynomial of cycle $C_n$ is
$$ w(x) =(x-1)^n+(-1)^n(x-1) $$
I saw algebraic proof but I am really interested in combinatoric proof of this fact
We choose random element (without lost of generality) and give him one of $x$ colour. $$ w(x) = x \cdot ... $$ Now we choose color for right neighbour on $(x-1)$ ways. And again for next right neighbour we choose in $(x-1)$ ways next color. We repeat that as long as we don't meet first vertex. So $$ w(x) = x(x-1)^n \neq (x-1)^n+(-1)^n(x-1) $$
Let us count the number of ways to color $C_n$ using $x$ colors. We let color $x$ be special, and consider all colorings of the cycles using the first $x-1$ colors. We also fix some orientation of the cycle.
Let us suppose first that not all vertices are colored using the same color. In that case, we can partition the colors into runs, each consisting of vertices colored using the same color. We switch the color of every second vertex, starting with the second, to color $x$. The resulting coloring is a valid coloring by construction. Also, this mapping is one-to-one, since we can recover the original coloring by replacing the color of each vertex colored $x$ with the color of its preceding neighbor.
If $n$ is odd then we cannot fix in this way a coloring in which all vertices are colored the same, so we get $(x-1)^n-(x-1)$ colorings. If $n$ is even then we can fix this coloring in two ways, so we get $(x-1)^n-(x-1)+2(x-1) = (x-1)^n+(x-1)$ colorings.