By _badass_, history, 3 weeks ago, ,  Comments (4)
 » Hint 1Firstly, note that if $k \gt n$, then by Pigeon Hole Principle, atleast two Rooks will be attacking, thus $ans = 0$. Hint 2Break down the problem into choosing $k$ distinct rows and $k$ distinct columns. Then you have rows — $r_{1}, r_{2}, ....., r_{k}$ and columns — $c_{1}, c_{2}, ...., c_{k}$.Then, you say that, first Rook is at $(r_{1}, c_{1})$, second Rook is at $(r_{2},c_{2})$, .... and so on. In general, $i^{th}$ Rook is at $(r_{i}, c_{i})$, for each $i \in [1,k]$. Hint 3Total ways of selecting k distinct rows is $C(n,k)$. And total ways of selecting k distinct columns is $C(n,k)$. Also, finally, we have not counted permuting the selected rows and columns. So we must multiply another $k!$.NOTE: Not $(k!)^2$ because, permuting both rows and columns means overcounting.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   Let's work through an example. Consider $n = 10$, $k = 3$.Then, first choose three rows, let's call them $r_1, r_2, r_3$. Ofcourse, we have $1 \le r_1, r_2, r_3 \le 10$. Similiarly, choose three columns, say $c_1, c_2, c_3$. Again, $1 \le c_1, c_2, c_3 \le 10$. So far, number of ways are — $C(10,3)$ ( for choosing $3$ rows ) AND $C(10,3)$ ( for choosing $3$ columns ). So, for now, $ans = C(10,3)*C(10,3)$. But we see that, we have $6$ configurations ( notice $6 = 3!$ ) for placing Rooks, when we have these $x$ and $y$ co-ordinates.These configurations are:1) $(r_1,c_1)$,$(r_2,c_2)$,$(r_3,c_3)$.2) $(r_1,c_1)$,$(r_2,c_3)$,$(r_3,c_2)$.3) $(r_1,c_2)$,$(r_2,c_1)$,$(r_3,c_3)$.4) $(r_1,c_2)$,$(r_2,c_3)$,$(r_3,c_1)$.5) $(r_1,c_3)$,$(r_2,c_1)$,$(r_3,c_2)$.6) $(r_1,c_3)$,$(r_2,c_2)$,$(r_3,c_1)$.So, final answer should be $C(10,3)*C(10,3)*3!$.In, general, we have $C(n,k)*C(n,k)*k!$.