Rook theory

Imagine a board of $$$n \times n$$$ , and upon that you are going to put some rooks on it, without letting them attack each other. (Recall that rook attacks all squares vertically and horizontally from where it is located) and you are going to calculate how many ways there are to do it.

Obviously, it is $$$n!$$$ .

What about the situation with some cells forbidden then?

Here comes the rook theory.

The rook theory utilise two polynomials: rook polynomial and the hit polynomial. Let's call the set of forbidden cells $$$\mathfrak{B}$$$ .

Rook polynomial:

Rook polynomial is that $$$R(x) = \sum{r_kx^k}$$$ , where $$$r_k$$$ is the number of ways to put $$$k$$$ rooks on $$$\mathfrak{B}$$$ ;

Hit polynomial:

Hit polynomial is that $$$H_n(t) = \sum{h_{n,k}t^k}$$$ , where $$$h_{n,k}$$$ is the number of ways to put $$$n$$$ rooks on the board with $$$k$$$ rooks on $$$\mathfrak{B}$$$ .

According to the Principle of Inclusion and Exclusion, we've got $$$H_n(t) = \sum{r_k(n-k)!(t-1)^k}$$$ .

What we care about is of course $$$h_{n,0}$$$ (With no rooks violate the rules), which got $$$h_{n,0} = H_n(0) = \sum{r_k(n-k)!(-1)^k}$$$ .

Let's introduce a formal variant $$$E$$$ that satisfy $$$E^n=n!$$$ for all $$$n$$$ . (I would say it works because the similarity between the ascending factorials and normal exponents)

Then we got

And we find that the overall rook polynomial can be calculated by multply certain numbers of partial rook polynomials that don't affect each other. Thus, we can use this property to solve some problems:

Problems

Disarrangement problem:

There are $$$n$$$ persons. Each of them send a present to others so that everyone receives a gift that does not come from themselves, how many ways there to do this?

Imagine this as a board. Each person is forbidden to send gifts to themselves, so we can see this as an $$$n \times n$$$ board that
each row signify the sender and each column signify the receiver. Then, the set of forbidden cells will be

This can be seen as $$$n$$$ independent $$$1 \times 1$$$ boards because no rooks puted on $$$\mathfrak{B}$$$ can attack each other. Each of the $$$1 \times 1$$$ boards got the rook polynomial $$$R_i(x) = x+1$$$ . So overall rook polynomial wiil be $$$R(x) = (x+1)^n$$$ .

Then, $$$h_{n,0} = E^n(-E^{-1}+1) = (E-1)^n$$$ .

We can find the property that $$$f(E) = f'(E) + f(0)$$$ (Think about the expanded formula), So lets replace $$$E$$$ with $$$x$$$ , then we got $$$h_{n,0}(x) = (x-1)^n$$$ , and then $$$h_{n,0}'(x) = n(x-1)^{n-1} $$$ .

thus,

This tells us that $$$h_{n,0} = nh_{n-1,0} + (-1)^n$$$ , i.e. the disarrangement number $$$D_n$$$ got the recurrence relation $$$D_n = nD_{n-1}+(-1)^n$$$.

Let's try develop further.

Bingo game problem: (105911H)

Brief statements: how many ways are there to fill most cells without satisfy the winning condition of $$$n \times n$$$ bingo game? (Recall that the winning condition of a bingo game is to have cells aligned in a row, a column,or a diagonal.)

Let's consider the cells unfilled.

When $$$n \gt 2$$$ , we can find that there is a unfilled cell for each row and each column, and there must be a unfilled cell on both diagonals. It's really like the situation of rooks, huh? We can further discover with a little usage of the Principle of Inclusion and Exclusion that the answer will be $$$A_n = n! - 2D_n + X_n$$$ , where $$$X_n$$$ is the situation that there is no unfilled cells on both diagonals.

We find that for the forbidden area of $$$X_n$$$ , we can divide it into $$$\left \lfloor \frac{n}{2} \right \rfloor $$$ parts of $$$(i,i) , (i,n-i+1) , (n-i+1,i) , (n-i+1,n-i+1)$$$, and if $$$n$$$ is odd , a part of $$$(\frac{n+1}{2},\frac{n+1}{2})$$$ .

Then for even $$$n$$$ :

The rook polynomial

So

And for odd $$$n$$$ :

Then

I.e.

Replacing $$$E$$$ with $$$x$$$, we got

And $$$X_n(E) = X_n'(E)+X_n(0)$$$ ,

So we find the recurrence relation

There, with the knowledge of $$$D_n$$$ and $$$X_n$$$ , we are able to solve the problem in $$$O(n)$$$ time.