# Colored stones on a chess board puzzle [closed]

We have a chess board of size n x n and there is exactly one stone on every square. We have green, blue and red stones. We must not have a row or a column full of stones of the same colour. We can omit using one of the colors. How many combinations of placing the stones are there?

## closed as off-topic by xnor, Deusovi♦, Dr Xorile, Milo Brandt, f''Nov 10 '15 at 1:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – xnor, Deusovi, Dr Xorile, Milo Brandt, f''
If this question can be reworded to fit the rules in the help center, please edit the question.

• Can we omit using two of the colors? – Engineer Toast Nov 9 '15 at 21:08
• @EngineerToast, that would have n rows and columns of all the same color. I'm sure you were being sarcastic though. – dfperry Nov 9 '15 at 21:09
• @dperry I suppose that means a 1x1 grid is disallowed. – Engineer Toast Nov 9 '15 at 21:14
• Are we to count all permutations or disregard rotations and reflections? – Engineer Toast Nov 9 '15 at 21:14
• This looks like a textbook combinatorics problem, and I see no reason for there to be a clever solution. – xnor Nov 9 '15 at 22:04

This can be done with the inclusion-exclusion principle, but it gets a little bit ugly because of the intersecting cases.

Step 1: There are $3^{n^2}$ ways of putting the coins down altogether.

Step 2: From that we need to subtract the ways of putting coins down that have at least one row or one column that are the same colour: $$2\times\dbinom{8}{1}\times3^1\times(3^{n(n-1)})$$ There's 16 rows and columns, which can each be 3 colours, and then a board of $n(n-1)$ left over.

Step 3: To that we need to add all the ways of putting coins down that have at least two rows or columns that are the same colour.

Step 3.1: Two rows or two columns: $$2\times\dbinom{8}{2}\times3^2\times(3^{n(n-2)})$$

Step 3.2: One row and one column (note they have to be the same colour): $$8^2\times3\times(3^{(n-1)(n-1)})$$

Step 4: To this we need to subtract all the ways of putting coins down that have at least three rows or columns that are the same colour.

Step 4.1: Three rows or three columns: $$2\times\dbinom{8}{3}\times3^3\times(3^{n(n-3)})$$

Step 4.2: One row and two columns or vice versa (note they have to be the same colour): $$2\times\dbinom{8}{2}\times\dbinom{8}{1}\times3\times(3^{(n-1)(n-2)})$$

Things carry on in this way for quite some time...

The tricksy thing is that the cases where there are a mixture of rows and columns of one colour, you immediately know that all the single colours rows and column are the same colour. This gives (thanks @Mike Earnest for writing this out):

$$3^{n^2}-2\sum_{i=1}^n (-1)^i\binom{n}i3^{n(n-i)+i}+\sum_{i,j=1}^n (-1)^{i+j}\binom{n}i\binom{n}{j}3^{(n-i)(n-j)+1}$$

where the first term is from step 1, the second term represents the cases where there are $i$ rows or $i$ columns, and the third term represents the cases where there are a mixture of at least 1 row and at least 1 column.

• You can the entire process as $3^{n^2}-2\sum_{i=1}^n (-1)^i\binom{n}i3^{n(n-i)+i}+\sum_{i,j=1}^n (-1)^{i+j}\binom{n}i\binom{n}{j}3^{(n-i)(n-j)+1}$. – Mike Earnest Nov 9 '15 at 23:53
• Thanks. I've updated my answer to include it. – Dr Xorile Nov 10 '15 at 0:40

$2(3)^{2n-2}$

I am assuming that n must be at least 2, otherwise the board would have a row or column of all the same color.

• Why would this be the answer? – Dr Xorile Nov 9 '15 at 23:27