2
$\begingroup$

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
    related: http://math.stackexchange.com/a/205501 (where I encouraged the OP to ask a separate question about understanding inclusion/exclusion)2012-11-08

1 Answers 1

1

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