Find the no. of ways to color the matrix..

Question

Given a $3 \times N$ matrix and three colors $a$, $b$ and $c$. In how many ways can all the cells be colored such that no row and no column contains all the cells of same color ?

I could not reach to any logical approach to the problem .

Answer 1

For $i=1,2,3$ let $R_i$ denote the set of colourings such that the cells in row $i$ get the same color.

For $j=1,\dots,N$ let $C_j$ denote the set of colourings such that the cells in column $j$ get the same color.

Then to be found is: $$3^{3N}-|R_1\cup R_2\cup R_3\cup C_1\cup\cdots\cup C_N|\tag1$$ For this we use inclusion/exclusion combined with symmetry. First an oversight of the terms that will show up in $(1)$

$\begin{array}{cccc} \text{term in }\left(1\right) & & & \text{coefficient in (1)}\\ \left|C_{1}\cap\cdots\cap C_{k}\right|=3^{3N-2k} & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{0}\left(-1\right)^{k}\\ \left|R_{1}\cap C_{1}\cap\cdots\cap C_{k}\right|=3^{2N-2k+1} & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{1}\left(-1\right)^{k+1}\\ \left|R_{1}\cap R_{2}\cap C_{1}\cap\cdots\cap C_{k}\right|=3^{N-k+1} & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{2}\left(-1\right)^{k+2}\\ \left|R_{1}\cap R_{2}\cap R_{3}\cap C_{1}\cap\cdots\cap C_{k}\right|=3 & \text{for }k=1,\dots,N & & \binom{N}{k}\binom{3}{3}\left(-1\right)^{k+3}\\ \left|R_{1}\right|=3^{2N+1} & & & \binom{N}{0}\binom{3}{1}\left(-1\right)^{1}\\ \left|R_{1}\cap R_{2}\right|=3^{N+2} & & & \binom{N}{0}\binom{3}{2}\left(-1\right)^{2}\\ \left|R_{1}\cap R_{2}\cap R_{3}\right|=27 & & & \binom{N}{0}\binom{3}{3}\left(-1\right)^{3} \end{array}$

Working this out we finally end up with:$$18\cdot3^N+24^N-9\cdot8^N+9\cdot2^N-24\tag2$$

possibilities. Note that $(2)$ gives $0$ for $N=1$ and gives $174$ for $N=2$.

Answer 2

Here is a solution via the Principle of Inclusion and Exclusion.

If we drop the requirement on the colors of the rows and columns, there are $n=3^{3N}$ ways to color the matrix.

Let's say that a coloring of the matrix has "property $R_i$" if row $i$ is a single color for $i=1,2,3$, and say it has "property $C_j$" if column $j$ is a single color for $j =1,2,3, \dots, N$. We want to find $S_k$, the number of colorings which have $k$ of the properties, for $k = 1,2,3,\dots,3+N$. So suppose $k$ is given; then the coloring must have $r$ of the $R_i$ properties and $c$ of the $C_j$ properties, where $r \ge 0$, $c \ge 0$, and $r+c=k$. That is, there are $r$ rows each of which have the same color, and $c$ columns each of which have the same color. (I am deviating slightly from the problem statement, where $c$ was a color; I would rather $c$ be an integer.)

The $r$ rows can be chosen in $\binom{3}{r}$ ways.

The $c$ columns can be chosen in $\binom{N}{c}$ ways.

The number of ways to color the $r$ rows and $c$ columns is $$f(r,c) = \begin{cases} 3^r &\text{if } c=0 \\ 3^c &\text{if } r=0 \\ 3 &\text{otherwise} \end{cases}$$

The number of ways to color the remaining cells is $3^{(3-r)(N-c)}$.

So $$S_k = \sum_{r+c=k} \binom{3}{r} \binom{N}{c} f(r,c) \;3^{(3-r)(N-c)}$$ where it is understood the summation takes place over all pairs $(r,c)$ with $0 \le r \le 3$, $0 \le c \le N$, and $r+c=k$.

Finally, by Inclusion / Exclusion, the number of colorings with none of the properties $R_i$ or $C_j$, i.e. the number of colorings of the matrix in which no row is a single color and no column is a single color, is $$n + \sum_{k=0}^{3+N} (-1)^k S_k$$