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 .

  • $\begingroup$ When you don't get a pattern, play with small $N$. $\endgroup$ – Teresa Lisbon Feb 4 '18 at 12:56
  • $\begingroup$ Ah, this is a difficult question. We will have to think a little more. $\endgroup$ – Teresa Lisbon Feb 4 '18 at 13:13
  • 1
    $\begingroup$ I obtained $174$ for the $3 \times 2$ case using the Inclusion-Exclusion Principle. However, it seems to me a more powerful technique (generating functions?) would be needed for the general case. $\endgroup$ – N. F. Taussig Feb 4 '18 at 14:01

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$.


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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.