# How many ways are there of coloring the vertices of a regular $n$-gon

How many ways are there of coloring the vertices of a regular $n$-gon with all $p$ colors ($n,p \ge 2$), such that each vertex is given one color, and every color isn't used for two adjacent vertices?

If in a way to color not necessarily use all $p$ colors, then the answer is $a_n=(-1)^n(p-1)+(p-1)^n\;.$

If in a way to color must use all $p$ colors, then, by using include & exclude, the answer is $\sum_{k=0}^p(-1)^{p-k}\binom pk(k-1)^n\;.$

But I do not know how to use the include/exclude to get such results. Can you explain this? Thank you!

• related: math.stackexchange.com/a/205501 (where I encouraged the OP to ask a separate question about understanding inclusion/exclusion) – joriki Nov 8 '12 at 11:58

## 1 Answer

Consider the sum

$$\sum_{k=0}^p(-1)^{p-k}\binom pka_n(k)\;,$$

where $$a_n(k)=(-1)^n(k-1)+(k-1)^n$$ is the number of colourings with at most $$k$$ colours and $$\binom pk$$ counts the ways of choosing the $$k$$ colours among all $$p$$ colours. A colouring with exactly $$r$$ colours is counted in the terms with $$k=r$$ through $$k=p$$, and it is counted $$\binom kr$$ times, once for each way of choosing $$r$$ colours from among the $$k$$ colours. Thus it contributes with coefficient

$$\sum_{k=r}^p(-1)^{p-k}\binom pk\binom kr=\delta_{pr}\;.$$

Thus we are counting each colouring with exactly $$p$$ colours with coefficient $$1$$ and each colouring with exactly $$r\ne p$$ colours with coefficient $$0$$, that is, we are counting the colourings with exactly $$p$$ colours.

Upon substituting the result for $$a_n(k)$$ given in the question, the sum is

$$\sum_{k=0}^p(-1)^{p-k}\binom pk\left((-1)^n(k-1)+(k-1)^n\right)\;,$$

and the sum over the first term vanishes, leaving

$$\sum_{k=0}^p(-1)^{p-k}\binom pk(k-1)^n\;.$$