-2
$\begingroup$

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?

$\endgroup$

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.

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

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: \begin{equation} 2\times\dbinom{8}{1}\times3^1\times(3^{n(n-1)}) \end{equation} 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: \begin{equation}2\times\dbinom{8}{2}\times3^2\times(3^{n(n-2)})\end{equation}

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


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: \begin{equation}2\times\dbinom{8}{3}\times3^3\times(3^{n(n-3)})\end{equation}

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


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):

\begin{equation} 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} \end{equation}

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – Mike Earnest Nov 9 '15 at 23:53
  • $\begingroup$ Thanks. I've updated my answer to include it. $\endgroup$ – Dr Xorile Nov 10 '15 at 0:40
-1
$\begingroup$

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

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

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