1
$\begingroup$

How many ways $6$ non-attacking rooks can be put on $8\times 8$ chessboard?

The problem is very common rook polynomial. From this article I see that it can be done on: $$6! \binom{8}{6}^2 = 564480 $$ ways. Ok, but I tried to solve this task using theorems from my lecture and getting result:

Facts

  • Permutations of rows and cols don't change rook polynomial
  • If we divide chessboard $B$ on $B_1$ and $B_2$ such as $B_1$ and $B_2$ have different coordinates of slots, then $$R_B(t) = R_{B_1}(t) \cdot R_{B_2}(t) $$ So I permutated my chessboard like this: $$ OOOOXXXX \\ OOOOXXXX \\ OOOOXXXX \\ OOOOXXXX \\ XXXXOOOO \\ XXXXOOOO \\XXXXOOOO \\XXXXOOOO \\$$ and consider two cases:
  • on left chessboard $(4\times 4)$ we have $3$ and on the second $3$ too. $$ \left(\frac{16\cdot 9 \cdot 4}{3!} \right)^2 = 9216$$
  • $2 \times$ when on first chessboard we have $4$ and on the second $2$ $$ 2 \cdot 4! \cdot \frac{16 \cdot 9}{2} = 3456 $$ But sum of these two cases doesn't give me correct answer. Where I failed?

Update

I have calculated rook polynomial: $$\left(\frac{(16\cdot 9\cdot 4) t^3}{3!}+\frac{(16\cdot 9) t^2}{2!}+24 t^4+16 t+1\right)^2 = 576 t^8+4608 t^7+12672 t^6+14592 t^5+8304 t^4+2496 t^3+400 t^2+32 t+1$$ and it gives me the same answer

$\endgroup$
  • $\begingroup$ Do you mean "rooks"? Though I do like the image of rocks on a chess board... $\endgroup$ – Xander Henderson Aug 10 '19 at 20:00
  • $\begingroup$ Rooks, not rocks $\endgroup$ – Tester1998 Aug 10 '19 at 20:01
  • $\begingroup$ I'll correct the title, then... $\endgroup$ – Xander Henderson Aug 10 '19 at 20:02
  • $\begingroup$ Ahhh, I didn't noticed that, thanks @XanderHenderson $\endgroup$ – Tester1998 Aug 10 '19 at 20:02
  • 3
    $\begingroup$ @XanderHenderson Not a chessboard (read it again :) ). $\endgroup$ – Tobias Kildetoft Aug 10 '19 at 20:09
1
$\begingroup$

Permuting the rows and columns does not change the answer, but given a permutation you don't have to have all the rooks in two quadrants as you show. Also the $6!$ in the correct answer represents the number of ways to put the rooks in the squares after you have selected the squares. Your approach puts all the rooks in one quadrant, then all the rooks in the other quadrant, so does not allow all the orders for placing rooks.

$\endgroup$
  • $\begingroup$ " you don't have to have all the rooks in two quadrants as you show" I don't understand - I still should put 6 rooks, so where should I put them if there not? $\endgroup$ – Tester1998 Aug 10 '19 at 21:51
  • $\begingroup$ I took the $X$s and $O$s to say that all the rooks were on one letter, so they were restricted to two quadrants of the board, but there are solutions where there are rooks in all four quadrants. You are correct that you can permute the rows and columns and still have a solution, but that doesn't help in counting the solutions. More extremely, we can always permute the rows and columns to get the solution $a1,b2,c3,d4,e5,f6$. $\endgroup$ – Ross Millikan Aug 10 '19 at 22:07
  • $\begingroup$ "but there are solutions where there are rooks in all four quadrants" - hmm, ok, but I have just done permutation to avoid that situation and transform all cases to two corner quadrants, is that right? $\endgroup$ – Tester1998 Aug 10 '19 at 22:13
  • 1
    $\begingroup$ When you permute the rows and columns all solutions are equivalent. One way to count the solutions is to start with a single one and count the number of ways of permuting the rows and columns. Permuting into the quadrants makes things much harder. Given one solution you have not defined which permutation you will use to get the rooks into quadrants. There will be a number of them. $\endgroup$ – Ross Millikan Aug 10 '19 at 22:18
  • $\begingroup$ I have calculated rook polynomial: $\left(\frac{(16\ 9\ 4) t^3}{3!}+\frac{(16\ 9) t^2}{2!}+24 t^4+16 t+1\right)^2 = 576 t^8+4608 t^7+12672 t^6+14592 t^5+8304 t^4+2496 t^3+400 t^2+32 t+1 $ and from that follows too that the answer is $12672$. $\endgroup$ – Tester1998 Aug 10 '19 at 22:23

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.