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.
Best Answer
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}$