Question

Given a 3xn board, find the number of ways to color it using at most 4 colors such that no two adjacent boxes have same color. Diagonal neighbors are not treated as adjacent boxes. Output the ways%1000000007 as the answer grows quickly.

Answer 1

Hi buddy

Here is your answer

Let’s first think how many of ways there’s exists valid colors when n = 1. For convenience, let’s encode our colors as numbers from 0 to 3. We can use 3 unique colors to form a board. It’s 3! factorial times the number of ways we can choose 3 colors out of 4 i.e. C(4, 3). Then it’s possible to make a board with only using 2 colors. The number of ways is 2: {1, 0, 1} or {0, 1, 0}. There’s exists C(4, 2) of possible combinations of this pairs. Overall, we have: 3! x C(4, 3) + 2 x C(4, 2) = 36.