Coloring a $3\times n$ board using $3$ colors

I have been reading about Combinatorial Material for a while now.

I also solved a few examples. However am stuck at this one.

Find the total number of ways a $3 \times n$ board can be painted using $3$ colors while making sure no cells of the same row or the same column have entirely the same color. The answer must be computed modulo $10^9 + 7$.

I saw the solutions to $3 \times n$ using colors but all these had the constraint that no adjacent cells were to have the same color. There's no such constraint here.

So am just not sure how to do this given the center row can have a bunch of options as well.

Thanks for any help.

Solution 1:

The best way is using the principle of inclusion exclusion.

There are $24^n$ ways to color the board so no columns is monochrome; $3\times 3\times 3-3$ ways to color each column, except for the three ways where that column is monochrome.

From these, we must subtract the colorings where no column is monochrome, but some row is monochrome. There are three choices for which row is monochrome, three choices for its color, then $3\times 3-1=8$ ways to fill each column. Therefore, it seems like the answer is $24^n-3\times 3\times 8^n$.

However, colorings with two monochrome rows have been double subtracted. These must be added back in. There are $\binom32=3$ ways to choose to the two rows.

• If the two rows are the same color, there are $3$ ways to choose the common color, and $2^n$ ways to fill in the rest of the board.

• If the rows are different colors, there are $3\cdot 2$ ways to color them, then $3^n$ ways to color the last cell in each row.

We are currently at $24^n-3\times 3\times 8^n+\binom32\times\Big(3\times 2^n+ 3\times 2\times 3^n\Big)$. We must now consider colorings where all three rows are monochrome. These were triple subtracted in the first step, then added back in three times in the previous step, so these need to be subtracted out again. There are only $24$ such colorings. The final answer is therefore $$ 24^n-9\times 8^n+18\times 3^n+9\times 2^n-24 $$