Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.