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!
Best 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\;. $$