# Number of ways of coloring n objects which are laid in a row with k colors such that the adjacent objects are of different colors

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.

• What you want is the chromatic polynomial for the path graph. – Gerry Myerson Jan 4 at 15:58
• I guess so. This is the chromatic polynomial as the adjacent colors have to be different – 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}$$