# Bijective proof for the chromatic polynomial of a cycle

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!

• Are you sure this is the correct formula? For example for $n=4$ and $k=2$, let the colours be $0$ and $1$ then $0101$ and $1010$ are the only possible necklaces but your formula gives $(4-1)^2+(4-1) = 9 + 3 = 12$. I think your $n$ and $k$ maybe the wrong way around in your formula. – PJF49 Aug 10 '17 at 23:35
• I've removed mentions of "necklaces" from your post. The term "necklace" means one is identifying up to rotation and the term "bracelet" means one is identifying up to rotation and reflection. – Trevor Gunn Aug 10 '17 at 23:36
• @PJF49 You're correct, the formula should be $$(k - 1)^n + (k - 1)(-1)^n.$$ See the wiki page for chromatic polynomials for more info. – Trevor Gunn Aug 10 '17 at 23:38
• @PJF49 and Trevor Gunn thank you both for clarifying that. I checked my reading and it was incorrectly written there. I have revised my post above. – Twiss013 Aug 11 '17 at 0:18

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.

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}$$

(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.