Exercise 877Combinatorics › Counting principlesL1Added 3 Nov 2026

Coloring problems

#coloring#product rule#recurrence

Statement

In how many ways can we color $n$ squares in a row with $k$ colors such that no two adjacent squares share a color?

Hint

First square has $k$ choices; each subsequent has $k-1$ .

Show solutionHide solution

Product. First square: $k$ choices. Each of the remaining $n-1$ squares: $k-1$ choices (must differ from the previous).

Total. $k(k-1)^{n-1}$ .

Conclusion. $k(k-1)^{n-1}$ colorings.