Given n objects, which are lying in a straight line next to each other, in how many ways we can color them with k colors (all must be painted) such that the adjacent boxes not of same colors.

I can feel that inclusion exclusion principle will apply here but I am not able to figure out where to start. Its been a while since I read about them.

  • $\begingroup$ What you want is the chromatic polynomial for the path graph. $\endgroup$ – Gerry Myerson Jan 4 at 15:58
  • $\begingroup$ I guess so. This is the chromatic polynomial as the adjacent colors have to be different $\endgroup$ – Brij Raj Kishore Jan 4 at 16:03

You can color the first box in any of $k$ colors availble to you. The second box can be colored with one of the remaining $k-1$ colors. The same is true for the third, fourth... So the total number of colorings is $k\times(k-1)^{n-1}$


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.