Given a square $n \times n$ chessboard and $m$ rooks (with $m \geq \lceil{n/2}\rceil$ and $m \leq n^2$) I would like to count how many of the total $\tbinom{n^2}{m}$ possible combinations cover each "index" (more below) on the board.
This problem differs from the standard class of chess domination problems by the way covering is meant. Chessboards usually have distinct rows and columns identified by letters and numbers. In the standard chess domination problem each row and each column must be covered separately.
While in this problem the chessboard looks exactly like the normal one, the covering works differently. Here the $i^{th}$-row and the $i^{th}$-column represent the same "index". For an "index" $i$ to be covered, it is enough that one rook is placed somewhere in the $i^{th}$-row or $i^{th}$-column. While each square on the diagonal covers just one index, the other squares cover two.
When in the traditional domination problem at least $n$ rooks are needed to dominate the chessboard, here $\lceil{n/2}\rceil$ are enough.
Consider for example the following instances with $n = 4$ and $m = 2$:
Valid case Invalid case
|---|---|---|---|---| |---|---|---|---|---|
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
|---|---|---|---|---| |---|---|---|---|---|
| 1 | | A | | | | 1 | | A | | |
|---|---|---|---|---| |---|---|---|---|---|
| 2 | | | | | | 2 | | | B | |
|---|---|---|---|---| |---|---|---|---|---|
| 3 | | | | B | | 3 | | | | |
|---|---|---|---|---| |---|---|---|---|---|
| 4 | | | | | | 4 | | | | |
|---|---|---|---|---| |---|---|---|---|---|
The placement on the left is valid since $A$ covers indexes $1$ and $2$ and rook $B$ covers indexes $3$ and $4$. All the $4$ indexes are covered by $A$ or $B$.
The placement on the right is invalid since the index $4$ in not covered by any rook.
When $m$ grows in size, indexes can be covered by more than one rook.
Given the explanation above, I would like to know if a polynomial algorithm/formula that given $n$ and $m$ computes how many of the $\tbinom{n^2}{m}$ possible rook placements are valid exists.
The exponential algorithm is trivial. Just iterate through all the possible $\tbinom{n^2}{m}$ placements and compute for each of them whether the placement is valid or not.
Best Answer
The answer is $$ \sum_{i=0}^{n-\lfloor \sqrt{m}\rfloor} (-1)^i\binom{n}i\binom{(n-i)^2}{m} $$ which is easily proved using the principle of inclusion exclusion. That is, start with all $\binom{n^2}{m}$ ways to place $m$ rooks on the board, and then for each $i$, subtract the placements which do not cover index $i$. Not covering $i$ constrains the rooks to $n-1$ rows and $n-1$ columns, so for each of the $n$ choices of $i$, we subtract $\binom{(n-1)^2}{m}$. However, arrangements with two missing indices have been double subtracted, and need to be added back in. There are $\binom n2$ pairs of indices, and for each pair, there are $\binom{(n-2)^2}{m}$ placements where both indices are missing, so we add $\binom{n}2\binom{(n-2)^2}{m}$ back in. Continuing with overcounting corrections leads to the formula above.
In the $i^{th}$ term of this summation, we are either adding or subtracting the number of ways to miss a subset of $i$ indices. In order for there to be enough non-missing rows and columns to choose $m$ squares in the first place, we need to have $(n-i)^2 \ge m$, which after some algebra is equivalent to $i\le n-\lfloor \sqrt m\rfloor $, hence the upper limit of summation.