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

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 number of 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\;.$$