I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position.
(Two rooks attack each other if they are in the same row or same column)
How many ways I can do that?
I saw somewhere that the problem can be described with a recurrence relation which would be R(m,n,p) = m . R(m-1,n-1,p-1) + R(m,n-1,p) .
I tried to figure it out but I couldn't.
How did this relation come?(I know the base cases, I just want to know how this formula works?)
EDIT : I have considered it already but that's where my confusion is.
Let's say I have a 3×3 chessboard.
Then when I want to put rooks in the first column I have 3 options (choosing cell 1,1 ; choosing cell 2,1 ; choosing cell 3,1) .
Now,from my poor drawing it's obvious when I'm putting the rook in the cell (1,1) or (3,1) I just have to find out how many ways I can put other (one less) rooks in the (2×2) chessboard.
But when I'm putting the rook in the cell (2,1) I see I have to find out how many ways I can put x rooks in a 1×2 chessboard and y rooks in a 1×2 chessboard.
Where,x+y = p - 1.
Now for any m and n this new recurrence relation has to be true R(m,n,k) = R(t,n,x) + R(m-t,n,k-x) .
Because if that's true then for placing every rook in the first column I can surely assume I can place other rooks in R(m-1,n-1,p-1) ways.
(I am not sure how this works and how x and y would vary.)
That's where I got stuck.
I will assume that you have $m$ rows and $n$ columns.
Case 1: There is a rook in the first column
This gives $m$ possibilities for placing this rook and $R(m-1,n-1,p-1)$ for placing the other rooks. (One rook less, remove first column, remove row with the first rook.)
Case 2: There is no rook in the first column
This is clearly the same problem with $n$ replaced by $n-1$.