Bijective proof for the chromatic polynomial of a cycle

Question

I was asked to give a bijective proof of the formula $$f(n,k) = (k-1)^{n}+(k-1)(-1)^{n}$$ for the number of ways of coloring a cycle of length $n$ with $k$ colors such that no two adjacent beads have the same color (different rotations and reflections are considered different).

My attempt: I've tried to place a weight function $w$ on a cycle of this form to map it into $[(n-1)^{k}+(n-1)(-1)^{k}]$ but I've been unsuccessful here. I could find two bijections, one for an even number of colors and one for an odd number, to get rid of the $(-1)^{k}$ term on the RHS, but I'd like to find a more elegant proof if possible...

I understand the Transfer-Matrix method proof of this formula but I'd like to find a bijective proof as well. I'd prefer a hint here rather than a solution if possible!

Answer 1

I think the trick here is to work backwards from your answer.

If you expand $f(n,k)$ out you get

$$f(n,k)=\sum_{r=0}^{n-1}(-1)^r\binom{n}{r}k^{n-r}+(-1)^n\binom{n}{n}k\tag{1}$$

I've added the $\binom{n}{n}$ in the last term for consistency with the following interpretation.

Hint: This looks very much like an inclusion-exclusion formula.

If you don't want the rest then please read no further.

---

Define our objects that we want to count as coloured convex $n$-gons with vertices labeled $1$ to $n$. Then define sets $A_{i,j}$ to be those containing coloured $n$-gons with adjacent vertices $i$ and $j$ equal colours.

So we have the general set intersection as the number of colourings of an $n$-gon with $r$ identical coloured pairs of adjacent vertices

$$|A_{i_1,j_1}\cap\cdots \cap A_{i_r,j_r}|=\begin{cases}k^{n-r}& r\lt n\\ k& r=n\end{cases}$$

and by the inclusion-exclusion principle $f(n,k)$ counts coloured $n$-gons belonging to none of those sets i.e. It counts coloured $n$-gons with no two adjacent equal colours.

Another interpretation, still thinking in terms of inclusion-exclusion, is to weight each of the $r$ edges of neighbouring identical coloured vertices with a $-1$. Then the weight of this n-gon is the product of these weights $(-1)^r$ and the right hand summation $(1)$ counts any particular $n$-gon with $r$ identical adjacent pairs of vertices according to each intersection of sets it belongs to, this gives the sum

$$\binom{r}{0}-\binom{r}{1}+\cdots +(-1)^r\binom{r}{r}=\begin{cases}0& r\gt 0\\ 1 &r=0\end{cases}$$

Answer 2

(This may not be the bijective proof you're looking for but it's another way of proving it.)

Hint:

If you take out any bead, then if the beads either side of the bead you took out are different you're left with a cycle of length $n-1$ with $k$ colours. If the beads either side are the same then take out one of those and you're left with a cycle of length $n-2$ with $k$ colours.

Hence $f(n,k) = (k-2)f(n-1,k) + (k-1)f(n-2,k)$ and the formula $(k - 1)^n + (k - 1)(-1)^n$ can then be proven inductively.