2

Let's say we have chess table $n^2$ and we want to put 8 rooks on the table, so that none of them are under eachother's fire.

I've come up with this: $$n^2 + n^2(n-1)+n^2(n-1)(n-2) ...$$ I think that I'm not taking into account that the pieces are indifferentiable. That means I should substract number of permutations, but how many? and is the first equation even correct?

user108078
  • 35

2 Answers2

1

You can choose $8$ rows and $8$ columns in $\binom n8^2$ ways, and then there is a standard rook placement (permutation) problem left, giving a factor $8!$. So you get $$ \binom n8^28!=\frac{n^2(n-1)^2\ldots(n-7)^2}{8!}\quad\text{solutions.} $$ This is also what you get from your method if you divide out the $8!$ ways to arrive at the same placement (given that the rooks are indistinguishable).

Marc van Leeuwen
  • 115,048
0

You have $8^2$ choices for the first rook, then $7^2$ for the second, $6^2$ for the third and so on. This gives $(8!)^2$ configurations, but you can permute the rooks in $8!$ ways, leaving $8!$.

Another way to see it is that you must have one rook per column. You have $8$ choices for the row of the one in the first column, then $7$ for the position in the second column, again leading to $8!$

Marc van Leeuwen
  • 115,048
Ross Millikan
  • 374,822
  • I understand that I have $n^2$ different options to place the first rook, for the next rook I must make the table 1 row and 1 column smaller which makes it $(n-1)^2$ and so on... How exactly do you get $8^2$ choices for the first rook? Doesn't the number of permutations have to take table size into account? – user108078 Nov 11 '13 at 18:09
  • I misread to think you specified an $8\times 8$ board. You are correct it is $n^2$ for the first, $(n-1)^2$ for the second – Ross Millikan Nov 11 '13 at 18:13
  • would you say that the answer is $$n^2(n-1)^2(n-2)^2(n-3)^2...$$ ? – user108078 Nov 11 '13 at 18:15
  • No, you need to divide by $8!$ but otherwise OK – Ross Millikan Nov 11 '13 at 18:18
  • Are you sure that I have to divide by $8!$. I tried it out with smaller table (3x3) and 3 rooks, then the answer should be simply $3^22^21^2$ – user108078 Nov 11 '13 at 18:23
  • For $3\times 3$ there are only $3!=6$ arrangements of three rooks. As they are indistinguishable, you need to divide by $3!$ permutations of the rooks. The configurations are the two diagonals plus each corner and the two squares a knight's move away for six. – Ross Millikan Nov 11 '13 at 18:29