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!

  • 1
    $\begingroup$ related: math.stackexchange.com/a/205501 (where I encouraged the OP to ask a separate question about understanding inclusion/exclusion) $\endgroup$ – 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 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\;. $$


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.