# Rook polynomial of quasi-Ferrers board?

One can compute the rook polynomial of the following board:

by transforming it to the following equivalent board,

which is a Ferrers board, and then using the formula given here: How to compute the rook polynomial of a Ferrers board?

Is it possible to use a similar trick to compute the rook polynomial of boards that look something like this?

• Sometimes shapes like the ones you have there are called "moon polyominoes." Could be a keyword to google... Commented Mar 18, 2021 at 3:21
• @SamHopkins no, sorry, the depicted one is not a moon polyomino. A defining condition for moon polyominoes is that given any two columns, one is contained in the other. Equivalently: any cell can be reached from any other cell by following a path of adjacent cells, such that the path changes direction only once. Commented Mar 18, 2021 at 10:47
• @MartinRubey: Ah, I stand corrected. Thank you! Commented Mar 18, 2021 at 12:29

The given board, call it $$D$$, can be viewed as the difference of two (unsorted) Ferrers boards with $$m=9$$ columns each: $$A=(4,5,6,7,8,9,8,7,6)$$ and $$B=(3,2,1,0,1,2,3,4,5)$$. We view $$B$$ as a sub-board of $$A$$ and are interested in enumerating placements of $$k$$ non-attacking rooks in $$A$$ such that no rook appears in $$B$$. This can be computed via inclusion-exclusion as follows: $$r_k(D) = \sum_{S\subseteq[m]\atop |S|=k} \sum_{T\subseteq S} (-1)^{|T|} r_k(A_{S\setminus T}\| B_T),$$ where $$B_T$$ is the sub-board of $$B$$ formed by the columns indexed by $$S$$, similarly $$A_{S\setminus T}$$ is the sub-board of $$A$$ formed by the columns indexed by the complement of $$S\setminus T$$, and $$\|$$ denotes concatenation of the two boards.

Here, each summand can be easily computed -- if $$A_{S\setminus T}\| B_T$$ is formed by elements $$c_1\leq c_2\dots \leq c_k$$, then $$r_k(A_{S\setminus T}\| B_T) = \prod_{i=1}^k (c_i - i + 1).$$

So, the formula for $$r_k(D)$$ involves up to $$3^m$$ summands but depends on sorting. Below we construct more explicit formula for the whole rook polynomial $$R_D(x):=\sum_k r_k(D)x^k$$, with the same number of summands.

Let $$A=(a_1,\dots,a_m)$$ and $$B=(b_1,\dots,b_m)$$. Let $$p_i$$ be the indicator for $$a_i\in S\setminus T$$ and $$q_i$$ be the indicator for $$b_i\in T$$. It follows that $$(p_i,q_i)\in\{(0,0),(1,0),(0,1)\}$$. Let $$\sigma$$ be a sorted permutation of $$A\|B$$, and $$\delta$$ be obtained from $$\sigma$$ by replacing each $$a_i$$ and $$b_i$$ with $$p_i$$ and $$q_i$$, respectively. Finally, let $$\tau_A(i)$$ be the order number of $$a_i$$ in $$\sigma$$ (i.e., $$\delta_{\tau_A(i)}=p_i$$), and $$\tau_B(i)$$ be the order number of $$b_i$$ in $$\sigma$$ (i.e., $$\delta_{\tau_B(i)}=q_i$$). Then $$(\star)\qquad R_D(x) = \sum_{(p,q)\in\{(0,0),(1,0),(0,1)\}^m} (-1)^{q_1+\cdots+q_m} \prod_{i=1}^m \big(1+p_i(a_i-\sum_{j=1}^{\tau_A(i)-1} \delta_j)x + q_i(b_i-\sum_{j=1}^{\tau_B(i)-1} \delta_j)x\big).$$

Example. In the given example, we have $$\sigma = (0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9)$$ and $$\delta = (q_4,q_3,q_5,q_2,q_6,q_1,q_7,p_1,q_8,p_2,q_9,p_3,p_9,p_4,p_8,p_5,p_7,p_6)$$. Correspondingly, $$\tau_A=(8,10,12,14,16,18,17,15,13)$$ and $$\tau_B=(6,4,2,1,3,5,7,9,11)$$. This leads to the formula for the rook polynomial for the board $$D$$: $$R_D(x) = 1 + 39 x + 563 x^2 + 3833 x^3 + 13039 x^4 + 21773 x^5 + 16516 x^6 + 4884 x^7 + 425 x^8 + 7 x^9.$$

ADDED. We can eliminate dependency between $$p_i$$ and $$q_i$$ by slightly modifying the formula $$(\star)$$: $$R_D(x) = \sum_{p,q\in\{0,1\}^m} (-1)^{q_1+\cdots+q_m} \prod_{i=1}^m \big(1-p_iq_i+p_i(1-q_i)(a_i-\sum_{j=1}^{\tau_A(i)-1} \delta_j)x + q_i(1-p_i)(b_i-\sum_{j=1}^{\tau_B(i)-1} \delta_j)x\big).$$ It can be seem that when $$p_i=q_i=1$$, the corresponding term becomes zero, while in all other cases, it is same as in $$(\star)$$.

Next, by substituting $$p_i := \frac{1-y_i}2$$ and $$q_i := \frac{1-z_i}2$$, we switch to summation over $$y,z\in\{-1,1\}^m$$. Let $$\delta'$$ be obtained from $$\delta$$ by such substitution. Then it can be seen that $$R_D(x)$$ equals the sum of the (polynomial in $$x$$) coefficients of terms $$y^{\alpha}z^{\beta}$$ in $$F_D(x;y_1,\dots,y_m,z_1,\dots,z_m):=\prod_{i=1}^m \big(4-(1-y_i)(1-z_i)+(1-y_i)(1+z_i)(a_i-\sum_{j=1}^{\tau_A(i)-1} \delta'_j)x + (1+y_i)(1-z_i)(b_i-\sum_{j=1}^{\tau_B(i)-1} \delta'_j)x\big),$$ where all components of $$\alpha$$ are even, and all components of $$\beta$$ are odd. From computational perspective, it is worth to consider $$F_D$$ modulo $$y_i^2-1$$ and $$z_i^2-1$$, which has at most $$2^{2m}$$ terms. That is, $$R_D(x) = [y_1^0\cdots y_m^0 z_1\cdots z_m]\ \big( F_D(x;y_1,\dots,y_m,z_1,\dots,z_m) \bmod (y_1^2-1,\dots,y_m^2-1,z_1^2-1,\dots,z_m^2-1)\big).$$ This formula may be not better than $$(\star)$$ from computational perspective, but it looks nice anyway.