2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – PJF49 Aug 10 '17 at 23:35
  • $\begingroup$ 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. $\endgroup$ – Trevor Gunn Aug 10 '17 at 23:36
  • 1
    $\begingroup$ @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. $\endgroup$ – Trevor Gunn Aug 10 '17 at 23:38
  • $\begingroup$ @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. $\endgroup$ – Twiss013 Aug 11 '17 at 0:18
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.