3
$\begingroup$

One can compute the rook polynomial of the following board:

enter image description here

by transforming it to the following equivalent board,

enter image description here

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?

enter image description here

$\endgroup$
3
  • $\begingroup$ Sometimes shapes like the ones you have there are called "moon polyominoes." Could be a keyword to google... $\endgroup$ Commented Mar 18, 2021 at 3:21
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Mar 18, 2021 at 10:47
  • 1
    $\begingroup$ @MartinRubey: Ah, I stand corrected. Thank you! $\endgroup$ Commented Mar 18, 2021 at 12:29

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.