# Colouring a $n\times n$ grid with $3$ colours

Let $$n$$ be a natural number divisible by $$3.$$ Let there be a $$n\times n$$ grid. You have three colours, say red, green, and blue. How many ways are there to colour the grid such that each row has $$\frac{n}{3}$$ cells of each colour and each column has $$\frac{n}{3}$$ cells of each colour?

I think I have been able to solve this for the $$3\times 3$$ case. Each valid permutation of the first row of a $$3\times 3$$ grid gives rise to two valid colourings of the grid. There are $$6$$ valid permutations of the first row. So, there are $$12$$ ways to colour a $$3\times 3$$ grid such that each row and each column has exactly $$\frac{n}{3}$$ cells of each colour. Is this right?

I am thinking of generalising this approach to solve the full question. Let $$n=3k.$$ Then, there are $${{3k}\choose{k}}{{2k}\choose{k}}$$ valid permutations of the first row. My thinking is, the number I'm looking for is some integer multiple of this number. I'm thinking something like $$n-1,$$ (since in the $$3\times 3$$ case, each valid permutation of the first row gave rise to $$3-1$$ valid colourings) but I'm not able to prove it. Of course, this is assuming that my approach and answer to the $$3\times 3$$ case is correct.

How to solve this question?

Possible off-topic question: What is a good way to develop combinatorial intuition? For some reason, I feel like I'm missing a small thing that turns this question from hard to easy. How does one train their brain to think combinatorially?

• Ok, then I'll do it. Also, 12 is the correct answer for n=3. There is 6 ways for the first row. Then there are 2 ways to complete the first column and after that the rest of the board fills up uniquely. Commented Jul 6, 2023 at 13:19
• Note that $k!^3{{3k}\choose{k}}{{2k}\choose{k}}=n!$, and any permutation of the columns of a valid solution results in a valid solution. However, for larger $n$ there could be identical columns, so there is no guarantee that the total number of solutions is a multiple of $n!$. I don't see any obvious way to count the solutions, and am not even sure there is a straightforward formula for it. Commented Jul 6, 2023 at 13:27
• Here is a possible ballpark figure. Put the rows in independently, which can be done in $(n!/((n/3)!)^3)^n$ ways. Treat the columns as independent random sets. Each has a chance of $(n!/((n/3)!)^3)/3^n$ of being correct. That gives $(n!)^{2n}/((n/3)!)^{6n}/3^{n^2}$. Using Stirling, that would be about $3^{n^2-n}/(2\pi n)^{2n}$ Commented Jul 6, 2023 at 13:47
• Note that if you get $n$ rows and $n-1$ columns, you get the last for free.
– Eric
Commented Jul 6, 2023 at 14:46
• I finished my code. @MikeEarnest, I fixed it. Now I too get the result 35 599 500 for the $6\times6$ table. I still don't understand why it should be divisible by the number you were talking about, even though it is. EDIT: I do now... Commented Jul 7, 2023 at 3:43

Too long for a comment, but here is what I could figure out.

I will refer to the three colors as $$0,1,$$ and $$2$$.

Let $$T_n$$ be the number of colorings of a $$(3n)\times (3n)$$ grid. We know that $$T_1=12$$.

Let us say that a coloring is "standard" if the first row and column consist of $$n$$ zeroes, followed by $$n$$ ones, followed by $$n$$ twos. Let $$t_n$$ be the number of standard colorings. For example, $$t_1=1$$, because the only standard $$3\times 3$$ coloring is $$\begin{bmatrix}0&1&2\\1&2&0\\2&0&1\end{bmatrix}$$

Lemma: For all $$n\ge 1$$, $$T_n=t_n\cdot \frac{(3n)!}{(n!)^3}\cdot \frac{(3n-1)!}{(n-1)!\cdot (n!)^2}$$

Proof: Note that $$\frac{(3n)!}{(n!)^3}$$ gives the number of ways to label the first row with $$n$$ zeroes, ones, and twos. Then, $$\frac{(3n-1)!}{(n-1)!\cdot (n!)^2}$$ gives the number of ways to fill out the remaining $$3n-1$$ entries in the first column. Therefore, to prove the lemma, we just need to give a bijection which takes in a standard coloring, a labeling for the first row, and a labeling for the rest of the first column, and returns an arbitrary coloring.

Let $$S$$ be a standard coloring, let $$R$$ be a coloring of the first row, and let $$C$$ be a coloring of the first column, such that $$R$$ and $$C$$ assign the same color to the top left entry. First, permute the columns of $$S$$ so that the first row of $$S$$ is colored like $$R$$. There are multiple ways to this, so to be precise, choose the permutation which preserves the order of any columns with the same topmost entry. Similarly, permute the $$3n-1$$ rows of $$S$$ besides the top row, in order to match the column coloring of $$C$$, while preserving the order of rows with the same leftmost entry. What remains is an arbitrary coloring. Since this process is reversible, this is a bijection. $$\square$$

This lemma is helpful because standard colorings are easier to enumerate by backtracking. Using this, myself and donaastor found that $$t_2=13185$$, so $$T_2=35599500$$. However, finding $$t_3$$ is beyond the capabilities of my computer.

Neither $$1,13185"$$ nor $$1,35599500"$$ returns any hits in OEIS. However, the related problem of balanced binary colorings of a $$(2n)\times(2n)$$ grid has an OEIS entry: https://oeis.org/A058527.

### Approximation

Let $$\Omega$$ be the set of ways to color a $$(3n)\times (3n)$$ matrix with three colors, where we only require all of the rows to be balanced. This means $$|\Omega|=\binom{3n}{n,n,n}^{3n}$$ Now, imagining sampling an element from $$\Omega$$ uniformly at random, and consider the probability of the event that all columns also happen to be balanced. If we could compute this probability, $$p$$, exactly, we would be able to compute $$T_n$$, since $$p=T_n/|\Omega|$$. I guess that $$p\approx \left(\binom{3n}{n,n,n}/3^{3n}\right)^{3n-1}$$ The reasoning is as follows. For each column index, $$i$$, let $$E_i$$ be the event that column number $$i$$ is balanced. It is exactly true that $$P(E_i)=\binom{3n}{n,n,n}/3^{3n}$$, because each column is equally likely to be any of the $$3^{3n}$$ ternary sequences. The events $$E_1,\dots,E_{3n}$$ are highly dependent. For example, if $$E_1,\dots,E_{3n-1}$$ all occur, then $$E_{3n}$$ automatically occurs. However, if we approximate the first $$3n-1$$ events as being independent, we are led to the value above. This suggests $$T_n\approx \binom{3n}{n,n,n}^{6n-1} 3^{-3n(3n-1)}$$ For example, this gives $$T_1\approx 10.6$$, which is quite close to $$T_1=12$$. Next is $$T_2\approx 1.524\times 10^7$$, which is about $$60\%$$ smaller than the true value of $$T_2=35599500$$. However, I cannot quantify the error of this approximation for larger $$n$$.